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(n1)
results = []
for i in range(n):
if i == 0:
continue
if i == n1:
break
results.append(prev[i] + prev[i1])
return [1] + results + [1]
# functional style, no loops
def pascal_fp(n):
if n == 1:
return [ 1 ]
prev = pascal_fp(n1)
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(n1)
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.