[Haskell-beginners] Missing termination rule for recursive function

Jay Sulzberger jays at panix.com
Mon Nov 5 22:27:47 CET 2012

On Mon, 5 Nov 2012, Oscar Benjamin <oscar.j.benjamin at gmail.com> wrote:

> 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 [] = []


   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


   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


must really be


but it is not.  [] is an object in the Haskell world, and a
subexpression zs appears in the expression on the right hand side

   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

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 "|".


> [1] http://www.haskell.org/pipermail/haskell-cafe/2002-June/003122.html
> _______________________________________________
> Beginners mailing list
> Beginners at haskell.org
> http://www.haskell.org/mailman/listinfo/beginners

More information about the Beginners mailing list