 Solution

ID: past-exam-of-the-year-1-of-the-computer-science-course-of-the-university-of-oxford/2018/functional-programming-design-and-analysis-of-algorithms/3/d/solution

One simple right-associated representation is

rep :: [a] -> CatList a
rep []     = Nil
rep (x:xs) = Cat (One x) (rep xs)

It constructs two data constructors per input element and one final Nil, so full construction takes $Θ (n + 1)$ time and produces

2 n + 1

constructors. Structural induction shows that its denotation is the original list.

 New to topics? Read the docs here!