Монастырь Пауза

Ответ 1

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

data Pause s a = Pause { runPause :: s -> (PauseResult s a, s) }

data PauseResult s a
    = Done a
    | Suspend (Pause s a)

instance Monad (Pause s) where
    return a = Pause (\s -> (Done a, s))
    m >>= k = Pause $ \s ->
        case runPause m s of
            (Done a, s') -> runPause (k a) s'
            (Suspend m', s') -> (Suspend (m' >>= k), s')

get :: Pause s s
get = Pause (\s -> (Done s, s))

put :: s -> Pause s ()
put s = Pause (\_ -> (Done (), s))

yield :: Pause s ()
yield = Pause (\s -> (Suspend (return ()), s))

step :: Pause s () -> s -> (Maybe (Pause s ()), s)
step m s =
    case runPause m s of
        (Done _, s') -> (Nothing, s')
        (Suspend m', s') -> (Just m', s')

Экземпляр Monad просто упорядочивает вещи обычным способом, передавая окончательный результат в продолжение k или добавляя оставшуюся часть вычисления, которое нужно сделать при приостановке.

Ответ 2

Примечание: вы не предоставили себе прямой доступ к текущему состоянию 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 к вашей существующей свободной монаде или просто использовать 'Church free' monad, оба из которых я подробно описываю в своем блоге.

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/

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

Ответ 3

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

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

Нет ничего необычного в том, чтобы писать F ^* X для такой вещи в математике, следовательно, имя моего cranky infix. Чтобы создать экземпляр, вам просто нужно 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 представляет собой выбор между модификацией и уступкой. Любая подпись простых команд (связь с миром в терминах значений, а не манипулирование вычислениями) может быть превращена в функтор таким образом. Это беспокоит, что я должен сделать это вручную!

Это дает мне вашу монаду: свободную монаду над сигнатурой изменения и урона.

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

Я могу определить команды изменения и вывода как однократные, а затем возвратные. Помимо согласования фиктивного ввода для yield, это просто механическое.

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

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

Затем функция 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 ()))

Функция step запускает стратегию до тех пор, пока она не завершится с помощью Ret, или это приведет к мутированию состояния по мере его появления.

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

Ответ 4

Не соответствует вашим типом подписей точно, но, безусловно, просто:

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

Ответ 5

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

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

Связано: приглашение монады в http://themonadreader.files.wordpress.com/2010/01/issue15.pdf

Ответ 6

Примечание. Этот ответ доступен как грамотный файл Haskell в Gist.

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

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

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

Поскольку мы имеем дело с состояниями, мы ищем шаблоны, которые могут быть эффективно описаны государственной монадой. В частности, 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 возвращает промежуточное значение вычисления.

Трансформатор Monad

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

Конечная монада

Функция 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, это просто монадическое значение, без каких-либо суспензии. Это приводит нас к тому, как реализовать упрощенную вещь - 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

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

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)

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

Coroutines и monad-coroutine

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

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