Sunday, January 08, 2012

Pascal's Triangle in Haskell

Summary: I'm continually amazed how concise and powerful Haskell is, compared to mainstream languages. This post describes how to write Pascal's Triangle, and gives some of the advantages of using Haskell.

Often, when programming in Haskell, I feel like I'm cheating. As an example, I recently came across this article by William Shields, which suggests that prospective interview candidates be given simple programming tasks like generating Pascal's Triangle. William gives examples in Python, including some of the answers a typical candidate might give.

Pascal's Triangle in Haskell

William describes Pascal's Triangle as:

"The root element is 1. Every other element is the sum of the one or two above it (diagonally left and diagonally right)."

As a Haskell programmer, the obvious technique to use is induction. The first row of the triangle is [1], and each row can be computed from the previous row by adding the row shifted left, and the row shifted right:


next xs = zipWith (+) ([0] ++ xs) (xs ++ [0])
pascal = iterate next [1]


Here, we define next to take one row and produce the next row. We then use the iterate function to repeatedly apply next starting at the root element. The solution is short, and follows from the definition.

Laziness for Modularity

William originally posed three questions:


  • Print out the triangle to a specific row: print $ take 100 pascal

  • Return a given row of the triangle: pascal !! 50

  • Return a given element (by row and index) of the triangle: pascal !! 10 !! 5



Thanks to laziness, we can concisely answer all these questions in terms of the original pascal definition. In contrast, using a language such as Python, the best solution (Dynamic Programming from the original article) can only perform the first task.

Interview problems

The original article was not about the choice of programming language, but about choosing suitable questions for interviewing programmers. I agree with William that Pascal's Triangle is a suitable problem - it isn't a trick puzzle, it isn't an API knowledge quiz - it's about understanding how to program. Given how much easier the problem is to solve in Haskell, I wonder if using Haskell in a job interview should be considered cheating? ;-)

6 comments:

Anonymous said...

Ok, it's a bit silly to quibble like this, but I can't resist:

What about

next xs = zipWith (+) ([0] ++ xs) (xs ++ [0])

?

Neil Mitchell said...

Anon: I did wonder if I should do that version myself - since what I've really done is a peephole optimisation of that where you know head xs == last xs == 1. Thinking further, you are completely right, so I've switched to your version. For future reference, my original version was:

next xs = [1] ++ zipWith (+) xs (tail xs) ++ [1]

Jan Van lent said...

It is not as elegant as in Haskell, but you can do something similar in Python using generators.

http://pastebin.com/1CjqH174

Anonymous said...

> I wonder if using Haskell in a job interview should be considered cheating? ;-)
I wouldn't consider using the right tool for the right job cheating.

After all, Haskell is pretty much literal Mathematics. And the Pascal Triangle is a Mathematical definition.

Fred Blasdel said...

Yes, in my experience interviewers will grimace at you if you solve their whiteboard problem in concise mathematical Haskell.

Even the rare interviewer that would be delighted if you did it in Common Lisp.

Nicolas Wu said...

Interesting question! :-)

Here's a silly solution I came up with:

> pascals = [1] : map (zipWith (+) <$> ([0] ++) <*> (++ [0])) pascals