The
unionAll computes the union of a (potentially) infinite
number of lists, under the assumption that the heads of the inner
lists are sorted. The result will duplicate an element as many times
as the maximum number of occurrences in any single list. Thus, the
result is a set if and only if every inner list is a set.
The
unionAll function is closely related to
foldr
union []. The former does not assume that the outer list
is finite, whereas the latter does not assume that the heads of the
inner lists are sorted. When both sets of assumptions are met, these
two functions are equivalent.
Note that there is no simple way to express
unionAll in terms
of
mergeAll or vice versa on arbitrary valid inputs. They are
related via
nub however, as
nub . mergeAll ==
unionAll . map nub. If every list is a set,
then
map nub == id, and in this special case (and only in
this special case) does
nub . mergeAll == unionAll.
This implementation of
unionAll uses a tree of comparisons, and
is based on input from Dave Bayer, Heinrich Apfelmus, Omar Antolin
Camarena, and Will Ness. See
CHANGES for details.