Missing termination rule for recursive function

Oscar Benjamin

5 Nov 2012 5 Nov '12

2:53 p.m.

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

Show replies by date

Daniel Fischer

5 Nov 5 Nov

4 p.m.

New subject: Missing termination rule for recursive function

On Montag, 5. November 2012, 19:53:52, Oscar Benjamin wrote:

...

Hi all,

I'm new to this list

Welcome, then.

...

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]] 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]] (as a consequence, it is a bit slower than an optimal implementation working only on finite lists could be).

...

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.

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

...

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

The type is still correct, the empty list can have elements of any type, [] :: [a] in particular, the elements can be lists, in which case the type is specialised to [] :: [[b]] So the compiler has no reason to complain. And at runtime, you're only `concatMap`ping over an empty list, resulting in an empty list, that's normal and nothing that could cause an exception.

...

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?

We had two cases above, the one without explicit base case remains

...

permutations xs = [ y:zs | (y,ys) <- selections xs, zs <- permutations ys ]

That leads to permutations [] = [ y:zs | (y,ys) <- selections [], zs <- permutations ys ] ~> [ y:zs | (y,ys) <- [], zs <- permutations ys ] and you're again `concatMap`ping over an empty list, resulting in an empty list. If you're starting with a non-empty finite list, the recursive call is to a list one element shorter etc. until finally permutations [] is called - and then you prepend an element ot each list in an empty list, resulting in an empty list...

...

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

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. Single-step through the evaluation of simple cases in the ghci debugger if necessary.

Oscar Benjamin

6:45 p.m.

New subject: Missing termination rule for recursive function

On 5 November 2012 21:00, Daniel Fischer wrote:

...

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

Daniel Fischer

6:53 p.m.

New subject: Missing termination rule for recursive function

On Tue, Nov 6, 2012 at 12:45 AM, Oscar Benjamin wrote:

...

On 5 November 2012 21:00, Daniel Fischer wrote

...

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

A permutation of a set is a bijection from the set to itself. There is one map from the empty set to itself, the empty map, that is a bijection. The number of permutations of a set of n elements is n!, and 0! = 1 should make you expect that there is one permutation of an empty set.

...

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

You can

ghci> :load *ModuleName to get it interpreted.

Jay Sulzberger

4:27 p.m.

On Mon, 5 Nov 2012, Oscar Benjamin 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@haskell.org http://www.haskell.org/mailman/listinfo/beginners

Oscar Benjamin

6:57 p.m.

New subject: Missing termination rule for recursive function

On 5 November 2012 21:27, Jay Sulzberger wrote:

...

On Mon, 5 Nov 2012, Oscar Benjamin wrote:

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

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

When you rephrase in set terminology like this it becomes easier to understand. I was thinking of it all in terms of loops before.

...

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.

That's exactly what confused me. It doesn't confuse me when it's laid out like this but in the list comprehension it did. Thanks for your help. Oscar

4579

Age (days ago)

4579

Last active (days ago)

List overview

Download

5 comments

3 participants

participants (3)

Daniel Fischer
Jay Sulzberger
Oscar Benjamin