On Mon, 5 Nov 2012, Oscar Benjamin
Hi all,
I'm new to this list and I'm in the very early stages of learning Haskell but I am confident with Python and some other languages. Seeing the connection between Haskell's lists and Python's generators I tried to reimplement a generator-based Python program in Haskell. I now have it working but I was hoping that someone could help me resolve a few queries.
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?
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. When I changed it to
permutations [] = [[]]
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. 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?
Let us assume we are in case 0: We have neither permutations [] = [] nor permutations [] = [[]] in our code. Then let us calculate permutations ["a"] Assuming selections is correct, we have permutations ["a"] ~> the list of all lists of form "a":(something that lies in permutations []) So what is the value of permutations []? It is the list of all things of form y:zs such that (y,ys) lies in selections xs and zs lies in permutations ys where xs = []. But there are no such things. And so the list of sll such things is the empty list []. What is perhaps confusing is that, at this juncture, one tends to think that y:zs must really be y:[] but it is not. [] is an object in the Haskell world, and a subexpression zs appears in the expression on the right hand side of permutations xs = [ y:zs | (y,ys) <- selections xs, zs <- permutations ys ] but there is no object in the Haskell world which can be the value of zs because there is no object which can be the value of (y, ys), because the line selections [] = [] appears in the definition of selections: (y, ys) would have to be an element, that is an object lying in, selections [], but selections [] = [].
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).
Thanks in advance, Oscar
I am not sure. I think many people just slowly "by hand" run their own interpreter in their head. ad types: I conjecture that Haskell's type checker, by design, when run on this code, treats the expressions [] and [["a"]] as both being of type [[a]]. If my conjecture is correct, then case 0 code would pass the type checker. ad termination: the "list comprehension" operator returns, correctly according to the conventions of the twentieth century, the null list when there are no objects which satisfy the conditions written to the right of the "|". oo--JS.
[1] http://www.haskell.org/pipermail/haskell-cafe/2002-June/003122.html
_______________________________________________ Beginners mailing list Beginners@haskell.org http://www.haskell.org/mailman/listinfo/beginners