Interleave two lists
apfelmus
apfelmus at quantentunnel.de
Thu Aug 28 03:49:45 EDT 2008
David Menendez wrote:
>
> The main disadvantage interleave and (|||) have, compared to mplus and
> (++), is that they aren't associative.
In fact, no interleaving operator (|||) that works for infinite lists can be
associative. Here's proof.
Every such operator corresponds to a pair of injective functions
f,g : N -> N N = natural numbers
who map the indexes of the elements of the left (f) and right (g) list to
indexes in the result. Their images are disjoint and complement each other, i.e.
ø = f(N) /\ g(N) and N = f(N) \/ g(N)
For example,
(x:xs) ||| ys = x : ys ||| xs
corresponds to the pair
(\n->2*n, \n->2*n+1)
because the left list xs is mapped to the even positions and the right list
ys is mapped to the uneven positions.
Now, consider interleaving three lists. The case
as ||| (bs ||| cs)
maps the elements of as , bs and cs as follows into the result:
as f
bs g . f
cs g . g
In the other case
(as ||| bs) ||| cs
the positions of the elements in the result lists are determined by applying the
functions
as f . f
bs f . g
cs g
Hence, if (|||) were associative, we would have
f = f . f
f . g = g . f
g . g = g
and hence
as f
bs f . g
cs g
But f and g already fill the entire result, there would be no room for the
bs in the result list, a contradiction.
Thus, no (|||) that merges infinite lists and is associative exists.
Regards,
apfelmus
More information about the Libraries
mailing list