[erlang-questions] How to understanding recursive inside comprehension lists?
I Gusti Ngurah Oka Prinarjaya
okaprinarjaya@REDACTED
Fri Aug 23 16:35:38 CEST 2019
Thank you @Brujo Benavides, i will read your blog.
Pada tanggal Jum, 23 Agu 2019 pukul 21.15 I Gusti Ngurah Oka Prinarjaya <
okaprinarjaya@REDACTED> menulis:
> 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/5fbbc29a/attachment.htm>
More information about the erlang-questions
mailing list