[Haskell-beginners] Missing termination rule for recursive function

[Jay Sulzberger]

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

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 at haskell.org
> http://www.haskell.org/mailman/listinfo/beginners
>
>