Монада паузы

примечание: что вы не предоставили себе прямого доступа к текущему состоянию s в этой монаде.

Pause s это просто свободная монада над mutate и yield операции. Реализовано непосредственно вы получаете:

data Pause s a
  = Return a
  | Mutate (s -> s) (Pause s a)
  | Yield (Pause s a)

instance Monad (Pause s) where
  return = Return
  Return a   >>= k = k a
  Mutate f p >>= k = Mutate f (p >>= k)
  Yield p    >>= k = Yield (p >>= k)

С помощью нескольких интеллектуальных конструкторов, чтобы дать вам нужный API:

mutate :: (s -> s) -> Pause s ()
mutate f = Mutate f (return ())

yield :: Pause s ()
yield = Yield (return ())

и шаг функции, чтобы управлять им

step :: s -> Pause s () -> (s, Maybe (Pause s ()))
step s (Mutate f k) = step (f s) k
step s (Return ()) = (s, Nothing)
step s (Yield k) = (s, Just k)

вы также можете определить это непосредственно с помощью

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

(из моего "бесплатный" пакет) с

data Op s a = Mutate (s -> s) a | Yield a

тогда у нас уже есть монада пауза

type Pause s = Free (Op s)

и просто нужно определить умные конструкторы и степпер.

что делает его быстрее.

теперь эти реализации легко рассуждать, но у них нет самой быстрой операционной модели. В частности, левое связанное использование ( > > = ) дает асимптотически более медленный код.

чтобы обойти это, вы можете применять в Codensity монада к вашей существующей свободной монаде, или просто используйте 'Свободной церкви' монада напрямую, оба из которых я подробно описываю в своем блоге.

http://comonad.com/reader/2011/free-monads-for-less/

http://comonad.com/reader/2011/free-monads-for-less-2/

http://comonad.com/reader/2011/free-monads-for-less-3/

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

вот как я бы это сделал, используя свободный монады. А что это такое? Это деревья с действиями в узлах и значениями в листьях, с >>= действуя как прививка деревьев.

data f :^* x
  = Ret x
  | Do (f (f :^* x))

это не редкость, чтобы написать F^*X для такой вещи в математике, отсюда мое капризное имя типа инфикса. Чтобы сделать экземпляр, вам просто нужно f чтобы быть чем-то, что вы можете сопоставить: любой Functor будет делать.

instance Functor f => Monad ((:^*) f) where
  return = Ret
  Ret x  >>= k  = k x
  Do ffx >>= k  = Do (fmap (>>= k) ffx)

это просто "применить k на всех листьях и прививках в полученных деревьях". Эти деревья могут представлять стратегии для интерактивных вычислений: все дерево охватывает все возможные взаимодействия с окружающей средой, и среда выбирает, какой путь в дереве следовать. Почему они свободный? Это просто деревья, на которых нет интересной эквационной теории, говорящей, какие стратегии эквивалентны другим стратегиям.

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

data (:>>:) s t x = s :? (t -> x)

instance Functor (s :>>: t) where
  fmap k (s :? f) = s :? (k . f)

захватывает идею получения значения в x после один команда с типом ввода s и выход типа t. Для этого вам нужно выбрать вход в s и объясните, как продолжить значение в x учитывая вывод команды в t. Чтобы отобразить функцию через такую вещь, вы прикрепляете ее к продолжению. Так далеко, стандартное оборудование. Для нашей задачи теперь мы можем определить два функтора:

type Modify s  = (s -> s) :>>: ()
type Yield     = () :>>: ()

это похоже на то, что я только что записал типы значений для команд, которые мы хотим сделать!

теперь давайте убедимся, что мы можем предложить выбор между этими командами. Мы можем показать, что выбор между функторами дает функтор. Более стандартное оборудование.

data (:+:) f g x = L (f x) | R (g x)

instance (Functor f, Functor g) => Functor (f :+: g) where
  fmap k (L fx) = L (fmap k fx)
  fmap k (R gx) = R (fmap k gx)

и Modify s :+: Yield представляет выбор между модификацией и получением. Любой подпись простых команд (общаясь с миром в терминах значений, а не манипулируя вычислениями) можно превратить в функтор таким образом. Это проблема, что я должен сделать это вручную!

это дает мне вашу монаду: свободную монаду над подписью modify и yield.

