[Haskell-beginners] Missing termination rule for recursive function

[Daniel Fischer]

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.