picks :: [a] -> [(a, [a])]
picks [] = []
picks (x:xs) = (x,xs) : [(y,x:ys)| (y,ys) <- picks xs]
picks [1..4] = [(1,[2,3,4]),(2,[1,3,4]),(3,[1,2,4]),(4,[1,2,3])]
This Haskell function works like a charm, but why? The first two tuples in the list are obvious enough, but how is the rest build up, just cracks my brain.
What does picks do? It returns all possible ways to choose one element from the list, in the form of a tuple (choice, rest), where choice is the item you chose and rest is the elements you did not choose. Note that [choice] ++ rest always contains the same elements as the original list, though not necessarily in the same order.
So how does picks work? When the argument is empty, it's simple: there are no ways to choose one element, so we return the empty list.
picks [] = []
When the argument is not empty, we can do one of two things. Either x is the first element of the tuple, or it is part of the second element. The easy thing to do is pick the first element; we unpack the list with (x:xs) and produce (x, xs).
picks (x:xs) = (x, xs) : ?
The other thing we can do is not pick x, but instead pick an element from xs. How do choose an element from xs? We use picks! This time, picks returns a list of tuples of where x is neither the first element nor a member of the second element. We just combine (x, xs) with this list.
-- x != y, x `elem` ys == False
picks (x:xs) = (x, xs) : [ (y, ?) | (y, ys) <- picks xs]
But x does need to be an member of the second element, because it's not the first element. So we have to put it back. The easiest place to put it is at the beginning of ys in each case:
picks (x:xs) = (x, xs) : [ (y, x:ys) | (y, ys) <- picks xs]
In many cases it helps to expand an expression manually:
picks [1..4] = (1, [2..4]) : [(y, 1:ys) | (y, ys) <- picks [2..4]]
-- continuing with picks [2..4]
picks [2..4] = (2, [3..4]) : [(y, 2:ys) | (y, ys) <- picks [3..4]]
-- continuing with picks [3..4]
picks [3, 4] = (3, [4]) : [(y, 3:ys) | (y, ys) <- picks [4]]
-- continuing with picks [4]
picks [4] = (4, []) : [(y, 4:ys) | (y, ys) <- picks []]
= (4, []) : [(y, 4:ys) | (y, ys) <- []]
= (4, []) : []
= [(4, [])]
picks [3, 4] = (3, [4]) : [(y, 3:ys) | (y, ys) <- [(4, [])]]
= (3, [4]) : [(4, 3:[])]
= (3, [4]) : [(4, [3])]
= [(3, [4]), (4, [3])]
-- and so one
The recursive case will return a list where the first item (x, xs) return a 2-tuple with as first item (the item we have picked) x, and with as remaining items the picks we make on the tail of the list and prepend all these items with x.
If we run this on a singleton list, for example [1], we thus get as options:
picks [1] = (1, []) : [(y, 1: ys) | (y,ys) <- picks []]since picks [] is equivalent to [], this thus means that we retrieve:
picks [1] = (1, []) : [(y, 1: ys) | (y,ys) <- []]hence the list comprehension will generate an empty list, and thus the result of picks [1] is:
picks [1] = [(1, [])]
If we now work with lists with two elements, the recursive call will return a list with one element: the only element of the tail and an empty list.
This thus means that if we run picks on picks [1,2], we thus get:
picks [1, 2] = (1, [2]) : [(y, 1:ys) | (y,ys) <- picks [2]]and since picks [2] returns [(2, [])], we thus will prepend the empty list in the (2, []) tuple with one, and we thus obtain:
picks [1, 2] = (1, [2]) : [(y, 1:ys) | (y,ys) <- [(2, [])]]
= (1, [2]) : [(2, [1])]
= [(1, [2]), (2, [1])]The x:ys part in the list comprehension will prepend the head of the list, so 1 to the lists returned by picks [2]. Since is not picked by the recursive call (we call picks recursively on the tail of the item), we thus need to insert it somewhere in the list, and the most easiest way is to prepend it.
If we thus work with three items, we will retrieve the data as:
picks [1, 2, 3] = (1, [2, 3]) : [(y, 1:ys) | (y,ys) <- picks [2, 3]]
= (1, [2]) : [(y, 1:ys) | (y,ys) <- [(2, [3]), (3, [2])]]
= (1, [2]) : [(2, [1, 3]), (3, [1, 2])]
= [(1, [2]), (2, [1, 3]), (3, [1, 2])]and so for lists with more than three items, the recursion each time will prepend the item that is definitely not picked by the recursive tail of picks xs, and prepend the lists of non-picked items with x.
This is a case where the formulation of the algorithm using higher order functions actually looks clearer than with a list comprehensions--based one:
picks [] = []
picks (x:xs) = -- (x,xs) : [(y, x:ys) | (y,ys) <- picks xs]
(x,xs) : map (second (x:)) (picks xs)
In case you don't understand what second (x:) is, you can read it as a pseudocode: it applies (x:) to the second part of a pair, so that second (x:) (a,b) = (a, x:b). And map does so for every element in its argument list (the map's second argument).
Thus we have, building our understanding from the ground up, stating with one-element lists, then two elements, three, and so on, to see the pattern:
picks ([1]) = picks (1:[]) =
-- picks (x:xs) --
= (x,xs) : map (second (x:)) (picks xs)
= (1,[]) : map (second (1:)) (picks [])
= (1,[]) : map (second (1:)) []
= (1,[]) : []
= [(1,[])]
picks [2,1] = picks (2:[1]) =
= (2,[1]) : map (second (2:)) (picks [1])
= (2,[1]) : map (second (2:)) [(1, [])]
= (2,[1]) : [(1,[2])]
= [(2,[1]) , (1,[2])]
picks [3,2,1] =
= (3,[2,1]) : map (second (3:)) (picks [2,1])
= (3,[2,1]) : map (second (3:)) [(2, [1]) , (1, [2])]
= [(3,[2,1]) , (2,[3,1]) , (1,[3,2])]
picks [4,3,2,1] =
= (4,[3,2,1]) : map (second (4:)) [(3,[2,1]) , (2,[3,1]) , (1,[3,2])]
= [(4,[3,2,1]) , (3,[4,2,1]) , (2,[4,3,1]) , (1,[4,3,2])]
picks [5,4,3,2,1] =
= [([5,[4,3,2,1]), (4,[5,3,2,1]), (3,[5,4,2,1]), (2,[5,4,3,1]), (1,[5,4,3,2])]
....
Putting them together to better see the pattern, the results are:
picks [ ] = [ ]
picks [ 1] = [ (1,[ ])]
picks [ 2,1] = [ (2,[ 1]) , (1,[ 2])]
picks [ 3,2,1] = [ (3,[ 2,1]) , (2,[ 3,1]) , (1,[ 3,2])]
picks [ 4,3,2,1] = [ (4,[ 3,2,1]) , (3,[ 4,2,1]) , (2,[ 4,3,1]) , (1,[ 4,3,2])]
picks [5,4,3,2,1] =
= [([5,[4,3,2,1]) , (4,[5,3,2,1]) , (3,[5,4,2,1]) , (2,[5,4,3,1]) , (1,[5,4,3,2])]
....
And so picks produces all the ways to pick an element, pairing it up with the remaining elements in the list after the element is removed from it.
It evidently does so for the length 0 (empty) list case, [], and the length 1 (singleton) case [] and the length 2 case [2,1] as seen above; and if it does so for a list of length n, then for the n+1 we know that it's right as well since it starts with the first pick, and then the map adds the first element into each of the remainders in the result produced for the n case. Which is correct.
Yes, you can read this as both "the n case is correct" and "hence, n+1 is correct". Thus (and given the correctness of the 0 case) by the induction principle the results are correct for any n. That is to say, for all of them. Yes there are infinitely many of them but each n in itself is finite.
If the starting point is right, and each step is right, then the whole journey must be right as well. We don't need to understand how exactly it does what it does for an n case, unrolling all the layers of recursion. That's hard. Instead, we prove the inductive step is right, the base case is right, and that's that.
The three most important rules in trying to understand how does a recursive function exactly do what it does, are:
Of course this version of picks is not too good. It is quadratic, and it destroys information.
We can address both flaws at once with
-- unfoldr :: (b -> Maybe (a, b)) -> b -> [a]
picks3 :: [a] -> [([a], a, [a])]
picks3 xs = unfoldr (\case { (_,[]) -> Nothing ;
(a,x:xs) -> Just ((a,x,xs), (x:a,xs)) })
([],xs)
So that
> picks3 [1..4]
[([],1,[2,3,4]),([1],2,[3,4]),([2,1],3,[4]),([3,2,1],4,[])]
Now this is linear, and it is easy to produce the output of picks from it, if we so choose and are willing to pay the price.
Without brain - cracking, simple to explain (but Eq a =>), has approximately 1.7 slower execution time trade off
mypicks :: Eq a => [a] -> [(a,[a])]
mypicks [] = []
mypicks lst = [ zsplit x lst | x <- lst]
zsplit :: Eq a => a -> [a] -> (a,[a])
zsplit z lst = esplit z lst []
where
esplit :: Eq a => a -> [a] -> [a] -> (a, [a])
esplit e [] lr = (e, lr)
esplit e (x:xs) lr
| e == x = (e, reverse lr ++ xs)
| otherwise = esplit e xs (x:lr)
--- using
perms2 [] = [[]]
perms2 xs = [x:zs | (x,ys) <- picks xs, zs <- perms2 ys]
perms2' [] = [[]]
perms2' xs = [x:zs | (x,ys) <- mypicks xs, zs <- perms2' ys]
--- and
T.measureTime $ length $ perms2 [1..9]
T.measureTime $ length $ perms2' [1..9]
--- delivers:
e: 362880
Computation time: 0.075562000 sec.
e: 362880
Computation time: 0.125598000 sec.