type Pause s = (:^*) (Modify s :+: Yield)

я могу определить команды modify и yield как one-do-then-return. Помимо согласования фиктивного ввода для yield, вот только механический.

mutate :: (s -> s) -> Pause s ()
mutate f = Do (L (f :? Ret))

yield :: Pause s ()
yield = Do (R (() :? Ret))

The step функция затем дает значение деревьям стратегий. Это же пульт управления, построение одного вычисления (возможно) из другого.

step :: s -> Pause s () -> (s, Maybe (Pause s ()))
step s (Ret ())            = (s, Nothing)
step s (Do (L (f  :? k)))  = step (f s) (k ())
step s (Do (R (() :? k)))  = (s, Just (k ()))

The step функция запускает стратегию до тех пор, пока она не завершится с Ret, или он уступает, мутируя состояние по мере его прохождения.

общий метод выглядит так: отделите команды (взаимодействуя в терминах значений) от операторы управления (манипулирование вычислениями); построить свободную монаду "деревьев стратегий" над сигнатурой команд (проворачивание дескриптора); реализовать операторы управления рекурсией над деревьями стратегий.

не соответствует вашим сигнатурам типа точно, но, конечно, просто:

{-# LANGUAGE FlexibleInstances, MultiParamTypeClasses, UndecidableInstances #-}
import Control.Monad.State

newtype ContinuableT m a = Continuable { runContinuable :: m (Either a (ContinuableT m a)) }
instance Monad m => Monad (ContinuableT m) where
    return = Continuable . return . Left
    Continuable m >>= f = Continuable $ do
        v <- m
        case v of
            Left  a -> runContinuable (f a)
            Right b -> return (Right (b >>= f))

instance MonadTrans ContinuableT where
    lift m = Continuable (liftM Left m)

instance MonadState s m => MonadState s (ContinuableT m) where
    get = lift get
    put = lift . put

yield :: Monad m => ContinuableT m a -> ContinuableT m a
yield = Continuable . return . Right

step :: ContinuableT (State s) a -> s -> (Either a (ContinuableT (State s) a), s)
step = runState . runContinuable

-- mutate unnecessary, just use modify

{-# LANGUAGE TupleSections #-}
newtype Pause s x = Pause (s -> (s, Either x (Pause s x)))

instance Monad (Pause s) where
  return x = Pause (, Left x)

  Pause k >>= f = Pause $ \s -> let (s', v) = k s in
                                case v of
                                  Left x -> step (f x) s'
                                  Right x -> (s', Right (x >>= f))

mutate :: (s -> s) -> Pause s ()
mutate f = Pause (\s -> (f s, Left ()))

yield :: Pause s ()
yield = Pause (, Right (return ()))

step :: Pause s x -> s -> (s, Either x (Pause s x))
step (Pause x) = x

вот как бы я это написал. Я дал step немного более общее определение, оно может быть также Назван runPause. Фактически думая о типе step приведите меня к определению Pause.

на монады-сопрограмма пакет вы найдете общий трансформатор монады. Элемент Pause s монада-это то же самое, что Coroutine (State s) Id. Вы можете комбинировать сопрограммы с другими монадами.

связанный: подсказка монады в http://themonadreader.files.wordpress.com/2010/01/issue15.pdf

Примечание: этот ответ скачать как грамотный файл Haskell в Gist.

мне очень понравилось это упражнение. Я пытался сделать это, не глядя на ответы, и это того стоило. Это заняло у меня значительное время, но результат удивительно близок к двум другим ответам, а также к монады-сопрограмма библиотека. Поэтому я думаю, что это несколько естественное решение этой проблемы. Без этого упражнения я бы не понял как монады-сопрограмма действительно работает.

чтобы добавить некоторую дополнительную ценность, я объясню шаги, которые в конечном итоге привели меня к решению.

признание государственной монады

поскольку мы имеем дело с состояниями, мы ищем шаблоны, которые могут быть эффективно описаны монадой состояния. В частности, s - s изоморфна s -> (s, ()), так что его можно заменить на State s (). И функция типа s -> x -> (s, y) можно перевернуть на x -> (s -> (s, y)), что на самом деле x -> State s y. Это приводит нас к обновленным подписям

mutate :: State s () -    Pause s ()
step   :: Pause s () -    State s (Maybe (Pause s ()))

обобщение

наши Pause монады в настоящее время осуществляется за счет государства. Однако теперь мы видим, что государство нам ни для чего не нужно, и мы не используем никакой специфики государственной монады. Поэтому мы могли бы попытаться сделать более общее решение, которое параметризуется любой монадой:

mutate :: (Monad m) =    m () -> Pause m ()
yield  :: (Monad m) =    Pause m ()
step   :: (Monad m) =    Pause m () -> m (Maybe (Pause m ()))

кроме того, мы могли бы попытаться сделать mutate и step более общий, позволяя любой вид значения, а не только (). И осознав это Maybe a изоморфна Either a () мы можем, наконец, обобщить наши подписи на

mutate :: (Monad m) =    m a -> Pause m a
yield  :: (Monad m) =    Pause m ()
step   :: (Monad m) =    Pause m a -> m (Either (Pause m a) a)

, так что step возвращает промежуточное значение вычисления.

монады трансформатор

Итак, мы видим, что мы на самом деле пытаемся сделать монада из монад - добавить некоторые дополнительные функции. Это то, что обычно называют монады трансформатор. Более того,mutateподпись точно такая же, как лифт С MonadTrans. Скорее всего, мы на правильном пути.

последняя монада

The step функция кажется самой важной частью нашей монады, она определяет только то, что нам нужно. Возможно, это может быть новая структура данных? Давайте попробуем:

import Control.Monad
import Control.Monad.Cont
import Control.Monad.State
import Control.Monad.Trans

data Pause m a
    = Pause { step :: m (Either (Pause m a) a) }

если Either часть Right, это просто монадическое значение, без любой приостановления. Это приводит нас к тому, как реализовать easist вещь -lift функция от MonadTrans:

instance MonadTrans Pause where
    lift k = Pause (liftM Right k)

и mutate - это просто специализация:

mutate :: (Monad m) => m () -> Pause m ()
mutate = lift

если Either часть Left, он представляет собой продолжение вычислений после перерыва. Так что давайте создадим функцию для этого:

suspend :: (Monad m) => Pause m a -> Pause m a
suspend = Pause . return . Left

теперь yielding вычисление просто, мы просто приостанавливаем с пустым вычисление:

yield :: (Monad m) => Pause m ()
yield = suspend (return ())

тем не менее, мы не хватает самой важной части. Элемент Monad экземпляра. Давайте исправим оно. Реализация return просто, мы просто поднимаем внутреннюю монаду. Реализация >>= немного сложнее. Если оригинал Pause значение было только простым значением (Right y), то мы просто обернуть f y как результат. Если это приостановленное вычисление, которое можно продолжить (Left p), мы рекурсивно спускаемся в него.

instance (Monad m) => Monad (Pause m) where
    return x = lift (return x) -- Pause (return (Right x))
    (Pause s) >>= f
        = Pause $ s >>= \x -> case x of
            Right y     -> step (f y)
            Left p      -> return (Left (p >>= f))

тестирование

давайте попробуем сделать некоторые модели функции что использует и обновляет состояние, уступая в то время как внутри расчета:

test1 :: Int -> Pause (State Int) Int
test1 y = do
            x <- lift get
            lift $ put (x * 2)
            yield
            return (y + x)

и вспомогательная функция, которая отлаживает монаду-выводит ее промежуточные шаги консоль:

debug :: Show s => s -> Pause (State s) a -> IO (s, a)
debug s p = case runState (step p) s of
                (Left next, s')     ->  print s' >> debug s' next
                (Right r, s')       ->  return (s', r)    

main :: IO ()
main = do
    debug 1000 (test1 1 >>= test1 >>= test1) >>= print

результат

2000
4000
8000
(8000,7001)

как и ожидалось.

сопрограммы и монады-сопрограмма

то, что мы реализовали, является довольно общим монадическим решением, которое реализует сопрограммы. Возможно неудивительно, что у кого-то была идея раньше: -), и создал монады-сопрограмма пакета. Менее удивительно, что это очень похоже на то, что мы создали.

пакет обобщает идею еще дальше. Непрерывное вычисление хранится внутри произвольного функтора. Это позволяет приостановить много вариантов, как работать с приостановленными вычислениями. Например, к передать значение функции резюме (который мы называется step), или дождитесь значения для продолжения и т. д.