# How to understanding recursive inside comprehension lists? Classic List Threaded 10 messages Open this post in threaded view
|

## How to understanding recursive inside comprehension lists?

 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]) ].Output:1> lib_misc:perms("123").["123","132","213","231","312","321"]Please enlightenmentThank you _______________________________________________ erlang-questions mailing list [hidden email] http://erlang.org/mailman/listinfo/erlang-questions
Open this post in threaded view
|

## Re: How to understanding recursive inside comprehension lists?

 Hi Try expanding it by hand with shorter lists, i.e. perms("1") and perms("12") To start you off, and using [a, b, c], instead of "123" perms([a]) = [ [H|T] || H <- [a], T <- perms([a]--H) ] = [ [a | T] T <- perms([a]--[a])]  %% replace H, one item = [ [a | T] T <- perms([])] ] = [ [a | T] T <- [[]] ] %% replace T = [ [a | []] ] = [ [a] ] perms([a, b]) = [ [H|T] || H <- [a, b], T <- perms([a, b]--H) ] = [ [a|T] || T <- perms([b]),      [b|T] || T <- perms([a]) ] %% replace H, two items = [ [a|T] || T <- [[b]],      [b|T] || T <- [[a]] ] = ... I'll let you complete the rest yourself ;-) HTH Cheers, Fred On 23/08/2019 13:03, I Gusti Ngurah Oka Prinarjaya 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]) ]. > > Output: > 1> lib_misc:perms("123"). > n > > Please enlightenment > > Thank you > > > > > _______________________________________________ > erlang-questions mailing list > [hidden email] > http://erlang.org/mailman/listinfo/erlang-questions> _______________________________________________ erlang-questions mailing list [hidden email] http://erlang.org/mailman/listinfo/erlang-questions
Open this post in threaded view
|

## Re: How to understanding recursive inside comprehension lists?

 In reply to this post by I Gusti Ngurah Oka Prinarjaya How to create all permutations of List:   Construct all possible lists [H|T]     where H is one element of List     and T is one of all the permutations of the remaining elements in List. And the empty list has one permutation; the empty list. /Sverker On fre, 2019-08-23 at 19:03 +0700, I Gusti Ngurah Oka Prinarjaya 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]) ]. > > Output: > 1> lib_misc:perms("123"). > ["123","132","213","231","312","321"] > > Please enlightenment > > Thank you > > > > _______________________________________________ > erlang-questions mailing list > [hidden email] > https://protect2.fireeye.com/url?k=39e8964b-6562b484-39e8d6d0-0cc47ad93ea4-789> 7557dbe1f450b&q=1&u=http%3A%2F%2Ferlang.org%2Fmailman%2Flistinfo%2Ferlang- > questions _______________________________________________ erlang-questions mailing list [hidden email] http://erlang.org/mailman/listinfo/erlang-questions
Open this post in threaded view
|

## Re: How to understanding recursive inside comprehension lists?

 In reply to this post by I Gusti Ngurah Oka Prinarjaya On Fri, Aug 23, 2019 at 2:03 PM I Gusti Ngurah Oka Prinarjaya <[hidden email]> 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 [hidden email] http://erlang.org/mailman/listinfo/erlang-questions
Open this post in threaded view
|

## Re: How to understanding recursive inside comprehension lists?

 Since I needed a bit more space to write an answer 🙄 I replied on my blog 😉Cheers :) On 23 Aug 2019, at 10:47, Jesper Louis Andersen <[hidden email]> wrote:On Fri, Aug 23, 2019 at 2:03 PM I Gusti Ngurah Oka Prinarjaya <[hidden email]> 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[hidden email]http://erlang.org/mailman/listinfo/erlang-questions_______________________________________________ erlang-questions mailing list [hidden email] http://erlang.org/mailman/listinfo/erlang-questions
Open this post in threaded view
|

## Re: How to understanding recursive inside comprehension lists?

 In reply to this post by Jesper Louis Andersen-2 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 <[hidden email]> menulis:On Fri, Aug 23, 2019 at 2:03 PM I Gusti Ngurah Oka Prinarjaya <[hidden email]> 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 [hidden email] http://erlang.org/mailman/listinfo/erlang-questions
Open this post in threaded view
|

## Re: How to understanding recursive inside comprehension lists?

Open this post in threaded view
|

## Re: How to understanding recursive inside comprehension lists?

 In reply to this post by Brujo Benavides-3 Nice explanation, thank you! For me, it helps to think of mathematical induction: First trying to get a model of the base case(s) - occasionally more than only one exist. After that I (try to) think of the step case - how to evolve from base or any given case to the next (more complex) one. The brilliance of the example is to show multiple conditions - one for head, one (dependent) for tail - are given the probably elegantest possible way. Eckard Am Fri, 23 Aug 2019 11:09:42 -0300 schrieb Brujo Benavides <[hidden email]>: > Since I needed a bit more space to write an answer 🙄 I replied on my > blog > > 😉 Cheers :) > > Brujo Benavides > > > > > On 23 Aug 2019, at 10:47, Jesper Louis Andersen > > <[hidden email]> wrote: > > > > On Fri, Aug 23, 2019 at 2:03 PM I Gusti Ngurah Oka Prinarjaya > > <[hidden email] > 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 > > [hidden email] > > http://erlang.org/mailman/listinfo/erlang-questions> -- Wir haften nicht für die korrekte Funktion der in dieser eMail enthaltenen Viren. We are not liable for correct function of the viruses in this email! :) _______________________________________________ erlang-questions mailing list [hidden email] http://erlang.org/mailman/listinfo/erlang-questions attachment0 (201 bytes) Download Attachment