Haskell：我刚刚重新发明了什么单子？

Question

我刚刚重新发明了一些单子，但我不确定是哪一个。它可以让您对计算步骤进行建模，这样您就可以交错进行大量计算的步骤来找出哪个步骤先完成。

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

我觉得这可能是某种线程单子？

Answer 1

它看起来像一个带有状态的恢复单子。我认为 GHC 6.6 左右的 MTL 中曾经有一个恢复单子，但如果有的话它就消失了。 William L. Harrison 有许多关于恢复 monad 的论文，包括 廉价（但功能性）线程 和 多任务处理的本质。

Answer 2

我不明白为什么不

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

我不确定这个 monad 是什么，但它肯定更简单，并且在大多数方面似乎是等效的。

Answer 3

我没有花太多时间理解你的代码，但它听起来确实像 monad-coroutine 包中的协程 monad，这可能更通用一些。

Answer 4

这看起来类似于 Don Stewart 不久前使用的流融合的定义，并且也与 iteratee 相关（尽管没有使用枚举器将数据推送到 iteratee 的概念），但我猜比流融合要少。

Answer 5

注意 Free monad 构造

data Free f a = Pure a | Free (f (Free f a))

因此，我们可以写

data ComputationF a = forall b. ComputationF b (b -> a)
type Computation = Free ComputationF