undefined | Better HN

0 pointsericbb14y ago0 comments

This kind of problem has really short solutions when you have access to collection-at-a-time operations. For example, in Haskell:

    pascal 1 = [1]
    pascal i = zipWith (+) ([0] ++ pascal (i - 1)) (pascal (i - 1) ++ [0])

I'm not answering your question but just wanted to pique your interest in this because you were asking about language choice and had mentioned that your solution took 50 lines.

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.

0 comments

2 comments · 1 top-level

harichinnan14y ago· 1 in thread

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

nandemo14y ago

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

j / k navigate · click thread line to collapse