Interleave two lists

[apfelmus]

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