[erlang-questions] How to understanding recursive inside comprehension lists?
Brujo Benavides
elbrujohalcon@REDACTED
Fri Aug 23 16:09:42 CEST 2019
Since I needed a bit more space to write an answer �� I replied on my blog <https://medium.com/erlang-battleground/how-to-comprehend-comprehensions-c924f92a97e1?sk=b668da926f05b7293f34dafa48fa5654> ��
Cheers :)
Brujo Benavides <http://about.me/elbrujohalcon>
> On 23 Aug 2019, at 10:47, Jesper Louis Andersen <jesper.louis.andersen@REDACTED> wrote:
>
> On Fri, Aug 23, 2019 at 2:03 PM I Gusti Ngurah Oka Prinarjaya <okaprinarjaya@REDACTED <mailto:okaprinarjaya@REDACTED>> wrote:
> Hi,
>
> Now I read Joe's book titled Programming Erlang 2nd Edition. I practice some functions such as for/3, quicksort/1, pythag/1, and perms/1, and perms/1 is the function that hard to understand.
>
> I understand comprehension lists, I fully understand for/3, I fully understand quicksort/1, pythag/1. But it's really hard for me to understand perms/1. Please teach me how to read and understand this perms/1 function.
>
> perms([]) -> [[]];
> perms(List) -> [ [H|T] || H <- List, T <- perms(List--[H]) ].
>
>
> Note you have two generators in the comprehension. So for each generated H, it generates all the possible T's. Also note that the T's depend on the H. It is akin to having a for-loop within a for-loop:
>
> for H := range(List) {
> for T := perms(List -- [H]) {
> Res := append(Res, [H|T])
> }
> }
>
> Now, to understand why this works, the argument is based on an induction principle:
>
> Observe that to generate a permutation, you first select something which goes first, H, and then you need to generate a permutation out of the remaining elements, List -- [H]. Suppose we fix H to some value in the list. Then surely, we can generate all the permutations where H goes first, by generating perms(List - [H]) and then attaching H to all the results:
>
> perms(List) ->
> H = pick_among(List),
> [ [H|T] || T <- perms(List -- [H]) ].
>
> But now note that to generate all permutations, any element could have been picked by pick_among/1. So we need to loop over all elements in the list one at a time, and consider what happens if that element goes first. This is what the original code is doing.
>
> Alternative wordings by Sverker and Fred :)
>
> _______________________________________________
> erlang-questions mailing list
> erlang-questions@REDACTED
> http://erlang.org/mailman/listinfo/erlang-questions
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://erlang.org/pipermail/erlang-questions/attachments/20190823/50fc6cb2/attachment.htm>
More information about the erlang-questions
mailing list