Pascal Triangle in Haskell

Question

The code below generates a list of Pascal Coefficients. e.g pascalList 3 outputs [[1], [1,1], [1,2,1], [1,3,3,1] Can we write below sample in more idiomatic way

pascalList 0 = [[1]]
pascalList 1 = [[1], [1, 1]]
pascalList n = let pList = pascalList (n-1)
 in pList ++ [([1] ++ pascalCoeff (last pList) ++ [1])]
 where pascalCoeff (x:y:ys) = (x+y) : pascalCoeff (y:ys)
 pascalCoeff (x:[]) = []

Following code prints above list

listtoString :: [Int] -> String
listtoString [] = []
listtoString [x] = show x
listtoString (x:xs) = show x ++ " " ++ listtoString xs
pascalTriangle :: Int -> IO ()
pascalTriangle n = mapM_ putStrLn (((justify n) . map listtoString) (pascalList n))
justify :: Int -> [String] -> [String]
justify n (x:xs) = (concat (replicate n " ") ++ x) : justify (n-1) xs
justify _ [] = []

The sample output of the pascalTriangle 4 will be

 1
 1 1
 1 2 1
 1 3 3 1
1 4 6 4 1

Answer 1

I don't know if this is more idiomatic, but ever since I've seen an infinite list construction for the Fibonacci numbers, I've been in love with it, so here goes nothing.

pascalTriangle :: [[Integer]]
pascalTriangle = [1] : map newRow pascalTriangle
 where newRow y = 1 : zipWith (+) y (tail y) ++ [1]

To understand this, perhaps first you should look at simpler examples, e.g. an infinite list of zeros,

zeros = 0 : zeros

or the list of natural numbers,

nats = 0 : map (+1) nats

or my favourite, the list of fibonacci numbers,

fibs = 1 : 1 : zipWith (+) fibs (tail fibs)

---

That being said...

The line

pascalList 1 = [[1], [1, 1]]

is unnecessary, because you've already specified pascalList 0. The line

[([1] ++ pascalCoeff (last pList) ++ [1])]

is equivalent to

[[1] ++ pascalCoeff (last pList) ++ [1]]

which is equivalent to

[ 1 : pascalCoeff (last pList) ++ [1]]

Whenever possible, I try to use functions from the standard library instead of rolling my own using recursion, so for example instead of

pascalCoeff (x:y:ys) = (x+y) : pascalCoeff (y:ys)
pascalCoeff (x:[]) = []

I'd say that this function takes a list e.g. [1,2,3,4] and does the following:

 [1, 2, 3]
 [2, 3, 4]
+ ---------
 [3, 5, 7]

so it takes the tail (all but the first element) of the list, and the init (all but the last element) of the list, and adds them together element-wise.

There are built-in functions tail, and init that yield you these parts from a list, and luckily the function

zipWith (+)

does the adding part, so you can simply say

pascalCoeff y = zipWith (+) (init y) (tail y)

which is, due to the way zipWith works, the same as

pascalCoeff y = zipWith (+) y (tail y)

---

Similarly,

listtoString [] = []
listtoString [x] = show x
listtoString (x:xs) = show x ++ " " ++ listtoString xs

could simply be

listToString = unwords . map show

---

And

justify :: Int -> [String] -> [String]
justify n (x:xs) = (concat (replicate n " ") ++ x) : justify (n-1) xs
justify _ [] = []

could be

justify n ss = zipWith (++) padding ss
 where padding = [ replicate k ' ' | k <- [n, n-1 .. 1]]

or equivalently, after eta-reduction

justify n = zipWith (++) padding
 where padding = [ replicate k ' ' | k <- [n, n-1 .. 1]]

---

Due to the fact that lists are linked lists, appending to a list is expensive, while prepending to it is cheap. So if you do decide to construct a list element-by-element, then I'd say you should prepend the new elements, and perhaps after the list is built, use a reverse.

By the same logic, head is cheap, last is expensive.

Here's a possible implementation that uses what I've just said.

pascalList = reverse . pascalList'
pascalList' 0 = [[1]]
pascalList' n = new : old
 where new = 1 : pascalCoeff (head old) ++ [1]
 old = pascalList' (n-1)

---

In my opinion it is a good idea to

• separate pure and impure code,
• keep your code as modular as possible,
• write type signatures,
• use a linter like hlint,
• use functions from the standard library instead of writing explicit recursions.

Keeping this in mind, here's how I'd write the printing part.

listToString :: (Show a) => [a] -> String
listToString = unwords . map show
leftPadStrings :: [String] -> [String]
leftPadStrings ss = map leftPad ss
 where maxlen = maximum $ map length ss
 leftPad s = replicate (div (maxlen - length s) 2) ' ' ++ s 
paddedPascalTriangle :: Int -> [String]
paddedPascalTriangle n = leftPadStrings 
 . map listToString 
 . take n 
 $ pascalTriangle
printPascalTriangle :: Int -> IO ()
printPascalTriangle = mapM_ putStrLn . paddedPascalTriangle

Running this, you should get something like the following:

*Main> printPascalTriangle 10
 1
 1 1
 1 2 1
 1 3 3 1
 1 4 6 4 1
 1 5 10 10 5 1
 1 6 15 20 15 6 1
 1 7 21 35 35 21 7 1
 1 8 28 56 70 56 28 8 1
1 9 36 84 126 126 84 36 9 1

• Zeta: You have presented an alternative solution, but haven't reviewed the code. Please explain your reasoning (how your solution works and why it is better than the original) so that the author and other readers can learn from your thought process.
• 200_success: @Zeta "It is a good idea to separate pure and impure code" was the justification given for the rewrite.
• Eman Yalpsid: @Zeta Your comment is justified, because initially I just wanted OP to know about infinite data types, because I think it's a cool concept. Since then I've added some of the more traditional code review.
• Zeta: If I had have time, I would have used the same concept :). That being said, zipWith func (init xs) (tail xs) is the same as zipWith func xs (tail xs), just as in fibs = 1 : 1 : zibWith (+) fibs (tail fibs).
• Eman Yalpsid: @Zeta ah, yes, you are right, thanks. In fact I've used the same property when I rewrote justify. Oh well, I'll edit it in.

Answer 2

The third case subsumes the second. All possible result lists are prefixes of the same infinite list - let's define that instead. iterate captures this pattern. A combination of zipWith and tail captures pascalCoeff.

pascalList :: [[Int]]
pascalList = flip iterate [1] $ \pList -> 1 : zipWith (+) pList (tail pList) ++ [1]