Haskell: Improving my tail-recursive fibonacci implementation

Question

I have come up with the following tail-recursive fibonacci generator that works:

let {
  fibo :: Integral x => [x]->x->x->x->[x]
  fibo l x y 0 = l
  fibo l x y n = fibo (l ++ [y+x] ++ [y+x+y]) (x+y) (y+x+y) (n-1)
}

Pardon me for the whole implementation put in one line because i am using the GHCi and haven't quite learnt how to put this in a file and run (i am yet to reach there). What i want to know is how this call:

fibo [0, 1] 0 1 5

can be improved. I do not want to pass the initial list with 0 and 1 and then pass 0 and 1 again with the limit. I believe that the implementation can be changed. What changes can be done?

You can just write it in a file line by line like you would in the interpreter (no need to wrap everything up in a let block either), and then load the file in the interpreter (in GHCi with :l filename) — Cubic
– Cubic, Commented Jul 25, 2012 at 18:58
Your code is tail-recursive, but nevertheless very inefficient, as (++) is linear in its first argument. But I guess that this is not part of the question. — Joachim Breitner
– Joachim Breitner, Commented Jul 25, 2012 at 18:58
Tail recursion in Haskell does not entail constant stack usage like it does in strict languages, and conversely non-tail recursion doesn't entail linear stack usage either, so I question the value of your exercise. Frankly, I'd go with the classic fibs = 0 : 1 : zipWith (+) fibs (tail fibs) or one of its variants with scanl or unfoldr. See this HaskellWiki page for a bunch of implementations. — Luis Casillas
– Luis Casillas, Commented Jul 25, 2012 at 20:13

ErikR · Accepted Answer · 2012-07-25 21:43:45Z

9

Your algorithm is tail-recursive, but it looks like it has other drawbacks, namely 1) you are building the result list by appending to the end of it, and 2) it's not lazy.

For 1), note that when you append two lists a ++ b, you essentially have to reallocate a. In your case a is the growing list of fibonacci numbers and b are the next two terms. So each iteration reallocates the fibonacci numbers that have already been computed and adds on two more elements which will result in quadratic running time. It would be more efficient to prepend b to the front of a. You'll be producing the fibonacci numbers in reverse, but the running time will be linear. You can then reverse the list at the end if you want the sequence in ascending order.

Note that building the list in reverse order allows you to easily get at the last two terms of the sequence by using Code-Guru's pattern-matching idea.

For 2), note that you can't get the first element of the list until the entire computation has completed. Compare with the following lazy generation of the sequence:

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

Even though it looks like the recursion never stops, fibs is only evaluated for as much as is needed. For example, fibs !! 3 only calls go a couple of times.

edited Jul 25, 2012 at 21:43

answered Jul 25, 2012 at 19:28

ErikR

52.2k9 gold badges78 silver badges136 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

badmaash Over a year ago

...which means i can control recursion from outside the function in Haskell?

ErikR Over a year ago

yes - that's one way to look at it - you don't have to decide ahead of time how many terms to compute

shang · Accepted Answer · 2012-07-25 19:46:25Z

I'm not going to go to the algorithm itself, but here's some advice on how to structure your recursive functions.

First, here's how you would format your code in a separate file

fibo :: Integral x => [x]->x->x->x->[x]
fibo l x y 0 = l
fibo l x y n = fibo (l ++ [y+x] ++ [y+x+y]) (x+y) (y+x+y) (n-1)

If you save this as fibo.hs, then you can start GHCi with

ghci fibo.hs

to load the file at start. You can also load the file after starting GHCi with the command

:l fibo.hs

(assumming you start GHCi in the same directory where you saved fibo.hs)

Another nice feature is that now when you edit the file, you can reload all your changes by simply entering

:r

in the GHCi prompt.

Now, to get rid of the extra parameters, the usual pattern in Haskell is to refactor the recursive part to its own helper function and have the main function as an entry point that only takes the necessary parameters. For example,

fibo :: Integral x => x -> [x]
fibo n = fiboHelper [0,1] 0 1 n

fiboHelper :: Integral x => [x]->x->x->x->[x]
fiboHelper l x y 0 = l
fiboHelper l x y n = fiboHelper (l ++ [y+x] ++ [y+x+y]) (x+y) (y+x+y) (n-1)

Now you can call fibo simply with

> fibo 3
[0,1,1,2,3,5,8,13]

Also, a helper function like this that is not useful by itself is usually hidden inside the main function as an inner function using let or where.

fibo :: Integral x => x -> [x]
fibo n = fiboHelper [0,1] 0 1 n where
    fiboHelper l x y 0 = l
    fiboHelper l x y n = fiboHelper (l ++ [y+x] ++ [y+x+y]) (x+y) (y+x+y) (n-1)

An inner function like this is usually given a shorter name, because the context makes its purpose clear, so we could change the name to e.g. fibo'.

go is another commonly used name for a recursive helper function.

Landei · Accepted Answer · 2012-07-26 13:01:30Z

3

Just for the record: The "usual" definition for a list of Fibonacci numbers is:

fibo = 0 : scanl (+) 1 fibo

answered Jul 26, 2012 at 13:01

Landei

54.6k13 gold badges105 silver badges195 bronze badges

1 Comment

fuz Over a year ago

Or (a little bit less arcane) fibo = 0 : 1 : zipWith (+) fibo (tail fibo)

Collectives™ on Stack Overflow

Haskell: Improving my tail-recursive fibonacci implementation

3 Answers 3

2 Comments

Comments

1 Comment

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

2 Comments

Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Linked

Related