Монада Пауза
Монады могут делать много удивительных, безумных вещей. Они могут создавать переменные, которые содержат суперпозицию значений. Они могут позволить вам получить доступ к данным из будущего, прежде чем вы их вычислите. Они могут позволить вам писать разрушительные обновления, но не совсем. И тогда монада продолжения позволяет сломать умы людей! Обычно твой собственный.;-)
Но вот проблема: вы можете сделать монаду, которая может быть приостановлена?
пауза данных s x Экземпляр Монады (Пауза с) mutate:: (s -> s) -> Пауза s () yield:: Pause s () step:: s -> Pause s () -> (s, может быть (Pause s ()))
Pause монада является своего рода государственной монадой (отсюда mutateс очевидной семантикой). Обычно такая монада имеет какую-то функцию "выполнения", которая выполняет вычисления и возвращает вам конечное состояние. Но Pause отличается: он обеспечивает step функция, которая выполняет вычисления, пока не вызовет магический yield функция. Здесь вычисление приостанавливается, возвращая вызывающей стороне достаточно информации, чтобы возобновить вычисление позже.
Для дополнительного удивления: позвольте вызывающему абоненту изменять состояние между step звонки. (Типовые подписи выше должны позволять это, например.)
Вариант использования: часто легко написать код, который делает что-то сложное, но всего PITA, чтобы преобразовать его, чтобы также вывести промежуточные состояния в его работе. Если вы хотите, чтобы пользователь мог что-то изменить в процессе выполнения, все очень быстро усложняется.
Идеи реализации:
Очевидно, что это можно сделать с помощью потоков, замков и
IO, Но можем ли мы сделать лучше?;-)Что-то безумное с продолжением монады?
Может быть, какая-то писательская монада, где
yieldпросто записывает текущее состояние, и тогда мы можем "притвориться"stepэто путем перебора состояний в журнале. (Очевидно, что это исключает изменение состояния между шагами, так как сейчас мы ничего не "приостанавливаем".)
6 ответов
Конечно; Вы просто позволяете любому вычислению либо заканчивать результатом, либо приостанавливать себя, давая действие, которое будет использоваться при возобновлении, вместе с состоянием в то время:
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 продолжение или добавление остальной части вычисления, которое должно быть выполнено на приостановке.
Примечание: что вы не предоставили себе прямой доступ к текущему состоянию 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 представляет выбор между изменением и уступкой. Любая сигнатура простых команд (взаимодействующих с миром в терминах значений, а не манипулирующих вычислениями) может быть превращена в функтор таким образом. Меня беспокоит то, что я должен сделать это вручную!
Это дает мне вашу монаду: свободную монаду над сигнатурой модифицируй и уступай.
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или это приводит к мутированию состояния.
Общий метод выглядит следующим образом: отделяйте команды (взаимодействующие в терминах значений) от управляющих операторов (манипулируя вычислениями); построить свободную монаду "деревьев стратегии" поверх сигнатуры команд (проворачивая ручку); реализовать операторы управления путем рекурсии по деревьям стратегий.
Точно не соответствует вашим типовым сигнатурам, но, безусловно, просто:
{-# 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
Примечание. Этот ответ доступен в виде грамотного файла на 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, Скорее всего, мы на правильном пути.
Финальная монада
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)
как и ожидалось.
Сопрограммы и монада-сопрограммы
Мы реализовали довольно общее монадическое решение, которое реализует сопрограммы. Возможно, неудивительно, что у кого-то была идея раньше:-), и он создал пакет monad-coroutine. Неудивительно, что это очень похоже на то, что мы создали.
Пакет обобщает идею еще дальше. Продолжающиеся вычисления хранятся внутри произвольного функтора. Это позволяет приостановить множество вариантов работы с приостановленными вычислениями. Например, чтобы передать значение вызывающей стороне резюме (которое мы назвали step) или дождаться предоставления значения для продолжения и т. д.
{-# 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, Вы можете комбинировать сопрограммы с другими монадами.
Связанный: Монада Prompt в http://themonadreader.files.wordpress.com/2010/01/issue15.pdf