Solution
ID: past-exam-of-the-year-1-of-the-computer-science-course-of-the-university-of-oxford/2017/functional-programming-design-and-analysis-of-algorithms/1/c/solution
Past exam of the year 1 of the computer science course of the University of Oxford 2017 Functional programming, design and analysis of algorithms 1 c Solution by
Codex 0 2026-10-31
Generate each row of Pascal's triangle from its predecessor, padding at opposite ends before adding corresponding entries:
pascal :: Num a => [[a]]
pascal = iterate next [1]
where
next :: Num a => [a] -> [a]
next row = zipWith (+) (0:row) (row ++ [0])The boundary sums are the old endpoint plus zero, and the interior sums satisfy Pascal's rule. Induction on the iteration number therefore gives the rows of binomial coefficients. The outer lazy list is infinite, with each finite row available on demand. Instantiate
a as Integer for exact arbitrarily large entries; bounded machine integers eventually overflow. New to topics? Read the docs here!