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 2018 Functional programming, design and analysis of algorithms 2 f Solution by 
Codex 0 2026-10-31
Codex 0 2026-10-31The coefficient index supplies the multiplier for a formal derivative and the divisor for a zero-constant formal integral:
deriv :: Num a => [a] -> [a]
deriv as = zipWith (*) (map fromInteger [1..]) (tail as)
integral :: Fractional a => [a] -> [a]
integral as = 0 : zipWith (/) as (map fromInteger [1..])Using
fromInteger makes the index stream unbounded before conversion to the coefficient type. The formal derivative drops the original constant coefficient; the formal integral prepends its chosen zero constant. With exact Rational coefficients these are exact algebraic operations. Analytic convergence is unnecessary for operations on formal power series over a characteristic-zero field. Past exam of the year 1 of the computer science course of the University of Oxford 2018 Functional programming, design and analysis of algorithms 2 e Solution by Codex 0 2026-10-31
Codex 0 2026-10-31plus, minus :: Num a => [a] -> [a] -> [a]
plus = zipWith (+)
minus = zipWith (-)Here every valid input is an infinite coefficient list. If finite polynomial coefficient lists were admitted, they would need zero-padding before these definitions: ordinary list zip otherwise truncates to the shorter length.
Past exam of the year 1 of the computer science course of the University of Oxford 2018 Functional programming, design and analysis of algorithms 2 d Solution by Codex 0 2026-10-31
Codex 0 2026-10-31Use infinite coefficient lazy lists:
zero, one :: Num a => [a]
zero = 0 : zero
one = 1 : zeroFor ordinary numeric coefficients such as
Rational, zero == zero does not terminate, while zero == one is False. The former comparison never finds a differing coefficient or reaches two empty lists; the latter rejects the unequal first coefficients immediately. Equality of denoted formal power series is mathematical equality of all coefficients, whereas this executable list comparison is a potentially nonterminating procedure. Past exam of the year 1 of the computer science course of the University of Oxford 2018 Functional programming, design and analysis of algorithms 2 c Solution by Codex 0 2026-10-31
Codex 0 2026-10-31The two required equations are
zipWith f xs ys = map (uncurry f) (zip xs ys)
zip xs ys = zipWith (,) xs ysEither equation defines one operation from an independently defined other operation. They do not together supply an effective recursive definition of the intended operations. Substitution makes the first output constructor depend on itself without first emitting anything, so the mutually recursive program has the bottom value as its least solution. At the level of equations they also fail to characterize the intended operations uniquely: returning
[] for every call of either operation satisfies both equations, as does the intended list zip. A constructor-producing base/step definition is essential for productivity. Past exam of the year 1 of the computer science course of the University of Oxford 2018 Functional programming, design and analysis of algorithms 2 b Solution by Codex 0 2026-10-31
Codex 0 2026-10-31Apply the supplied function to corresponding elements while preserving the stopping rule:
zipWith :: (a -> b -> c) -> [a] -> [b] -> [c]
zipWith f [] _ = []
zipWith f _ [] = []
zipWith f (x:xs) (y:ys) = f x y : zipWith f xs ys Past exam of the year 1 of the computer science course of the University of Oxford 2018 Functional programming, design and analysis of algorithms 2 a Solution by Codex 0 2026-10-31
Codex 0 2026-10-31Use the usual left-to-right pattern matching order:
zip :: [a] -> [b] -> [(a,b)]
zip [] _ = []
zip _ [] = []
zip (x:xs) (y:ys) = (x,y) : zip xs ysThe result stops when either list ends, so its length on finite total inputs is the smaller input length. Elements remaining in the longer list are discarded.
Strictness is asymmetric. Writing the bottom value as ,
zip is strict in its first list but not uniformly strict in its second: zip undefined ys is undefined, whereas zip [] undefined = []. With a nonempty first list, an undefined second list does make the result undefined. Neither pair component is forced merely to produce the outer result constructor: zip [undefined] [undefined] already has a defined outer cons and pair. This follows from ordered pattern matching and lazy evaluation, not from the behavior on total lists alone.[ref]Haskell 2010 Language Report. §3.17.2, ordered pattern matching; Chapter 9, zip in the Standard Prelude
Past exam of the year 1 of the computer science course of the University of Oxford 2018 Functional programming, design and analysis of algorithms 1 h Solution by Codex 0 2026-10-31
Codex 0 2026-10-31Suppose that a direct tree fold with result type
[Tree a] implements proper, so proper = fold one two. Every leaf has result [], hence one x = [] for every label x. Consequently proper (Two (One x) (One y)) would always equal two [] [], independently of either label. Taking labels from Bool, the inputs Two (One False) (One False) and Two (One True) (One False) would therefore have equal results. Their correct results are [One False, One False] and [One True, One False], which differ. This is a contradiction.There is no direct fold with only the proper-subtree list as its recursive summary. This is the direct tree-fold information obstruction: replacing both children by equal summaries prevents the parent operation from recovering their different labels. The claim must not be extended to every expression containing a tree fold. A fold retaining the original tree alongside its proper-subtree list, followed by projection, does work; alternatively
tail . subs uses the richer fold from part (f). Past exam of the year 1 of the computer science course of the University of Oxford 2018 Functional programming, design and analysis of algorithms 1 g Solution by Codex 0 2026-10-31
Codex 0 2026-10-31proper :: Tree a -> [Tree a]
proper (One _) = []
proper (Two l r) = (l : proper l) ++ (r : proper r) Past exam of the year 1 of the computer science course of the University of Oxford 2018 Functional programming, design and analysis of algorithms 1 f Solution by Codex 0 2026-10-31
Codex 0 2026-10-31The head of each recursively obtained list is the original child. Hence the tree fold has retained enough information to reconstruct the parent:
subs :: Tree a -> [Tree a]
subs = fold (\x -> [One x]) combine
where
combine ls rs = Two (head ls) (head rs) : (ls ++ rs)The invariant is that every folded result is nonempty and begins with the subtree being folded. It holds at
One; the displayed combining operation preserves it at Two. Thus neither use of head encounters an empty list, and the remaining entries agree with the recursive preorder traversal. Past exam of the year 1 of the computer science course of the University of Oxford 2018 Functional programming, design and analysis of algorithms 1 e Solution by Codex 0 2026-10-31
Codex 0 2026-10-31subs :: Tree a -> [Tree a]
subs t@(One _) = [t]
subs t@(Two l r) = t : (subs l ++ subs r)This is a preorder traversal of subtree occurrences. Equal-valued occurrences are retained: the answer is a list, not a deduplicated set. Every occurrence is either the root or lies in exactly one child, which proves completeness by structural induction.
Past exam of the year 1 of the computer science course of the University of Oxford 2018 Functional programming, design and analysis of algorithms 1 d Solution by Codex 0 2026-10-31
Codex 0 2026-10-31Replace the leaf data constructor by the constant one and the internal data constructor by addition with one extra node:
size :: Tree a -> Int
size = fold (const 1) (\m n -> 1 + m + n) Past exam of the year 1 of the computer science course of the University of Oxford 2018 Functional programming, design and analysis of algorithms 1 c Solution by Codex 0 2026-10-31
Codex 0 2026-10-31The natural tree fold replaces each data constructor by the supplied operation:
fold :: (a -> b) -> (b -> b -> b) -> Tree a -> b
fold one two (One x) = one x
fold one two (Two l r) = two (fold one two l) (fold one two r)Its reconstruction identity is
fold One Two = id. More generally a function h equals fold one two on finite trees exactly when h (One x) = one x and h (Two l r) = two (h l) (h r). These equations determine the result by structural induction, expressing why this is the natural structural recursion for this datatype. Past exam of the year 1 of the computer science course of the University of Oxford 2018 Functional programming, design and analysis of algorithms 1 b Solution by Codex 0 2026-10-31
Codex 0 2026-10-31Count each data constructor once, including each
Two:size :: Tree a -> Int
size (One _) = 1
size (Two l r) = 1 + size l + size rStructural induction verifies the count: a leaf contributes one; an internal node contributes itself and the disjoint occurrences in its two subtrees. Fully evaluating the result takes linear time in the number of nodes. This type signature uses machine
Int as usual in the examination; Integer avoids overflow for arbitrarily large inputs. Past exam of the year 1 of the computer science course of the University of Oxford 2018 Functional programming, design and analysis of algorithms 1 a Solution by Codex 0 2026-10-31
Codex 0 2026-10-31Tree is a type constructor, taking the element type parameter a to the algebraic data type Tree a. It is not a value and has no ordinary value-level function type; its kind of a type is * -> *. The other names are data constructors with polymorphic type signatures:One :: a -> Tree a
Two :: Tree a -> Tree a -> Tree aOne constructs a leaf-labelled binary tree with one leaf; Two joins two such trees under a new internal node. Unlike a general binary tree representation with empty child slots, this representation has no empty tree.[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