Haskell: Как написать интерактивный переводчик поверх государственной монады?

Question

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

class Monad m => FS m where
  isDirectory  :: Path -> m Bool
  children     :: Path -> m [Path]
  ...

Мы работаем над небольшим интерактивным интерпретатором, который будет предлагать такие команды, как cd, ls, cat и так далее.Операция в интерпретаторе может быть записана следующим образом:

fsop :: FS m => Operation -> m Response

Определения Operation и Response не важны;если хотите, считайте их строками.

Проблема, которую я пытаюсь решить , состоит в том, чтобы написать цикл верхнего уровня в монаде ввода-вывода, который интерпретирует файловую систему Operation s.и печатает ответы.Если бы IO был экземпляром FS (то есть, если бы мы работали непосредственно с монадой IO), жизнь была бы простой: мы могли бы написать

loop :: Path -> IO ()
loop currentDir = do
        op <- getLine
        case read op of
          ChangeDir d -> loop d -- should test 'isDirectory d', but let's not
          Ls -> do { files <- children currentDir
                   ; mapM_ putStrLn files
                   ; loop currentDir }
          Exit -> return ()

Но это не то, что я хочу.Я хочу использовать Control.Monad.State:

newtype Filesystem a = Filesystem (State (Data.Map.Map Path Contents) a)

и объявить

instance Monad Filesystem ...
instance FS Filesystem ...

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

step :: FS fs => Path -> Operation -> fs (Path, Response)
step currentDir op = 
        case op of
          ChangeDir d -> return (d, "")
          Ls -> do { files <- children currentDir
                   ; return (currentDir, unlines files) }

На данный момент я полностью застрял. Что я хочу сделать, это написать интерактивный цикл в IOмонада, которая может читать Operation с и печатать Response с, но которая работает на монаде состояния, которая не обязательно IO.(Одна из причин наличия модели, которая не находится в IO, заключается в том, что мы можем тестировать свойства QuickCheck.)

Мне кажется, что это должна быть стандартная проблема - интерактивный цикл read-eval-print onвершина абстракции с состоянием, которая не IO - но я, должно быть, упускаю что-то невероятно очевидное, потому что я не могу понять это.Я смотрел в Интернете, но не был просвещен.

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

Answer 1

А как насчет использования монадных трансформаторов?Это более или менее стандартный способ объединения монад.Вот упрощенный пример:

type Foo a = StateT String IO a

replT :: Foo ()
replT = do
  str   <- liftIO getLine
  state <- get
  liftIO $ putStrLn ("current state: " ++ state)
  liftIO $ putStrLn ("setting state: " ++ str)
  put str
  replT

Ниже приведены результаты запуска replT из ghci.

*Main> runStateT replT "Initial state"
asd
current state: Initial state
setting state: asd
zxc
current state: asd
setting state: zxc
asdasd

Есть три библиотеки монадных трансформаторов.MTL, трансформаторы и монадЛиб.Я не могу порекомендовать ни одного из них, так как не пользуюсь ими много.

Answer 2

Отказ от ответственности : Я не могу обещать, что это хороший способ сделать это, но работа над этим звучит весело .Давайте возьмем это для вращения, не так ли?

---

Несколько обязательных импортов

Сначала давайте отбросим некоторые типы данных.Я собираюсь заполнить некоторые детали и немного доработать, чтобы определить простую «файловую систему», с которой мы можем реально взаимодействовать.

type Path = String
type Response = Maybe String
type Contents = [String]

data Operation = Cd Path 
               | Ls 
               | MkDir Path
               | Quit
    deriving (Read, Show)

Далее, мы сделаем что-то немного острый ... убери все монады.Какие?Это безумие!Возможно, но иногда вся скрытая сантехника, которую обеспечивает >>=, скрывает вещи немного слишком очень.

Для самой файловой системы мы просто сохраним текущий рабочий каталог и карту путей к их дочерним элементам.Нам также понадобится несколько функций для взаимодействия с ним.

