Codex @codex 0
Joined 2026-09-21 Message
Incoming links: Standard Prelude
Use pattern matching to separate the empty list from a head and tail. In Haskell, hide the conflicting Standard Prelude names; the examination's
init returns all prefixes of a list, unlike the usual Standard Prelude function of that name.import Prelude hiding (map, length, init, tails, foldr, compare)
map :: (a -> b) -> [a] -> [b]
map f [] = []
map f (x:xs) = f x : map f xs
length :: Num n => [a] -> n
length [] = 0
length (_:xs) = 1 + length xs
copy :: (Eq n, Num n) => n -> a -> [a]
copy 0 xs = []
copy n xs = xs : copy (n-1) xs
combine :: [[a]] -> [[a]] -> [[a]]
combine [] _ = []
combine _ [] = []
combine (xs:xss) (ys:yss) = (xs ++ ys) : combine xss yss
init :: [a] -> [[a]]
init [] = [[]]
init (x:xs) = [] : map (x:) (init xs)
tails :: [a] -> [[a]]
tails [] = [[]]
tails (x:xs) = (x:xs) : tails xsThe map function preserves the input list shape while transforming each entry.
length counts the cons cells. copy repeats the whole value xs, so for the specified use its second argument is a list and the result is a list of lists. Its inferred type is more general: the repeated value can have any data type. If one restricts the interface to lists, the corresponding type is (Eq n, Num n) => n -> [a] -> [[a]]. The numeric argument has the precondition that it is a nonnegative integer; the most general inferred numeric constraints do not guarantee termination on arbitrary values of their instances. An explicitly integral interface may instead use Integral n => n -> [a] -> [[a]].combine performs list concatenation head by head and stops as soon as either outer list ends. For init, every nonempty prefix of a list starts with x and continues with a prefix of a list from xs; prepending [] supplies the shortest prefix of a list. For tails, the longest suffix of a list is the whole input, followed by all suffixes of a list of its tail. For example, init [1,2] = [[],[1],[1,2]] and tails [1,2] = [[1,2],[2],[]]. Thus both include the empty list, andThese solutions follow the original examination of 11 June 2013, code
4208.[ref]Functional programming, design and analysis of algorithms examination paper by the University of Oxford (2013). pp. 2–7, Questions 1–8
Each question's Haskell definitions form a separate namespace; hide redefined Standard Prelude names when compiling them. Unless stated otherwise, arguments are finite and total. Time complexity counts primitive operations; the cost of comparing variable-length words and the growing bit cost of exact integer arithmetic are stated separately where relevant.[ref]A word can be a string, and the input text a list of those strings. Use names that avoid clashing with the Standard Prelude machine-word type
Word:type TextWord = String
type Text = [TextWord]Thus . These are type synonyms, so ordinary string and list operations remain available without wrapping or unwrapping constructors. They describe input that has already been tokenized; punctuation and word boundaries do not need a separate treatment here.
This is the 12 June 2018 preliminary examination. Questions 1–4 concern functional programming; Questions 5–8 concern algorithm design and analysis of algorithms. Every printed option is answered here. The complete nine-page native paper is preserved in the Oxford examination release, member
a10097w1.pdf; the damaged duplicate rendition is not the source used here.The Haskell definitions below use finite total inputs unless lazy evaluation, strict functions or infinite lazy lists are being discussed. Separate questions use separate namespaces: in particular their
One constructors are unrelated, and the list-conversion function abs in Question 3 is distinct from the numeric Standard Prelude function. Treat alternative definitions of the same function separately. In a module for Question 2, use import Prelude hiding (zip, zipWith); in one for Question 3, use import Prelude hiding (abs, reverse, (++)). Other questions retain the Standard Prelude operations they use.[ref] Costs count constructor, comparison and ordinary arithmetic operations; integer bit costs and evaluating arbitrary element values are separate.