1

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 (?)

14
  • 1
    "global variable, which is the key concept of Dynamic Programming" Really? My copy of CLRS has plenty of examples of dynamic programming without global variables. Granted, these examples use mutation, but you can usually find a recursive alternative that doesn't rely on mutation. If all else fails, you can use the State monad to 'simulate' local state mutation. Commented Aug 7 at 6:41
  • It is not dynamic programming: you don't generate a new list with fibs, the remaining items of fibs are just "to be determined". Commented Aug 7 at 7:04
  • I believe this is a form of dynamic programming. It should be space efficient, if you add an explicit signature like fibs :: [Integer]. It's not time efficient though, since fibs !! ... 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.)
    – chi
    Commented Aug 7 at 7:13
  • 1
    @chi Why would an explicit type signature change anything?
    – Bergi
    Commented Aug 7 at 8:11
  • 2
    @Bergi If a polymorphic type gets inferred, like 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.
    – chi
    Commented Aug 7 at 11:40

1 Answer 1

1

Your solution is quadratic time, but about as space-efficient as it gets, provided as suggested in the comments you give it a monomorphic type signature. The quadratic time complexity comes from the repeated use of !! for indexing; that function is linear time, and it is used in a linear-length loop, giving a top-level quadratic runtime. There are various tricks for dealing with this. One particularly beautiful (and standard) one is to get adjacent elements of the list using a zip.

fibs = [0,1] ++ zipWith (+) fibs (tail fibs)

If space efficiency matters enough to start worrying about the constants in your asymptotics, you will need to go to rather greater lengths to make this better -- say, a list of increasingly-long arrays or something like that.

(Actually, the Fibonacci numbers get big enough fast enough that there's some subtleties here about the asymptotics of + itself! I've just gone ahead and assumed + is O(1) to keep the presentation simple, but if you're a real stickler or if you start doing actual measurements, it is something to keep in mind.)

1
  • I understand how why my solution is quadratic time due to the use of (!!) operator. And the classic the way to get pairs, Graham Hutton taught in his course! Now I remember
    – kichii112
    Commented Aug 7 at 18:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.