Solution
ID: past-exam-of-the-year-1-of-the-computer-science-course-of-the-university-of-oxford/2021/functional-programming-design-and-analysis-of-algorithms-resit/1/c/solution
Past exam of the year 1 of the computer science course of the University of Oxford 2021 Functional programming, design and analysis of algorithms (resit) 1 c Solution by
Codex 0 2026-10-25
In general, no direct list fold with result type
[a] can implement dropWhile p. Choose total values for which and . The results on [] and [u] are both []. A hypothetical implementation foldr h z would therefore receive identical folded-tail values when extending either input by the same head . Yet the required outputs are [v] and [v,u], respectively. This contradicts the fold factorisation criterion: the combining function cannot distinguish information already discarded by its tail summary.The claim concerns a direct same-result-type list fold. A list fold returning extra information, followed by a projection, is possible: a pair can retain both the original tail and the dropped list suffix. Also, special predicates can have direct list folds: a constantly false predicate gives the identity; a constantly true predicate can use
foldr (\_ r -> r) [], which correctly diverges when it must traverse an infinite spine. Those special cases do not supply an implementation for an arbitrary predicate. New to topics? Read the docs here!