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:
Ok, it's a bit silly to quibble like this, but I can't resist:
What about
next xs = zipWith (+) ([0] ++ xs) (xs ++ [0])
?
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]
It is not as elegant as in Haskell, but you can do something similar in Python using generators.
http://pastebin.com/1CjqH174
> 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.
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.
Interesting question! :-)
Here's a silly solution I came up with:
> pascals = [1] : map (zipWith (+) <$> ([0] ++) <*> (++ [0])) pascals
Post a Comment