[erlang-questions] How to understanding recursive inside comprehension lists?
Eckard Brauer
eckard.brauer@REDACTED
Fri Aug 23 16:38:47 CEST 2019
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 <elbrujohalcon@REDACTED>:
> 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
>
--
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! :)
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 195 bytes
Desc: Digitale Signatur von OpenPGP
URL: <http://erlang.org/pipermail/erlang-questions/attachments/20190823/b2607cc6/attachment.bin>
More information about the erlang-questions
mailing list