data Filesystem = Filesystem { wd :: Path, files :: M.Map Path Contents }
    deriving Show

newFS = Filesystem "/" (M.singleton "/" [])

isDirectory p fs = M.member p $ files fs
children p fs = fromMaybe [] . M.lookup p $ files fs
cd p fs = fs { wd = p }
create p fs = let newPath = wd fs ++ p ++ "/"
                  addPath = M.insert newPath [] . M.adjust (p:) (wd fs)
              in (newPath, fs { files = addPath $ files fs })

Теперь для безмонадной версии функции step.Нужно взять Operation и Filesystem и вернуть Response и (возможно измененный) Filesystem:

step :: Operation -> Filesystem -> (Response, Filesystem)
step (Cd d) fs = (Just "Ok\n", cd d fs)
step (MkDir d) fs = first (\d -> Just $ "Created " ++ d ++ "\n") $ create d fs
step Ls fs = let files = children (wd fs) fs
             in (Just $ unlines files, fs)
step Quit fs = (Nothing, fs)

... хмм, эта сигнатура типа уже выглядит какочень похоже на смелость State монады.Ну что ж, просто пока проигнорируйте это и начните действовать вслепую.

Теперь нам нужна функция, которая предоставит универсальный интерфейс для интерпретатора Filesystem.В частности, мы хотим, чтобы интерфейс был, по крайней мере, несколько самодостаточным , чтобы при любом использовании интерфейса не приходилось переходить вручную, но мы хотим, чтобы интерфейс был достаточно незаметным для кода, использующего его, которыймы можем связать его с IO монадой, какой-то другой Monad или даже без монады вообще.

В первую очередь это говорит нам о том, что нам нужно каким-то образом чередовать внешний код с интерпретатором , вместо того чтобы контролировать какую-либо часть.Теперь Haskell - это функциональный язык , так что это означает, что использование множества функций высшего порядка - это хорошо, верно?Звучит правдоподобно для меня, поэтому вот стратегия, которую мы будем использовать: Если функция не знает, что делать дальше, мы передадим ей другую функцию, которую мы предполагаем, делает. Повторяйте, пока все не будут знать, что происходитна.Безупречный план, не так ли?

Сердце всего этого - функция step, поэтому мы начнем с того, что просто позвоним.

interp1 :: Operation -> Filesystem -> (Response, Filesystem)
interp1 op fs = step op fs

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

interp2 :: ((Operation -> (Response, Filesystem)) -> t) -> Filesystem -> t
interp2 inp fs = inp (\op -> step op fs)

Конечно, теперь у нас есть только одна глупость t, которую мы даже не знаем, что это такое.Мы знаем, что в нем где-то должны быть Response и Filesystem, но мы ничего не можем делать с этим, поэтому мы вернем его обратно в другую функцию вместе с некоторыми инструкциямио том, как действовать ... что, конечно, потребует передачи еще большего количества функций.Вы знаете, что он функционирует до самого конца.

interp3 :: ((Operation -> (Response, Filesystem)) -> a)
           -> (a -> ((Response, Filesystem) -> b) -> c)
           -> (Filesystem -> b)
           -> (String -> Filesystem -> b) 
           -> Filesystem 
           -> c
interp3 inp check done out fs = check (inp (\op -> step op fs)) test
    where test (Nothing, fs) = done fs
          test (Just s, fs)  = out s fs

... ну, это довольно уродливо.Но не волнуйтесь, все идет по плану.Далее мы можем сделать пару замечаний:

• Тип a существует только между inp и check, поэтому, оглядываясь назад, мы могли бы также объединить их заранее и просто передатьСоставная функция для интерпретатора.
• Когда мы называем done, это должно означать именно то, что написано на банке.Таким образом, тип возвращаемого значения для done должен совпадать с типом интерпретатора, то есть b и c должны быть одного типа.

