sicp-1.12.hs

-- SICP 1.12
--
-- The following pattern of numbers is called Pascal's triangle.
--
--      1
--     1 1
--    1 2 1
--   1 3 3 1
--  1 4 6 4 1
--     ...
--
-- The numbers at the edge of the triangle are all 1, and each
-- number inside the triange is the sum of the two numbers above
-- it. Write a procedure that computes elements of Pascal's
-- triangle by means of a recursive process.

pascalsTriangle :: Integer -> [[Integer]]
pascalsTriangle 1 = [[1]]
pascalsTriangle rowIndex =
    let upperTriangle = pascalsTriangle $ rowIndex - 1
        upperRow = last upperTriangle
        thisRow = 1 : innerRow upperRow [] ++ [1]

    in upperTriangle ++ [thisRow]

innerRow :: [Integer] -> [Integer] -> [Integer]
innerRow (_:[]) newRow = newRow
innerRow (x:y:xs) newRow = innerRow (y:xs) (newRow ++ [x + y])