4.2 Fundamentaloperatoren: Nest, Fold, Map, Apply, Thread

Nest

Nest[ $f$, $x$, $n$ ] $\to$ $f$[ $f$[ $f$[ $\cdots$ $f$[ $x$ ] $\cdots$ ] ] ]

• $f$ muß eine Funktion mit genau einem Argument sein.
• $x$ ist der Startwert.
• $n$ ist die Anzahl der Iterationen

In FORTRAN (prozeduraler Stil) könnte man folgendes Konstrukt verwenden:

       Res=x
       DO 100 I=1, n
         Res=F(Res)
100    CONTINUE

NestList[$f$,$x$,$n$] $\to$ {$x$,$f$[$x$],$f$[$f$[$x$]],..., $f$[$f$[$f$[$\cdots$$f$[$x$]$\cdots$]]]}

NestList[$f$,$x$,0] $\to$ {$x$}
NestList[$f$,$x$,1] $\to$ {$x$, $f$[$x$]}

Nest und NestList eignen sich besonders für die Iteration von Funktionen mit nur einem Argument. Diese müssen ihr eigenes Ergebnis wieder als Argument akzeptieren. Grundsätzlich lassen sich alle tail-recursive-Algorithmen mit Nest formulieren.

Fehlerhaftes Beispiel

In[1]:= Clear[f]
Out[1]=

In[2]:= f[{x_,y_}]:=x+y
Out[2]=

In[3]:= Nest[f,{1,2},3]
Out[3]= f[f[3]]
f erwartet eine Liste mit zwei Elementen als Argument, liefert aber eine Zahl als Ergebnis.

Fold

Fold[$f$,$x$,{$a$,$b$,...}] $\to$ $f$[ $\cdots$ $f$[ $f$[ $f$[ $x$, $a$ ], $b$ ], $c$ ] $\cdots$ ]

FoldList[$f$,$x$,{$a$,$b$,...}] $\to$ {$x$, $f$[$x$,$a$], $f$[$f$[$x$,$a$],$b$],...}

• $f$ muß eine Funktion mit genau zwei Argumenten sein.
• $f$[$x$,$a$] muß als Ergebnis eine expression zurückgeben, die als erstes Argument von $f$ akzeptiert wird.

Beispiel

Finite Automata

$\parbox{7cm}{ \includegraphics[scale=1]{mma3.eps} }$ $\parbox{4cm}{ Transition Diagram \\ \\ \includegraphics[scale=1]{mma4.eps} }$

Moore Automaten kennen

• 2 Input Symbole: ,,0`` und ,,1``
• 4 interne Zustände
• keine Output Symbole

Die diskrete Entwicklung des Automaten bei gegebenem Input von einem bestimmten Anfangszustand kann mit folgendem Programm untersucht werden:

In[4]:= Automat[1,0]:=4
Out[4]=

In[5]:= Automat[1,1]:=3
Out[5]=

In[6]:= Automat[2,0]:=1
Out[6]=

In[7]:= Automat[2,1]:=3
Out[7]=

In[8]:= Automat[3,_]:=4
Out[8]=

In[9]:= Automat[4,_]:=2
Out[9]=

In[10]:= evolve[aut_,initstate_,input_List]:= Fold[aut,initstate,input]
Out[10]=

In[11]:= evolve[Automat,1,{0,0,1,1}]
Out[11]= 4

Map

Map[$f$, {$a$,$b$,$c$,...}] $\to$ {$f$[$a$], $f$[$b$], $f$[$c$],...}

Spezielle Eingabeform: $f$ /@ {$a$,$b$,$c$,...}

Map[$f$, $expr$, $levelspec$]

$levelspec$ ist eine Liste, die angibt, auf welche Stufen von $expr$ die Funktion $f$ angewendet werden soll. (z.B. {$n$} wodurch $f$ nur auf die $n$te Stufe oder {$n$, $m$} wodurch $f$ auf die $n$te bis einschließlich $m$te Stufe angewendet wird)

expression	f	[	g	[	h	[$\cdots$]],	u	[$\cdots$]]
Stufe	$0$		$1$		$2$	$3$	$1$	$2$

Beispiel

In[12]:= Clear[f]
Out[12]=

In[13]:= sq[x_]:=x^2
Out[13]=

In[14]:= sq /@ Range[5]


Out[14]= {1,4,9,16,25}
$\to$ sq /@ {1,2,3,4,5} $\to$ {sq[1], sq[2], sq[3], sq[4], sq[5]}

In[15]:= f /@ {{1,2},{a,b}}
Out[15]= {f[{1,2}], f[{a,b}]}

In[16]:= Map[f,{{1,2},{a,b}},{2}]
Out[16]= {{f[1],f[2]},{f[a],f[b]}}

In[17]:= Map[f,{{1,2},{a,b}},2]
Out[17]= {f[{f[1],f[2]}],f[{f[a],f[b]}]}

Verwandte Operatoren: MapAll, MapAt, MapIndexed, MapThread. In[18]:= MapThread[f,{{a,b,c,...},{1,2,3,...}}]
Out[18]= {f[a,1],f[b,2],f[c,3],...}

Apply

Apply[$f$, $expr$]
Apply $f$ to the head of $expr$. = Ersetze den Kopf von $expr$ durch $f$.

Kurzschreibweise: f @@ expr

Beispiel

In[19]:= Plus @@ Range[100]
Out[19]= 5050
$\to$ Plus @@ List[1,2,3,...,100] $\to$ Plus[1,2,3,...,100]

In[20]:= And @@ {True, False, True}
Out[20]= False

In[21]:= Or @@ {True, False, True}
Out[21]= True

Thread

Thread[$f$[$arg_1$, $arg_2$,...]]
Threads $f$ over any lists that appear in arguments $arg_1$, $arg_2$, ...

Beispiel

In[22]:= Thread[f[{1,2,3}]]
Out[22]= {f[1], f[2], f[3]}
$\equiv$ f /@ {1,2,3}
(wäre ca. 5% schneller)

Wenn mehrere Listen als Argumente übergeben werden, müssen sie dieselbe Länge besitzen.

In[23]:= Thread[f[{a,b,c},{1,2,3}]]
Out[23]= {f[a,1], f[b,2], f[c,3]}

In[24]:= Thread[f[{A,B,C},{a,b,c},{1,2,3}]]
Out[24]= {f[A,a,1], f[B,b,2], f[C,c,3]}

In[25]:= Thread[f[a,{1,2,3},A]]
Out[25]= {f[a,1,A], f[a,2,A], f[a,3,A]}

Thread ist somit in gewisser Weise ,,verwandt`` mit dem Attribut Listable. Wenn $f$ dieses Attribut besitzt wird Thread sozusagen automatisch ausgeführt.