Теперь, если done завершит все это, что будет out?Как следует из названия, не слишком тонкого, он обеспечивает вывод во внешний код, но куда он идет после этого?Он должен каким-то образом возвращаться в интерпретатор, и мы могли бы заметить, что наш интерпретатор еще не рекурсивен.Путь вперед ясен - переводчик, как и Йормунганд, таким образом захватывает свой собственный хвост;возвращаться к бесконечности до тех пор, пока не закончится интерпретация (или пока Ragnarök, в зависимости от того, что наступит раньше).

interp4 :: ((Operation -> (Response, Filesystem)) 
               -> ((Response, Filesystem) -> r) -> r)
           -> (Filesystem -> r)
           -> (String -> Filesystem -> (Filesystem -> r) -> r)
           -> Filesystem
           -> r
interp4 checkInp done out fs = checkInp (\op -> step op fs) test
    where loop = interp4 checkInp done out
          test (Nothing, fs) = done fs
          test (Just s, fs)  = out s fs loop

... о, я упоминал, что это работает сейчас?Нет, серьезно!

Вот некоторый IO код для использования интерфейса:

ioIn f k = putStr "> " >> (k . f =<< readLn)
ioDone fs = putStrLn "Done" >> return fs 
ioOut x fs k = putStr x >> k fs

ioInterp :: IO Filesystem
ioInterp = interp4 ioIn ioDone ioOut newFS

А вот код, который запускает список команд, формируя список выходных строк:

scriptIn f k (x:xs) = k (f x) xs
scriptDone fs xs = ["Done\n"]
scriptOut r fs k xs = r : k fs xs

scriptInterp :: [Operation] -> [String]
scriptInterp = interp4 scriptIn scriptDone scriptOut newFS

Примеры запускаемых здесь обоих в GHCi , если только код недостаточно щекочет ваше воображение.

---

Ну, вот и все.Либо это?Честно говоря, этот переводчик - это код, который может любить только мама.Есть ли что-то, что элегантно связало бы все это?Что-то, чтобы раскрыть основную структуру кода?

... хорошо, так что довольно очевидно, к чему это приведет.Общий дизайн функций, вызывающих друг друга в кругах, выглядит очень похожим на стиль продолжения, и не один раз, а дважды в сигнатуре интерпретатора можно найти характерный образец (foo -> r) -> r, более известныйкак монада продолжения.

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

Answer 3

Я могу придумать два решения здесь:

1) Используйте библиотеку монадных преобразователей. Я не могу улучшить ответ Шимуара, кроме некоторых подробностей о библиотеках. Трансформеры сами по себе не дают необходимых примеров; вам нужно будет использовать преобразователи и monads-tf или monads-fd, которые предлагают реализации, основанные на семействах типов и fundeps, соответственно. Я предпочитаю monads-tf, если вы идете по этому пути. API почти идентичен с MTL. У меня нет опыта работы с MonadLib, но он тоже выглядит неплохо.

2) Запишите ваш основной цикл в IO, и для каждой итерации цикла вызовите runState для оценки монады состояния. Примерно так:

loop path state = do
  op <- readOp
  let ((newpath, resp), newstate) = runState (step path op) state
  print resp
  loop newpath newstate

Это должно работать, но это гораздо менее идиоматично, чем использование монадных преобразователей.

Answer 4

Требуется, чтобы ваши экземпляры FS были экземплярами MonadIO, а не просто Monad:

class MonadIO m => FS m where ...

Тогда вам будет доступен метод liftIO для поднятия FS в IO:

liftIO :: MonadIO m => m a -> IO a

так что вы можете написать в IO монаде:

files <- liftIO $ children currentDir

и т.д.. Конечно, это означает, что вам нужно будет реализовать liftIO для каждого FS, прежде чем вы даже напишите экземпляр FS, но для это приложение (не видя реальных деталей) Похоже, это должно быть просто.