[erlang-questions] Joe

[Ivan Carmenates García]

Hi all, I’m reading the Making Reliable Distributed Systems in the Presence
of Software Errors by Joe Armstrong Thesis of 2003 and I found this little
algorithm using list of compression and there is no way I can understand how
internally it work.

 

perms([]) -> [[]];

perms(L) -> [[H|T] || H <- L, T <- perms(L--[H])].

 

I did figure out that the recursion does first I mean the call to the
function T <- perms(L--[H]) but step by step I can not follow.

First, the function is called using [1,2,3] list so 

[[1|T] || H <- L, T <- perms([1,2,3]--[1] = [2,3])]

[[1|[2|T]] || H <- L, T <- perms([2,3]--[2] = [3])]

[[1|[2|[3|T]]] || H <- L, T <- perms([3]--[3] = [])]

[[1|[2|[3|[]]]] || H <- L, T <- [])]

 

And now what! What’s the next step?

 

I changed the code in order to print the steps so I can understand but even
with that the debug is so confuse. Because the order changes, maybe because
of the recursive thing.

But I don’t understand why in the head the value 1 is repeated to yield the
next value [[1,2,3), [1,3,2], 
]

 

perms([]) -> [[]];

perms(L) ->

      io:format("L = ~p~n", [L]),

      [[{H,io:format("H = ~p - ", [H])}| {T, io:format("T = ~p~n", [T])}] ||
H <- L, T <- perms(L--[H])].

 

This is the exit

 

74> test:perms([1,2,3]).

L = [1,2,3]

L = [2,3]

L = [3]

H = 3 - T = []

H = 2 - T = [{3,ok}|{[],ok}]

L = [2]

H = 2 - T = []

H = 3 - T = [{2,ok}|{[],ok}]

H = 1 - T = [{2,ok}|{[{3,ok}|{[],ok}],ok}]

H = 1 - T = [{3,ok}|{[{2,ok}|{[],ok}],ok}]

L = [1,3]

L = [3]

H = 3 - T = []

H = 1 - T = [{3,ok}|{[],ok}]

L = [1]

H = 1 - T = []

H = 3 - T = [{1,ok}|{[],ok}]

H = 2 - T = [{1,ok}|{[{3,ok}|{[],ok}],ok}]

H = 2 - T = [{3,ok}|{[{1,ok}|{[],ok}],ok}]

L = [1,2]

L = [2]

H = 2 - T = []

H = 1 - T = [{2,ok}|{[],ok}]

L = [1]

H = 1 - T = []

H = 2 - T = [{1,ok}|{[],ok}]

H = 3 - T = [{1,ok}|{[{2,ok}|{[],ok}],ok}]

H = 3 - T = [{2,ok}|{[{1,ok}|{[],ok}],ok}]

[[{1,ok}|{[{2,ok}|{[{3,ok}|{[],ok}],ok}],ok}],

[{1,ok}|{[{3,ok}|{[{2,ok}|{[],ok}],ok}],ok}],

[{2,ok}|{[{1,ok}|{[{3,ok}|{[],ok}],ok}],ok}],

[{2,ok}|{[{3,ok}|{[{1,ok}|{[],ok}],ok}],ok}],

[{3,ok}|{[{1,ok}|{[{2,ok}|{[],ok}],ok}],ok}],

[{3,ok}|{[{2,ok}|{[{1,ok}|{[],ok}],ok}],ok}]]

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://erlang.org/pipermail/erlang-questions/attachments/20130304/971a1a02/attachment.htm>