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

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 $\Theta (n+1)$ time and produces $2n+1$ constructors. Structural induction shows that its denotation is the original list.