Ist Haskells Faulheit eine elegante Alternative zu Pythons Generatoren?

Question

In einer Programmierübung wurde zuerst gebeten, die faktorielle Funktion zu programmieren und dann die Summe zu berechnen: 1! + 2! + 3! +... n! in O(n) Multiplikationen (so können wir die Fakultät nicht direkt verwenden). Ich suche nicht nach der Lösung für dieses spezielle (triviale) Problem, ich versuche Haskell Fähigkeiten zu erforschen und dieses Problem ist ein Spielzeug, mit dem ich gerne spielen würde.

Ich dachte, Pythons Generatoren könnten eine gute Lösung für dieses Problem sein. Zum Beispiel:

from itertools import islice 
def ifact(): 
    i , f = 1, 1 
    yield 1 
    while True: 
     f *= i 
     i += 1 
     yield f 

def sum_fact(n): 
    return sum(islice(ifact(),5)) 

Dann habe ich versucht, um herauszufinden, ob es etwas in Haskell war ein ähnliches Verhalten als dieser Generator mit und ich dachte, dass Faulheit zu tun alle Mitarbeiter ohne zusätzliches Konzept.

Zum Beispiel könnten wir meinen Python ifact mit

fact = scan1 (*) [1..] 

ersetzen und dann die Übung mit dem folgenden lösen:

sum n = foldl1 (+) (take n fact) 

Ich frage mich, ob diese Lösung wirklich „gleichwertig“ ist zu Pythons eines hinsichtlich zeitlicher Komplexität und Speicherauslastung. Ich würde sagen, dass die Lösung von Haskell niemals alle Fakten der Liste speichert, da ihre Elemente nur einmal verwendet werden.

Bin ich richtig oder total falsch?

---

EDIT: Ich sollte genauer prüfen lassen:

Prelude> foldl1 (+) (take 4 fact) 
33 
Prelude> :sprint fact 
fact = 1 : 2 : 6 : 24 : _ 

So (meine Implementierung) Haskell das Ergebnis speichern, auch wenn es nicht mehr benutzt, um.

Answer 1

Ihre Beispiele sind nicht äquivalent im Speicherverbrauch. Es ist leicht zu sehen, wenn Sie * durch einen + ersetzen (so dass die Zahlen nicht zu schnell zu groß werden) und dann beide Beispiele auf einem großen n wie 10^7 ausführen. Ihre Haskell-Version wird viel Speicher verbrauchen und Python wird es niedrig halten.

Python Generator wird keine Liste von Werten generieren und dann zusammenfassen. Stattdessen erhält die Funktion sum Werte nacheinander vom Generator und akkumuliert sie. Daher wird die Speichernutzung konstant bleiben.

Haskell wird Funktionen faul bewerten, aber um zu berechnen, sagen foldl1 (+) (take n fact) wird es den vollständigen Ausdruck bewerten müssen. Für große n wird dies zu einem großen Ausdruck auf die gleiche Weise wie (foldl (+) 0 [0..n]) entfaltet. Weitere Details zur Bewertung und Reduzierung finden Sie hier: https://www.haskell.org/haskellwiki/Foldr_Foldl_Foldl%27.

Sie können Ihre sum n mit foldl1' anstelle von foldl1 wie auf dem obigen Link beschrieben beheben. Wie @ user2407038 in seinem Kommentar erklärt, müssten Sie auch fact lokal behalten. Die folgenden Arbeiten in GHC mit einer konstanten Speichernutzung:

let notfact = scanl1 (+) [1..] 
let n = 20000000 
let res = foldl' (+) 0 (take n notfact) 

Beachten Sie, dass es im Fall des tatsächlichen faktorielles anstelle von notfact Speichern Überlegungen weniger problematisch. Die Zahlen werden schnell groß, Arithmetik mit willkürlicher Genauigkeit wird die Dinge verlangsamen, so dass Sie nicht in der Lage sein werden, große Werte von n zu erreichen, um den Unterschied tatsächlich zu sehen.

Answer 2

Grundsätzlich, ja: Haskells Lazy-Listen ähneln Pythons Generatoren, wenn diese Generatoren mühelos klonbar, cachefähig und zusammensetzbar sind. Anstatt StopIteration zu erhöhen, geben Sie [] von Ihrer rekursiven Funktion zurück, die den Status in den Generator einbinden kann.

Sie machen etwas kühlere Sachen wegen Selbstrekursion. Zum Beispiel wird Ihr faktoriellen Generator mehr idiomatically erzeugt wie:

