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

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 

How does Haskell interpret this? How to make this function faster?

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.