Functional - Question regarding Erlang's list comprehensions.

Author

Question regarding Erlang's list comprehensions.

vfoley

2007-03-24, 10:06 pm

Hello,

I started learning Erlang recently with the help of the (Beta) book
written by Joe Armstrong, "Programming Erlang: Software for a
Concurrent
World", and I have a question regarding list comprehensions.

In "Structure and Interpretation of Computer Programs", Abelson and
Sussman give a way to reason about programs (with no state), they
explain a substitution model. I used this model to understand how
qsort() (page 50 in the current Beta book) works:

qsort([]) -> [];
qsort([Pivot|T]) -> qsort([X || X <- T, X =< Pivot])
++ [Pivot] ++
qsort([X || X <- T, X > Pivot]).

qsort([3, 1, 2, 4])
qsort([1, 2]) ++ [3] ++ qsort([4])
qsort([]) ++ [1] ++ qsort([2]) ++ [3] ++ qsort([]) ++ [4] ++ qsort([])
[] ++ [1] ++ qsort([]) ++ [2] ++ qsort([]) ++ [3] ++ [] ++ [4] ++ []
[] ++ [1] ++ [] ++ [2] ++ [] ++ [3] ++ [] ++ [4] ++ []
[1, 2, 3, 4]

I am now trying to apply the same technique to the permutation
function,
especially since no explanation is given. However, I am not sure how
to
apply the substitution model to that function, could anyone help me
out?
Here's the definition given:

perm([]) -> [[]];
perm(L) -> [[H|T] || H <- L, T <- perm(L -- [H])].

perm([a, b, c]).

If anyone could explain to me how to develop this function as I did
qsort(), I would very much appreciate. The section is also a bit
unclear on the details when multiple qualifiers are given in a list
comprehensions. Are the H and T variables assigned "in parallel"[1]
or
as in two for loops[2]?

[1]
for (H = 0, T = 0; ...; H++, T++) {
...;
}

[2]
for (H = 0; ...; H++) {
for (T = 0; ...; T++) {
...;
}
}

Regards,

Vincent.

almostbored@gmail.com

2007-03-25, 4:04 am

i am just learning erlang too, but this is how i reasoned that
example:

assignments are done like nested for loops. for example,

[ {A, B} || A <- [1,2], B <- [1,2] ].

evaluates to:

[{1,1}, {1,2}, {2,1}, {2,2}].

for a single member list, perms expands as follows:

perms([a]) ->
[ [H|T] || H <- a, T <- perms([a] -- [a]) ].
[ [H|T] || H <- a, T <- [] ].
[ [ a | [] ] ].
[ a ].

the perms list comprehension expands to:

[
[ [H|T] || H <- a, T <- perms([a,b,c] -- [a]) ] ++
[ [H|T] || H <- b, T <- perms([a,b,c] -- [b]) ] ++
[ [H|T] || H <- c, T <- perms([a,b,c] -- [c]) ]
].

[ [H|T] || H <- a, T <- perms([a,b,c] -- [a]) ].

evaluates similar to the tuple example:

[ [H|T] || H <- a, T <- perms([b,c]) ].

perms([b,c]) ->
[
[ [H|T] || H <- b, T <- perms([c]) ] ,
[ [H|T] || H <- c, T <- perms([b]) ]
].

[
[ [H|T] || H <- b, T <- c ] ,
[ [H|T] || H <- c, T <- b ]
].

[
[ [b|c] ] ,
[ [c|b] ]
].

[
[b,c] ,
[c,b]
].

so substituting back into our initial expansion and keeping in mind
our example with the tuple list comprehension, we get:

[ [H|T] || H <- a, T <- [ [b,c] , [c,b] ] ].
[ [a|[b,c]] , [a|[c,b]] ].
[ [a,b,c] , [a,c,b] ].

then we move on to the next item in the list, b:

[ [H|T] || H <- b, T <- [ [a,c] , [c,a] ] ].
[ [b|[a,c]] , [b|[c,a]] ].
[ [b,a,c] , [b,c,a] ].

and then c...

....so our final expansion is:

[ [a,b,c] , [a,c,b] , [b,a,c] , [b,c,a] , [c,a,b] , [c,b,a] ].

hope this helps.

Ulf Wiger

2007-03-26, 8:29 am

>>>>> "a.b." == almostbored <almostbored@gmail.com> writes:

a.b.> i am just learning erlang too, but this is how i reasoned that
a.b.> example:

a.b.> assignments are done like nested for loops. for example,

a.b.> [ {A, B} || A <- [1,2], B <- [1,2] ].

a.b.> evaluates to:

a.b.> [{1,1}, {1,2}, {2,1}, {2,2}].

a.b.> for a single member list, perms expands as follows:

a.b.> perms([a]) -> [ [H|T] || H <- a, T <- perms([a] -- [a]) ]. [
a.b.> [H|T] || H <- a, T <- [] ]. [ [ a | [] ] ]. [ a ].

Since this is comp.lang.functional, one might suggest the following
approach to p

ing behind the scenes:

erlc +dcore perms.erl
cat perms.core
module 'perms' ['module_info'/0,
'module_info'/1,
'perms'/1]
attributes []
'perms'/1 =
%% Line 5
fun (_cor0) ->
case _cor0 of
<[[]|[]]> when 'true' ->
[[]|[]]
%% Line 6
<L> when 'true' ->
letrec
'lc$^0'/1 =
fun (_cor3) ->
case _cor3 of
<[H|_cor2]> when 'true' ->
letrec
'lc$^1'/1 =
fun (_cor6) ->
case _cor6 of
<[T|_cor5]> when 'true' ->
let <_cor7> =
apply 'lc$^1'/1
(_cor5)
in [[H|T]|_cor7]
<[]> when 'true' ->
apply 'lc$^0'/1
(_cor2)
( <_cor6> when 'true' ->
primop 'match_fail'
({'function_clause',_cor
6})
-| ['compiler_generated'] )
end
in let <_cor8> =
call 'erlang':'--'
(L, [H|[]])
in let <_cor9> =
apply 'perms'/1
(_cor8)
in apply 'lc$^1'/1
(_cor9)
<[]> when 'true' ->
[]
( <_cor3> when 'true' ->
primop 'match_fail'
({'function_clause',_cor3})
-| ['compiler_generated'] )
end
in apply 'lc$^0'/1
(L)
( <_cor10> when 'true' ->
primop 'match_fail'
({'function_clause',_cor10})
-| ['compiler_generated'] )
end

The listing is in Core Erlang, and the list comprehensions
have been expanded to letrecs and funs.

A description of Core Erlang can be found here:
http://www.it.uu.se/research/public...ports/2000-030/

BR,
Ulf W
--
Ulf Wiger, Senior Specialist,
/ / / Architecture & Design of Carrier-Class Software
/ / / Team Leader, Software Characteristics
/ / / Ericsson AB, IMS Gateways

Poter16

2007-04-21, 7:52 pm

Halle Berry in anal action!
http://Halle-Berry-anal-action.org/...hp?movie=148803

Sponsored Links