Proposal: Add these two handy functions to Data.List

[Cale Gibbard]

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]

-- | 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]

It would be really nice if they were in Data.List. The first I find
occurring in my code moreso than the second, though just a moment ago,
the second of these was quite useful to a beginner on #haskell, and it
has come up quite a number of times before for me.

Twan van Laarhoven suggested that the following generalisation of
select might also be useful:

select' :: [t] -> [(t, ([t] -> [t]) -> [t])]
select' [] = []
select' (x:xs) = (x,\f -> f xs) : [(y,\f -> x:ys f) | (y,ys) <- select' xs]

This satisfies the equation

select = map (second ($ id)) . select'

and allows for simple replacement after modification of the selected
element, for instance:

[xs (toUpper x :) | (x,xs) <- select' "abcd"] == ["Abcd","aBcd","abCd","abcD"]

but we're unsure if this might be too subtle to be as useful on a regular basis.

 - Cale Gibbard