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