Haskell make the memoization of algebraic recursion generic -


my idea like:

class memo1d m -- one-dimensional function     memo1d :: m -> [a]  instance memo1d ((->) int)     memo1d f = map f [0 ..] 

so, add memoization integer-recursive-problem generic:

fib :: int -> int fib 0 = 1 fib 1 = 1 fib n = (memo_fib !! (n - 1)) + (memo_fib !! (n - 2)) memo_fib = memo1d fib 

and furthermore, if want memoization in 2-d function, recieve 2 integer parameters, have add more code (the (int->int->) error, how declare it?):

class memo2d m     memo2d :: m -> [[a]] instance memo2d (int -> int ->) -- (int -> int ->) error, how declare kind recieve `a` type , become (int->int->a) ?     memo2d f = map (\v -> map v [0 ..]) (map f [0 ..]) 

and "2-d fibnacci number" memoization coded like:

fib2 0 0 = 1 fib2 0 1 = 1 fib2 1 0 = 1 fib2 j = if j > 0 memo_fib2 !! !! (j - 1) else 0 +            if j > 1 memo_fib2 !! !! (j - 2) else 0 +            if > 0 memo_fib2 !! (i - 1) !! j else 0 +            if > 1 memo_fib2 !! (i - 2) !! j else 0 memo_fib2 = memo2d fib2 

and 3-d, 4-d, etc. have type corresponding class , instance. there way make these elegant , effective on multiple-dimension function, in here multiple-dimension specific (int->int-> ... -> a) kind function?

how below. however, in practice pick 1 of existing memoization libraries hackage.

{-# language multiparamtypeclasses, flexibleinstances #-}  class memo m     memo :: m ->  instance memo a     memo = id  instance (memo m a) => memo (int -> m) [a]     memo f = map (memo . f) [0..]  fib :: int -> int fib 0 = 1 fib 1 = 1 fib n = memo_fib (n - 1) + memo_fib (n - 2) memo_fib = (memo fib !!)  fib2 0 0 = 1 fib2 0 1 = 1 fib2 1 0 = 1 fib2 j = sum . concat $ [ [ memo_fib2 (j-1) | j > 0 ]                           , [ memo_fib2 (j-2) | j > 1 ]                           , [ memo_fib2 (i-1) j | > 0 ]                           , [ memo_fib2 (i-2) j | > 1 ]                           ] memo_fib2 = let tab = memo fib2 in \x y -> tab !! x !! y 

Comments

Popular posts from this blog

c++ - Difference between pre and post decrement in recursive function argument -

php - Nothing but 'run(); ' when browsing to my local project, how do I fix this? -

php - How can I echo out this array? -