Haskell：我剛剛改造了哪個monad？

Question

我剛剛重新發明了一些monad，但我不確定哪一個。它可以讓你對一個計算的步驟進行建模，這樣你就可以交錯計算大量的步驟，找出哪一步先完成。

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

我覺得這可能是某種線程monad？

Answer 1

它看起來像一個恢復狀態monad。我認爲在GHC 6.6周圍的MTL中曾經有過恢復單元，但是如果它消失的話。密蘇里大學的William Harrison有許多關於恢復單子的文章 - http://people.cs.missouri.edu/~harrisonwl/publications.html

Answer 2

我沒花太多時間來理解你的代碼，但它聽起來像monad-coroutine包中的協程monad，它可能有點更一般。

Answer 3

這看起來與Don Stewart先前使用的流融合的定義類似，也與迭代有些相關（儘管沒有使用枚舉器將數據推入迭代器的概念），但不如流合成我猜。

Answer 4

我不明白爲什麼不

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 

我不知道這個單子是什麼，但它絕對簡單，似乎是在許多方面等價的。