Making a list of lists to compute Pascal's triangle in Haskell

Question

I'm trying to make a function that takes in an integer m and returns the rows of Pascal's triangle up to that mth row.

I have already constructed a choose function, that takes in two integers n and k, and returns the value n choose k. For example, choose 3 2 returns 3.

So far, I have

pascal 0 = [1]
pascal m = [x | x <- pascal (m-1)] ++ [choose m k | k <- [0,1..m]

This is returning one big list, but really, I want a list of lists, where each list corresponds to a row in Pascal's triangle. For example pascal 3 should return [[1],[1,1],[1,2,1],[1,3,3,1]]. It currently is returning [1,1,1,1,2,1,1,3,3,1].

Answer 1

There are solutions, and then there are solutions. Let's start with solutions first, and work our way up to solutions.

The first thing to observe is that if we want the result you claimed, we have to change the type, and do a bit more wrapping:

-- was pascal :: Integer -> [Integer]
pascal :: Integer -> [[Integer]]
pascal 0 = [[1]]
pascal m = [x | x <- pascal (m-1)] ++ [[choose m k | k <- [0,1..m]]]

Now then, a few syntactic pointers: [x | x <- foo] is better written just foo, and [0,1..m] is often the same as just [0..m]:

pascal m = pascal (m-1) ++ [[choose m k | k <- [0..m]]]

You'll observe that this is appending singleton lists to the end of another list on each recursive call. This is inefficient; it's better to build lists from the front. So, we'll use a common refactoring: we'll create a helper with an accumulator.

pascal = go [] where
    go 0 acc = [1] : acc
    go m acc = go (m-1) ([choose m k | k <- [0..m]] : acc)

The next observation is that you can do things a bit more efficiently than recomputing choose m k every time: you can compute the next row of Pascal's triangle using only the previous row and some additions. This means we can build a lazy (infinite) list of all the rows of Pascal's triangle.

nextRow vs = [1] ++ zipWith (+) vs (tail vs) ++ [1]
allPascals = iterate nextRow [1]

Finally, since all of the rows of Pascal's triangle are symmetric across their midpoint, you might try to build an infinite list of just the first halves of each row. This would have the benefit of eliminating the remaining "append to the end of a list" operation. I leave this as an exercise; keep in mind that rows alternate between an even and odd number of elements, which makes this part a bit trickier (and uglier).