in Code, Haskell, Python

Pascal Triangle Generator in Python, and then in Haskell – The Gubatron Method

Here’s in python, imperatively, and then in functional style without the need for loops.


def pascal(n):
if n == 1:
return [ 1 ]
if n == 2:
return [ 1, 1 ]
prev = pascal(n-1)
results = []
for i in range(n):
if i == 0:
continue
if i == n-1:
break
results.append(prev[i] + prev[i-1])
return [1] + results + [1]
# functional style, no loops
def pascal_fp(n):
if n == 1:
return [ 1 ]
prev = pascal_fp(n-1)
return list(map(lambda x,y:x+y, [0] + prev, prev + [0]))

view raw

pascal.py

hosted with ❤ by GitHub

Here’s in Haskell, I call it the gubatron’s method, explained in the comments.
Saw it by looking at a pattern while trying to solve it in paper, it just clicked.
Not sure if this is how other people code this solution.


— Gubatron's method
— n=3 [1, 2, 1]
— copy the list and append a 0 on the left of the first
— and append a 0 at the end of the second
— [0, 1, 2, 1]
— [1, 2, 1, 0]
— add them up!
— n=4 [1, 3, 3, 1]
— append 0s to both sides and add them up
— n=4 [1, 3, 3, 1]
— [0, 1, 3, 3, 1]
— [1, 3, 3, 1, 0]
— n=5 [1, 4, 6, 4, 1]
— and so on
— add two lists, for clarity
addLists :: Num c => [c] -> [c] -> [c]
addLists l1 l2 = zipWith (+) l1 l2
pascal :: (Eq a1, Num a1, Num a2) => a1 -> [a2]
pascal 1 = [ 1 ]
pascal n =
let prev = pascal(n-1)
zero_prev = [0] ++ prev
prev_zero = prev ++ [0]
in
addLists zero_prev prev_zero
— [1,2,3] -> "1 2 3"
listToString = unwords. map show
— mapM_ -> map monadic so no weird IO errors are triggered
printTriangle n = mapM_ putStrLn (map listToString (map pascal [1..n]))
main = do
input <- getLine
printTriangle . (read :: String -> Int) $ input

view raw

pascal.hs

hosted with ❤ by GitHub

 

Write a Comment

Comment

This site uses Akismet to reduce spam. Learn how your comment data is processed.