-- Memorized variant is near instant even after 10000
memoized_fib :: Int -> Integer
memoized_fib = (map fib [0 ..] !!)
where fib 0 = 0
fib 1 = 1
fib n = memoized_fib (n-2) + memoized_fib (n-1)
or
fibM = \n -> values !! n
where values = [fibAux m | m <- [0..]]
fibAux n | n <= 1 = n
| otherwise = fibM (n-2) + fibM (n-1)
or
fibM2 :: Int -> Integer
fibM2 = \n -> values !! n
where values = [fibAux m | m <- [0..]]
fibAux 0 = 0
fibAux 1 = 1
fibAux n = fibM2 (n-2) + fibM2 (n-1)
Run the following at the ghci Haskell prompt:
memoized_fib 47
fibM 47
fibM2 47
If you want to wait try:
-- Traditional implementation of fibonacci, hangs after about 30
slow_fib :: Int -> Integer
slow_fib 0 = 0
slow_fib 1 = 1
slow_fib n = slow_fib (n-2) + slow_fib (n-1)
-- Memorized variant is near instant even after 10000 memoized_fib :: Int -> Integer memoized_fib = (map fib [0 ..] !!) where fib 0 = 0 fib 1 = 1 fib n = memoized_fib (n-2) + memoized_fib (n-1)
or
fibM = \n -> values !! n where values = [fibAux m | m <- [0..]] fibAux n | n <= 1 = n | otherwise = fibM (n-2) + fibM (n-1)
or
fibM2 :: Int -> Integer fibM2 = \n -> values !! n where values = [fibAux m | m <- [0..]] fibAux 0 = 0 fibAux 1 = 1 fibAux n = fibM2 (n-2) + fibM2 (n-1)
Run the following at the ghci Haskell prompt:
memoized_fib 47
fibM 47
fibM2 47
If you want to wait try:
-- Traditional implementation of fibonacci, hangs after about 30 slow_fib :: Int -> Integer slow_fib 0 = 0 slow_fib 1 = 1 slow_fib n = slow_fib (n-2) + slow_fib (n-1)