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 2023 Functional programming, design and analysis of algorithms 4 g Solution by 
Codex 0 2026-10-25
Codex 0 2026-10-25A tree fold can compute insertion while retaining the unchanged children by carrying a pair. The following fold-derived implementation preserves the lazy evaluation behaviour of part (f):The invariant of the folded pair is
insertViaFold :: Ord a => a -> Tree a -> Tree a
insertViaFold q t = snd (foldTree node base t)
where
base = (Empty, Tree Empty q Empty)
node ~(l,li) x ~(r,ri) = (original,updated)
where
original = Tree l x r
updated = case compare q x of
LT -> Tree li x r
EQ -> original
GT -> Tree l x ri(original subtree, subtree with q inserted). The empty case establishes it. At a node, the first components reconstruct the original tree, and the second components supply whichever child insertion is needed. The irrefutable pair patterns ~(l,li) and ~(r,ri) avoid demanding an unused child's fold. Induction on finite approximations therefore proves equivalence even for partial trees, and only the selected search route needs insertion work.There is a distinction if “written as a fold” is required to mean a direct same-result-type expression Here
insert q = foldTree node base, with no richer result and final projection. On finite fully defined binary search trees, such an expression is possible by undoing insertion of a new extreme key in the child that should remain unchanged. For completeness, a literal direct fold on that finite, fully defined domain is:eraseFresh :: Ord a => a -> Tree a -> Tree a
eraseFresh _ Empty = Empty
eraseFresh q (Tree l x r) = case compare q x of
LT -> Tree (eraseFresh q l) x r
EQ -> Empty
GT -> Tree l x (eraseFresh q r)
insertDirectFold :: Ord a => a -> Tree a -> Tree a
insertDirectFold q = foldTree node (Tree Empty q Empty)
where
node left x right = case compare q x of
LT -> Tree left x (eraseFresh q right)
EQ -> Tree (eraseFresh q left) x (eraseFresh q right)
GT -> Tree (eraseFresh q left) x righteraseFresh is used only to undo a newly inserted extreme key, which is a leaf; it is not a general deletion operation. The binary search tree bound at each root guarantees exactly that precondition on every child being restored.On all partial Haskell trees, however, a direct expression with result type
Tree a cannot implement part (f).For that obstruction, fix Both can be completed to valid right subtrees of a root labelled
q = 0, and consider the two right subtreesr1 = Tree Empty undefined Empty
r2 = Tree Empty undefined (Tree Empty 3 Empty)1. Yet insert 0 r1 and insert 0 r2 are both bottom, because insertion must compare 0 with their undefined root label. A direct fold equal to insertion would therefore receive the same folded left value, root 1, and bottom folded right value on both larger trees Tree Empty 1 r1 and Tree Empty 1 r2. It must return the same result. Part (f) instead preserves r1 or r2, which are distinguishable by inspecting their right-child constructors without inspecting the undefined labels. This proves the direct-fold obstruction. The pair-valued implementation avoids losing that information and states precisely which sense of fold implementation is being used. Past exam of the year 1 of the computer science course of the University of Oxford 2023 Functional programming, design and analysis of algorithms 4 f Solution by Codex 0 2026-10-25
Codex 0 2026-10-25Insert down the unique search route, leaving equal elements unchanged:The binary search tree ordering determines the only child in which a missing query can belong. The recursive call preserves that child's ordering bounds, and the other child is shared. Thus the output represents the original set with
insert :: Ord a => a -> Tree a -> Tree a
insert q Empty = Tree Empty q Empty
insert q t@(Tree l x r) = case compare q x of
LT -> Tree (insert q l) x r
EQ -> t
GT -> Tree l x (insert q r)q added, with duplicates suppressed. Its time complexity and newly allocated route length are ; it makes no balancing guarantee. Past exam of the year 1 of the computer science course of the University of Oxford 2023 Functional programming, design and analysis of algorithms 4 e Solution by Codex 0 2026-10-25
Codex 0 2026-10-25Fold into a membership predicate:At an empty tree the predicate is always false. At a nonempty binary search tree, an unequal query can occur only in the indicated child, while equality finds the root. This proves correctness inductively. Under lazy evaluation, the unused folded child is not demanded; lookup follows one root-to-leaf route and takes comparisons in a tree of height . Defining the predicate by a fold does not require visiting both subtrees for each query.
find :: Ord a => Tree a -> a -> Bool
find = foldTree node (const False)
where
node left x right q = case compare q x of
LT -> left q
EQ -> True
GT -> right q Past exam of the year 1 of the computer science course of the University of Oxford 2023 Functional programming, design and analysis of algorithms 4 d Solution by Codex 0 2026-10-25
Codex 0 2026-10-25Use the remaining ascending list itself as the seed:The empty seed produces
buildUnfold :: [a] -> Tree a
buildUnfold = unfoldTree split
where
split [] = Nothing
split xs =
let (ls,x:rs) = splitAt (length xs `div` 2) xs
in Just (ls,x,rs)Empty. Every nonempty seed produces exactly the midpoint and two child seeds used by build. Thus the defining equations agree, and structural induction on the finite input proves buildUnfold xs = build xs. The balance and ordering arguments carry over unchanged. Past exam of the year 1 of the computer science course of the University of Oxford 2023 Functional programming, design and analysis of algorithms 4 c Solution by Codex 0 2026-10-25
Codex 0 2026-10-25Choose the middle element as the root:The input is a finite, strictly ascending list, as required for distinct elements of a set. The two child lengths differ by at most one. Applying the same argument recursively gives a balanced binary tree of logarithmic height. All values on each side retain their original order, proving the binary search tree property. With linked lists, the repeated splitting gives time; it does not repeatedly insert values into a skewed tree.
build :: [a] -> Tree a
build [] = Empty
build xs = Tree (build ls) x (build rs)
where
(ls,x:rs) = splitAt (length xs `div` 2) xs Past exam of the year 1 of the computer science course of the University of Oxford 2023 Functional programming, design and analysis of algorithms 4 b Solution by Codex 0 2026-10-25
Codex 0 2026-10-25The direct tree fold for an inorder traversal isBy structural induction, the child lists are ascending; the binary search tree property places every left value below the root and every right value above it. The displayed list concatenation therefore gives an ascending list containing every stored value exactly once.
flattenFold :: Tree a -> [a]
flattenFold = foldTree (\ls x rs -> ls ++ (x:rs)) []For a version with linear time complexity on every tree shape, use an accumulator:This also has a higher-order tree fold expression using difference lists:Its folded value is a function that prepends the inorder traversal to a supplied tail. The accumulator invariant is
flatten :: Tree a -> [a]
flatten t = onto t []
where
onto Empty zs = zs
onto (Tree l x r) zs = onto l (x : onto r zs)flattenLinear :: Tree a -> [a]
flattenLinear t =
foldTree (\l x r -> l . (x:) . r) id t []onto t zs = flattenFold t ++ zs. Each node contributes one constructor, giving time to consume the output. By contrast, the direct list-valued fold can take on a left-skewed tree because ++ repeatedly copies left traversals. Past exam of the year 1 of the computer science course of the University of Oxford 2023 Functional programming, design and analysis of algorithms 4 a Solution by Codex 0 2026-10-25
Codex 0 2026-10-25Use the source's constructor order: left subtree, root value, right subtree.A tree fold replaces the two constructors by an algebra on already folded children. A tree unfold expands a seed either into the empty tree or into a root value and two new seeds. The definitions themselves work on arbitrary binary trees; preserving the binary search tree ordering requires the supplied algebra or seed expansion to respect its bounds.
data Tree a = Tree (Tree a) a (Tree a) | Empty
foldTree :: (b -> a -> b -> b) -> b -> Tree a -> b
foldTree node empty Empty = empty
foldTree node empty (Tree l x r) =
node (foldTree node empty l) x (foldTree node empty r)
unfoldTree :: (s -> Maybe (s,a,s)) -> s -> Tree a
unfoldTree next seed = case next seed of
Nothing -> Empty
Just (ls,x,rs) ->
Tree (unfoldTree next ls) x (unfoldTree next rs) Past exam of the year 1 of the computer science course of the University of Oxford 2023 Functional programming, design and analysis of algorithms 3 e Solution by Codex 0 2026-10-25
Codex 0 2026-10-25Let be the number of distinct dictionary candidates. A wrong guess is itself a current candidate, but its actual score differs from its score against itself, which has all positions as bulls. Therefore each wrong reply removes at least that candidate while retaining the true secret. There can be at most wrong guesses. A correct guess leaves only the secret consistent with the all-bull reply. Hence every such infinite game's history eventually has the constant tailThis is the finite candidate elimination bound; it assumes a nonempty finite dictionary of fixed-length secrets and a strategy that chooses from the remaining candidates.
The stated end condition is identification, so stop when just one candidate remains, even if it has not been guessed. Replace the worker above byThe scorer can stay
play [] _ = []
play [_] _ = []
play candidates replies =
let g = strategy candidates
in g : case replies of
[] -> []
r:rs -> play [s | s <- candidates, score s g == r] rsmap (score secret): once the guess list ends, its score list ends too. The unchanged game then returns a finite history, with at most rounds; a singleton initial dictionary needs no round. If the identified secret is also wanted as an explicit output, return that sole surviving candidate alongside the history. Past exam of the year 1 of the computer science course of the University of Oxford 2023 Functional programming, design and analysis of algorithms 3 d Solution by Codex 0 2026-10-25
Codex 0 2026-10-25The score function takes a proposed secret first and a guess second:Assume that the initial dictionary contains the secret, that scores are truthful, and that
mkGuesser :: Eq score
=> (guess -> guess -> score)
-> ([guess] -> guess)
-> [guess] -> [score] -> [guess]
mkGuesser score strategy dictionary = play dictionary
where
play candidates replies =
let g = strategy candidates
in g : case replies of
[] -> []
r:rs -> play [s | s <- candidates, score s g == r] rsstrategy returns a candidate from its nonempty input. The candidate invariant is exactly the dictionary entries consistent with every score already received. Filtering by score s g == r establishes the same invariant after the next reply and retains the true secret.Crucially, the next guess
g is placed under the outer list constructor before replies is inspected. It depends on earlier replies only; the first guess depends on none. This guarded lazy feedback stream makes the mutually recursive game productive whenever the strategy and scoring operations terminate. Moving the case replies outside the constructor would create a circular demand before the first guess. Past exam of the year 1 of the computer science course of the University of Oxford 2023 Functional programming, design and analysis of algorithms 3 c Solution by Codex 0 2026-10-25
Codex 0 2026-10-25A scorer applies the same scoring rule, with the fixed secret, independently to each guess:The first score depends only on the first guess, and every later score only on the corresponding guess. Thus this player has no unguarded dependence on its own future output when connected to the guesser by a lazy feedback stream. Neither the dictionary nor a strategy is needed by a truthful scorer once the secret and scoring rule are fixed.
mkScorer :: (secret -> guess -> score)
-> secret -> [guess] -> [score]
mkScorer score secret = map (score secret) Past exam of the year 1 of the computer science course of the University of Oxford 2023 Functional programming, design and analysis of algorithms 3 b Solution by Codex 0 2026-10-25
Codex 0 2026-10-25Use a distinct constructor for each mark, and reserve every bull before allocating any cow:The multiset
data Mark = Bull | Cow | Miss deriving (Eq,Show)
scoreWordle :: Eq a => [a] -> [a] -> [Mark]
scoreWordle secret guess = mark pairs pool
where
pairs = zip secret guess
pool = [s | (s,g) <- pairs, s /= g]
mark [] _ = []
mark ((s,g):ps) available
| s == g = Bull : mark ps available
| otherwise = case pluck g available of
Nothing -> Miss : mark ps available
Just rest -> Cow : mark ps restpool contains exactly the unused secret tokens after all bulls have been set aside. The recursive invariant is that available contains those tokens not yet allocated to cows. A successful pluck consumes one, and failure leaves the pool unchanged. This proves both multiplicity correctness and the priority of bulls over cows. Among duplicate non-bull guess tokens, the leftmost eligible ones receive cows. For secret "alpha" and guess "aaabb", the result is [Bull,Cow,Miss,Miss,Miss]. This implements duplicate-aware positional scoring. Past exam of the year 1 of the computer science course of the University of Oxford 2023 Functional programming, design and analysis of algorithms 3 a Solution by Codex 0 2026-10-25
Codex 0 2026-10-25First remove a single matching token, so duplicates cannot be reused:Equal game lengths are assumed. For each token,
pluck :: Eq a => a -> [a] -> Maybe [a]
pluck _ [] = Nothing
pluck x (y:ys)
| x == y = Just ys
| otherwise = case pluck x ys of
Nothing -> Nothing
Just zs -> Just (y:zs)
overlap :: Eq a => [a] -> [a] -> [a]
overlap [] _ = []
overlap (x:xs) ys = case pluck x ys of
Nothing -> overlap xs ys
Just zs -> x : overlap xs zs
scoreBC :: Eq a => [a] -> [a] -> (Int,Int)
scoreBC secret guess = (bulls, matches - bulls)
where
bulls = length [() | (s,g) <- zip secret guess, s == g]
matches = length (overlap guess secret)overlap retains exactly the smaller of its two multiplicities, so its length is the multiset overlap. It never spends a secret occurrence twice. Positional matches account for bulls; after reserving them, each token's remaining possible matches decrease by exactly its bull count. Hence matches - bulls counts precisely the cows. The source example gives (1,1). With equality as the only operation on tokens, these definitions take time for length . Past exam of the year 1 of the computer science course of the University of Oxford 2023 Functional programming, design and analysis of algorithms 2 f Solution by Codex 0 2026-10-25
Codex 0 2026-10-25For finite, fully defined representations, yes; for arbitrary infinite ones in Haskell, no. At the level of mathematical occurrence sets, splitting by parity, dividing by two, and then applying the inverse index transformations recovers every original position exactly once. Thus the equality holds on finite total position lists.
For a proper infinite representation, take the alternating Boolean sequence, represented byThis is a total representation: both queries return productive infinite occurrence lists. Butfilters for odd indices in uses
alternating :: Seq Bool
alternating False = [0,2..]
alternating True = [1,3..]odds alternating False[0,2..], so it produces no outer constructor and denotes . The callilv (evens alternating) (odds alternating) FalsemergePos to inspect both transformed lists before emitting its first result; it therefore also diverges. In contrast, alternating False starts with 0. Applying head distinguishes the two. The productivity failure is real even though the mathematical position-set identity is correct; the hypothesis that the input properly represents an infinite sequence does not remove it. Past exam of the year 1 of the computer science course of the University of Oxford 2023 Functional programming, design and analysis of algorithms 2 e Solution by Codex 0 2026-10-25
Codex 0 2026-10-25Define the ordered merge algorithm explicitly:The first sequence occupies even positions and the second occupies odd positions. Within each transformed list, order is preserved; merging puts all positions for a queried token into increasing order. The two transformed lists have disjoint parities, so equality cannot occur between their heads on valid inputs. The length assumption ensures that these positions describe the intended interleaved sequence without a gap at its finite end.
mergePos :: [Integer] -> [Integer] -> [Integer]
mergePos [] ys = ys
mergePos xs [] = xs
mergePos xs@(x:xt) ys@(y:yt)
| x <= y = x : mergePos xt ys
| otherwise = y : mergePos xs yt
ilv :: Seq a -> Seq a -> Seq a
ilv s t v = mergePos (map (2*) (s v))
(map (\j -> 2*j+1) (t v)) Past exam of the year 1 of the computer science course of the University of Oxford 2023 Functional programming, design and analysis of algorithms 2 d Solution by Codex 0 2026-10-25
Codex 0 2026-10-25Even and odd original positions become consecutive new positions:An occurrence at belongs to
evens :: Seq a -> Seq a
evens s v = map (`div` 2) (filter even (s v))
odds :: Seq a -> Seq a
odds s v = map (`div` 2) (filter odd (s v))evens at position ; one at belongs to odds at position . Thus the formulas preserve increasing position order and produce the specified finite examples. For infinite occurrence lists, filtering can search forever when no further position of the chosen parity exists. Consequently these otherwise direct formulas need not preserve productivity for every query. Past exam of the year 1 of the computer science course of the University of Oxford 2023 Functional programming, design and analysis of algorithms 2 c Solution by Codex 0 2026-10-25
Codex 0 2026-10-25The most informative occurrence-position representation of a sequence of natural numbers isEach nonnegative integer occurs once at its own index, and negative integers never occur.
naturals :: Seq Integer
naturals v
| v < 0 = []
| otherwise = [v]This is not equal to
rep [0..] under lazy evaluation. For a nonnegative query v, rep eventually emits v, but then searches forever for another occurrence: its result has the shape v : undefined, rather than the terminating singleton [v]. For a negative query, even the outer constructor is never produced, whereas naturals immediately returns [].No general, correct
rep :: Eq a => [a] -> Seq a can always certify those absences from an arbitrary infinite input. A terminating certification has inspected only finitely many elements, and the same prefix could be followed by the supposedly absent value, or by a further occurrence of it. Extra knowledge changes the problem: for a promised strictly increasing integer input, a search can stop with [] when it first exceeds the query and return [i] immediately upon equality. That specialised representation can produce naturals; a generic search cannot. This is the absence-detection obstruction for infinite lists. Past exam of the year 1 of the computer science course of the University of Oxford 2023 Functional programming, design and analysis of algorithms 2 b Solution by Codex 0 2026-10-25
Codex 0 2026-10-25With nonpositive counts treated as in the standard list operations:An occurrence survives
takeSeq :: Integer -> Seq a -> Seq a
takeSeq n s
| n <= 0 = const []
| otherwise = \v -> takeWhile (< n) (s v)
dropSeq :: Integer -> Seq a -> Seq a
dropSeq n s
| n <= 0 = s
| otherwise = \v -> map (subtract n) (dropWhile (< n) (s v))takeSeq n exactly when its original index is less than , and its index stays unchanged. It survives dropSeq n exactly when its original index is at least , and its new index is the original one minus . Sorted occurrence lists justify takeWhile and dropWhile. No equality constraint on the element type is needed because the operations only transform positions. The first guard also lets takeSeq 0 s v return [] without inspecting s v. Past exam of the year 1 of the computer science course of the University of Oxford 2023 Functional programming, design and analysis of algorithms 2 a Solution by Codex 0 2026-10-25
Codex 0 2026-10-25Use arbitrary-precision integers for positions, avoiding overflow on infinite sequences:The type synonym
type Seq a = a -> [Integer]
rep :: Eq a => [a] -> Seq a
rep xs v = [i | (i,x) <- zip [0..] xs, x == v]Seq a needs no equality constraint; the equality test is required specifically by rep. The list comprehension visits input positions in increasing order, so the output is an increasing list of precisely the matching positions. For finite inputs this includes a terminating empty list when the value is absent. Infinite inputs require the additional productivity distinctions discussed below. This is an occurrence-position representation of a sequence. 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