连续抽象

Question

在基于此 article 的关于并发的一般练习中。

我们有：

-- a is the result type on which after we continue
type Continuation a = a-> Action

type ContinuationPseudoMonad a = Continuation a -> Action
-- pseudoMonad because it will need Concurrent wrapper Monad:
-- so as to define bind operation and return operation on it

data Concurrent a = Concurrent (ContinuationPseudoMonad a)

所以 Concurrent a 是一个单子，我们必须用它的两个强制性法则 return 和绑定来实现。

不幸的是，我找不到足够的词来更准确地定义 ContinuationPseudoMonad 东西......如果我缺乏词，我的头脑就缺乏抽象。

你怎么称呼它？

有没有一个词的意思是Continuation a -> Action而不是我那尴尬无意义的ContinuationPseudoMonad？

正在执行的操作：

data Action = Atom (IO Action)
            | Fork Action Action
            | Stop

Answer 1

你似乎在学习一些词汇，这是一个很难用词组表达的问题。让我们将您所拥有的分解为几个步骤，看看是否有帮助。

data Action = Atom (IO Action)
            | Fork Action Action
            | Stop

Action 是一个 代数数据类型 ，具有三个 构造函数 。它是一种 corecursive 数据类型，因为它是根据自身定义的。

type Continuation a = a -> Action

Continuation a 是 函数类型 a -> Action 的 类型别名 。这是一个 contravariant functor 的例子，因为我们可以定义一个函数

contramap :: (a -> b) -> Continuation b -> Continuation a
contramap aToB bToAction = aToAction 
  where aToAction = \a -> bToAction (aToB a)

注意反转 - contramap 采用函数 a -> b 并创建函数 Continuation b -> Continuation a。

type ContinuationPseudoMonad a = Continuation a -> Action

ContinuationPseudoMonad a是函数类型的另一种类型别名，但是由于Continuation a也是函数类型，所以ContinuationPseudoMonad a是高阶函数的一种类型，因为它接受一个函数作为参数。

ContinuationPseudoMonad a 也是一个函子，但它是一个 协变函子 ，因为我们可以定义一个函数 [=26] =]

fmap :: (a -> b) -> ContinuationPseudoMonad a -> ContinuationPseudoMonad b
fmap aToB aToActionToAction = bToActionToAction
  where bToActionToAction = \bToAction -> aToActionToAction (\a -> bToAction (aToB a))

Answer 2

很明显 Concurrent a 与 Cont Action a 相同，其中 Cont 是延续单子。这是对延续的简单解释：

考虑一些任意类型 a 和 b 的函数 f :: a -> b。我们想将此函数转换为连续传递样式。我们如何做到这一点？
假设我们有一个延续 k :: b -> r，它将 f 的 return 值作为输入，它本身 return 是一个任意类型的值 r.在此之后，我们可以将 f 转换为 CPS。
设g :: a -> (b -> r) -> r为f的CPS版本函数。请注意，它需要一个额外的参数（即延续 k）和 returns k 的结果应用于其输出 b.

我们举一个实际的例子，其中f是谓词函数odd :: Int -> Bool:

odd :: Int -> Bool
odd n = n `mod` 2 == 1

下面是用连续传递样式编写的相同函数：

odd' :: Int -> (Bool -> r) -> r
odd' n k = k (n `mod` 2 == 1)

(Bool -> r) -> r部分可以抽象出来作为continuation monad:

data Cont r a = Cont { runCont :: (a -> r) -> r }

odd' :: Int -> Cont r Bool
odd' n = return (n `mod` 2 == 1)

instance Monad (Cont r) where
    return a = Cont (\k -> k a)
    m  >>= f = Cont (\k -> runCont m (\a -> runCont (f a) k))

请注意，对于某些任意类型 r，延续 k 的类型是 Bool -> r。因此，continuation k 可以是任何以 Bool 作为参数的函数。例如：

cont :: Bool -> IO ()
cont = print

main :: IO ()
main = odd' 21 cont

但是，在 Concurrent 的情况下，这个 r 不是任意的。它专门用于 Action。实际上，我们可以将Concurrent定义为Cont Action的类型同义词，如下所示：

type Concurrent = Cont Action

现在，我们不需要为 Concurrent 实现 Monad 实例，因为它与上面定义的 Cont r 的 Monad 实例相同。

runConcurrent :: Concurrent a -> ContinuationPseudoMonad a
runConcurrent (Concurrent g) = g

instance Monad Concurrent where
    return a = Concurrent (\k -> k a)
    m  >>= f = Concurrent (\k -> runConcurrent m (\a -> runConcurrent (f a) k))

请注意，在 instance Monad Concurrent 的定义中，我们没有使用 Action。那是因为 Concurrent = Cont Action 和 Cont r 的 monad 实例透明地使用 r。

连续抽象

Continuation abstraction

haskell

abstraction