Примечания: Этот ответ available как грамотный файл 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 transformer. Кроме того, подпись 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. Менее удивительно, это очень похоже на то, что мы создали.
Пакет обобщает эту идею еще дальше. Продолжающееся вычисление хранится внутри произвольного функтора. Это позволяет suspend много вариантов работы с приостановленными вычислениями. Например, чтобы pass a value к вызывающему resume (который мы назвали step), или к wait for a value быть предусмотрено, чтобы продолжить и т.д.
Нет более безумен, чем любой другой 'Cont' Например, я думаю; ткнуть в 'callCC'. – geekosaur
В первом случае я попытался бы построить свободную монаду на сигнатуре {mutate :: (s -> s) ->(); yield ::() ->()}. – pigworker
У GHC была монада, которую вы могли бы _resume_ (ResumeT), но по какой-то причине она исчезла около версии 6.8. Думаю. –