Skip to content

Instantly share code, notes, and snippets.

@gubatron
Last active January 27, 2021 05:17
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save gubatron/c690b46f72e0bb1bab378da8a49348c1 to your computer and use it in GitHub Desktop.
Save gubatron/c690b46f72e0bb1bab378da8a49348c1 to your computer and use it in GitHub Desktop.
Pascal triangle row generator in Haskell
-- 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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment