7. Weitere Übungsaufgaben

Endrekursion und List.foldl / List.foldr

Übungsaufgabe Schreiben Sie eine rekursive Funktion firstElementWithRec : (a -> Bool) -> List a -> Maybe a, die das erste Element zurückgibt, das eine gewisse Bedingung erfüllt: 

firstElementWithRec (\x -> x >= 0) [-1, -2, 2, 0, -2, 3]                            
Just 2

Ist Ihre Funktion endrekursiv? Wenn ja, dann wird es ja wohl folgenden Aufruf überleben: 

firstElementWithRec (\x -> x \lt 0) (List.range 0 20000)

Als nächstens wollen wir firstElementWithoutRec implementieren. Diese soll im Prinzip das Selbe berechnen, allerdings ohne Rekursion, sondern mit List.foldl. Da das nicht ganz einfach ist, nähern wir uns Schritt für Schritt. Erinnern Sie sich: 

List.foldl                        
<function> : (a -> b -> b) -> b -> List a -> b

Die Semantik von List.foldl f y_0 list ist, dass wir die Liste $(x_0, \dots, x_{n-1})$ durchgehen, folgende Werte berechnen:

\begin{align*} y_1 & := f(x_0, y_0) \\ y_2 & := f(x_1, y_1) \\ y_3 & := f(x_2, y_2) \\ & \vdots \\ y_n & := f(x_{n-1}, y_{n-1}) \end{align*}

und dann $y_n$ zurückgeben. Der Code von firstElementWithoutRec wird im Prinzip so aussehen: 

firstElementWithoutRec : (a -> Bool) -> List a -> Maybe a
firstElementWithoutRec cond list =
    let
        y_0 : b
        y_0 =
            bla

        f : a -> b -> b
        f =
            bla
    in
    List.foldl f y_0 list

und wir müssen herausfinden, was y_0 und f sein sollen. Der Rückgabewert b von f wird dann auch der Wert des gesamten Ausdrucks List.foldl f y_0 list und somit der Rückgabewert von firstElementWithoutRecsein, also Maybe a. Der Typ von y_0 muss auch b sein, also Maybe a. Die Signaturen von y_0 und f sind also 

y_0 : Maybe a                        
f : a -> Maybe a -> Maybe a

Soweit hilft uns das Typensystem von Elm. Weiter können wir das Selbst-Nachdenken allerdings nicht aufschieben. Wir müssen uns klarmachen, was wir berechnen wollen. Vielleicht hilft es, sich klarzumachen, dass in dem Ausdruck f x y das x das nächste Element der Liste repräsentiert, y jedoch das "bisherige Ergebnis", oder eher: das, was das Gesamtergebnis wäre, wenn die Liste hier zu Ende wäre und es kein x mehr gäbe. Wenn y also bereits ein Just _ ist, dann gibt es vor dem x bereits ein Element, dass die Bedingung cond erfüllt, und wir ignorieren alles von hier ab. Daher: 

        f : a -> Maybe a -> Maybe a
        f x y =
            case y of
                Just _ ->
                    y

                Nothing ->
                    if cond x then
                        Just x

                    else
                        Nothing

Welchen Startwert y_0 sollen wir wählen? Das ist der Wert, der bei einer leeren Liste gelten soll. Da in einer leeren Liste kein Element die Bedingung cond erfüllt, ist klar: Nothing. Somit hier die ganze Funktion: 

firstElementWithoutRec : (a -&gt; Bool) -&gt; List a -&gt; Maybe a
firstElementWithoutRec cond list =
    let
        y_0 : Maybe a
        y_0 =
            Nothing

        f : a -&gt; Maybe a -&gt; Maybe a
        f x y =
            case y of
                Just _ -&gt;
                    y

                Nothing -&gt;
                    if cond x then
                        Just x

                    else
                        Nothing
    in
    List.foldl f y_0 list

Übungsaufgabe Wiederholen Sie die obige Übung für lastElementWithRec. Das soll das letzte Element einer Liste zurückgeben, dass die Bedingung cond erfüllt. Schreiben Sie eine rekursive Funktion!