facts = 1 : zipWith (*) facts [1..] 

oder The Fibonaccis als:

fibs = 1 : 1 : zipWith (+) fibs (tail fibs) 

Im Allgemeinen jede iterative Schleife zu einem rekursiven Algorithmus umgewandelt werden kann durch die Schlingen Zustand Förderung zu Argumente einer Funktion und dann rekursiv aufrufen, um den nächsten Schleifenzyklus zu erhalten. Generatoren sind genau so, aber wir stellen einige Elemente jeder Iteration der rekursiven Funktion vor, `go ____ = (stuff): go ____.

Das perfekte Äquivalent ist daher:

ifact :: [Integer] 
ifact = go 1 1 
    where go f i = f : go (f * i) (i + 1) 

sum_fact n = sum (take n ifact) 

In Hinblick darauf, was am schnellsten, die absolut schnellste in Haskell wird wahrscheinlich die "for-Schleife" sein:

sum_fact n = go 1 1 1 
    where go acc fact i 
      | i <= n = go (acc + fact) (fact * i) (i + 1) 
      | otherwise = acc 

Die Tatsache, dass dies " tail-rekursive "(ein Aufruf von go leitet keine Unteraufrufe an go an eine andere Funktion wie (+) oder (*)) bedeutet, dass der Compiler es in eine wirklich enge Schleife packen kann, und deshalb vergleiche ich es mit" for loops ", obwohl das für Haskell keine echte Idee ist.

die oben sum_fact n = sum (take n ifact) ist ein wenig langsamer als dies aber schneller als sum (take n facts) wo facts mit zipWith definiert ist. Die Geschwindigkeitsunterschiede sind nicht sehr groß und ich denke, dass es meistens nur zu Speicherzuweisungen kommt, die nicht wieder verwendet werden.

Answer 3

In der Tat können faule Listen auf diese Weise verwendet werden. Es gibt jedoch einige feine Unterschiede:

• Listen sind Datenstrukturen. So können Sie sie behalten, nachdem Sie sie bewertet haben, was sowohl gut als auch schlecht sein kann (Sie können die Neuberechnung von Werten und rekursive Tricks vermeiden, wie @ChrisDrost beschrieben, auf Kosten von unveröffentlichtem Speicher).
• Listen sind rein. In Generatoren können Sie Berechnungen mit Nebenwirkungen haben, das können Sie nicht mit Listen machen (was oft wünschenswert ist).
• Da Haskell eine faule Sprache ist, ist Faulheit überall und wenn Sie nur ein Programm von einer imperativen Sprache in Haskell konvertieren, können sich die Speicheranforderungen erheblich ändern (wie @RomanL in seiner Antwort beschreibt).

Aber Haskell bietet erweiterte Tools, um das Generator/Verbraucher-Muster zu erreichen. Derzeit gibt es drei Bibliotheken, die sich auf dieses Problem konzentrieren: pipes, conduit and iteratees. Mein Favorit ist conduit, es ist einfach zu bedienen und die Komplexität seiner Typen wird niedrig gehalten.

Sie haben mehrere Vorteile, insbesondere, dass Sie komplexe Pipelines erstellen können und Sie können sie auf einer ausgewählten Monade basieren, die Ihnen erlaubt zu sagen, welche Nebenwirkungen in einer Pipeline erlaubt sind.

Mit Leitung, Ihr Beispiel ausgedrückt werden könnte wie folgt aussehen:

import Data.Functor.Identity 
import Data.Conduit 
import qualified Data.Conduit.List as C 

ifactC :: (Num a, Monad m) => Producer m a 
ifactC = loop 1 1 
    where 
    loop r n = let r' = r * n 
       in yield r' >> loop r' (n + 1) 

sumC :: (Num a, Monad m) => Consumer a m a 
sumC = C.fold (+) 0 

main :: IO() 
main = (print . runIdentity) (ifactC $= C.isolate 5 $$ sumC) 
-- alternatively running the pipeline in IO monad directly: 
-- main = (ifactC $= C.isolate 5 $$ sumC) >>= print 

Hier schaffen wir eine Producer (eine Leitung, die keinen Eingang verbraucht), das factorials auf unbestimmte Zeit ergibt. Dann stellen wir es mit isolate zusammen, was sicherstellt, dass nicht mehr als eine gegebene Anzahl von Werten durch es weitergegeben werden, und dann komponieren wir es mit einer Consumer, die nur Werte summiert und das Ergebnis zurückgibt.