Haskell: Wie funktioniert das?
Hallo,
hier einmal der Code:
fun :: (Int -> Int) -> Bool -> Int -> Int
fun g b n | n <= 0 && b = 1
| even n = fun (fun g b) False (g (div n 2))
fun g _ n = g (fun (g . g) True (n-2))
*der . bei dem g . g ist die Funktions Komposition*
Die Aufhabe anhand dieser Funktion ist es zu entscheiden ob dies Funktionsaufrufe terminieren oder nicht und wenn ja mit welchem Wert.
- fun (\x->x) True 2
- fun (\x->x-1) True 4
Die Lösungen sind 1 und 0. Aber wieso bekommt man das raus?
Meine erste Auswertung für 1 als Beispiel für mein Problem damit:
- ..= fun (fun (\x->x) True) False 1
Wieso kann ich fun (\x->x) True schreiben? Ich hatte erst gedacht, dass durch eta reduction das n=2 einfach ausgelassen wird und der Aufruf eigentlich so aussähe fun (\x->x) True 2, aber wenn ich oben in den Code das n dort einfüge bekomme ich vom Compiler die Fehlermeldung "could not match Int->Int mit Int". Ich verstehe was der meint weil fun :: ...->Int als Ergebnis hat, aber dann macht es ja keinen sinn, dass fun als g verwendet werden darf und besonders, dass fun g b erlaubt ist...
Wieso geht das also?
Schonmal vielen Dank:))
1 Antwort
Wieso kann ich fun (\x->x) True schreiben?
Dieser Ausdruck erzeugt aus fun eine Neue Funktion, für die die Parameter g und b feststehen und der Parameter nicht feststeht. Diese Funktion hat die Signatur
Int -> Int
Sie ist also mit einem Int-Wert aufzurufen und liefert einen Int-Wert als Ergebnis.
In der Terminologie von Haskell sagt man, dass fun (\x->x) True eine partial Application von fun ist. Dahinter steht der Currying genannte Mechanismus.
nvm ich habe mir currying mal genauer angeschaut und verstehe jetzt was passiert die funktion fun g b ist fun :: (Int->Int)->Bool->(Int->Int) deshalb kann ich das nutzen als argument für fun. Jetzt ist nur noch die Frage wie sieht der Aufruf der letzten Funktionsdefintion vom fun aus wenn man fun g b als g hat?
Aber die Funktion kann doch schon nicht vom Typen Int->Int sein. Wenn ich doch habe fun (\x->x ) True dann sollte der Typ doch eher (a->a)->Bool->... sein. Oder nicht?