Übungsaufgabe Stellen Sie sicher, dass Ihre Implementierung von lastElementWithRec endrekursiv ist.

Übungsaufgabe Implementieren Sie lastElementWithRec ohne Rekursion, nur mit List.foldl. Welchen Vorteil hat Ihre rekursive Implementierung eventuell gegenüber der Implementierung mit List.foldl?

Jetzt gibt es noch herausforderndere Aufgaben für List.foldl bzw. List.foldr:

Übungsaufgabe Die Funktion indexEachElement soll jedem Element in einem Array einen Index geben: 

indexEachElement 1 ["Mo", "Di", "Mi", "Do", "Fr", "Sa", "So"]
[(1,"Mo"),(2,"Di"),(3,"Mi"),(4,"Do"),(5,"Fr"),(6,"Sa"),(7,"So")]

oder noch schöner:

indexEachElement 0 (String.toList "Programmierparadigmen")                            
[(0,'P'),(1,'r'),(2,'o'),(3,'g'),(4,'r'),(5,'a'),(6,'m'),(7,'m'),(8,'i'),(9,'e'),(10,'r'),(11,'p'),(12,'a'),(13,'r'),(14,'a'),(15,'d'),(16,'i'),(17,'g'),(18,'m'),(19,'e'),(20,'n')]

Implmentieren Sie indexEachElement, ohne selbst Rekursion zu verwenden. Benutzen Sie stattdessen List.foldl (und eventuell List.reverse, wenn Sie es brauchen).

Verrenken Sie Ihr Gehirn noch ein bisschen mehr:

Übungsaufgabe Schreiben Sie eine Funktion listOfSuffixes : List a -> List (List a), die folgendes tut: 

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

Natürlich wieder ohne Rekursion, nur mit List.foldl bzw. List.foldr.

Currying

Wir wollen so etwas wie einen "Ableitungsoperator" für Funktionen natürlicher Zahlen definieren. Erinnern Sie sich: die Ableitung einer reellen Funktion $f : \R \rightarrow \R$ am dem Punkt ist

\begin{align*} \lim_{h \rightarrow 0} \frac{f(x+h)}{h} \ , \end{align*}

falls denn dieser Grenzwert existiert. Für eine Funktion $f : \N \rightarrow \N$ definieren wir

\begin{align*} f'(n) := f(n) - f(n-1) \end{align*}

und nennen das die diskrete Ableitung oder discrete Derivative auf Englisch. Schreiben Sie eine Funktion discreteDerivate, die ich so verwenden kann: 

sqr n = n^2                        
diffSqr = discreteDerivative sqr
diffSqr 20
39

Zusammengesetzte Datentypen

Hier sehen Sie meinen Datentyp Employee:

type alias Employee =
    { name : String, wordID : String }

Ich instanziiere mal einen Wert:

employee = {name : "Dominik Scheder", wordID : "50984"}

Übungsaufgabe Fügen Sie dem Datentyp Employee ein Feld reportsTo hinzu, das den direkten Vorgesetzten / die direkte Vorgesetzte bezeichnet. Welchen Datentyp sollte reportsTo haben? Beginnen Sie mit reportsTo : Employee, arbeiten sich durch die Fehlermeldungen und erarbeiten eine Lösung, die funktioniert.

In den nächsten Übungen wollen wir einen Datentyp für natürliche Zahlen implementieren. Dabei tun wir so, als gäbe es Int nicht. Die Implementierung ähnelt dem, wie man in der mathematischen Logik und in der Mengenlehre die natürlichen Zahlen einführt bzw. definiert. 

type Integer
    = Zero
    | Succ Integer


one =
    Succ Zero


two =
    Succ one


three =
    Succ two

Übungsaufgabe Implementieren Sie in diesem Datentyp die folgenden Funktionen:

  • add: Integer -> Integer -> Integer
  • mult: Integer -> Integer -> Integer
  • exp: Integer -> Integer -> Integer
  • toInt : Integer -> Int
  • fromInt : Int -> Integer