这种请求-响应类型是否有标准的抽象？

Question

我有以下类型：

data S req rsp = Done rsp | Next req (rsp -> S req rsp)

想法是将其用作网络通信的纯粹表示，即：

... Next GetUser $ \uid -> Next (Login uid) $ \success -> Done success

然后将由一些不纯函数求值 eval。

现在，这是什么（如果有的话？）据我所知，它不是单子，也不是箭头。它似乎介于 stream/pipe/automaton/fsm 和延续 monad 之间。这让我觉得对于这类事情可能有更好的表现形式，但是什么？

Answer 1

是Free Monad。这个想法是你有一个指令的描述，你可以有多个解释器，比如你的 eval 函数。 Free Monad 抽象了该任务所具有的模式。有关详细信息，我建议 this great post。

要使您的类型适应 Free，我们可以执行以下操作：

{-# LANGUAGE DeriveFunctor #-}

import Control.Monad.Free

data Instruction req rsp next =
  Respond rsp |
  Interact req (rsp -> next)
  deriving (Functor)

type S req rsp =
  Free (Instruction req rsp)

respond :: rsp -> S req rsp ()
respond rsp =
  liftF (Respond rsp)

interact :: req -> S req rsp rsp
interact req =
  liftF (Interact req id)

现在，感谢 Free，S req rsp 是一个 monad，这意味着您现在可以使用 Monad 组合 respond 和 interact 函数API.

还有更多。 respond 和 interact 函数可以使用模板 Haskell 和以下额外代码生成：

{-# LANGUAGE TemplateHaskell #-}

import Control.Monad.Free.TH

makeFree ''Instruction

Answer 2

你的类型有点像Apfelmus's operational monad, also known as the Freer monad:

data Program inst a where
    Return :: a -> Program inst a
    Bind :: inst a -> (a -> Program inst b) -> Program inst b

instance Monad (Program inst) where
    return = Return
    Return x >>= f = f x
    Bind i next >>= f = Bind i (fmap (>>= f) next)

-- plus the usual Functor and Applicative boilerplate

Program :: (* -> *) -> * -> * 表示一系列指令 inst，它们使用它们的类型参数来指示运行的 "return type"在解释器中执行该指令。 Bind 构造函数在从解释器接收到指令结果后接受一条指令和一个可以是运行的延续。请注意 a 是如何量化的，反映了计算中所有中间步骤的类型与整体类型无关的事实。

Program 和您的类型之间的重要区别在于，响应的类型由指令决定，而不是在整个计算过程中固定不变。这使我们能够对每个请求期望引起的响应做出更细粒度的保证。

例如，这里的状态 monad 写成 Program:

data StateI s r where
    Get :: StateI s s
    Put :: s -> StateI s ()

type State s = Program (StateI s)

get :: State s s
get = Bind Get Return
put :: s -> State s ()
put s = Bind (Put s) Return

modify :: (s -> s) -> State s ()
modify f = do
    x <- get
    put (f x)

runState :: State s a -> s -> (s, a)
runState (Return x) s = (s, x)
runState (Bind Get next) s = runState (next s) s
runState (Bind (Put s) next) _ = runState (next ()) s

co-Yoneda 引理告诉我们 Program 同构于 Free。直觉上，它是一个基于 -> 的 Functor 实例的免费 monad。对于像左关联绑定这样的某些操作，Program 比 Free 更有效，因为它的 >>= 基于函数组合，而不是可能昂贵的 fmapping 一个任意 Functor.

这种请求-响应类型是否有标准的抽象？

Is there a standard abstraction for this request-response type?

haskell

monads

continuations

arrows

haskell-pipes