17

我们正在开发一个在内部使用状态单子的模型文件系统。我们有一个类型类，其操作如下：

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并不重要；如果你喜欢，把它们当作字符串。

我要解决的问题是在 I/O monad 中编写一个顶级循环来解释文件系统Operation并打印响应。如果 IO 是 FS 的一个实例（也就是说，如果我们直接使用 IO monad），生活会很简单：我们可以写

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 monad 中编写一个交互式循环，它可以读取Operations 和 print Responses，但它适用于不一定是 IO 的状态monad。（有一个不在 IO 中的模型的原因之一是我们可以测试 QuickCheck 属性。）

我觉得这必须是一个标准问题——在一个非有状态抽象之上的交互式读取 - 评估 - 打印循环- 但我一定遗漏了一些非常明显的东西，因为我似乎无法 IO弄清楚。我在网上看过，但没有开悟。

任何帮助编写可以调用的交互式、执行 IO 的计算step将不胜感激。

4

4 回答 4

8

使用单子变压器怎么样？它们或多或少是组合 monad 的标准方式。这是一个简单的例子：

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

下面是从 ghci 中运行 replT 的结果。

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

有三个 monad 转换器库。mtl、变压器和 monadLib。我不能推荐它们中的任何一个，因为我不经常使用它们。

于 2010-07-08T20:37:20.217 回答
6

免责声明：我不能保证以下是解决问题的好方法，但完成它听起来很有趣。让我们试一试，好吗？

一些强制性进口

首先，让我们扔掉一些数据类型。我将填写一些细节并稍作调整，以便定义一个我们可以实际交互的简单“文件系统”。

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现在是该函数的无 monad 版本。它需要一个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特别是，我们希望接口至少在某种程度上是自包含的，这样无论使用该接口的什么都不必手动执行，但我们希望接口能够充分忽略使用它的代码，以便我们可以将其连接到IOmonad，其他一些，Monad甚至根本没有 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我们甚至不知道它是什么的愚蠢。我们知道它必须在某个地方有 aResponse和 a 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只存在于inpand之间check，所以事后看来，我们不妨提前将它们组合起来，然后将组合函数传递给解释器。
  • 当我们打电话时done，它的意思应该与锡上所说的完全一致。所以 for 的返回类型done应该和整个解释器一样，意思b和c应该是相同的类型。

现在，如果done结束整个事情，那是什么out？顾名思义，它向外部代码提供输出，但之后它会去哪里呢？它需要以某种方式循环回解释器，我们可能会注意到我们的解释器还不是递归的。前进的道路是明确的——译者和耶梦甘一样，因此抓住了自己的尾巴；无限循环直到解释完成（或直到诸神黄昏，以先到者为准）。

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.

于 2010-07-09T03:14:37.503 回答
2

我可以在这里想到两个解决方案：

1）使用单子变压器库。除了图书馆的一些细节外，我无法改进 Shimuuar 的回复。Transformers 本身不提供必要的实例。您将需要使用转换器和 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

这应该可行，但它远不如使用 monad 转换器那么惯用。

于 2010-07-08T23:43:20.923 回答
0

要求您的实例FS是 的实例MonadIO，而不仅仅是Monad：

class MonadIO m => FS m where ...

然后你将有可用的liftIO方法提升FS到IO：

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

所以你可以在IOmonad 中写：

files <- liftIO $ children currentDir

等等当然，这意味着您甚至需要在编写 FS 实例之前liftIO 为每个实现FS，但是对于这个应用程序（没有看到实际细节）听起来应该很简单。

于 2010-07-08T20:31:21.503 回答