Существует ли стандартная абстракция для этого типа запроса-ответа?

Question

У меня есть следующий вид:

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

Идея заключается в том, чтобы использовать его в качестве чистого представления для сети связи, то есть:

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

, которые затем будут оценены по некоторым нечистым функции eval.

Теперь, что это (если что?) Это не монада, ни стрелка, насколько я могу видеть. Кажется, что-то между потоком/трубой/автоматом/fsm и продолжением монады. Это заставляет меня думать, что может быть лучшее представление для этого типа вещей, но что?

Answer 1

Это Free Monad. Идея состоит в том, что у вас есть описание инструкций, для которых у вас может быть несколько интерпретаторов, например, ваша функция eval. Бесплатные рефераты 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 является монадой, что означает, что теперь вы можете создавать свои respond и interact функции, используя Monad API.

Есть еще кое-что. В respond и interact функции могут быть получены с использованием шаблона Haskell со следующим дополнительным кодом:

{-# LANGUAGE TemplateHaskell #-} 

import Control.Monad.Free.TH 

makeFree ''Instruction 

Answer 2

Ваш тип выглядит немного как Apfelmus's operational monad, также известный как 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, которые используют свой параметр типа, чтобы указать «тип возврата» выполнения этой команды в интерпретаторе. Конструктор Bind принимает инструкцию и продолжение, которое может быть запущено после получения результата от интерпретатора. Обратите внимание, как a экзистенциально квантуется, что отражает тот факт, что типы всех промежуточных шагов в вычислении не относятся к общему типу.

Важное различие между Program и вашим типом заключается в том, что тип ответа определяется инструкцией, а не фиксируется по всему вычислению. Это позволяет нам делать более мелкие гарантии относительно ответа, который каждый запрос ожидает спровоцировать.

Например, вот состояние монады написано как 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 

Совместно Йонеды лемма говорит нам, что Program изоморфна Free. Интуитивно, это бесплатная монада, основанная на ->Functor экземпляре.Для некоторых операций, таких как левоассоциативные связки, Program может быть более эффективным, чем Free, поскольку его >>= основан на функциональном составе, а не, возможно, на дорогостоящем fmap ping произвольным Functor.