[erlang-questions] Joe

Danil Zagoskin <>
Tue Mar 5 19:57:57 CET 2013


maybe this (almost equivalent) code will give output with more clear apply
order. I tried to draw how perms() calls itself. Hope it helps to
understand:
perms(L) ->
  perms("", L).

perms(_Prefix, []) -> [[]];
perms(Prefix, L) ->
  ListOfPermLists = [perms(Prefix, L, H, L -- [H]) || H <- L],
  lists:merge(ListOfPermLists).

perms(Prefix, L, H, Others) ->
  io:format("~s-L = ~p, [H] = ~p, Others = ~p~n", [Prefix, L, [H], Others]),
  OthersPerms = perms(" |" ++ Prefix, Others),
  Emit = [ [H|T] || T <- OthersPerms],
  Emitted = [io_lib:format("~p ", [E]) || E <- Emit],
  io:format("~s L = ~p, [H] = ~p, T <- ~p >>> emit ~s~n", [Prefix, L, [H],
OthersPerms, Emitted]),
  Emit.



2013/3/4 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}]]****
>
> _______________________________________________
> erlang-questions mailing list
> 
> http://erlang.org/mailman/listinfo/erlang-questions
>
>


-- 
---------------------------------------------
Данил Загоскин | +7 906 064 20 47 | 
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://erlang.org/pipermail/erlang-questions/attachments/20130305/9094ebd0/attachment.html>


More information about the erlang-questions mailing list