Solution

ID: past-exam-of-the-year-1-of-the-computer-science-course-of-the-university-of-oxford/2013/functional-programming-design-and-analysis-of-algorithms/2/d/solution

Set both and equal to list concatenation, with . Associativity gives xs ++ (ys ++ zs) = (xs ++ ys) ++ zs, which is equation (1). The two identity laws give xs ++ [] = [] ++ xs, which is equation (2). Part (b) therefore yields
concat :: [[a]] -> [a]
concat = foldl (++) []
Thus on finite lists. The argument order is unchanged: the accumulator is the already concatenated prefix, and the next inner list is appended to its right. This preserves the order but repeatedly copies that prefix.

New to topics? Read the docs here!