Past exam of the year 1 of the computer science course of the University of Oxford / 2023 / Functional programming, design and analysis of algorithms / 1 / d / Solution

tails is not a direct list fold. Every foldr c z is strict in its list argument, but tails undefined = undefined : undefined has a defined outer constructor. Applying null distinguishes this result from $\perp$.

ptails is not a direct list fold either. On a type with distinct values u and v,A fold step given the same new head x and these equal folded tails must return the same result. However,Thus the tail information needed by the next step does not factor through ptails; this violates the fold factorisation criterion even on finite total lists.

ntails is a direct list fold:When the tail is nonempty, its first nonempty suffix of a list is the tail itself; otherwise it is recovered as []. Hence original (ntailsFold xs) = xs. The inner case distinction is delayed beneath constructors, so the definition also preserves the required behaviour on partial and infinite lazy lists. Building a suffix head does not first demand the whole folded tail.