I'm not interested in the actual solution or other methods solving the problem, it's the memoization i need help with :)
I need help doing a pascals triangle problem with memoization. I want to get the middle number in the base of the triangle. (Project Euler 15)
The first example is not memoized (although the name suggests so) "20 20" not solvable
Second attempt is an attempt on doing something similar to: http://www.haskell.org/haskellwiki/Memoization
Third is hlints suggestion on no2 if that is more readable for someone.
I get this error, but i'm not sure its right even if it would compile... (run from ghci with 2 2 as params
no instance for (Num [a0])
arising from a use of `zmemopascals'
Possible fix: add an instance declaration for (Num [a0])
In the expression: zmemopascals 2 2
In an equation for `it': it = zmemopascals 2 2
.
Code:
--1
memopascals r c = [[pascals a b | b<-[1..c]] | a<-[1..r]] !! (r-1) !! (c-1)
where pascals 1 _ = 1
pascals _ 1 = 1
pascals x y = memopascals (x-1) y + memopascals x (y-1)
--2
--xmemopascals :: Int -> Int -> Int
xmemopascals r c = map (uncurry pascals) (zip [1..] [1..]) !! (r-1) !! (c-1)
where pascals 1 _ = 1
pascals _ 1 = 1
pascals x y = memopascals (x-1) y + memopascals x (y-1)
--3
zmemopascals r c = zipWith pascals [1 ..] [1 ..] !! (r-1) !! (c-1)
where pascals 1 _ = 1
pascals _ 1 = 1
pascals x y = memopascals (x-1) y + memopascals x (y-1)
There are several guidelines to achieving memoization (take a look here for some recent discussion).
First, use -O2 optimization flag with GHC compiler. Second, use monomorphic type signature. Name your intermediate list(s), that you want to achieve sharing of.
Then, pay attention to your nested definitions. If a nested definition depends on value of an argument in its enclosing ("outer") scope, that means each call to that outer function will have to create all its nested definitions anew, so there won't be any one list to be shared, but many separate independent ones.
Here in your function, separating out and naming the list expression that you want shared, we get
memopascals r c = xs !! (r-1) !! (c-1)
where
xs = [[pascals a b | b<-[1..c]] | a<-[1..r]]
pascals 1 _ = 1
pascals _ 1 = 1
pascals x y = memopascals (x-1) y + memopascals x (y-1)
Your xs definition is dependent on values of r and c, but you call your "outer" function, memopascals, from within a nested one, pascals. Each invocation of memopascals has to create its own copy of xs because it depends on memopascals's arguments, r and c. No sharing possible.
If you need to have that dependent definition, you must arrange not to call "out of scope", but rather stay inside that scope, so that all the internal ("nested") definitions can be reused.
memopascals r c = f r c
where
f r c = xs !! (r-1) !! (c-1)
xs = [[pascals a b | b<-[1..c]] | a<-[1..r]]
pascals 1 _ = 1
pascals _ 1 = 1
pascals x y = f (x-1) y + f x (y-1)
Now each invocation of memopascals creates its internal definitions (from its nested scope) which then call each other, never calling out of scope - so the list xs gets reused, achieving sharing.
But another call to memopascals will create its own new copy of its internal definition of the list xs, and will use it. We can call this a "local" sharing, not a "global" sharing (i.e. memoization). That means it runs fast, but second call with same parameters takes the same time as the first - not the 0 time as with full memoization.
There's only one way to achieve that, and that is to make your xs definition independent. Then the compiler can smash all the nested scope frames together, perform lambda lifting turning nested closures into plain lambdas, etc. etc.:
memopascals :: Int -> Int -> Integer
memopascals r c = [[pascals a b | b<-[1..]] | a<-[1..]] !! (r-1) !! (c-1)
where
pascals 1 _ = 1
pascals _ 1 = 1
pascals x y = memopascals (x-1) y + memopascals x (y-1)
With -O2 switch, GHC performs full memoization even for this version. As long as we don't forget the monomorphic type signature (or it's local sharing again).