select and selectSplit

[Cale Gibbard]

I know Bulat will be terribly disappointed by my suggestion to make an
addition to Data.List ;) but I mentioned the following couple of
functions on #haskell and got some positive response that they were
things other people ended up writing all the time as well, so I
decided I'd propose them here as additions to Data.List and see what
kind of reaction I got:

-- | The 'select' function takes a list and produces a list of pairs
-- consisting of an element of the list together with a list of the
-- remaining elements.
select :: [a] -> [(a,[a])]
select [] = []
select (x:xs) = (x,xs) : [(y,x:ys) | (y,ys) <- select xs]

-- | The 'selectSplit' function takes a list and produces a list of
-- triples consisting of a prefix of the list, the element after it,
-- and the remainder of the list.
selectSplit :: [a] -> [([a],a,[a])]
selectSplit [] = []
selectSplit (x:xs) = ([],x,xs) : [(x:lys,y,rys) | (lys,y,rys) <- selectSplit xs]

These tend to be very handy in the list monad. The names are off the
top of my head. Logan Capaldo also suggested 'pick' for the first,
which is a name that I've used as well. Faxathisia mentioned that it's
called 'select' in Prolog as well.

As a side note, the state transformer makes it relatively easy to pick
n elements using this:
pick n = runStateT . replicateM n . StateT $ select

(Showing that select is secretly an operation in a state transformed
list monad, where the state is a list of elements.)

If the order of the pairs in the MTL is fixed in the future in order
to better reflect the available instances of Functor/etc., at that
point we may want to consider flipping the pairs in the result of
select to match.

 - Cale