Referentin: Hermine Reichau

Proseminar : Funktionale Programmierung

Thema des Vortrags : Kombinatoren für die Breitensuche

Bezogener Text: ,Combinators for breadth-first search′ von Michael Spivey,

in:

J. Funktional Programming 10

: S. 397 ­ 408, Juli 2000,

Cambridge University Press

Inhaltsverzeichnis

1. Ergebnisräume multipler Funktionen

2. Breitensuche

3. Kompositionen

4. Assoziativität von

join

5. Infopapier zu den verwendeten Operationen

Hermine Reichau

Prof.Dr.M.Schmidt-Schauß/ M.Mann

Proseminar: Funktionale Programmierung

14.06.2002

1

---

Kombinatoren für die Breitensuche

1. Ergebnisräume multipler Funktionen

Der ein oder andere hat sicherlich bereits festgestellt, dass es Funktionen gibt, welche neben

einer Reihe erfolgreicher Berechnungsergebnisse zusätzlich eine Anzahl von

Berechnungsfehlschlägen zurückgeben. Dies lässt sich umgehen, indem man sich von diesen

multiplen Funktionen1 eine Liste der erfolgreichen Berechnungen zurückgeben lässt.

Allerdings kann es passieren, dass diese Listen leer sind oder, was weitaus schlimmer ist, dass

sie nicht terminieren. Das Generieren dieser Erfolgslisten ist vergleichbar mit der

unvollständigen Tiefensuche in Prolog; wir werden gleich am Beispiel der Faktorensuche zu

einer gegebenen Zahl n sehen weshalb.

Die Lösung für dieses Problem erscheint zunächst einfach: Wissen wir, dass uns eine

Funktion entweder kein Ergebnis oder unvorhersagbar viele Ergebnisse zurück gibt, so

ersetzen wir diese durch eine genuine Funktion welche uns einen lazy stream zurückgibt:

Angenommen, wir möchten zu einer frei gewählten Zahl n alle Paare von Faktoren

herausfinden, welche miteinander multipliziert gerade das Produkt n ergeben. Deshalb

nehmen wir alle möglichen Faktoren und fassen sie jeweils zu Paaren zusammen, so dass

jeder Faktor mit jedem Faktor kombiniert wird, und daraufhin getestet wird ob das Produkt

eines Paares n ergibt. Wenn das der Fall ist, war der Test erfolgreich und das Paar wird in eine

Ergebnisliste eingetragen, andernfalls wird das Paar fallen gelassen. Unter bestimmten

Umständen kann es aber sein, dass eine solche Ergebnisliste entweder leer bleibt oder aber

divergiert.

Eine Funktion die eventuell eine unendliche Anzahl von Berechnungsschritten und

Ergebnissen hervorruft, kann nicht allein durch endliche Listen implementiert werden. Daher

müssen wir unterscheiden zwischen finiten Listen ( list) und Listen die potentiell infinit sein

können. Diese Listen werden als lazy2 streams ( stream) bezeichnet. Beide Listentypen

werden auf die gleiche Weise implementiert.

Gegeben seien zwei Funktionen f und g mit:

(1) f :: stream

(2) g :: stream

Die Komposition dieser Funktionen ist gegeben durch

g

f

::

stream

.

Weiterhin sei g*=map g, d.h. g wird auf jedes Element seiner Argumentenliste angewendet

und das Ergebnis der Anwendung wird in einen neuen Stream geschrieben. Die Argumentliste

von g ist aber bereits ein Stream, der zuvor mit (1) durch f erzeugt wurde. Daher beschreibt

g* eine Funktion vom Typ:

stream ( stream) stream

Die Komposition

g

f

kann also definiert werden durch:

1 multipel deshalb weil sie mehr als ein Ergebnis zurückgeben

