Монада продолжения для функции yield/await в Haskell

Я хочу создать тип автомата с таким типом:

newtype Auto i o = Auto {runAuto :: i -> (o, Auto i o)}

Я знаю, что это тип стрелы автоматов, но я не ищу стрелку. Я хочу сделать это монадой, так что, вероятно, у нее будет такой тип

newtype Auto i o a = ???? What goes here?

с такой функцией:

yield :: o -> Auto i o i

Поэтому, когда я вызываю "yield" из монады "Авто", функция "runAuto" возвращает пару, состоящую из аргумента "yield" и функции продолжения. Когда прикладная программа вызывает функцию продолжения, аргумент затем возвращается в монаде как результат "yield".

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

Я также знаю, что это скорее напоминает монаду Майкла Сноймана "Проводник", за исключением того, что он разделяет "урожайность" и "ожидание". Эта монада должна иметь ровно один выход для каждого входа.

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

редактировать

Все это оказалось не совсем правильным. Я написал код, предложенный Петром Пудлаком в его ответе, и он, похоже, сработал, но операция "yield" всегда давала вывод из предыдущего результата. Который был странным.

После долгого взгляда на экран я наконец понял, что мне нужен код, вставленный здесь. Принципиальное отличие заключается в типе AutoF. Сравните приведенную ниже с предложенной Петром.

import Control.Applicative
import Control.Monad
import Control.Monad.IO.Class
import Control.Monad.State.Class
import Control.Monad.Trans.Class
import Control.Monad.Trans.Free
import Data.Void

class (Monad m) => AutoClass i o m | m -> i, m -> o where
   yield :: o -> m i

data AutoF i o a = AutoF o (i -> a)

instance Functor (AutoF i o) where
   fmap f (AutoF o nxt) = AutoF o $ \i -> f $ nxt i

newtype AutoT i o m a = AutoT (FreeT (AutoF i o) m a)
   deriving (Functor, Applicative, Monad, MonadIO, MonadTrans, MonadState s)

instance (Monad m) => AutoClass i o (AutoT i o m) where
   yield v = AutoT $ liftF $ AutoF v id

runAutoT :: (Monad m) => AutoT i o m Void -> m (o, i -> AutoT i o m Void)
runAutoT (AutoT step) = do
   f <- runFreeT step
   case f of
      Pure v -> absurd v
      Free (AutoF o nxt) -> return (o, AutoT . nxt)


-- Quick test
--
-- > runTest testStart
testStart :: Int -> AutoT Int Int IO Void
testStart x = do
   liftIO $ putStrLn $ "My state is " ++ show x
   y <- liftIO $ do
      putStrLn "Give me a number: "
      read <$> getLine
   v1 <- yield $ x + y
   liftIO $ putStrLn $ "I say " ++ show v1
   v2 <- yield $ 2 * v1
   testStart v2

runTest auto = do
   putStrLn "Next input:"
   v1 <- read <$> getLine
   (v2, nxt) <- runAutoT $ auto v1
   putStrLn $ "Output = " ++ show v2
   runTest nxt
Источник

2 ответа

Решение

Вы могли бы расширить свой автомат в духе Conduit то есть, позволить ему выйти и вернуть значение на конечном количестве входов:

data Auto i o a
    = Step (i -> (o, Auto i o a))
    | End a

Затем вы можете определить экземпляр монады, который объединяет два автомата, используя >>=: Когда первый заканчивается, второй продолжается.

Хорошей новостью является то, что вам не нужно реализовывать это самостоятельно. Возврат значения или вложение с использованием функтора - это именно то, что делает свободная монада (см. Документацию по пикше). Итак, давайте определимся

{-# LANGUAGE DeriveFunctor #-}
import Control.Monad.Free
import Data.Void

-- | A functor describing one step of the automaton
newtype AutoF i o t = AutoF (i -> (o, t))
  deriving (Functor)

Тогда оригинал Auto Тип может быть определен как псевдоним:

type Auto i o = Free (AutoF i o)

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

-- | If @a@ is 'Void', the machine runs forever:
runAuto :: Auto i o Void -> i -> (o, Auto i o Void)
runAuto (Pure v)  _         = absurd v
runAuto (Free (AutoF f)) i  = f i

yield :: o -> Auto i o ()
yield x = liftF (AutoF $ \_ -> (x, ()))

Обратите внимание, что использование того же функтора с FreeT Вы получаете соответствующий монадный трансформатор:

import Control.Monad.Trans.Free

type AutoT i o = FreeT (AutoF i o)

yieldT :: (Monad m) => o -> AutoT i o m ()
yieldT x = liftF (AutoF $ \_ -> (x, ()))

...
Источник

Этот тип - машина Мили. См. https://hackage.haskell.org/package/machines-0.5.1/docs/Data-Machine-Mealy.html для нескольких примеров - но обратите внимание, что Monad экземпляр всегда будет медленным, потому что он требует диагонализации по законам монады.

Похоже, что вы действительно хотите, это автоматический пакет в любом случае.

Источник
Другие вопросы по тегам