Interleave two lists
Mark Jones gave several talks at Advanced Functional Programming 2008. In one of them, he presented approaches to enumerating the elements of various datatypes. I found several interesting things in it, but one function stuck out as being perhaps useful in general. infixr 5 ||| (|||) :: [a] -> [a] -> [a] [] ||| ys = ys (x:xs) ||| ys = x : ys ||| xs It interleaves the elements of two lists. It's defined exactly as (++) with the exception that the arguments are swapped for the recursive application. This works nicely when one wants to merge infinite lists. For example, suppose you want a list of the enumerable numbers with a balance of positive and negative: enums :: (Num a, Enum a) => [a] enums = [0..] ||| map negate [1..] You can't use (++) here, because the left side never completes. Does (|||) seem useful to others? Is it already available in some other form (or in a library) of which I'm not aware? If yes and no are the answers, then I wonder if it's useful enough for Data.List (modulo any expected renaming). Sean
Sean Leather wrote:
Mark Jones gave several talks at Advanced Functional Programming 2008. In one of them, he presented approaches to enumerating the elements of various datatypes. I found several interesting things in it, but one function stuck out as being perhaps useful in general.
infixr 5 |||
(|||) :: [a] -> [a] -> [a] [] ||| ys = ys (x:xs) ||| ys = x : ys ||| xs
It interleaves the elements of two lists. It's defined exactly as (++) with the exception that the arguments are swapped for the recursive application. This works nicely when one wants to merge infinite lists. For example, suppose you want a list of the enumerable numbers with a balance of positive and negative:
enums :: (Num a, Enum a) => [a] enums = [0..] ||| map negate [1..]
You can't use (++) here, because the left side never completes.
Does (|||) seem useful to others? Is it already available in some other form (or in a library) of which I'm not aware? If yes and no are the answers, then I wonder if it's useful enough for Data.List (modulo any expected renaming).
It seems like it would be difficult to extend this definition (to interleave 3 or more lists) in a fair manner. You could probably do better using a revolving (Data.)sequence of lists. Just an idea.. Regards -- Adrian Hey
2008/8/24 Sean Leather
Does (|||) seem useful to others? Is it already available in some other form (or in a library) of which I'm not aware? If yes and no are the answers, then I wonder if it's useful enough for Data.List (modulo any expected renaming).
There's a generalized version of (|||) called "interleave" defined in
the paper "Backtracking, Interleaving, and Terminating Monad
Transformers"
http://www.cs.rutgers.edu/~ccshan/logicprog/LogicT-icfp2005.pdf
The logict package has an implementation
http://hackage.haskell.org/cgi-bin/hackage-scripts/package/logict
In short, logict provides a class MonadLogic whose members support
interleave, among other functions:
class (MonadPlus m) => MonadLogic m where
msplit :: m a -> m (Maybe (a, m a))
...
interleave :: m a -> m a -> m a
interleave a b = msplit a >>= maybe b (\(x,a') -> return x
`mplus` interleave b a')
instance MonadLogic [] where
msplit [] = [Nothing]
msplit (x:xs) = [Just (x,xs)]
The main disadvantage interleave and (|||) have, compared to mplus and
(++), is that they aren't associative.
--
Dave Menendez
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
I have seen this operator spelled (/\/) in a few places. Usually in the definition of a non-space-leaking powerset generating function. John -- John Meacham - ⑆repetae.net⑆john⑈
participants (5)
-
Adrian Hey -
apfelmus -
David Menendez -
John Meacham -
Sean Leather