[erlang-questions] List Comprehensions permutation

[Richard O'Keefe]

On 3 Apr 2009, at 8:34 am, contact@REDACTED wrote:

> Hi all,
>
> I recently bought the book "Programming Erlang" by Joe Armstrong and I
> have a little problem of comprehension about the logical of an
> algorithm.
>
> Here is the sample from the book :
>
> perms([]) -> [[]];
> perms(L) ->
> 	[[H|T] || H <- L, T <- perms(L--[H])].
>
> I would like to know why we return [[]] and not [] ?

Because it simply isn't true that there are no
permutations of the empty list.  perms(L) returns a list
of all the permutations of L.  There is ONE permutation
of the empty list, namely [].  So perms([]) returns a
list containing that one permutation, [[]].

> I have try some tests :
>
> 6> [[H|T] || H <- [1], T <- []].
> []
> 7> [[H|T] || H <- [1], T <- [[]]].
> [[1]]
>
> For me it's not logical,

> in my brain its should be something like :
>
> 8> [1|[]].
> [1]

[1|[]] is indeed [1].  But perms([1]) is supposed to
return a LIST OF PERMUTATIONS, not a single permutation.
So perms([1]) should return [[1]], just as
perms([1,2]) should return [[1,2],[2,1]] or something
like that.