Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Fibonacci numbers without using zipWith

I have been trying to implement a list of Fibonacci number sequence from 0 to n without using the lazy zipwith method. What I have so far is code that returns a list from n to 1. Is there any way I can change this code so it returns the list from 0-n at all?

Example:

fib_seq 4 = [3,2,1,1] 
-- output wanted: [1,1,2,3]

If there is not a way to do what I want the code to do, is there a way to just return the list of Fibonacci numbers taking in a number say again 4 it would return [0, 1, 1, 2].

fib_seq :: Int -> [Int]
fib_seq 0 = [0]
fib_seq 1 = [1]
fib_seq n = sum (take 2 (fib_seq (n-1))) : fib_seq (n-1)
like image 211
Jimbhoy Avatar asked Feb 12 '21 22:02

Jimbhoy


3 Answers

It feels a bit like cheating, but you could use the closed formula for the Fibonacci sequence like this:

fib n = (phi^n - psi^n) / sqrt 5
  where
    phi = (1 + sqrt 5) / 2
    psi = (1 - sqrt 5) / 2

fibSeq n = fib <$> [1 .. n]

Otherwise the Haskell Wiki has many more implementation variants to chose from. For example very succinctly

fibs = 0 : 1 : next fibs
  where
    next (a : t@(b:_)) = (a+b) : next t
like image 94
michid Avatar answered Oct 02 '22 07:10

michid


Another way you could choose to implement the fib numbers is the use of a helper function then a function on it's own that will produce the infinite list of fib numbers, or you could use take 10 fibs and the output for this would be the first 10 fib numbers. My function is definitely not the fastest way to work out the fib numbers infintely that would be with the zipWith function, but you are not using that here so here is my way to implement it without zipWith.

for example take 10 fibs would return: [0,1,1,2,3,5,8,13,21,34]

fib :: Int -> Int
fib 0 = 0
fib 1 = 1
fib n = fib (n-1) + fib (n-2)   

fibs :: [Int]
fibs = (map fib [0..])
like image 6
program.exe Avatar answered Oct 18 '22 21:10

program.exe


It is often the case that you can solve a problem by considering a slightly more general version of it.

Say we want the infinite Fibonacci list starting with two prescribed initial values a and b. There is an obvious recursive solution:

$ ghci
GHCi, version 8.8.4: https://www.haskell.org/ghc/  :? for help
 ...
 λ> 
 λ> aux_fib a b = a : (aux_fib b (a+b))
 λ> 
 λ> take 4 (aux_fib 1 1)
 [1,1,2,3]
 λ> 

And so:

 λ> 
 λ> fib_seq n = take n (aux_fib 1 1)
 λ> 
 λ> fib_seq 4
 [1,1,2,3]
 λ> 

Note: camel case is regarded as more idiomatic in Haskell, so it would be more like auxFib and fibSeq.

like image 5
jpmarinier Avatar answered Oct 18 '22 20:10

jpmarinier