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