Wie Schreibe rekursive lambda-Ausdruck in Haskell?

Ich bin nicht sicher, ob dies guter Programmierstil ist, aber ich würde gerne wissen, ob man definieren kann, eine rekursive Funktion mit dem lambda-Ausdruck.

Dies ist ein künstliches Beispiel, das ich aus: So kann man es definiert die Fakultät-Funktion in Haskell rekursiv wie folgt 

factorial :: Integer -> Integer 
factorial 1 = 1
factorial (n + 1) = (n + 1) * factorial n

Nun möchte ich eine Funktion f so dass f n = (factorial n) + 1. Anstatt einen Namen für factorial n (D. H. Definition der vor der hand), möchte ich definieren f wo factorial n ist, da ein lambda-Ausdruck in der definition von f. Kann ich eine rekursive lambda-definition in f im Ort mit dem Namen Fakt?

  • Y-combinator
  • Warum nicht einfach einen Namen geben? Es muss nicht eine Globale Namen, es gibt let und where.
  • Beachten Sie übrigens, dass n+k mustern, wie Sie verwendet in Ihrer definition von factorial wurden entfernt sich von der Sprache wie von Haskell 2010. Es ist ratsam, nicht mehr verwenden.
  • p.s. Ich bevorzuge den base case 0: factorial 0 = 1 die es Ihr ermöglichen, zu arbeiten, für eine größere Anzahl
  • Ich denke, Sie wird nicht, wie mein code da fast alles importiert Data.Function (fix)
  • Der Y-combinator ist nicht gut-geschrieben in Haskell.

InformationsquelleAutor user898033 | 2011-08-21
  1. 29

    Die kanonische Art und Weise zu tun, die Rekursion mit reinen lambda-Ausdrücken ist die Verwendung eines fixpoint combinator, die eine Funktion mit der Eigenschaft

    fixpoint f x = f (fixpoint f) x

    Wenn wir davon ausgehen, dass eine solche combinator vorhanden ist, können wir schreiben die rekursive Funktion als

    factorial = fixpoint (\ff n -> if n == 1 then 1 else n * ff(n-1))

    Das problem ist nur, dass fixpoint sich noch rekursiv. Im reinen lambda-Kalkül, es gibt Möglichkeiten zum erstellen von fixpoint combinators, die bestehen nur aus Lambda-Ausdrücke, zum Beispiel der klassischen "Y-combinator":

    fixpoint f = (\x -> f (x x)) (\x -> f (x x))

    Aber wir haben noch Probleme, weil diese definition ist nicht gut typisierte nach Haskell -- und es kann bewiesen werden, dass es keine Möglichkeit schreiben ein gut-geschrieben fixpoint combinator mit nur Lambda-Ausdrücke und Funktions-Anwendungen. Es kann getan werden, durch die Verwendung eines Hilfs-Daten-Typ-Schuhlöffel in einer Art Rekursion:

    data Paradox a = Self (Paradox a -> a)
fixpoint f = let half (Self twin) = f (twin (Self twin))
             in half (Self half)

    (Beachten Sie, dass, wenn die Injektionen und Projektionen aus der singleton-Daten-Typ entfernt sind, ist dies genau die Y combinator!)

    • Obwohl es nicht typecheck, kann man immer noch Spaß haben! Fakultät, factorial 3 🙂
    • Gibt es einen Grund für die Verwendung data hier, oder wird newtype Arbeit als gut (besser)?
    • Wahrscheinlich newtype besser funktionieren würde -- ich war nicht bewusst, dass Sprache-Funktion, wenn ich schrieb die Antwort.
    InformationsquelleAutor Henning Makholm
  2. 29

    Ja, mit der fixed-point-Funktion Update:

    fact :: Int -> Int
fact = fix (\f n -> if n == 0 then 1 else n * (f (n-1)))

    Eigentlich keinen Namen, da es ein lambda-Ausdruck, so nehmen Sie die Funktion als argument. Fix wendet die Funktion an sich "unendlich" viele Male:

    fix f = f (fix f)

    und ist in Data.Function.

    InformationsquelleAutor Owen
  3. 1

    Warum verwenden wir lambda statt let in?

    Prelude> (let fib n = if n == 1 then 1 else n * fib(n-1) in fib ) 4
24
    • let noch erfordert die Benennung von Funktionen.
    InformationsquelleAutor Anon Imous
  4. 0

    Owen ist vor Ort auf mit der Update-Funktion

    Prelude> fix f = f (fix f)
Prelude> fix (\f n -> if n == 0 then 1 else n * f (n - 1)) 6
720

    Den namenlosen Lambda-Funktion selbst beenden, auch wenn der fix nicht.
    Owen ' s fix-Funktion schlägt die Update-Funktion in der Regel verwendet in Haskell, die

    fix :: (a -> a) -> a
fix f = let {x = f x} in x

    Sowohl anonyme rekursive lambda-Funktionen

    InformationsquelleAutor fp_mora
Schreibe einen Kommentar