Skip to content

Instantly share code, notes, and snippets.

@chiller
Created March 27, 2018 12:02
Show Gist options
  • Save chiller/e296a11af26a94d07749bc5da949c702 to your computer and use it in GitHub Desktop.
Save chiller/e296a11af26a94d07749bc5da949c702 to your computer and use it in GitHub Desktop.
Haskell Memoized Fibonacci
fibo 0 = 1
fibo 1 = 1
fibo k = memo_fibo (k - 1) + memo_fibo (k - 2)
memo_fibo :: Int -> Int
memo_fibo = ((map fibo [0..]) !! )
-- memo_fibo k = ((map fibo [0..]) !! k)
-- this doesn't get memoized
-- https://stackoverflow.com/questions/11466284/how-is-this-fibonacci-function-memoized
fib = (map fib' [0..] !!)
where fib' 1 = 1
fib' 2 = 1
fib' n = fib (n-2) + fib (n-1)
main = do
print "*" -- here so you can get a sense of how much time it takes
print $ memo_fibo 30
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment