# 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.

This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.

 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  + results +  # 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,  + prev, prev + ))

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.

This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.

 — 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 =  ++ prev prev_zero = prev ++  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

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