 Solution

ID: past-exam-of-the-year-1-of-the-computer-science-course-of-the-university-of-oxford/2022/functional-programming-design-and-analysis-of-algorithms-resit/2/e/solution

Repeated constant time insertion constructs the representation:

fromList :: [a] -> List a
fromList = foldr cons nil

The right fold preserves order because cons prepends its argument. On a finite length-

n

list, there are

n

calls of cons; completely constructing the result takes $Θ (n)$ time and

O (n)

constructors. This claim concerns finite inputs, not productivity of conversion from an infinite lazy list.

 New to topics? Read the docs here!