On 5 November 2012 21:00, Daniel Fischer
On Montag, 5. November 2012, 19:53:52, Oscar Benjamin wrote:
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]]
I thought as much.
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]]
I'm not sure if I'm ready to understand that one yet...
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 [] = []
Ok, I see how that works. So you carefully follow through with how the comprehension behaves for a concrete simple case until you can see exactly what you end up with. I guess I know how to do that for procedural languages but haven't really got my head around how to follow the execution in Haskell yet.
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'm trying to convince myself that this is logically necessary but it still seems consistent in my mind that the set of permutations of an empty list is empty. I guess maybe if you posit that a sequence should always be contained by the set of its permutations then you reach this conclusion.
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.
I see what you mean now.
Single-step through the evaluation of simple cases in the ghci debugger if necessary.
I need to work out how to use this. I've just found why I was unable to use it before: it only works if the file is interpreted. The quick fix was to delete all files created by the compiler. Is there a way that I can tell ghci to just ignore those files and load my program as interpreted for debugging? Thanks again, Oscar