Apr 2009

Nochmal List Comprehensions

Weil es so schön ist, hier noch zwei weitere Beispiele von List Comprehensions.

Beispiel 1: Die Funktion pyth(N) erzeugt eine Liste aller Integer-Tripel {A, B, C} für die A^2 + B^2 = C^2 und die Summe der Seiten kleiner oder gleich N gilt.

pyth(N) ->
    [ {A,B,C} ||
       A <- lists:seq(1,N),
       B <- lists:seq(1,N),
       C <- lists:seq(1,N),
       A+B+C =< N,
       A*A+B*B == C*C
    ].


> beispiele:pyth(32).
[{3,4,5},{4,3,5},{5,12,13},{6,8,10},{8,6,10},{12,5,13}]

Beispiel 2:
Die Funktion sort(N) sortiert eine Liste N.

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

Der Ausdruck [ X || X <- T, X < Pivot] sammelt alle Elemente X auf, die aus der Liste T stammen und dem Ausdruck X < Pivot genügen.

++ ist die Infix-Darstellung der Erlang Append-Funktion, mit der Listen konkateniert werden. Das Muster [Pivot | T ] im Funktionskopf zerlegt die Liste in zwei Teile: Pivot ist der Listenkopf, T der Rest der Liste.

> beispiele:sort([4,3,14,5,4,3]).
[3,3,4,4,5,14]

List Comprehensions

List Comprehensions sind ebenfalls eine elegante Möglichkeit Listenerzeugung sehr kompakt in Erlang auszudrücken. List Comprehensions folgen dem Schema zur Konstruktion mathematischer Mengen.

Beispiel 1:
> S1 = [ 2 * X || X <- [1,2,3,4]]
[2,4,6,8]

S1 ist die Liste aller 2*X wobei X aus der Liste [1,2,3,4] stammt.

List Comprehensions können auch alternativ zu den schon vorgestellten Funktionen auf Listen, wie map und filter, verwendet werden.

Beispiel 2:
> S2 = [Quadrat(X) || X <- [1,2,3,4,5,6,7,8,9], Gerade(X)].
[4,16,36,64]

S2 ist die Liste aller X zum Quadrat (Quadrat(X)), wobei X aus der Liste [1,2,3,4,5,6,7,8,9] stammt und X gerade ist (Gerade(X)).

Quadrat und Gerade sind wie im Blogeintrag „Funktionen auf Listen“ definiert.

In Erlang sind List Comprehensions wie folgt aufgebaut:

   [Expr || Qualifier1, ..., QualifierN]

Ein Qualifier ist dabei entweder ein Generator der Form Pattern <- ListExpr oder ein boolescher Test-Ausdruck, genannt filter.

Beispiel 3:
Hier werden die Komponenten M und N aller Paare {M,N} aus der PaarListe addiert, falls M < N ist.

> AddiereGeordPaare =
   fun(PaarListe) -> [ M+N || {M,N} <- PaarListe, M < N] end.

...
> AddiereGeordPaare([{2,3}, {2,1}, {7,8}]).
[5,15]


Beispiel 4:
Aus einer Datenbank sollen weibliche Personen, die nach 1970 geboren wurden, selektiert werden. Der Einfachheit halber ist unsere Datenbank eine Variable DB an die eine Liste von Personen-Strukturen gebunden ist.

> DB =
 [{person,"Hans",maennlich,1971},
  {person,"Franz",maenlich,1990},
  {person,"Michaela",weiblich,1988},
  {person,"Steffi",weiblich,1978},
  {person,"Boris",maennlich,1969},
  {person,"Petra",weiblich,1968}].


Die entsprechende Selektion ist so definiert:

> [ P || P = {person, _, Geschlecht, Geburtsjahr} <- DB,
         Geschlecht == weiblich, Geburtsjahr > 1970].
[{person,"Michaela",weiblich,1988},
{person,"Steffi",weiblich,1978}]


Erlang - The Smarter Way of Programming.

Und tschüss.

Server mit mehreren Arbeiterprozessen

Heute zeigen wir ein kleines Beispiel zur Programmierung mit Prozessen. In diesem Beispiel nimmt ein Serverprozess Sortieraufträge eines (oder mehrerer) Klienten entgegen und leitet diese an einen frisch erzeugten Arbeiterprozess (dem Sortierer) weiter. Der Arbeiterprozess verarbeitet den Auftrag und sendet das Ergebnis an seinen Klienten zurück und beendet sich.

Hier der Codeschnippsel:

-module(server).
-export([start/0, loop/0]).

%% erzeuge Serverprozess
start() ->
  register(server, spawn(server, loop, [])).

loop() ->
  receive
    {sortiere, Pid, Liste} ->
       erzeuge_sortierer(Pid, Liste),
       loop();
     _ ->
       loop()
  end.

%%% erzeuge Sortiererprozess
erzeuge_sortierer(Pid, Liste) ->
  spawn(fun() -> sortierer(Pid, Liste) end).

sortierer(Pid, Liste) ->
  Ergebnis = lists:sort(Liste),
  Pid ! Ergebnis.