2 Diese Listen werden mittels `lazy evaluation′ ausgewertet, das heißt, ein Ausdruck oder Teilausdruck wird nur

berechnet, wenn es unbedingt nötig ist, und dann auch nur einmal.

2

---

g

f

=

concat

g

*

f

3

Äquivalent dazu lässt sich der Kompositionsoperator wie folgt definieren:

(

g

f

)

x

= [

z

y

;

fx z

gy

]

Behauptung

Der Kompositionsoperator ist assoziativ.4

Zu zeigen: (

h

g

)

f

=

h

(

g

f

) .

Voraussetzung

(a)

h

*

concat

=

concat

h

**

(b)

concat

concat

* =

concat

concat

(c) (

q

p

)* =

q

*

p

*

Beweis

(

h

g

)

f

def

concat

(

concat

h

*

g

) *

f

(

c

)

concat

concat

*

h

**

g

*

f

(

b

)

concat

concat

h

**

g

*

f

(

a

)

concat

h

* (

concat

g

*

f

)

def

h

(

g

f

)

Zurück zu dem Faktorisierungsproblem am Anfang. Zunächst benötigen wir eine Funktion,

die eine vorgegebene Liste potentieller Faktoren für eine Zahl n so erweitert, dass letztendlich

alle möglichen Paare von Faktoren gebildet werden. Die Ergebnisse sollen uns als lazy stream

übergeben werden.

Wir definieren die Funktion vom Typ

choose:: int list

(int list) stream

mit

choose xs = [xs++[x]|x [1...]]

Haben wir die nötigen Elemente ausgewählt wollen wir testen, ob sie Faktoren von n sind.

Dies testen wir mit der Funktion

test n

. Falls das getestete Paar miteinander multipliziert n

ergibt, wird es als [x,y] zurück gegeben und in einen Stream aus Listen geschrieben,

andernfalls wird nichts [] zurückgegeben. Die Funktion

test

ist also vom Typ

test:: int

int
list

( int list ) stream

und wird definiert durch

test n[x,y] = if

x

y

=

n

then[[x,y]] else[]

Hieraus lässt sich nun eine Funktion zusammensetzen welche nach Faktorenpaaren einer

gesuchten Zahl n sucht:

factorize n = (

test n

choose

choose

)[]

Diese Funktion arbeitet folgendermaßen:

Das rechte

choose

wird auf die leere Argumentliste[] angewendet, so dass wir hieraus eine

Liste aus Listen gewinnen, die jeweils ein einziges Element haben. Es wird theoretisch der

stream [[1],[2],[3]...] erzeugt. Da wir streams aber mittels lazy evaluation auswerten wollten,

wird zunächst einmal nur das erste Element ausgewertet, indem es an das linke

choose

übergeben wird. Dieses kombiniert nun alle möglichen Faktoren mit dieser [1], so dass

3 Zunächst wird die Funktion f auf x angewendet, woraus wir y erhalten. g wird dann auf y angewendet woraus

wir schließlich z erhalten.

4 Das muß er sein, damit die Funktionen die diesen Komparator verwenden eindeutig sind. Siehe hierzu auch

Seite 7 unten.

3

---

folgender Stream erzeugt wird [[1,1], [1,2], [1,3],...,[1,59], [1,60], [1,61]...]. Direkt nach der

Erzeugung eines Paares, wird das Paar von der Funktion

test

ausgewertet. Nehmen wir n = 40

an, dann würde der Ergebnisstream nur einen einzigen Eintrag erhalten, nämlich [[1,40]].

Danach würde

factorize

divergent weitere Paare mit 1 als erstem Element hervorbringen und

niemals zu 2 als erstes Element gelangen. Die einzige Lösung die dieses Programm findet ist

[[1,n]].

Ein äquivalentes Verhalten zeigt folgendes Prologprogramm:

factorize(N,X,Y) :- choose(X), choose(Y), X*Y= :=N

Auch hier wird X=2 niemals erreicht, da Prolog Probleme über Tiefensuche verarbeitet.

2. Breitensuche

Ein effektiverer Ansatz um das Faktorisierungsproblem zu lösen ist der, nicht nacheinander

jedes x mit allen möglichen y zu Paaren zusammenzufassen und dann zu x+1 überzugehen,

sondern parallel alle möglichen x mit allen möglichen y zusammenzuschließen. Wir

initialisieren hierfür einen Baum der zunächst die möglichen x abträgt:

[1]

[2]

[3]

[4]

Mit jedem Blatt wird ein Index verknüpft, der angibt, wie viele Auswahlschritte gebraucht

wurden um es zu erreichen. Wir legen fest, dass der Index für die Auswahl von [n] gleich n-1

ist.

In unserem Faktorisierungsprogramm werden zwei Auswahlen hintereinander getroffen:

choose

choose

. Um dies zu veranschaulichen erweitern wir den bereits vorhandenen Baum,

indem wir an jedes Blatt eine Kopie des Baumes einfügen der durch das zweite choose

generiert wird, und dessen Blätter potentielle Faktorenpaare darstellen:

[1]

[1,1] [2]

[1,2] [2,1] [3]

[1,3] [2,2] [3,1]

[1,4] [2,3] [3,2]

Jede Ebene des Baumes ist verbunden mit einem spezifischen Index für die Anzahl

der Auswahlschritte eines Paares.

Wenn wir nun nach in Frage kommenden Faktoren suchen, möchten wir möglichst alle Paare

finden und das in einer akzeptablen Zeit. Eine Tiefensuche würde sich hier in einem der noch

4

---

immer infiniten Teiläste des Baumes verlieren, während Blätter in anderen Teilästen

unbesucht blieben. Besser geeignet ist hier offensichtlich eine Breitensuche. Die Breitensuche

sucht ihrer Natur nach in der Reihenfolge, die der Index vorgibt, das garantiert, dass wir nach

und nach jeden Ast mit jedem Blatt besuchen. Auf diese Weise wird der Baum Ebene für

Ebene abgearbeitet.

Um diese Idee umzusetzen ist es notwendig, nicht nur alle potentiellen Faktorenpaare in

einem Stream zu sammeln, sondern, um die Baumstruktur nachzuempfinden, muss jedes

Faktorenpaar mit seinem Index verbunden werden. Dies leistet der Stream, den wir zu Anfang

verwendet haben, nicht mehr. Daher definieren wir uns hier einen neuen Typ, der dieses

leisten kann:

matrix =( list) stream

Hierbei handelt es sich um einen infiniten stream, der finite Listen zum Inhalt hat. Jede Liste

enthält alle potentiellen Faktorenpaare mit dem gleichen Index. Auf diese Weise werden die

Paare Zeile für Zeile zusammengefasst wobei jede Zeile einen anderen Index repräsentiert.

Anders als bei herkömmlichen Matrizen, hat unsere Matrix jedoch eine unendliche Anzahl

von Zeilen und die Länge der Zeilen variiert.

Beispiel:

Für unseren Baum oben erhalten wir in etwa folgende Matrix:

Index Listeninhalt

0 [[1,1]]

1 [[1,2],[2,1]]

2 [[1,3],[2,2],[3,1]]

3 [[1,4],[2,3],[3,2],[4,1]]

Die Funktionen choose und test müssen neu definiert werden, um den Matrix-Typ zu

implementieren. Von choose möchten wir gerne einen stream mit finiten Listen zurück

bekommen, so dass jede Liste eine einzige Auswahl enthält:

choose xs =

[[xs ++[x]]x [1...]]

Von test erwarten wir nun ebenfalls einen Stream aus Listen:

test n

[x,y] = if

x

y

=

n

then [[[x,y]]] else []

Mit diesen Hilfsdefinitionen lässt sich nun unser Faktorisierungsprogramm modifizieren:

factorize n

= (

test n

choose

choose

)[]

Hiermit müssten sich also alle Faktorenpaare von n finden lassen. Allerdings terminiert die

Berechnung noch immer nicht, da es ja selbst nachdem es alle Faktorenpaare gefunden hat

weiter Ebene für Ebene durchsucht und es ja unendlich viele Ebenen gibt. Auf den unteren

Ebenen werden nur noch leere Listen zurück gegeben. Solange also unser Suchraum infinit ist

lässt sich dieses nicht vermeiden. Wir benötigen also einen begrenzten Suchraum und einen

modifizierten Algorithmus der auf ihm arbeitet.

3. Kompositionen

5

---

Bisher ist offen geblieben, was der neue Kompositionsoperator ′ eigentlich leistet. Was wir

bisher voraussetzen ist, dass er mit den neu definierten Typen kompatibel ist.

Was uns fehlt, ist zum einen eine Definition dieses Operators und die Gewissheit, dass er

assoziativ ist. Assoziativ muss er sein damit so ein Programm wie factorize n eindeutig sein

kann.

Gegeben sei eine unbekannte Funktion vom Typ

join

:: ( matrix)matrix matrix. Diese

Funktion ist also ähnlich wie die Funktion concat, welche auf Listen funktioniert.

Wir können nun ′ äquivalent zu unserem alten Operator definieren als:

g

′

f

=

join

g

**

f

mit

g**:: matrix ( matrix)matrix

und f :: matrix ; g :: matrix

Wenn es diese Funktion

join

geben sollte, so müsste es relativ einfach sein, Assoziativität für

′ nachzuweisen, und zwar mit den gleichen Argumenten wie schon gezeigt.

Auf der Suche nach einer geeigneten Definition für

join

, halten wir nach ein paar nützlichen

Hilfsfunktionen Ausschau, aus denen wir schließlich

join

zusammensetzen können.

Voraussetzung: alle potentiell infiniten streams sind tatsächlich infinit, so dass nicht auf die

Möglichkeit Rücksicht genommen werden muss, dass sie eventuell doch terminieren.

Da matrix = ( list)stream, kann es nützlich sein, über eine Funktion vom

Typ ( stream)list ( list)stream zu verfügen. Diese kann definiert werden als ein fold auf

Listen

trans[] = repeat []

trans(xs:xss) = zipWith(:)xs(trans[])5

Diese Funktion nimmt also eine Liste in der streams enthalten sind. Von jedem stream nimmt

sie das erste Element (head) und schreibt alle ersten Elemente in eine Liste (nach

Reisverschlussprinzip), danach wird das ganze mit dem zweiten und jedem weiteren Element

wiederholt, da wir zu Anfang eine Liste aus Streams haben, erzeugen wir auf diese Weise

einen Stream aus finiten Listen. Das heißt, wir können

trans

alternativ auch wie folgt

definieren:

trans xss = (head*xss):(trans(tail*xss))

Anschaulich macht diese Funktion also folgendes:

trans[[x00, x01, x02...], [x10, x11, x12...], [x20, x21, x22...]...[x(n-1)0, x(n-1)1, x(n-1)2...]]

stream

list

= [[x00, x10, x20,...x(n-1)0], [x01, x11, x21...x(n-1)1]...]

list

stream

Das Ergebnis ist eine Matrix mit infiniter Zeilenanzahl. Für

join

wünschen wir uns, dass es

folgendes leistet: ( matrix)matrix matrix. Mit der Typdefinition

matrix =( list)stream erhalten wir daraus:

join

:: ((( list)stream)list)stream ( list)stream

Dann können wir mit trans folgende Komposition für join definieren:

5 also gilt für trans als fold-Operation: trans = foldr(zipWith(:))(repeat[ ] )

6

---

LSLS trans

*

LLSS

concat L concatS

LS

( L= Liste, S= Stream)

Mit concatL concatS = concatL* . concatS = concatS .

concatL** 6 Wobei concatL auf Listen

ausgeführt wird und concatS auf streams.

Diese Definition für join hat aber leider einen Haken: Die Ergebnisse müssen ihrem Index

nach aufsteigend geordnet sein. concatS kommt dieser Notwendigkeit nicht nach. Daher

brauchen wir noch weitere Hilfsfunktionen.

Wir definieren eine weitere Funktion vom Typ :

diag

:: ( stream)stream ( list)stream mit

diag

((

x

:

xs

) :

xss

) = [

x

] :

zipWith

(:)

xs

(

diag xs

))

Die Idee für eine Funktion die dieses erfüllt, verwendet eine Matrizendiagonali-sierung. Sie

übernimmt einen stream of streams. Diesen kann man sich als eine infinite Matrix vorstellen

welche eine unendliche Anzahl von Zeilen und Spalten hat. Diese Matrix wird nun diagonal

abgearbeitet, so dass sich hieraus ein stream aus finiten Listen ergibt:

x

x

x

00

01

02

x

x

x

10

11

12

diag

= [[

x

],[

x

,

x

],[

x

,

x

,

x

] ]

00

01

10

02

11

20

x

x

x

20

22

23

Wenn wir infinite Streams diagonalisieren können, warum haben wir das nicht gleich ganz am

Anfang getan, als uns die Funktionen einfache lazy streams zurückgegeben haben?

Definieren wir einmal den alten Kombinationsoperator mit Hilfe unserer neuen Funktion

diag

wie folgt:

g

f

=

concat

diag

g

*

f

In Anlehnung an unser kleines Faktorisierungsprogramm wählen wir

f

=

choose

und

g

=

test n

choose

, so dass f die erste Zahl auswählt. g wählt die zweite Zahl und gibt das

Ergebnis aller Faktorkombinationen wieder. Für n=6 erhielten wir dann folgenden Stream,

nachdem f und g* berechnet wurden:

]

6

,

1

[[

: ,

[ ]

3

,

2

: ,

,

3

[

]

2 :, ,

,

[ ]

1

,

6 : ,

,

,

]

Wählt f eine Zahl die ein Faktor von n ist, hier 1, 2, 3, 6 dann gibt g einen Stream wieder der

als erstes Element das korrekte Faktorenpaar hat, danach rechnet die Funktion mit 1 an erster

stelle weiter terminiert aber nie. Wählt f eine Zahl die kein Faktor von n ist, so verfängt sich

die Funktion sofort in einer nichtterminierenden Berechnung. Wenden wir nun

diag

auf diesen

String an, so divergiert diese Funktion bereits nach dem ersten Element [1,6], denn es

durchläuft ebenso den infiniten tail. Für [2,3] gibt es keine Möglichkeit mehr bei einer

folgenden Berechnung den Index festzulegen, denn es gibt ja bereits nach [1,6] eine

unendliche Anzahl von Entscheidungen, auch wenn sie alle eine leere Liste zurück geben.

Das Matrizen-Modell muss also re-definiert werden, damit

join

die richtige Form bekommt.

Mit unserer Hilfsfunktion

diag

können wir

join

nun wie folgt komponieren:

LSLS trans

*

LLSS

diag

LLLS

(

concat concat

)*

LS

6 zur Erinnerung: h* . concat = concat . h**

7

---

Wird unser neuer Kombinationsoperator ′ durch die so definierte Funktion

join

festgelegt,

so muss sie auch assoziativ sein. Dies ist leider nicht so.

Jede finite Liste, welche durch h g f erzeugt wird, enthält alle Ergebnisse mit dem

Gesamtindex x + y + z, wobei x, y und z angeben wie viele Auswahlen gebraucht wurden um

f, g und h zu berechnen.7

Die Ergebnismenge{(x,y,z)x + y + z =const} lässt sich als Dreieck in einem 3-

dimensionalen Raum darstellen:

Alle Ergebnisse die h (g f) als auch (h g) f

liefern, liegen in diesem Dreieck. Allerdings geschieht

z

die Berechnung in unterschiedlicher Reihenfolge.

h (g f) teilt das Dreieck in Streifen, welche parallel

zur xy-Kante verlaufen, während (h g) f das

y

Dreieck in Streifen teilt, welche parallel zur yz-Kante

verlaufen.

x

4. Assoziativität von join

Das obige Problem existiert nur, solange wir es mit geordneten Listen zu tun haben. Wenn es

uns egal ist, in welcher Reihenfolge uns die Ergebnisse, die den gleichen Index tragen,

übergeben werden, so gilt h (g f) = (h g) f. Es geht letztendlich nur um das Dreieck als

Ergebnisraum und nicht um seine Erschließung.

Diese Idee können wir dazu verwenden, für

join

die gewünschte Assoziativität herzustellen.

Definition: Ein Bag ist eine endliche Liste in welcher die Reihenfolge der Elemente

irrelevant ist.8

(1) Wenn gilt f :: dann ist f :: bag bag und

union

::

( bag) bag bag

(2) Implementieren wir Bags über finite Listen so schreiben wir f*, in diesem Fall

wird union über concat realisiert.

(3) Seien zwei Bags über finite Listen implementiert, dann sind die Bags gleich, wenn

die eine Liste eine Permutation der anderen Liste ist.

Tauschen wir die zuvor verwendeten Listen gegen Bags aus so können wir für

join

Assoziativität nachweisen.

Behauptung

join

ist assoziativ, es gilt:

join

join

=

join

join

*

7 also den jeweiligen Index

8 Es können in Bags ebenfalls mehrere gleiche Elemente vorkommen.

8

---

Vorbereitungen für den Beweis

Allgemeine Gesetzmäßigkeiten:

1.) für und * gilt:

( g

.

f )* = g*

.

f*

(g

.

f) = g

.

f

2.) polymorphe Funktionen9 wie

diag

sind natürliche Transformationen, so dass für jede

Funktion f gilt:

diag

.

f** = f*

.

diag

f**

( stream) stream

( stream ) stream

diag

diag

( bag) stream

f

* ( bag) stream

3.) Ist eine polymorphe Funktion t:: T T′ eine natürliche Transformation, so ist t*::

(T) list (T′) list auch eine.

4.) Assoziativgesetz für

union

:

union

.

union = union

.

union*

Fügen wir auf beiden Seiten den Funktor * hinzu so erhalten wir:

union*

.

union* = union*

.

union**

( im Beweis gekennzeichnet mit (1) )

Lemmata für die Interaktion der Hilfsfunktionen:

a. trans/union

Gegeben sei ein Wert vom Typ (( stream) bag) bag, dann gilt:

trans.

.

union = union*

.

trans

.

trans

Dies kann man infolgendem Beispieldiagramm nachvollziehen:

SBB

union

SB

trans

BSB

trans

trans

BBS

*

union

BS

b. diag

Es sei diag

.

diag = diag

.

diag* , dann gilt

union*

.

diag

.

trans*

.

diag = union*

.

diag

.

diag*

9 polymorphe Funktionen: Es ist möglich eine Liste generisch zu initialisieren, d.h. der Datentyp den die Liste

enthalten darf, wird als Parameter deklariert, so dass hinterher bei bedarf die Deklaration nach konkretisiert

werden kann. Funktionen deren Typ alle möglichen Versionen generischer Typen quantifizieren sind

polymorphe Funktionen.

9

---

Anschaulich gemacht in folgendem Diagram:

SSS

diag

SBS

trans

* BSS

diag

diag*

BBS

union*

BSS

diag

BBS

*

union

BS

c. trans/diag

Es gilt:

union*

.

diag

.

trans*

.

trans = union*

.

trans

.

diag

Dargestellt durch folgendes kommutatives Diagramm:

SSB

trans

SBS

*

tran

BSS

diag

diag

BBS

union*

BSB

trans

BBS

*

union

BS

Wir haben nun einige Hilfsfunktionen und ihre Beziehungen untereinander, sowie einige

nützliche Definitionen zusammengetragen mit deren Hilfe wir die Assoziativität von

join

zeigen können. Ganz zu Anfang haben wir die Assoziativität für den herkömmlichen

Kompositionsoperator gezeigt. Können wir die Assoziativität von

join

zeigen, so läßt sich

der erste Beweis auch auf unseren neuen Operator ′ anwenden. Wie zu Anfang schon

einmal erwähnt wurde.

Beweis

In Abschnitt 2 definierten wir die gesuchte Funktion

join

wie folgt:

LSLS trans

*

LLSS

diag

LLS

(

concat concat

)*

LS

Aus 1.) folgt für

(concat

.

concat)*= concat*

.

concat*

Da wir hier auf Bags operieren müssen wir

concat

durch

union

vertauschen.

So erhalten wir für

join

folgende Definition:

()

join

::

union

*

union

*

diag

trans

*

Für die Assoziativität von

join

erhalten wir dann:

10

---

join

join

=

join

join

*

union*

.

union*

.

diag

.

trans*

.

union*

.

union*

.

diag

.

trans*

= union*

.

union*

.

diag

.

trans*

.

union*

*

.

union*

*

.

diag

*

.

trans*

*

Im vollständigen Beweis ist für jedes Diagramm angegeben warum es kommutiert. Dabei

bedeutet A* die Verwendung von Lemma A, bei dem auf beiden Seiten der Funktor *

hinzugefügt wurde und [

union*

] zeigt an, dass

union*

eine natürliche Transformation

darstellt.

trans* diag union* union*

(BS)3 BSB2S2 BSB3S BSB2S (BS)2

trans**

B2S2BS

trans *

B2S2

diag* diag

B3S

B3SBS union*

union**

B2SBS B2S

union ** union*

trans* diag union* union*

(BS)2 B2S2 B3S B2S BS

Dies ist nur das äußere Gerüst des Beweises, zusätzlich müssen auch alle inneren Diagramme kommutieren.

Aus Platzgründen wurden sie hier weggelassen. Wer den ganzen Beweis nachvollziehen möchte, der schaue

hierzu in den referierten Text.

5. abschließende Betrachtung

Der assoziative Kompositionsoperator ′ der hier für die Breitensuche entwickelt wurde, und

der sich in der logischen Programmierung wie ein ,AND′ verhält, ist nur ein Teil einer

größeren algebraischen Theorie, welche sich mit Suchstrategien in der logischen

Programmierung auseinandersetzt.

Parallel zu diesem AND-Operator entwickelten Michael Spivey und Silvia Seres einen

entsprechenden OR-Operator ′ welcher sich wie folgt definieren lässt:

11

---

(

f

′

g) x = zipWith(++)(fx)(gx)

Die beiden Operatoren ′ und ′ weisen unter einer Reihe anderer algebraischer

Eigenschaften auch Distributivität auf und es gibt ein neutrales Element für jeden Operator.

Die neutralen Elemente dieser Operatoren sind die Funktionen

true

und

false

wobei:

true

::

matrix

definiert durch:

true x = x

:

repeat

10

neutrales Element für ′

false

::

matrix

definiert durch:

false x

=

repeat

neutrales Element für ′

Infopapier

Verwendete Begriffe und Listen-Operationen:

xs

bezeichnet eine Liste

xss

bezeichnet eine Liste aus Listen

xsss ...

++

konkateniert zwei Listen

: (sprich Kons)

- fügt einen Wert als neues

erstes

Element in eine Liste ein

-

Kons ist rechtsassoziierend

-

für ++ und Kons gilt: x : xs = [x] ++ xs

Zwischen (++) und (:) gibt es einen wichtigen Unterschied: mit Hilfe von [] und (:) kann jede Liste auf genau

eine

Weise ausgedrückt werden; dies trifft nicht auf die Konkatenation mit ++ zu, die ja eine assoziative

Operation darstellt:

Beispiel:

Kons [1,2] : [3] = [3,1,2] [1] : [2,3] = [2,3,1]

++ [1,2] ++ [3] = [1,2,3] = [1] ++ [2,3] = [1,2,3]

1.

feststehende Operationen

concat

Diese Funktion konkateniert eine Liste von Listen in eine große Liste. Sie entspricht also der großen

Vereinigungsmenge in der Mengenlehre ( ++ ist die kleine Vereinigung, da hier einfach zwei Listen gleichen

Typs konkateniert werden ). Es gilt also:

concat

[[]]

[]

concat xss =

[

x xs

;

xss x

xs

]

10 senkrechte Doppelstriche stehen für Bags

12

---

Beispiel:

concat

[[1,2],[a,b],[x,y,3]] = [1,2,a,b,x,y,3]

zipWith

Diese Funktion übernimmt ein Listenpaar und kombiniert jeweils das n-te Element der einen Liste mit dem n-ten

Element der anderen Liste. Wenn die beiden Argumentenlisten nicht gleich lang sind, hat die Ergebnisliste die

Länge des kürzeren Arguments.

Beispiel:

[1,2,3,4]

zipWith

([a,b,c]) = [(1,a), (2,b), (3,c)]

head

Diese Funktion wählt das erste Element einer Liste.

head

([x]++xs) = x

Beispiel:

head

([h,e,a,d]) = h

tail

Diese Funktion wählt den Rest einer Liste ohne das erste Element.

tail

([x]++xs) = xs

Beispiel :

head

([h,e,a,d]) = [e,a,d]

Die Beziehung zwischen head und tail kann folglich ausgedrückt werden über:

x = [

head

xs] ++

tail

xs

foldr

Die meisten bisher genannten Operationen liefern Listen als Ergebnisse. Demgegenüber ist ein Faltungsoperator

allgemeiner, weil er Listen auch in andere Werttypen umformen kann.

Für das Falten nach rechts auf Listen gilt:

( )

[ ]

Bei

faltr

ist die Klammerung rechtsassoziierend, das heißt für die Anwendung auf eine Funktion über Listen:

faltr

f

a[x1, x2, ...,xn] =

f

x1(

f

x2(...(

f

xna)...)) wobei a das neutrale Element ist.

Das zweite Argument der Funktion muss den gleichen Typ besitzen wie das Ergebnis der Funktion, während das

erste Argument im allgemeinen einen anderen Typ besitzen kann.

Sei eine Operatorvariable, die an eine Funktion mit zwei Argumenten gebunden ist, dann kann wie folgt

rechts gefaltet werden:

faltr

() a [] = a

faltr

() a [x1] = x1 a

faltr

() a [x1, x2] = x1 (x2 a )

faltr

() a [x1, x2, x3] = x1 (x2 (x3 a ) )

...

Beispiele:

summe =

faltr

(+) 0

produkt =

faltr

(*) 1

concat

=

faltr

(++) []

2.

generierte Operationen

13

---

choose

Diese Funktion wird im Beispiel der Faktorensuche für eine gegebene Zahl n zur Auswahl der einzelnen

Faktoren verwendet. Sie tritt in zwei Variationen auf:

(1)

choose

= [xs++[x] x [1...]]

(2)

choose

= [[xs++[x]] x [1...]]

test

Diese Funktion übernimmt ein Paar ausgewählter Faktoren und überprüft, ob sie Faktoren der vorgegebenen

Zahl n sind. Falls dies der Fall ist wird das Paar in einen Stream of Lists geschrieben, ansonsten wird eine leere

Liste geschrieben. Auch hier gibt es zwei Variationen:

(1)

test

n[x,y] = if x

.

y = n then [[x,y]] else []

(2)

test

n[x,y] = if x

.

y = n then [[[x,y]]] else []

factorize

Diese Funktion setzt die Funktionen

choose

und

test

so zusammen, dass nach Faktorenpaaren für eine Zahl n

gesucht werden kann. ( Die Ausführung geschieht von rechts nach links ).

(1)

factorize

n = (

test n

choose

choose

)[]

(2)

factorize n

= (

test n

choose

choose

)[]

trans

Diese Funktion vertauscht zwei Werttypen und ist vergleichbar mit einem fold auf Listen. Sie wird hier dazu

verwendet eine Liste aus Streams in einen Stream aus Listen umzuschreiben.

trans

[] =

repeat

[]

trans

(xs:xss) =

foldr

(

zipWith

(:))(

repeat

[])

Diese Funktion nimmt also eine Liste in der streams enthalten sind. Von jedem stream nimmt

sie das erste Element (head) und schreibt alle ersten Elemente in eine Liste (nach

Reisverschlussprinzip), danach wird das ganze mit dem zweiten und jedem weiteren Element

wiederholt, da wir zu Anfang eine Liste aus Strings haben, erzeugen wir auf diese Weise eine

divergierende Liste aus finiten Listen: einen stream of lists. Das heißt, wir können

trans

alternativ auch wie folgt definieren:

trans

xss = (

head

*xss):(

trans

(

tail

*xss))

diag

Diese Funktion nimmt einen Stream aus Streams und verwandelt ihn in einen Stream aus

finiten Listen. Dies geschieht indem eine infinite Matrix diagonalisiert wird:

x

x

x

00

01

02

x

x

x

10

11

12

diag

= [[

x

],[

x

,

x

],[

x

,

x

,

x

] ]

00

01

10

02

11

20

x

x

x

20

22

23

Diese Funktion sieht folgender maßen aus:

diag

((

x

:

xs

) :

xss

) = [

x

] :

zipWith

(:)

xs

(

diag xs

))

14

---

3.

Verwendete Werttypen

list

Hierbei handelt es sich um eine gewöhnliche Liste von Elementen deren Position festgelegt

ist. In einer Liste treten alle Elemente nur einmal auf.

stream

..ist seinem Wesen nach auch nichts anderes als eine Liste. Das besondere ist aber die Art und

Weise wie diese Liste verarbeitet wird. Da ein Stream potentiell infinit ist, würde es keinen

Sinn machen vor seiner Weiterverarbeitung darauf zu bestehen, dass alle enthaltenen

Elemente bereits fest definiert sind. Daher wird ein stream mittels ,lazy evaluation′

ausgewertet. Das bedeutet, jedes Element wird nur dann konkretisiert, wenn es tatsächlich

gebraucht wird und dann auch nur ein einziges mal.

matrix

Der Werttyp

matrix

beschreibt einen Stream aus Listen. Der Idee nach, werden alle Listen

untereinander geschrieben, so dass eine Matrix entsteht, deren Zeilen an sich zwar endlich

sind, deren Zeilen Anzahl aber infinit sind.

bag

Ein Bag ist eine spezielle Art von Liste. Anders als bei herkömmlichen Listen ist die

Reihenfolge in einem Bag nicht festgelegt, d.h. es gibt weder ein erstes noch zweites noch

n-tes Element. Außerdem kann ein Bag ein Element mehrmals aufnehmen. Bags können auch

über finite Listen realisiert werden. Ist dies der Fall, dann gilt für zwei dieser Bags Gleichheit,

wenn die eine finite Liste eine Permutation der anderen Liste ist, da ja die Reihenfolge

irrelevant ist.

15

---