Erlang (programming language)/Tutorials/List Comprehensions: Difference between revisions

From Citizendium
Jump to navigation Jump to search
imported>Eric Evers
imported>Chris Day
(becuase to because)
 
(4 intermediate revisions by 2 users not shown)
Line 1: Line 1:
{{subpages}}
===Intermediate list comprehensions===
===Intermediate list comprehensions===


Line 10: Line 11:


Note: in general using huge numbers of atoms is not a good idea.
Note: in general using huge numbers of atoms is not a good idea.
 
%======================================================================
  -module(think).              %
  -module(think).              %
  -compile(export_all).        %
  -compile(export_all).        %
Line 30: Line 31:
  parent(noah,shem) -> true;
  parent(noah,shem) -> true;
  parent(_X,_Y) -> false.
  parent(_X,_Y) -> false.
                                                %
%
people() -> [ adam, shem, cain, abel, eve, noah ].
%
father_of() -> [ {X,Y} || X <- people(), Y <- people(), parent(X,Y), male(X) ].
mother_of() -> [ {X,Y} || X <- people(), Y <- people(), parent(X,Y), female(X) ].
%============================================================================
compile with c(think). and generate output with:
17> think:father_of() ++ think:mother_of().
[{adam,cain},{adam,abel},{noah,shem},{eve,cain},{eve,abel}]
%============================================================================
 
The above program is terse and logical. Unfortunately, the traditional predicate
ancestor(X) is not included in module think.erl because it is a recursive predicate
and can not be programmed simply.
 
Erlang does not do recursive backtracking in list comprehensions,
so we need to program our recursive predicates in all their gory detail.
The advantage of gory detail is that we can control exactly the way that the
recursion happens.
 
Aside: debugging erlang and other languages
 
The advantage of highly declarative programming languages like prolog is
that recursive backtracking is implicit. Built in backtracking makes the code
very short and simple. This can make it possible to do very complex things
quickly and easily. The disadvantage of highly declarative programming languages like prolog is that recursive backtracking can make debugging very difficult and non-intuitive.
 
Erlang makes everything flow one-way. Pattern matching only the forward half of  unification but it does not backtrack. Recursive predicates are explicit,
which makes it easy to SEE what might be wrong with an algorithm. As Joe Armstrong
has said, erlang is very easy to debug because state is immutable.
 
Once one has developed well behaved recursive predicates like ancestor, they
can be but into a library and used in very terse list comprehensions.
 
In the program below we include the recursive predicate
ancestor(), for completeness.
 
%=============================================================================
 
-module(family).
-compile(export_all).
 
  people() ->
  people() ->
        [ adam, shem, cain, abel, eve, noah ].
    [amy,
                                                %
    mark, maya,  
father_of() ->
    joe,  
        [ {X,Y} || X <- people(), Y <- people(), parent(X,Y), male(X) ].
    fred,  
mother_of() ->
    alice].
        [ {X,Y} || X <- people(), Y <- people(), parent(X,Y), female(X) ].


compile with c(think). and generate output with:
parent(amy, mark) -> true;
  17> think:father_of() ++ think:mother_of().
parent(maya, joe) -> true;
  [{adam,cain},{adam,abel},{noah,shem},{eve,cain},{eve,abel}]
parent(mark, joe) -> true;
parent(joe, fred) -> true;
parent(fred, alice) -> true;
parent(_,_) -> false.
 
male(fred) -> true;
male(joe) -> true;
male(mark) -> true;
male(_) -> false.
% calc_parent() might be empty
calc_parent(Child) ->   
        _P = [Parent || Parent <- people(), parent(Parent,Child)]. 
 
% ancestor predicate is recursive and returns true or false
ancestor(A, C) -> 
        Is_Parent = parent(A, C),
        if
                Is_Parent == true ->
                      true;
                true ->
                        P = calc_parent(C),
                        if
                                P == [] ->
                                        false;
                                length(P) == 1 ->
                                        ancestor(A, hd(P));   
                                        % has only one parent
                                true ->
                                        ancestor(A, hd(tl(P))) or ancestor(A, hd(P)) 
                                        % has more than one parent
                end
        end.
 
% find all {ancestor, descendend} pairs where their genders match
 
  start() ->  
        Question = ["who is an ancestor and the same gender?"],
        Answer = [{A,B} || A <- people(), B <- people(), ancestor(A,B),
                male(A)==male(B)],
        {Question, Answer}.
%===========================================================================
% Sample output --------------------
% 1> family:start().
  % {
% ["who is an ancestor and the same gender?"],
% [{amy,alice},{maya,alice},{mark,joe},{mark,fred},{joe,fred}]
% }
%===========================================================================

