[erlang-questions] How to understanding recursive inside comprehension lists?
I Gusti Ngurah Oka Prinarjaya
okaprinarjaya@REDACTED
Fri Aug 23 16:15:56 CEST 2019
Hi Folks,
Wowwwwww... thank you very much for your attention guys.
Thank you very much for all of your answers, then now is my turn to make
practice based on all of the answers.
Thank you all. I hope i can grok how this code works
Pada tanggal Jum, 23 Agt 2019 20.47, Jesper Louis Andersen <
jesper.louis.andersen@REDACTED> menulis:
> On Fri, Aug 23, 2019 at 2:03 PM I Gusti Ngurah Oka Prinarjaya <
> 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 :)
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://erlang.org/pipermail/erlang-questions/attachments/20190823/9f25bfe3/attachment.htm>
More information about the erlang-questions
mailing list