Proposal: Add these two handy functions to Data.List

[Simon Marlow]

On 02/07/2010 00:48, Cale Gibbard wrote:
> When working with the list monad, I often find myself in need of one
> of the two following functions:
>
> -- | Produce a list of all ways of selecting an element from a list,
> each along with the remaining elements in the list.
> -- e.g. select [1,2,3,4] == [(1,[2,3,4]),(2,[1,3,4]),(3,[1,2,4]),(4,[1,2,3])]
> -- This is useful for selection without replacement in the list monad
> or list comprehensions.
> select :: [a] ->  [(a,[a])]
> select [] = []
> select (x:xs) = (x,xs) : [(y,x:ys) | (y,ys)<- select xs]

I'd start with something a bit more basic, that we don't have yet:

splits :: [a] -> [([a],[a])]
splits xs = zipWith splitAt [0..length xs] (repeat xs)

and then

select xs = [ (b,as++bs) | (as,b:bs) <- splits xs ]

(you probably wouldn't define them like this in practice, of course)

> -- | Produce a list of all ways of separating a list into an initial
> segment, a single element, and a final segment.
> -- e.g. separate [1,2,3,4] ==
> [([],1,[2,3,4]),([1],2,[3,4]),([1,2],3,[4]),([1,2,3],4,[])]
> separate :: [a] ->  [([a],a,[a])]
> separate [] = []
> separate (x:xs) = ([],x,xs) : [(x:us,v,vs) | (us,v,vs)<- separate xs]

separate xs = [ (as, b, bs) | (as, b:bs) <- splits xs ]


splits seems like a no-brainer to me.  I can imagine using select, but I 
don't think I've ever encountered a use for separate, and in any case 
it's very similar to splits while being less general.  In summary, MHO:

  +1 for splits
  +1 for select
  -1 for separate

Cheers,
	Simon