Wie schreibe rekursive faktorielle Funktion in Haskell ohne, wenn dann sonst Statement

Question

Ich weiß nicht, wie eine rekursive faktorielle Funktion ohne if-Anweisungen schreiben. Unser Professor sagte etwas über Lambda-Kalkül.

Answer 1

Pattern Matching und Wächter sind zwei besonders einfache Wege. Wächter sind im Wesentlichen eine andere Syntax für Wenn-dann-sonst; Sie sehen so aus:

fac n | n < 2  = 1 
     | otherwise = n * fac (n-1) 

Im Gegensatz zu if-then-else, unterstützen sie sauber mehrere Bedingungen; man könnte auch schreiben, zum Beispiel

fac n | n < 0 = error "nah" 
     | n == 0 = 1 
     | n == 1 = 1 
     | n > 1 = n * fac (n-1) 

die würde viel weniger schön in Wenn-dann-sonst-Form aussehen.

mit Mustervergleich, würde man typischerweise schreiben mehrere Definitionsgleichungen:

fac 0 = 1 
fac 1 = 1 
fac n = n * fac (n-1) 

Für Zahlen insbesondere diese auch zu desugars Wesentlichen ein if-then-else; aber für Datentypen mit weniger Compiler-Integration kann oft nicht mit if-then-else emuliert werden, und führt auch oft zu sehr natürlich aussehenden Code.

Ein anderer sehr netter Ansatz wäre, Ihre Rekursion in bestehende Prelude-Funktionen zu schieben; Je mehr Sie Iterationsmuster in der Praxis erkennen können, desto mehr Fehler können Sie vermeiden, indem Sie dieselben Schleifen nicht immer wieder neu implementieren. Für diese, könnten Sie product und die spezielle Aufzählung Syntax:

fac n = product [1..n] 

Eine erweiterte (und deutlich schlechter) Technik, um eine neue Art von Zahl zu definieren wäre; z.B. Kirchenziffern erlauben dem Hersteller der Nummer, die Rekursion zu steuern, und der Konsument (hier fac) liefert nur Basisfälle. In diesem Stil, könnten Sie so etwas wie dies sehen:

fac n = fst (n (1,1) (\(prod, sum) -> (prod*sum, sum+1))) 

(Beachten Sie aber auch, dass dies eine ganz besondere Art von Zahlen erfordert - sicherlich die Art der fac ist nicht einer von einer Funktion, die Int oder Integer könnte annehmen !) Dieser Witz wird in The Evolution of a Haskell Programmer zu seiner logischen und erschreckenden Schlussfolgerung gebracht.

Answer 2

Wenn/then/else und guards sind eigentlich nur syntaktischer Zucker für die Mustererkennung.

if b 
    then c 
    else d 

desugars zu

case b of 
    True -> c 
    False -> d 

, Ähnlich

f x 
    | b = c 
    | d = e 
f x = g 

desugars zu

f x = case b of 
     True -> c 
     False -> case d of 
      True -> e 
      False = g 

So können Sie immer case direkt verwenden. Es gibt jedoch eine ziemlich einfache Optimierung, die Sie von Hand durchführen können.Wenn Sie

case x == p of 
    True -> a 
    False -> b 

sehen, wo p von Konstrukteuren und Literale gemacht wird, kann man das Ganze mit

case x of 
    p -> a 
    _ -> b 

Answer 3

ersetzen versuchen, diese:

factorial 0 = 1 
factorial n = n * factorial (n - 1) 

---

Mit Endrekursion:

factorial n = f n 1 

f 0 acc = acc 
f n acc = f (n-1) (acc*n) 

main = print $ factorial 5 

Ausgabe:

120