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 / a

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