Memory of the Pascals of the Triangle

Question

I am not interested in the actual solution or other methods of solving the problem, this memoization I need help with :)

I need help to make the triangle triangle a memory problem. I want to get the average in the base of the triangle. (Project Euler 15)

The first example is not stored in memory (although this implies the name) "20 20" is not resolvable

The second attempt is an attempt to do something similar to: http://www.haskell.org/haskellwiki/Memoization

Thirdly, this is a hlints sentence at no2 if it is more readable for someone.

I get this error, but I'm not sure of her right, even if it compiles ... (executed from ghci with 2 2 as parameters

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 rc = [[pascals ab | b<-[1..c]] | a<-[1..r]] !! (r-1) !! (c-1) where pascals 1 _ = 1 pascals _ 1 = 1 pascals xy = memopascals (x-1) y + memopascals x (y-1) --2 --xmemopascals :: Int -> Int -> Int xmemopascals rc = map (uncurry pascals) (zip [1..] [1..]) !! (r-1) !! (c-1) where pascals 1 _ = 1 pascals _ 1 = 1 pascals xy = memopascals (x-1) y + memopascals x (y-1) --3 zmemopascals rc = zipWith pascals [1 ..] [1 ..] !! (r-1) !! (c-1) where pascals 1 _ = 1 pascals _ 1 = 1 pascals xy = memopascals (x-1) y + memopascals x (y-1) 

Answer 1

There are several guidelines for creating memoization (look at here for a recent discussion).

First use the O2 optimization flag with the GHC compiler. Secondly, use a monomorphic type signature. What is your intermediate list (s) that you want to reach?

Then pay attention to your nested definitions. If the nested definition depends on the value of the argument in its covering ("external") area, this means that each call to this external function will have to create all its nested definitions again, therefore there will not be a single list that will be shared, but many separate independent.

Here, in your function, separating and naming the list expression that you want to use together, we get

 memopascals rc = xs !! (r-1) !! (c-1) where xs = [[pascals ab | b<-[1..c]] | a<-[1..r]] pascals 1 _ = 1 pascals _ 1 = 1 pascals xy = memopascals (x-1) y + memopascals x (y-1) 

Your definition of xs depends on the values ​​of r and c , but you call your "external" memopascals function from within the nested, pascals . Each memopascals call must create its own copy of xs because it depends on the arguments of memopascals , r and c . Without the possibility of exchange.

If you need to have this dependent definition, you should settle down not to call it “out of scope”, but rather stay inside that area so that all internal (“nested”) definitions can be reused.

 memopascals rc = frc where frc = xs !! (r-1) !! (c-1) xs = [[pascals ab | b<-[1..c]] | a<-[1..r]] pascals 1 _ = 1 pascals _ 1 = 1 pascals xy = f (x-1) y + fx (y-1) 

Now each call to memopascals creates its own internal definitions (from its nested scope), which then call each other without ever calling from the scope - therefore, the xs list is reused, reaching the exchange.

But another call to memopascals will create its own new copy of the xs list internal definition and use it. We can call this "local" sharing, rather than "global" sharing (i.e., Memonymization). This means that it works quickly, but the second call with the same parameters takes the same time as the first, and not 0 times, as with a full record.

There is only one way to achieve this, and that should make your xs definition independent. Then the compiler can break all the nested frames of the frame, perform a lambda lift , turning the nested shutters into simple lambdas, etc. Etc.:

 memopascals :: Int -> Int -> Integer memopascals rc = [[pascals ab | b<-[1..]] | a<-[1..]] !! (r-1) !! (c-1) where pascals 1 _ = 1 pascals _ 1 = 1 pascals xy = memopascals (x-1) y + memopascals x (y-1) 

With the -O2 switch, the GHC performs full memoization even for this version. Until we forget the signature of the monomorphic type (or its local exchange again).

Answer 2

Remembering does not work in your functions, because calling memopascals 5 5 creates the inside of the triangle and returns a single value from it. Another call to mempascals 6 6 has nothing to do with this partial triangle internal to memopascals 5 5 .

For effective memoization, you need a common part (for example, a list of lists that represent calculated numbers in a triangle) in a separate function, which is then used by functions that access specific indices. Thus, you use the same list of lists to search for different indexes.

Usually the easiest way to do this is to write one function of the type fullpascals :: [[Int]] , which creates a complete (infinite) data structure, and another function to access this data structure, for example

 memopascals xy = fullpascals !! (x-1) !! (y-1) 

In your case, fullpascals will match one of your current functions, but without parameters for a specific index. It can even use memopascals internally for recursion.

---

Sidenote: In the memoized_fib example in the wiki, the “common part” that memoized is not a direct list of all feeds, but a function that accesses a list of all feeds. The effect is the same since the compiler is smart enough to optimize this.

Answer 3

 zmemopascals rc = zipWith pascals [1 ..] [1 ..] !! (r-1) !! (c-1) where pascals 1 _ = 1 pascals _ 1 = 1 pascals xy = memopascals (x-1) y + memopascals x (y-1) 

Not that this is important for the error, but on the last line you want to call zmemopascals , not memopascals .

On the first line, you have two list index operators. Therefore, zipWith pascals [1 .. ] [1 .. ] must be of type [[a]] for some a . pascals definition says

 pascals :: Num t => Int -> Int -> t 

thus zipWith pascals [1 .. ] [1 .. ] :: [t] . Therefore, type inference discovers that t = [a] , but the compiler does not find an instance of Num [a] .

For memoisation, you must specify a name for the complete triangle, for example, @sth, to avoid recalculation (Fibonacci memoisation only works because the compiler is smart enough, it is not guaranteed by its shape).

Another option is to build a triangle using iterate ,

 pascal :: Int -> Int -> Integer pascal nk = iterate nextRow [1] !! n !! k where nextRow ks = zipWith (+) (0:ks) (ks ++ repeat 0)