Duplicate removal

Replacing a list by a list containing each of its distinct elements once. Retaining first occurrences gives a stable order. A recursive implementation emits the head and removes all its occurrences from the tail before continuing. On an infinite input with only finitely many distinct values, detecting that there are no further new values may diverge; on an infinite input with infinitely many distinct values and terminating equality tests, each successive new value has a finite position and can be emitted.

Retain the first occurrence of each distinct value in a list. The right fold foldr (\x ys -> x : filter (/= x) ys) [] preserves this order under lazy evaluation. With terminating equality tests, an infinite input containing infinitely many distinct values produces every finite output prefix. If only finitely many distinct values occur, those values appear but the remaining infinite input cannot generally be certified empty: the result has an undefined tail rather than a terminating empty list.