Latest revision as of 00:57, 6 February 2010


Intermediate list comprehensions

An important use of List Comprehensions is to help translate prolog into erlang.

1- Erlang is a functional language designed for message passing (MIMD) parallel processing. Prolog is designed for logic programming. Sometimes a problem is most easily defined as a logical set of constraints on some set of data. If one thinks logically or thinks in constraints, or thinks in prolog, this style of list comprehensions can be a helpful way to do your tasks in erlang. There exist many useful solutions in prolog that can be moved to erlang via list comprehensions.

2- Constraint programming and logic programming are considered a higher level way to program then functions, and hence, are a good way to save you time and increase terseness.

Warning: constraint and logic based programs can be harder to debug because strict step by step actions are hidden and delegated to the list comprehension engine. Order of constraints in erlang list comprehensions can affect the output. Order dependence of constraints can be a non-intuitive distraction.

Note: in general using huge numbers of atoms is not a good idea.

%======================================================================
-module(think).              %
-compile(export_all).        %
                             %
male(adam) -> true;          %
male(seth) -> true;
male(cain) -> true;
male(abel) -> true;
male(noah) -> true;
male(_X) -> false.
                             %
female(eve) -> true;
female(_X) -> false.
                             %
parent(adam,cain) -> true;
parent(adam,abel) -> true;
parent(eve,cain) -> true;
parent(eve,abel) -> true;
parent(noah,shem) -> true;
parent(_X,_Y) -> false.
%
people() -> [ adam, shem, cain, abel, eve, noah ].
%
father_of() -> [ {X,Y} || X <- people(), Y <- people(), parent(X,Y), male(X) ].
mother_of() -> [ {X,Y} || X <- people(), Y <- people(), parent(X,Y), female(X) ].
%============================================================================
compile with c(think). and generate output with: 
17> think:father_of() ++ think:mother_of().
[{adam,cain},{adam,abel},{noah,shem},{eve,cain},{eve,abel}]
%============================================================================

The above program is terse and logical. Unfortunately, the traditional predicate ancestor(X) is not included in module think.erl because it is a recursive predicate and can not be programmed simply.

Erlang does not do recursive backtracking in list comprehensions, so we need to program our recursive predicates in all their gory detail. The advantage of gory detail is that we can control exactly the way that the recursion happens.

Aside: debugging erlang and other languages

The advantage of highly declarative programming languages like prolog is that recursive backtracking is implicit. Built in backtracking makes the code very short and simple. This can make it possible to do very complex things quickly and easily. The disadvantage of highly declarative programming languages like prolog is that recursive backtracking can make debugging very difficult and non-intuitive.

Erlang makes everything flow one-way. Pattern matching only the forward half of unification but it does not backtrack. Recursive predicates are explicit, which makes it easy to SEE what might be wrong with an algorithm. As Joe Armstrong has said, erlang is very easy to debug because state is immutable.

Once one has developed well behaved recursive predicates like ancestor, they can be but into a library and used in very terse list comprehensions.

In the program below we include the recursive predicate ancestor(), for completeness.

%=============================================================================
-module(family).
-compile(export_all).
people() ->
    [amy,
    mark, maya, 
    joe, 
    fred, 
    alice].
parent(amy, mark) -> true;
parent(maya, joe) -> true;
parent(mark, joe) -> true;
parent(joe, fred) -> true;
parent(fred, alice) -> true;
parent(_,_) -> false.
male(fred) -> true;
male(joe) -> true;
male(mark) -> true;
male(_) -> false.
% calc_parent() might be empty
calc_parent(Child) ->    
       _P = [Parent || Parent <- people(), parent(Parent,Child)].   
% ancestor predicate is recursive and returns true or false
ancestor(A, C) ->  
       Is_Parent = parent(A, C),
       if
               Is_Parent == true ->
                      true;
               true -> 
                       P = calc_parent(C),					
                       if
                               P == [] -> 
                                       false;
                               length(P) == 1 ->
                                       ancestor(A, hd(P));    
                                       % has only one parent
                               true ->
                                       ancestor(A, hd(tl(P))) or ancestor(A, hd(P))  
                                       % has more than one parent
                end
       end.
% find all {ancestor, descendend} pairs where their genders match
start() -> 
       Question = ["who is an ancestor and the same gender?"],
       Answer = [{A,B} || A <- people(), B <- people(), ancestor(A,B), 
                male(A)==male(B)],
       {Question, Answer}.
%===========================================================================
% Sample output --------------------
% 1> family:start().
% {
% ["who is an ancestor and the same gender?"],
% [{amy,alice},{maya,alice},{mark,joe},{mark,fred},{joe,fred}]
% }
%===========================================================================