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

To agree with the example, preserve the first occurrence of each value. This first-occurrence duplicate removal is a right fold:

remalldups = foldr step []
  where step x ys = x : filter (/= x) ys

The folded tail has no repetitions by the induction hypothesis. The list filter removes any occurrence of the new head from that tail; prepending the head then gives exactly one occurrence of it, in its first input position. Other values retain their relative order. For the supplied example the intermediate folded results, from right to left, are [1], [3,1], [2,3,1], and [1,2,3]. ThusUnder lazy evaluation, constructing x : ... does not first demand the folded tail. That observation is essential for the infinite cases below. The alternative step that first asks whether x belongs to the folded tail would lose this property and would also keep last occurrences instead of matching the stated example.