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

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

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

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

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

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

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

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 . Он должен принять операцию и файловую систему и вернуть ответ и (возможно, измененную) файловую систему :

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 , какой-нибудь другой монаде или даже к монаде вообще.

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

В основе всего этого лежит функция step , поэтому мы начнем с ее вызова.

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

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

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

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

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 должен быть таким же, как и для всего интерпретатора, то есть b и c должны быть того же типа.

Итак, если сделано , все закончится, что на выходе ? Как не слишком тонко следует из названия, он обеспечивает вывод во внешний код, но куда он будет идти после этого? Ему нужно как-то вернуться в интерпретатор,и мы могли бы отметить, что наш интерпретатор еще не рекурсивен. Путь вперед ясен - интерпретатор, подобно Йормунганду, хватает себя за хвост; бесконечное количество циклов, пока интерпретация не закончится (или до Рагнарёка, в зависимости от того, что наступит раньше).

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 .

Требовать ваши экземпляры 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, но для это приложение (не ознакомившись с фактическими подробностями) похоже, что это должно быть просто.

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

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, transformers и monadLib. Я не могу порекомендовать ни одну из них, так как не часто их использую.