Haskell: Improving Tail Recursive Fibonacci Implementation

Question

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

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

Excuse me for the whole implementation, put on one line, because I use GHCi and did not quite understand how to put this in a file and run it (I have not reached it yet). I want to know how this call is:

 fibo [0, 1] 0 1 5 

can be improved. I do not want to pass the original list with 0 and 1, and then again pass 0 and 1 with a limit. I believe the implementation is subject to change. What changes can be made?

Answer 1

Your algorithm is tail-recursive, but it looks like it has other drawbacks, namely: 1) you build a list of results by adding it to the end, and 2) it is not lazy.

For 1), note that when adding two lists of a ++ b you need to redistribute a . In your case, a is a growing list of Fibonacci numbers, and b is the next two terms. Therefore, each iteration redistributes the Fibonacci numbers that have already been calculated, and adds two more elements that will lead to a quadratic run time. It would be more efficient to add b to the beginning of a . You will produce the fibonacci number in the reverse order, but the runtime will be linear. You can then reverse list at the end if you want the sequence to be in ascending order.

Note that building the list in reverse allows you to easily get the last two members of the sequence using the idea of ​​matching the Code-Guru pattern.

For 2), please note that you cannot get the first element of the list until the calculation is complete. Compare the following lazy generation sequences:

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

Although recursion never stops, fibs are only evaluated as much as needed. For example, fibs !! 3 fibs !! 3 only calls go couple of times.

Answer 2

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

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

 fibo :: Integral x => [x]->x->x->x->[x] fibo lxy 0 = l fibo lxyn = 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 startup. You can also upload the file after starting GHCi with the command

 :l fibo.hs 

(if you run GHCi in the same directory where you saved the fibo.hs file)

Another nice feature is that now that you are editing a file, you can reload all your changes just by entering

 :r 

at the invitation of GHCi.

Now, to get rid of additional parameters, the usual template in Haskell is to reorganize the recursive part into its own helper function and have the main function as an entry point that accepts only 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 lxy 0 = l fiboHelper lxyn = fiboHelper (l ++ [y+x] ++ [y+x+y]) (x+y) (y+x+y) (n-1) 

Now you can call fibo just with

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

In addition, a helper function like this, which is not useful in itself, is usually hidden inside the main function as an internal function using let or where .

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

An internal function like this is usually assigned a shorter name because the context makes its purpose clear, so we could change the name, for example. fibo' .

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

Answer 3

For write only: “Normal” definition for a list of Fibonacci numbers:

 fibo = 0 : scanl (+) 1 fibo