Pascal triangle row generator in Haskell
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.
Learn more about bidirectional 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 = [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