Mit server:start() wird der Hauptprozess des Servers gestartet. Die Funktion spawn/1 erzeugt hier den Prozess, wobei die Funktion loop/0 zur Ausführung übergeben wird. Mit register/1 wird der Prozess Identifier - das Ergbnis von spawn/1 - unter den Namen server in der Erlang VM registriert. In der loop/0 verarbeitet der Server eingehende Aufträge der Form {sortierte, Pid, Liste}, wobei Pid der Prozess Identifier des Klienten und Liste die zu sortierende Liste ist. Empfängt (receive ... end) der Server eine solche Nachricht wird mit erzeuge_sortierer/2 ein neuer Prozess erzeugt, dessen Funktion sortierer/2 die eigentliche Sortierung der Liste durchführt und mit Pid ! Ergebnis das Resultat zurück an den Klienten sendet. Der Serverprozess läuft in einer „Endlosschleife“ (beachte den rekursiven Aufruf loop()).

Zum Test hier noch ein einfacher Klient:

-module(client).
-export([sortiere/1]).

sortiere(Liste) ->
  server ! {sortiere, self(), Liste},
  receive
    SortierteListe ->
       SortierteListe
  end.

Der Klient sendet den Auftrag an den Server und wartet auf die Antwort.

Das Ganze in der Erlang-Shell:

Zunächst den Server starten:

> server:start()

Dann der Sortierauftrag senden.

> client:sortiere([33,21,42,13]).
[13,21,33,42]


Kurz und knapp.

Funktionen auf Listen

Funktionen Höherer Ordnung in Kombination mit Listen offenbaren die wahre Eleganz funktionaler Programmierung. Schnell drei einfache Beispiele in Erlang.

Beispiel 1: Die Funktion lists:map(Fun, List1) -> List2 erwartet als Argument eine Funktion Fun sowie eine Liste List1. Auf jedes Element von List1 wird Fun angewendet und das Ergebnis in List2 aufgenommen.

> Quadrat = fun(X) -> X*X end.
...
> lists:map(Quadrat, [1,2,3,4]).
[1,4,9,16]


Wie könnte die Definition der Funktion map aussehen?

map(_,[]) -> [];
map(Fun,[Kopf|Rest]) -> [Fun(Kopf)|map(Fun, Rest)].

Beispiel 2: Die Funktion lists:filter(Praed, List1) -> List2 wendet auf jedes Element die boolesche Funktion Praed an. List2 ist eine Liste der Elemente, für die Praed true ist.

> Gerade = fun(X) -> (X rem 2) =:= 0 end.
...
> lists:filter(Gerade, [1,2,3,4]).
[2,4]


Wie könnte filter definiert sein?

filter(Praed, [Kopf|Rest]) ->
  case Praed(Kopf) of
    true -> [Kopf|filter(Praed, Rest)] ;
    false -> filter(Praed, Rest)
  end.

Beispiel 3: Die Funktion lists:foldl(Fun, Acc0, List) -> Acc1 faltet rekursiv die Liste List gemäss der Funktion Fun und einem Startwert Acc0.

> Add = fun(X,Y) -> X+Y end.
...
> lists:foldl(Add,0,[1,2,3,4,5]).
15

Der Aufruf foldl(Add,0,[1,2,3,4,5]) entspricht somit Add(5, Add(4, Add(3, Add(2, Add(1, 0)))))

Die Funktion foldl ist wie folgt definiert:

foldl(Fun, Acc, []) -> Acc;
foldl(Fun, Acc, [Kopf|Rest]) ->
  foldl(Fun, Fun(Kopf, Acc), Rest).


Das macht spass.

Fakultät

Was das Hello World für imperative Programmierung ist, ist die Fakultätsfunktion für die Welt der funktionalen Programmierung. Hier der Klassiker in Erlang:

-module(beispiele).
-export([fac/1]).
fac(N) when N > 0 ->
  N * fac(N-1);
fac(0) ->
  1.

Die Funktion fac ist innerhalb des Moduls beispiele definert. Mit der Export Anweisung wird auf die Funktion fac von ausserhalb des Moduls zugreifbar. Fac/1 bedeutet, dass die Funktion nur ein Argument erwartet. Der When-Ausdruck der Funktion fac, ein boolesche Ausdruck, wird Guard genannt. Falls der Guard zu true evaluiert, wird der Rumpf der Funktion (alles nach dem ->) ausgewertet. Im Rumpf folgt der rekursive Aufruf fac(N-1).

Die Auswertung der Funktion kann direkt an der Erlang-Shell durchgeführt werden. Wie am Ergebnis schnell erkennbar ist, können Erlangs Integerwerte beliebig gross sein. Sie sind nur durch den Hauptspeicher begrenzt.

1>beispiele:fac(40).
815915283247897734345611269596115894272000000000

Einfach und immer wieder schön.

Codeschnippsel und mehr

In diesem Blog folgen immer mal wieder kleine Erlang-Codeschnippsel oder kürzere Berichte zu Community-Projekten. Schaut öfters mal vorbei. Falls Ihr selbst spannendes zu berichten habt, schickt uns doch einen Beitrag, den wir hier unterbringen sollen.