How to define an infinite 2D array recursively in Haskell?

Question

I'm new to Haskell, and I like its graceful grammar. But I haven't found a suitable way to define an infinite 2D array -- for example, the Pascal Triangle:

1  1  1  1  1  ...
1  2  3  4  5  ...
1  3  6 10 15  ...
1  4 10 20 35  ...
1  5 15 35 70  ...
...

I know how to define a simple function:

pascal :: Int -> Int -> Int
pascal 1 _ = 1
pascal _ 1 = 1
pascal x y = (pascal (x - 1) y) + (pascal x (y - 1))

Since Haskell do not memorize function values, a call to pascal 20 20 will take a long time. How could I define a fast version (like an infinite 2D array)?

Answer 1

You can create the pascal triangle as an infinite, lazy, nested list

pascal :: [[Integer]]
pascal = repeat 1 : map (scanl1 (+)) pascal

The above definition is a bit terse but what it essentially means is just that each row is an accumulating sum of the previous row, starting from repeat 1 i.e. an infinite list of ones. This has the advantage that we can calculate each value in the triangle directly without doing any O(n) indexing.

Now you can index the list to find the value you need, e.g.

> pascal !! 19 !! 19
35345263800

The list will only get partially evaluated for the values you need.

You can also easily output a range of values:

> putStrLn $ unlines $ take 5 $ map (unwords . map show . take 5) $ pascal
1 1 1 1 1
1 2 3 4 5
1 3 6 10 15
1 4 10 20 35
1 5 15 35 70

Another option is to use your original function but memoize it using one of the various memorization libraries available. For example, using data-memocombinators:

import Data.MemoCombinators

pascal :: Integer -> Integer -> Integer
pascal = memo2 integral integral pascal'

pascal' :: Integer -> Integer -> Integer
pascal' 1 _ = 1
pascal' _ 1 = 1
pascal' x y = (pascal (x - 1) y) + (pascal x (y - 1))

Answer 2

The obvious choice for an infinite 2D "array" would be a nested list, i.e. an infinite list of infinite lists. It might thus be

pascal' :: [[Integer]]
pascal' = repeat 1 : [ 1 : [ pascalGen x y | y<-[1..] ] | x<-[1..] ]
 where pascalGen x y = pascal' !! (x-1) !! y + pascal' !! x !! (y - 1)

This now has the function calls memoised. It's still not optimal because of list O (n) access, but not that bad either.