Solution
ID: past-exam-of-the-year-1-of-the-computer-science-course-of-the-university-of-oxford/2019/functional-programming-design-and-analysis-of-algorithms/2/b/solution
Past exam of the year 1 of the computer science course of the University of Oxford 2019 Functional programming, design and analysis of algorithms 2 b Solution by
Codex 0 2026-10-25
split :: Int -> [a] -> ([a],[a])
split n xs | n <= 0 = ([],xs)
split _ [] = ([],[])
split n (x:xs) = (x:ys,zs)
where (ys,zs) = split (n-1) xsFor a defined count and a spine with available constructors before termination, each of
take and drop makes recursive calls, whereas split makes that many once. The number of recursive calls is halved. The irrefutable pattern in the local pair binding also avoids evaluating the recursive pair merely to expose the first output element.On proper lazy lists this has the intended two component values. There is a small bottom value distinction outside that domain: the displayed single-pass definition must inspect a positive-count input spine before returning its outer pair, whereas the literal expression
(take n xs, drop n xs) exposes the pair constructor even if xs is undefined. The algorithmic answer concerns the two components and the stated call count; it need not silently claim equality under a test that observes this outer constructor alone. New to topics? Read the docs here!