Haskell does not allow mutating a global variable, which is the key concept of Dynamic Programming, so I come up with a solution. This relies on Haskell's lazy evaluation and infinite lists Is it linear time and space efficient is my question (?)
This is my solution
fibs = [0,1] ++ [n | i <- [2..], let n = fibs !! (i-1) + fibs !! (i-2)]
We add the first 2 fibs numbers which are 0, 1 with a potential infinite list.
The list has a generator for indexes (infinite).
We declare a local variable n = fibs !! (i-1) + fibs !! (i-2)
So I am trying to use old result to get the new one. Now is this space-efficient (?)
fibs
, the remaining items offibs
are just "to be determined".fibs :: [Integer]
. It's not time efficient though, sincefibs !! ...
takes linear time. Still, it can be good enough. (One could try to use another list-like data structure with better access times, but it has to allow lazy generation of elements like lists for this code to work -- I'm unsure about what can be used.)fibs :: Num a => [a]
, no memoization happens and the list is recomputed at each call. That should not happen because of the monomorphism restriction, yet I prefer to be explicit on that.