Re:Why 37signals Doesn't Hire Programmers Based on Brainteasers
by harichinnan on Thursday January 05, 2012 @07:00PM
(#3431221)
Beginner Haskell Solution:
pascal 1 = [1]
pascal 2 = [1,1]
pascal n = [1] ++ sum' (pascal (n - 1))
sum' [] = []
sum' [1] = [1]
sum' (x:xs) = [x + head' xs] ++ sum' xs
head' [] = 0
head' xs = head xs
Re:Why 37signals Doesn't Hire Programmers Based on Brainteasers
by nandemo on Thursday January 05, 2012 @09:57PM
(#3431727)
1) When you're writing a function on integers or lists using explicit recursion, usually there's need for only one base case. Do you really need a separate definition for pascal 2? What about sum' [1]?
2) Often it's better to use fold instead of explicit recursion. If you wonder whether you can rewrite your function in terms of fold...
"A tutorial on the universality and expressiveness of fold" http://www.cs.nott.ac.uk/~gmh/fold.pdf
The above solution expresses the recursive solution as the sum of two earlier rows after appending some zeros. There is very little room for errors to hide and it provides you with a kind of 'definitional' starting point to begin optimizing if you want.