[Haskell-beginners] Missing termination rule for recursive function

[Oscar Benjamin]

On 5 November 2012 21:00, Daniel Fischer
<daniel.is.fischer at googlemail.com> 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