Haskell: quale monade ho appena reinventato?

Question

Ho appena reinventato un po 'di monade, ma non sono sicuro di quale. Permette di modellare le fasi di un calcolo, in modo da poter interlacciare i passaggi di numerosi calcoli per trovare quale finisce per primo.

{-# 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 

Mi sento come questo è probabilmente un qualche tipo di filettatura monade?

Answer 1

Sembra una monade di ripresa con stato. Penso che ci fosse una monade di ripresa in MTL intorno a GHC 6.6 ma se fosse scomparso. William Harrison presso l'Università del Missouri ha un numero di articoli sulle monadi di ripresa - http://people.cs.missouri.edu/~harrisonwl/publications.html

Answer 2

Non ho speso troppo tempo a capire il tuo codice, ma suona davvero come il monogramma di coroutine dal pacchetto monade-coroutine, che può essere un po 'più generico

Answer 3

Questo è simile alla definizione di fusione di flusso utilizzata da Don Stewart qualche tempo fa, ed è anche in qualche modo correlato agli iterate (sebbene non includa la spinta di dati nell'iterazione utilizzando un enumeratore), ma meno della fusione di flussi Suppongo.

Answer 4

non capisco perché non

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 

Non sono sicuro di ciò che questo monade è, ma è sicuramente più semplice e sembra essere equivalente sotto molti aspetti.