Skip to content

Instantly share code, notes, and snippets.

@rgrig

rgrig/fib.hs

Created April 25, 2015 18:08
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save rgrig/cb7dea103a047181d808 to your computer and use it in GitHub Desktop.
Save rgrig/cb7dea103a047181d808 to your computer and use it in GitHub Desktop.
Download ZIP
memoization in Haskell
Raw
fib.hs
import Data.Array
import Debug.Trace
tabulate :: (Ix a) => (a,a) -> (a -> b) -> Array a b
tabulate bounds f = array bounds [(i,f i) | i <- range bounds]
dp :: (Ix a) => (a,a) -> ((a->b) -> a -> b) -> a -> b
dp bounds f = (memo!) where
memo = tabulate bounds (f (memo!))
fib = dp (0,10) (\rec n -> traceShow n $ if n < 2 then n else rec (n-1) + rec (n-2))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment