[Haskell-beginners] Missing termination rule for recursive function

[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?

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

[1] http://www.haskell.org/pipermail/haskell-cafe/2002-June/003122.html