Past exam of the year 1 of the computer science course of the University of Oxford / 2003 / Functional programming, data structures and algorithms, procedural programming, and digital hardware / 2

For finite lists, Cartesian lifting of a binary operation to lists preserves associativity. Both associations enumerate triples in the same order: the entry from xs changes slowest, then the entry from ys, then the entry from zs changes fastest. The results are respectivelyandAssociativity makes corresponding entries equal; their order and multiplicity already agree. Empty lists make both sides empty. Therefore

Commutativity of the element binary operation does not remove the ordering of a list comprehension. For ordinary addition, take xs = [1,2] and ys = [10,20]. ThenThe middle entries occur in opposite orders. Hence

Idempotence concerns applying an operation to the same whole value. It says more than saying that the equal-entry pairs are unchanged. Choose the idempotent binary operation min. ThenMore generally, a finite list of length $m$ paired with itself produces $m^2$ entries, so length alone contradicts idempotence when $m>1$. Therefore

A right fold replaces the empty list by a seed and each cons by an application of the combining function:

foldr :: (a -> b -> b) -> b -> [a] -> b
foldr op e [] = e
foldr op e (x:xs) = op x (foldr op e xs)

For example, foldr op e [a,b,c] = op a (op b (op c e)). The concise defining law is

Each entry contributes a choice between omission and inclusion. Use list concatenation as $\oplus$, so that Cartesian lifting of a binary operation to lists joins every choice from an earlier position to every choice from later positions:

crossAppend :: [[a]] -> [[a]] -> [[a]]
crossAppend xss yss = [xs ++ ys | xs <- xss, ys <- yss]

f :: a -> [[a]]
f x = [[],[x]]

subs :: [a] -> [[a]]
subs xs = foldr crossAppend [[]] (map f xs)

The seed is [[]], because the empty list has one subsequence, namely [], and concatenating the empty list changes nothing. If rest lists the subsequences of the tail, crossAppend [[],[x]] rest lists all omissions of x first and all inclusions second. For [a,b,c], the last position changes fastest, producing the specified order [], [c], [b], [b,c], [a], [a,c], [a,b], [a,b,c]. Repeated input values can give equal subsequences at distinct choices of positions; those repetitions are retained. Thus