2

In Haskell, the canonical zipWith implementation of the fibonacci function is :

fibs :: [Integer]
fibs = 1 : 1 : zipWith (+) fibs (tail fibs)

I have difficulty analysing the time complexity of this (fibs !! n). Trying to write it on paper, at first i thought it was exponential. Then O(n^2) , but I have no clue how it happens to be linear.

Why i think it is linear : https://wiki.haskell.org/The_Fibonacci_sequence#Canonical_zipWith_implementation

Also, i wrote another code :

fibs :: [Integer]
fibs = inc (0,1) where inc (a,b) = a : inc (b,a+b)

This, I believe is clearly O(n). But using the :set +s option in ghci, I see that the zipWith implementation clearly beats mine.

Note: I know that it takes O(n) time for addition of nth and (n-1)th fibonacci number. Thus while testing, i made the base case, i.e. the first two elements 0 : 0 . Time complexities are mentioned using the same assumption.

It would be great if i could get some help with tracing these function calls. I'm interested to know which function was called when and maybe print something to let me know what is going on.

My unsuccessful attempt at this : 

zipWith' = trace ("Called zipWith") (zipWith)
add' a b = trace (show a ++ " + " ++ (show b)) (add a b)
fibs = trace ("Called fibs") (1 : 1 : zipWith (+) fibs (tail fibs))

This does not work. The statements are printed exactly one. Except for add' which works fine, surprisingly.

I wish to know how many times and in what order these functions were called.

Jatin Sharma
  • 331
  • 1
  • 10
  • I don't understand your note. – dfeuer Mar 22 '19 at 04:49
  • 1
    @dfeuer The note means: `fib` is linear in number of additions, but as we know addition is not constant-time on normal CPUs if the inputs are large enough. To counteract this fact, Jatin Sharma benchmarked the two implementations with a base case of `(0,0)` instead of `(0,1)`, ensuring the inputs would not grow large. – amalloy Mar 22 '19 at 07:45
  • `zipWith` is traced wrong. That should be `zipWith' f a b = trace ("Called zipWith") (zipWith f a b)`. But it won't make any difference, because `fibs`, `zipWith`, and `tail` are each called once. `(+)` is actually the only function called multiple times. – dfeuer Mar 22 '19 at 09:04
  • 1
    nice pictures [here](https://stackoverflow.com/a/37243672/849891), showing a *linear* process of fleshing out the *one* list of Fibonacci numbers, top-down. – Will Ness Mar 22 '19 at 09:12
  • @WillNess Thanks, that was very helpful indeed. How do i give a helpful comment upvote? I can't seem to find a function. – Jatin Sharma Mar 22 '19 at 11:41
  • @dfeuer I seem to get fibs now. Thanks a lot! Why is my zipWith trace wrong, btw? – Jatin Sharma Mar 22 '19 at 11:43
  • @WillNess Can you please clarify this for me? If i go by the answer you posted, i would like to see how `nine = 9 : nine` is evaluated. Is it nine = 9 : 9 : nine => nine = 9 : 9 : 9 : 9 : nine => 9 : 9 : (8 times) : nine... Or is it one by one? i.e. nine = 9 : 9 : nine => nine = 9 : 9 : 9 : nine ? – Jatin Sharma Mar 22 '19 at 12:32
  • (it's not *my* answer...). `take 2 nines = take 2 (9:nines) = 9:(take 1 nines) = 9:(take 1 (9:nines)) = 9:(9:take 0 nines) = 9:(9:[])`. (I also gave some answers similar to this [before](https://stackoverflow.com/search?q=user%3A849891+interim+name+%5Bhaskell%5D)). – Will Ness Mar 22 '19 at 12:46
  • @JatinSharma, sorry I never answered your question. `zipWith' = trace ("Called zipWith") zipWith` traces the evaluation of the `zipWith` function itself, *not* the evaluation of the result of applying it to arguments. – dfeuer Apr 10 '19 at 17:41

1 Answers1

3

I believe your version is slow primarily because you're running it without optimization, and so you end up building a bunch of unnecessary tuples. The partially hand-optimized (and more idiomatic) version would be

fibs = inc 0 1
  where
    inc a b = a : inc b (a+b)

Let's look at the classic:

fibs = 1 : 1 : zipWith (+) fibs (tail fibs)

The initial representation in memory looks very much like that. It's a list cons pointing to the number 1 and a second list cons pointing to the number 1 and a thunk representing zipWith (+) fibs (tail fibs). What happens when that thunk is forced? Well zipWith needs to inspect both of it's list arguments. It does so, and, seeing that they're not null, produces a list cons pointing to a thunk representing 1+1 and a thunk representing zipWith (+) fibs' (tail fibs'), where fibs' is a pointer to the second cons in the sequence. There's no need to evaluate fibs again for each of the zipWith arguments or anything like that.

dfeuer
  • 48,079
  • 5
  • 63
  • 167
  • I see, I'm sorry i've just started out, does cons mean constructor? I'll have to think more on this with a pen paper. Is there anyway i can see how many times each function was called? I tried using Debug.Trace (trace) but it didn't work properly for me. Apparently, they are evaluated only once (the first time) and i couldn't glean more info. – Jatin Sharma Mar 22 '19 at 08:47
  • @JatinSharma, cons is the traditional name for the nonempty list constructor. That name has been used since the early days of Lisp. – dfeuer Mar 22 '19 at 08:48
  • @JatinSharma, tracing can be a bit subtle. I doubt I'll be able to comment meaningfully on what you tried unless you give the details (preferably by putting them in your question). – dfeuer Mar 22 '19 at 08:50
  • 1
    ... and the `zipWith` that they are testing comes from a library, so it is compiled, unlike their code which is interpreted, most likely. – Will Ness Mar 22 '19 at 09:16