[Haskell-cafe] speeding up fibonacci with memoizing

[Thomas Hartman]

I just thought this was interesting, so I would share it.

Thanks to whoever it was on #haskell who helped me, sorry I can't remember who.

-- horribly slow. try slow_fibs 30, not too much higher than that and it hangs
slow_fibs = map slow_fib [1..]
slow_fib 1 = 1
slow_fib 2 = 1
slow_fib n = ( slow_fib (n-2) )  + (slow_fib(n-1))

-- versus, try memoized_fibs !! 10000
memoized_fibs = map memoized_fib [1..]
memoized_fib = ((map fib' [0 ..]) !!)
    where
      fib' 0 = 0
      fib' 1 = 1
      fib' n = memoized_fib (n - 1) + memoized_fib (n - 2)