Hinweis: Diese Antwort available als gebildete Haskell-Datei an Gist ist.
Ich habe diese Übung sehr genossen. Ich habe versucht, es zu tun, ohne mir die Antworten anzusehen, und es hat sich gelohnt. Es hat viel Zeit gekostet, aber das Ergebnis ist überraschend nahe zwei der anderen Antworten, sowie monad-coroutine Bibliothek. Also ich denke, das ist eine natürliche Lösung für dieses Problem. Ohne diese Übung würde ich nicht verstehen, wie monad-coroutine wirklich funktioniert.
Um zusätzlichen Wert hinzuzufügen, erkläre ich die Schritte, die mich schließlich zur Lösung geführt haben.
den Zustand Monade erkennen
Da wir mit Staaten zu tun haben, es wir nach Mustern suchen, die effektiv durch den Staat Monade beschrieben werden kann. Insbesondere ist s - s isomorph zu s -> (s,()), so dass es durch State s() ersetzt werden könnte. Und Funktion des Typs s -> x -> (s, y) kann zu x -> (s -> (s, y)) umgedreht werden, das ist eigentlich x -> State s y. Dies führt uns zu aktualisierten Signaturen
mutate :: State s() - Pause s()
step :: Pause s() - State s (Maybe (Pause s()))
Generalisierung
Unsere Pause Monade derzeit vom Staat parametrisiert. Aber jetzt sehen wir, dass wir den Staat für nichts wirklich brauchen, noch verwenden wir irgendwelche Spezifika der Staatsmonade. So konnten wir versuchen, eine allgemeine Lösung zu machen, die von jedem Monade parametrisiert:
mutate :: (Monad m) = m() -> Pause m()
yield :: (Monad m) = Pause m()
step :: (Monad m) = Pause m() -> m (Maybe (Pause m()))
Auch wir könnten versuchen, indem sie jede Art von Wert mutate und step allgemeinere zu machen, nicht nur (). Und durch die Erkenntnis, dass Maybe a isomorph ist zu Either a() können wir endlich unsere Unterschriften verallgemeinern zu
mutate :: (Monad m) = m a -> Pause m a
yield :: (Monad m) = Pause m()
step :: (Monad m) = Pause m a -> m (Either (Pause m a) a)
so dass step kehrt der Zwischenwert der Berechnung.
Monad Transformator
Jetzt sehen wir, dass wir tatsächlich eine Monade von einem Monade zu machen versuchen - fügen Sie einige zusätzliche Funktionen. Dies wird normalerweise monad transformer genannt. Darüber hinaus ist die Signatur mutate genau gleich lift von MonadTrans. Höchstwahrscheinlich sind wir auf dem richtigen Weg.
Der letzte Monade
Die step Funktion scheint der wichtigste Teil unserer Monade zu sein, ist es genau das, was wir brauchen, definiert. Vielleicht könnte dies die neue Datenstruktur sein? Lassen Sie uns versuchen:
import Control.Monad
import Control.Monad.Cont
import Control.Monad.State
import Control.Monad.Trans
data Pause m a
= Pause { step :: m (Either (Pause m a) a) }
Wenn der Either Teil Right ist, es ist nur ein monadischen Wert, ohne Suspensionen. Dies führt uns, wie die easist Sache zu implementieren - die lift Funktion von MonadTrans:
instance MonadTrans Pause where
lift k = Pause (liftM Right k)
und mutate ist einfach eine Spezialisierung:
mutate :: (Monad m) => m() -> Pause m()
mutate = lift
Wenn der Either Teil Left ist, stellt es die fortgesetzte Berechnung nach einer Suspension. Lassen Sie sich also eine Funktion für das Erstellen:
suspend :: (Monad m) => Pause m a -> Pause m a
suspend = Pause . return . Left
Jetzt yield ing eine Berechnung einfach ist, wir nur mit einer leeren Berechnung auszusetzen:
yield :: (Monad m) => Pause m()
yield = suspend (return())
Dennoch sind wir den wichtigsten Teil fehlen. Die Monad Instanz. Lassen Sie uns es beheben. return Die Implementierung ist einfach, wir die innere Monade nur heben. Implementieren >>= ist ein bisschen schwieriger. Wenn der ursprüngliche Pause Wert nur ein einfacher Wert (Right y) war, dann wickeln wir nur f y als das Ergebnis. Wenn es sich um eine pausierte Berechnung ist, die fortgesetzt werden kann (Left p), steigen wir rekursiv hinein.
instance (Monad m) => Monad (Pause m) where
return x = lift (return x) -- Pause (return (Right x))
(Pause s) >>= f
= Pause $ s >>= \x -> case x of
Right y -> step (f y)
Left p -> return (Left (p >>= f))
Testing
Lasst uns versuchen, einige Modellfunktion zu machen, und Updates Zustand verwendet, wodurch man während in der Berechnung:
test1 :: Int -> Pause (State Int) Int
test1 y = do
x <- lift get
lift $ put (x * 2)
yield
return (y + x)
Und eine Hilfsfunktion, die die Monade debuggt - druckt seine Zwischenschritte die Konsole:
debug :: Show s => s -> Pause (State s) a -> IO (s, a)
debug s p = case runState (step p) s of
(Left next, s') -> print s' >> debug s' next
(Right r, s') -> return (s', r)
main :: IO()
main = do
debug 1000 (test1 1 >>= test1 >>= test1) >>= print
Das Ergebnis ist
2000
4000
8000
(8000,7001)
wie erwartet.
Koroutinen und Monade-Koroutine
Was wir implementiert haben, ist eine ganz allgemeine monadischen Lösung, die Coroutines implementiert. Vielleicht nicht überraschend, hatte jemand die Idee vor :-), und schaffte das monad-coroutine Paket. Weniger überraschend, es ist ziemlich ähnlich zu dem, was wir geschaffen haben.
Das Paket verallgemeinert die Idee noch weiter. Die fortlaufende Berechnung wird in einem beliebigen Funktor gespeichert. Dies ermöglicht suspend viele Variationen wie mit suspendierten Berechnungen zu arbeiten. Zum Beispiel, um pass a value an den Aufrufer von resume (die wir step genannt) oder wait for a value vorgesehen werden, um fortzufahren usw.
nicht mehr verrückt als jede andere 'Cont' Beispiel würde ich denken; stochern bei 'callCC'. – geekosaur
In der ersten Instanz würde ich versuchen, die freie Monade auf der Signatur zu konstruieren {muate :: (s -> s) ->(); Ausbeute ::() ->()}. – pigworker
GHC hatte eine Monade, die Sie könnten _resume_ (ResumeT), aber aus irgendeinem Grund verschwand es um Version 6.8, denke ich. –