Was sind paramorphisms?
Lesen durch dieses klassische Papier, ich bin stuck on paramorphisms. Leider ist der Abschnitt sehr Dünn, und die Wikipedia-Seite sagt nichts.
Mein Haskell übersetzung:
para :: (a -> [a] -> b -> b) -> b -> [a] -> b
para f base = h
where
h [] = base
h (x:xs) = f x xs (h xs)
Aber ich habe nicht Begriffen, dass Sie -- ich habe kein Gespür für die Art Unterschrift oder das gewünschte Ergebnis.
Was ist ein paramorphism, und was sind einige nützliche Beispiele in Aktion?
Ja, ich habe gesehen,diese Fragen, aber Sie decken nicht paramorphisms direkt und ausschließlich Punkt-zu -Ressourcen, die hilfreich sein könnten als Hinweise, aber nicht als Lernmaterial.
para f base xs = foldr (uncurry f) base $ zip xs (tail $tails xs)
, dünkt mich.- Nach diese wiki-Seite, paramorphisms "Modell primitive Rekursion über induktive Datentypen". Bedeutet das, dass nichts/helfen?
- Jeremy Gibbons die "Kernspaltung" Papier, das ich wies in einem Kommentar zu einer der Fragen ist sehr nützlich learning-material. cs.ox.ac.uk/jeremy.gibbons/Publikationen/Spaltung.pdf Es funktioniert durch zahlreiche Rekursion Muster sehr deutlich.
- Daniel ' s re-write kann vereinfacht werden, da
para f base xs = foldr g base (init $ tails xs) where g (x:xs) = f x xs
. Das erinnert an Common Lisp istmaplist
.
Du musst angemeldet sein, um einen Kommentar abzugeben.
Ja, das ist
para
. Vergleichen Sie mit catamorphism, oderfoldr
:Manche Leute nennen paramorphisms "primitive Rekursion" durch den Kontrast mit catamorphisms (
foldr
) als "iteration".Wo
foldr
's zwei Parameter gegeben sind eine rekursiv berechnete Wert für jede rekursive Unterobjekt des input-Daten (hier, das ist der Schwanz von der Liste)para
's Parameter erhalten sowohl die original-Unterobjekt, und der Wert berechnet rekursiv aus.Beispiel Funktion, das ist schön ausgedrückt mit
para
ist die Sammlung der richtigen genügt eine Liste.so, dass
Vielleicht einfacher noch ist
in der die "Nachteile" - Zweig ignoriert seine rekursiv berechnet argument und gibt nur wieder der Schwanz. Bewertet faul, die rekursive Berechnung nie passiert und der Schwanz wird extrahiert, in konstanter Zeit.
Können Sie definieren
foldr
mitpara
ganz einfach; es ist ein wenig schwieriger zu definierenpara
ausfoldr
, aber es ist sicherlich möglich, und jeder sollte wissen, wie es geht!Den trick zu definieren
para
mitfoldr
ist die Rekonstruktion einer kopieren der ursprünglichen Daten, so dass wir Zugriff auf eine Kopie der Schwanz bei jedem Schritt, obwohl wir hatten keinen Zugriff auf das original. Am Endesnd
verwirft die Kopie der Eingabe und gibt nur die Ausgabe Wert. Es ist nicht sehr effizient, aber wenn Sie interessiert sind, in reiner Expressivitätpara
gibt Sie nicht mehr alsfoldr
. Wenn Sie diesefoldr
-codierte version despara
, dannsafeTail
dauert lineare Zeit, nachdem alle, ist das kopieren des tail-element von element.So, das ist es:
para
ist ein komfortabler version vonfoldr
das gibt Ihnen sofortigen Zugriff auf den Schwanz der Liste sowie den Wert daraus berechnet.Im Allgemeinen Fall die Arbeit mit einem Datentyp erzeugt als die rekursive fixpoint eines funktors
haben Sie
wieder, die beiden sind wechselseitig definierbar, mit
para
definiertcata
von der gleichen "make a copy" trickWieder
para
ist nicht mehr expressive alscata
, aber bequemer, wenn Sie benötigen einen einfachen Zugriff auf teilstrukturen der Eingabe.Edit: erinnerte ich mich an ein anderes schönes Beispiel.
Betrachten binäre suchbäume gegeben durch
Fix TreeF
wound versuchen Sie die Definition einsetzen für binäre suchbäume, zunächst als
cata
, dann alspara
. Finden Sie diepara
version viel einfacher, als an jedem Knoten müssen Sie in einem Teilbaum, sondern die Erhaltung der anderen, wie es war.