On Montag, 5. November 2012, 19:53:52, Oscar Benjamin wrote:
Hi all,
I'm new to this list
Welcome, then.
The Python program used itertools.permutations which is an iterator that yields all permutations of a sequence. Does Haskell have a similar function in it's standard library?
There's permutations in Data.List Prelude Data.List> permutations [1,2,3] [[1,2,3],[2,1,3],[3,2,1],[2,3,1],[3,1,2],[1,3,2]] which even works on infinite lists: Prelude Data.List> map (take 5) . take 5 $ permutations [1 .. ] [[1,2,3,4,5],[2,1,3,4,5],[3,2,1,4,5],[2,3,1,4,5],[3,1,2,4,5]] (as a consequence, it is a bit slower than an optimal implementation working only on finite lists could be).
I found a suggestion [1] for implementing a permutations function:
-- Select each item and remainder from a sequence selections :: [a] -> [(a, [a])] selections [] = [] selections (x:xs) = (x,xs) : [ (y,x:ys) | (y,ys) <- selections xs ]
-- Permutations of a sequence permutations :: [a] -> [[a]] permutations xs = [ y:zs | (y,ys) <- selections xs, zs <- permutations ys ]
After a while I established that this permutations function seemed to be returning an empty list. Looking at it I thought that it might be missing a termination condition so I added
permutations [] = []
but the result was unchanged.
permutations [x] = [ y:zs | (y,ys) <- selections [x], zs <- permutations ys] ~> [ y:zs | (y,ys) <- [(x,[])], zs <- permutations ys] ~> [ x:zs | zs <- permutations []] ~> [] since permutations [] = []
When I changed it to
permutations [] = [[]]
That changes the last steps above to ~> [ x:zs | zs <- permutations []] ~> [ x:zs | zs <- [[]] ] ~> [ x:[] ] ~> [ [x] ] and the former is not even correct, because there is exactly one permutation of an empty list.
I got the desired result. I can understand why this termination condition is needed to make the function recurse properly.
What's confusing me though is why neither of the first two raised any kind of error at compile- or run-time.
The type is still correct, the empty list can have elements of any type, [] :: [a] in particular, the elements can be lists, in which case the type is specialised to [] :: [[b]] So the compiler has no reason to complain. And at runtime, you're only `concatMap`ping over an empty list, resulting in an empty list, that's normal and nothing that could cause an exception.
I would understand if an infinite loop had occurred (a common result for non-terminating recursion) but as far as I can tell it just returned an empty list. Can anyone explain to me how the function terminates in the three different cases?
We had two cases above, the one without explicit base case remains
permutations xs = [ y:zs | (y,ys) <- selections xs, zs <- permutations ys ]
That leads to permutations [] = [ y:zs | (y,ys) <- selections [], zs <- permutations ys ] ~> [ y:zs | (y,ys) <- [], zs <- permutations ys ] and you're again `concatMap`ping over an empty list, resulting in an empty list. If you're starting with a non-empty finite list, the recursive call is to a list one element shorter etc. until finally permutations [] is called - and then you prepend an element ot each list in an empty list, resulting in an empty list...
Also what is a good way of debugging this kind of problem? I found it quite difficult to establish that permutations was returning an empty list (in context there were other functions that could have been failing).
Trace the execution of very simple cases (empty lists, singleton lists, lists with two elements) by hand with pencil and paper. That's the most instructive and fruitful way. Check the results of simple cases against what you know the result ought to be. Single-step through the evaluation of simple cases in the ghci debugger if necessary.