[Haskell-beginners] Missing termination rule for recursive function
Daniel Fischer
daniel.is.fischer at googlemail.com
Mon Nov 5 22:00:22 CET 2012
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.
More information about the Beginners
mailing list