Ist mapM in Haskell streng? Warum erhält dieses Programm einen Stack-Überlauf?

8

Das folgende Programm wird ordnungsgemäß beendet:

%Vor%

Läuft:

%Vor%

Wenn es jedoch mit einer unendlichen Liste versehen wird, wird das Programm niemals beendet, und wenn es kompiliert wird, gibt es schließlich einen Stapelüberlauffehler!

%Vor%

Laufen,

%Vor%

Ich habe erwartet, dass das Programm getStdRandom jedes Mal, wenn ich ein Element von der Liste abhole, nach fünfmal fertig bearbeite. Warum versucht es die gesamte Liste zu bewerten?

Danke.

Gibt es einen besseren Weg, um eine unendliche Liste von Zufallszahlen zu erhalten? Ich möchte diese Liste in eine reine Funktion übergeben.

EDIT: Etwas mehr lesen ergab, dass die Funktion

%Vor%

habe ich gesucht.

EDIT2: Nachdem ich die Antwort von camccann gelesen hatte, erkannte ich, dass getStdGen bei jedem Aufruf einen neuen Startwert erhält. Stattdessen sollten Sie diese Funktion lieber als einfachen Zufallsgenerator verwenden:

%Vor%

Aber ich verstehe immer noch nicht, warum mein mapM -Aufruf nicht beendet wurde. Offensichtlich nicht mit Zufallszahlen verwandt, aber etwas mit mapM vielleicht zu tun.

Zum Beispiel habe ich festgestellt, dass das Folgende auch nicht endet:

%Vor%

Was gibt? Übrigens, IMHO, sollte die obige Funktion randomInts in System.Random sein. Es ist sehr praktisch, wenn man sehr einfach einfach eine zufällige Liste in der IO-Monade erzeugen und bei Bedarf in eine reine Funktion übergeben kann. Ich sehe nicht, warum dies nicht in der Standardbibliothek sein sollte.

    
Steve 29.07.2010, 01:50
quelle

2 Antworten

5

Ich würde etwas mehr tun, indem ich RandomRs die Arbeit mit einem anfänglichen RandomGen machen lasse:

%Vor%

Was die Faulheit angeht, was passiert hier, dass mapM ist (sequence . map)

Sein Typ ist: mapM :: (Monad m) => (a -> m b) -> [a] -> m [b]

Er bildet die Funktion ab, gibt [m b] aus und muss dann alle diese Aktionen ausführen, um eine m [b] zu erstellen. Es ist die Sequenz, die niemals die unendliche Liste durchläuft.

Dies wird in den Antworten auf eine frühere Frage besser erklärt: Ist Haskells mapM nicht faul?

    
dino 29.07.2010, 02:20
quelle
12

Zufallszahlen im Allgemeinen sind nicht streng, aber monadische Bindung ist - das Problem hier ist, dass mapM die gesamte Liste sequenzieren muss. Betrachten Sie die Typensignatur, (a -> m b) -> [a] -> m [b] ; wie dies impliziert, ist es zuerst map die Liste vom Typ [a] in eine Liste vom Typ [m b] , dann sequence die Liste, um ein Ergebnis vom Typ m [b] zu erhalten. Wenn Sie also das Ergebnis der Anwendung von mapM , zB binden, indem Sie es auf die rechte Seite von <- setzen, bedeutet dies, dass Sie diese Funktion der Liste zuordnen und dann ausführen monadische Aktion, und kombinieren Sie die Ergebnisse in einer einzigen Liste ". Wenn die Liste unendlich ist, wird dies natürlich nicht beendet.

Wenn Sie einfach einen Strom von Zufallszahlen wünschen, müssen Sie die Liste generieren, ohne eine Monade für jede Zahl zu verwenden. Ich bin nicht ganz sicher, warum Sie das Design, das Sie haben, verwendet haben, aber die Grundidee ist: Geben Sie einen Seed-Wert, verwenden Sie einen Pseudozufallszahlengenerator, um ein Paar 1) eine Zufallszahl 2) einen neuen Samen zu erzeugen , dann wiederhole mit dem neuen Samen. Jeder gegebene Samen wird natürlich jedes Mal dieselbe Sequenz bereitstellen. Sie können also die Funktion getStdGen verwenden, die einen frischen Startwert in der IO Monade liefert; Sie können dann diesen Seed verwenden, um eine unendliche Sequenz in vollständig reinem Code zu erstellen.

Tatsächlich bietet System.Random Funktionen für genau diesen Zweck, randoms oder randomRs anstelle von random und randomR .

Wenn Sie aus irgendeinem Grund es selbst machen wollen, ist das, was Sie wollen, im Wesentlichen ein Entfalten . Die Funktion unfoldr von Data.List hat die Typensignatur (b -> Maybe (a, b)) -> b -> [a] , was ziemlich selbsterklärend ist: Bei einem Wert vom Typ b wendet sie die Funktion an, um entweder etwas vom Typ a und einen neuen Generator zu erhalten Wert des Typs b oder Nothing , um das Ende der Sequenz anzugeben.

Sie möchten eine unendliche Liste, so dass Sie nie Nothing zurückgeben müssen. Wenn man also randomR teilweise auf den gewünschten Bereich anwendet und es mit Just zusammensetzt, ergibt dies:

%Vor%

Wenn Sie das in unfoldr einspeisen, erhalten Sie:

%Vor%

... was genau so geschieht, wie es behauptet: Wenn eine Instanz von RandomGen gegeben wird, wird eine unendliche (und faule ) Liste von Zufallszahlen erzeugt, die aus diesem Seed generiert werden.

    
C. A. McCann 29.07.2010 02:22
quelle

Tags und Links