Memoized Pascal Recursion in Haskell-CodePudding

Referencing this article on Memoization, I believe that this approach is an approach that use memoization, and should be fast. However, it doesn't seem to be the case here.

Code:

pascal :: Int -> Int -> Integer
pascal a = (map ((map pascal' [0..]) !! a) [0..] !!)
  where pascal' a b | a == 1 && b == 1  = 1
                    | a <= 0 || b <= 0  = 0 
                    | otherwise         = pascal (a-1) (b-1)   pascal (a-1) b

Could anyone point out how Haskell interpret this, or how to make this function faster?

Thanks in advanced.

CodePudding user response：

You need to separate the construction of the (complete) data structure from the selection of the correct element within the data structure.

That is, you need to define the whole Pascal triangle:

triangle :: [[Integer]]
triangle = [[pascal' a b | b <- [0..]] | a <- [0..]]
  where pascal' a b | a == 1 && b == 1  = 1
                    | a <= 0 || b <= 0  = 0
                    | otherwise         = triangle !! (a-1) !! (b-1) 
                                            triangle !! (a-1) !! b

and then selection from the triangle will be memoized:

> triangle !! 100 !! 50
50445672272782096667406248628
>

After the data structure is defined and given a name, you can define a function for accessing the elements:

pascal :: Int -> Int -> Integer
pascal a b = triangle !! a !! b

giving the memoized call:

> pascal 100 50
50445672272782096667406248628

You can move triangle into the where clause, giving the complete code:

pascal :: Int -> Int -> Integer
pascal a b = triangle !! a !! b
  where
    triangle = [[pascal' a b | b <- [0..]] | a <- [0..]]
    pascal' a b | a == 1 && b == 1  = 1
                | a <= 0 || b <= 0  = 0
                | otherwise         = triangle !! (a-1) !! (b-1)
                                        triangle !! (a-1) !! b

which should work fine, even when compiled unoptimized or loaded into GHCi.