Haskell: ¿Qué mónada acabo de reinventar?

Question

Acabo de reinventar alguna mónada, pero no estoy seguro de cuál. Le permite modelar los pasos de un cálculo, por lo que puede intercalar los pasos de numerosos cálculos para encontrar cuál termina primero.

{-# LANGUAGE ExistentialQuantification #-} 
module Computation where 

-- model the steps of a computation 
data Computation a = forall b. Step b (b -> Computation a) | Done a 

instance Monad Computation where 
    (Step b g) >>= f = Step b $ (>>=f) . g 
    (Done b) >>= f = Step b f 
    return = Done 

runComputation :: Computation a -> a 
runComputation (Step b g) = runComputation (g b) 
runComputation (Done a) = a 

isDone :: Computation a -> Bool 
isDone (Done _) = True 
isDone _ = False 

-- an order for a set of computations 
data Schedule a = a :> Computation (Schedule a) | Last 

toList :: Schedule a -> [a] 
toList Last = [] 
toList (a :> c) = a : (toList . runComputation) c 

-- given a set of computations, find a schedule to generate all their results 
type Strategy a = [Computation a] -> Computation (Schedule a) 

-- schedule all the completed computations, and step the rest, 
-- passing the remaining to the given function 
scheduleOrStep :: (Queue (Computation a) -> Computation (Schedule a)) -> Strategy a 
scheduleOrStep s cs = scheduleOrStep' id cs 
    where scheduleOrStep' q ((Done a):cs) = Done $ a :> scheduleOrStep' q cs 
     scheduleOrStep' q ((Step b g):cs) = scheduleOrStep' (q . (g b:)) cs 
     scheduleOrStep' q [] = s q 

-- schedule all completed compuations, step all the rest once, and repeat 
-- (may never complete for infinite lists) 
-- checking each row of 
-- [ [ c0s0, c1s0, c2s0, ... ] 
-- , [ c0s1, c1s1, c2s1, ... ] 
-- , [ c0s2, c1s2, c2s2, ... ] 
-- ... 
-- ] 
-- (where cNsM is computation N stepped M times) 
fair :: Strategy a 
fair [] = Done Last 
fair cs = scheduleOrStep (fair . ($[])) cs 

-- schedule more steps for earlier computations rather than later computations 
-- (works on infinite lists) 
-- checking the sw-ne diagonals of 
-- [ [ c0s0, c1s0, c2s0, ... ] 
-- , [ c0s1, c1s1, c2s1, ... ] 
-- , [ c0s2, c1s2, c2s2, ... ] 
-- ... 
-- ] 
-- (where cNsM is computation N stepped M times) 
diag :: Enqueue (Computation a)-> Strategy a 
diag _ [] = Done Last 
diag enq cs = diag' cs id 
    where diag' (c:cs) q = scheduleOrStep (diag' cs) (enq c q $ []) 
     diag' [] q = fair (q []) 

-- diagonal downwards : 
-- [ c0s0, 
-- c1s0, c0s1, 
-- c2s0, c1s1, c0s2, 
-- ... 
-- cNs0, c{N-1}s1, ..., c1s{N-1}, c0sN, 
-- ... 
-- ] 
diagd :: Strategy a 
diagd = diag prepend 

-- diagonal upwards : 
-- [ c0s0, 
-- c0s1, c1s0, 
-- c0s2, c1s1, c2s0, 
-- ... 
-- c0sN, c1s{N-1}, ..., c{s1N-1}, cNs0, 
-- ... 
-- ] 
diagu :: Strategy a 
diagu = diag append 

-- a queue type 
type Queue a = [a] -> [a] 
type Enqueue a = a -> Queue a -> Queue a 

append :: Enqueue a 
append x q = q . (x:) 

prepend :: Enqueue a 
prepend x q = (x:) . q 

Creo que esto es probablemente una especie de mónada de enhebrar?

Answer 1

Parece una mónada de reanudación con estado. Creo que solía haber una mónada de reanudación en MTL alrededor de GHC 6.6, pero si había desapareció. William Harrison de la Universidad de Missouri tiene una serie de documentos sobre la reanudación de las mónadas: http://people.cs.missouri.edu/~harrisonwl/publications.html

Answer 2

No he dedicado demasiado tiempo a comprender su código, pero realmente suena como la mónada de coronas del paquete de mónadas-coronas, que puede ser un poco más general.

Answer 3

Esto se parece a la definición de fusión de secuencias usada por Don Stewart hace un tiempo, y también algo relacionado con iterar (aunque sin la idea de insertar datos en iteratee usando un enumerador), pero menos que la fusión de secuencias Supongo.

Answer 4

No entiendo por qué no

data Computation a = Step (Computation a) | Done a 

instance Monad Computation where 
    (Step g) >>= f = Step $ g >>= f 
    (Done b) >>= f = Step (f b) 
    return = Done 

No estoy seguro de lo que esta mónada es, pero definitivamente es más simple y parece ser equivalente en muchos aspectos.