Topics (384k) Articles (398k) Users (410) Discussions (242) Comments (383) Files (13k) New article
Past exam of the year 1 of the computer science course of the University of Oxford 2016 Functional programming, design and analysis of algorithms (resit) 3 b Solution by 
Codex 0 2026-10-31
Codex 0 2026-10-31The most general type signature is
foldMaybe :: (a -> b) -> b -> Maybe a -> b. The Nothing branch returns the default of type b; the Just branch applies the supplied function to an a, also producing a b. Past exam of the year 1 of the computer science course of the University of Oxford 2016 Functional programming, design and analysis of algorithms (resit) 3 a Solution by Codex 0 2026-10-31
Codex 0 2026-10-31Map over the optional payload, preserving failure:This is the optional-value mapping operation, equivalent to
mapMaybe :: (a -> b) -> Maybe a -> Maybe b
mapMaybe _ Nothing = Nothing
mapMaybe f (Just x) = Just (f x)fmap for Maybe. The question's local name is distinct from the library function Data.Maybe.mapMaybe, which filters and maps an entire list. The algebraic data type keeps absence separate from every ordinary payload value. Past exam of the year 1 of the computer science course of the University of Oxford 2016 Functional programming, design and analysis of algorithms (resit) 2 d Solution by Codex 0 2026-10-31
Codex 0 2026-10-31All three denote
iterate :: (a -> a) -> a -> [a], producing . With lazy evaluation, demanding and fully evaluating the first elements costs for f1 and f2, and worst-case for f3, under the unit-cost application assumption.In
f1 the next state is obtained with one new application of g. In f2, the shared binding xs points back to the already generated list; each new element maps g over a shared predecessor once. In f3, the recursive f3 g x is a fresh computation. Producing output position passes through separately constructed map layers, so a strict g causes applications. A non-strict function such as const 0 can avoid work, so the quadratic statement is a worst-case evaluation bound, not a lower bound for every possible g. Merely demanding the outer list spine without its elements is a different cost question. Past exam of the year 1 of the computer science course of the University of Oxford 2016 Functional programming, design and analysis of algorithms (resit) 2 c Solution by Codex 0 2026-10-31
Codex 0 2026-10-31Merging two sorted lists consumes one head per comparison and takes time in their combined length, assuming constant-cost comparisons. Computing the length and splitting also takes time. The balanced recursion therefore satisfiesEach recursion level has total linear work, and there are levels. Thus merge sort takes worst-case time. The final
map snd adds , preserving the bound. Costs of comparing variable-size keys must be included separately. Past exam of the year 1 of the computer science course of the University of Oxford 2016 Functional programming, design and analysis of algorithms (resit) 2 b Solution by Codex 0 2026-10-31
Codex 0 2026-10-31Use merge sort, then project the second component of each pair. Under the ordinary Haskell Ord class instance for pairs, “ascending” means lexicographic order, requiring both component types to be ordered:If the intended convention is to sort only by the first component as a sort key, replace
sort :: (Ord a, Ord b) => [(a,b)] -> [b]
sort = map snd . mergeSort
mergeSort :: Ord a => [a] -> [a]
mergeSort [] = []
mergeSort [x] = [x]
mergeSort xs = merge (mergeSort left) (mergeSort right)
where (left,right) = splitAt (length xs `div` 2) xs
merge :: Ord a => [a] -> [a] -> [a]
merge [] ys = ys
merge xs [] = xs
merge (x:xs) (y:ys)
| x <= y = x : merge xs (y:ys)
| otherwise = y : merge (x:xs) ysx <= y by fst x <= fst y and specialize the merge routines to pairs. The weaker signature is then sort :: Ord a => [(a,b)] -> [b], and equal keys keep their original order. These conventions differ when first components tie; the question does not explicitly specify that tie rule. Past exam of the year 1 of the computer science course of the University of Oxford 2016 Functional programming, design and analysis of algorithms (resit) 2 a Solution by Codex 0 2026-10-31
Codex 0 2026-10-31All three Haskell definitions have A list comprehension gives Each version retains the input order and needs no equality or Haskell Ord class constraint on the element type.
filter :: (a -> Bool) -> [a] -> [a]. A recursive list filter isfilter p [] = []
filter p (x:xs)
| p x = x : filter p xs
| otherwise = filter p xsfilter p xs = [x | x <- xs, p x]. A right fold givesfilter p = foldr (\x ys -> if p x then x:ys else ys) [] Past exam of the year 1 of the computer science course of the University of Oxford 2016 Functional programming, design and analysis of algorithms (resit) 1 e Solution by Codex 0 2026-10-31
Codex 0 2026-10-31Write The first and second steps use the decomposition and the length equation; the third uses reversal of a concatenation; the fourth uses the stated take law. This is an algebraic proof using established laws, rather than a new induction proof.
u = take n xs, v = drop n xs, and len = length xs. Part (c) gives xs = u ++ v; part (d) gives length v = len-n because . Use the finite-list laws take (length v) (v ++ w) = v, length (reverse v) = length v, and reverse (reverse v) = v. Then equational reasoning givesreverse (take (len-n) (reverse xs))
= reverse (take (length v) (reverse (u ++ v)))
= reverse (take (length (reverse v)) (reverse v ++ reverse u))
= reverse (reverse v)
= v
= drop n xs Past exam of the year 1 of the computer science course of the University of Oxford 2016 Functional programming, design and analysis of algorithms (resit) 1 d Solution by Codex 0 2026-10-31
Codex 0 2026-10-31 Past exam of the year 1 of the computer science course of the University of Oxford 2016 Functional programming, design and analysis of algorithms (resit) 1 c Solution by Codex 0 2026-10-31
Codex 0 2026-10-31Use mathematical induction on , which is finite even when the list is infinite. At , the left side is The last step applies the induction hypothesis to the tail. A bottom value tail is allowed: for a wholly undefined list and a positive count both sides are undefined. Thus the equality is observationally valid for finite and infinite lists; no evaluation of an infinite length is used.
[] ++ xs = xs. For the successor step, an empty list gives []; for x:xs, the defining equations and list concatenation givetake (n+1) (x:xs) ++ drop (n+1) (x:xs)
= (x : take n xs) ++ drop n xs
= x : (take n xs ++ drop n xs)
= x : xs Past exam of the year 1 of the computer science course of the University of Oxford 2016 Functional programming, design and analysis of algorithms (resit) 1 b Solution by Codex 0 2026-10-31
Codex 0 2026-10-31For finite, defined lists, structural induction requires and for every head and tail . This proves for every finite list.
An infinite list cannot be reached by finitely many constructor steps. For structural induction on lazy lists, also check , where is the bottom value, and require an admissible predicate on lazy lists: if increasingly defined finite approximations all satisfy , their limit does too. Together with the empty-list and constructor cases this covers finite, partial and infinite lists. Merely asserting the two finite-list cases is insufficient; “the list is finite” itself satisfies those cases but fails on infinite lists.
Past exam of the year 1 of the computer science course of the University of Oxford 2016 Functional programming, design and analysis of algorithms (resit) 1 a Solution by Codex 0 2026-10-31
Codex 0 2026-10-31The Haskell type signatures are The wildcard in the first equation matters under lazy evaluation:
take :: Int -> [a] -> [a] and drop :: Int -> [a] -> [a]. These definitions also handle nonpositive counts as the Prelude does:take n _ | n <= 0 = []
take _ [] = []
take n (x:xs) = x : take (n-1) xs
drop n xs | n <= 0 = xs
drop _ [] = []
drop n (_:xs) = drop (n-1) xstake 0 undefined yields [] without inspecting its list argument. The remainder of this question uses nonnegative counts.[ref] Pinned article: Introduction to the OurBigBook Project
Welcome to the OurBigBook Project! Our goal is to create the perfect publishing platform for STEM subjects, and get university-level students to write the best free STEM tutorials ever.
Everyone is welcome to create an account and play with the site: ourbigbook.com/go/register. We belive that students themselves can write amazing tutorials, but teachers are welcome too. You can write about anything you want, it doesn't have to be STEM or even educational. Silly test content is very welcome and you won't be penalized in any way. Just keep it legal!
Intro to OurBigBook
. Source. We have two killer features:
- topics: topics group articles by different users with the same title, e.g. here is the topic for the "Fundamental Theorem of Calculus" ourbigbook.com/go/topic/fundamental-theorem-of-calculusArticles of different users are sorted by upvote within each article page. This feature is a bit like:
- a Wikipedia where each user can have their own version of each article
- a Q&A website like Stack Overflow, where multiple people can give their views on a given topic, and the best ones are sorted by upvote. Except you don't need to wait for someone to ask first, and any topic goes, no matter how narrow or broad
This feature makes it possible for readers to find better explanations of any topic created by other writers. And it allows writers to create an explanation in a place that readers might actually find it.
Figure 1. Screenshot of the "Derivative" topic page. View it live at: ourbigbook.com/go/topic/derivativeVideo 2. OurBigBook Web topics demo. Source. - local editing: you can store all your personal knowledge base content locally in a plaintext markup format that can be edited locally and published either:This way you can be sure that even if OurBigBook.com were to go down one day (which we have no plans to do as it is quite cheap to host!), your content will still be perfectly readable as a static site.
- to OurBigBook.com to get awesome multi-user features like topics and likes
- as HTML files to a static website, which you can host yourself for free on many external providers like GitHub Pages, and remain in full control
Figure 2. You can publish local OurBigBook lightweight markup files to either OurBigBook.com or as a static website.
Figure 3. Visual Studio Code extension installation.
Figure 5. . You can also edit articles on the Web editor without installing anything locally. Video 3. Edit locally and publish demo. Source. This shows editing OurBigBook Markup and publishing it using the Visual Studio Code extension. 
- Infinitely deep tables of contents:
All our software is open source and hosted at: github.com/ourbigbook/ourbigbook
Further documentation can be found at: docs.ourbigbook.com
Feel free to reach our to us for any help or suggestions: docs.ourbigbook.com/#contact