monad 初体验 (Haskell)

Question

对于主题不清楚，我深表歉意。我是 Haskell 99 初学者，在 the solution to 67A 中遇到了人生中第一次遇到 monad 的概念。我正在努力解决的问题的一部分是定义一个函数 stringToTree 将 a(b,c) 之类的序列转换为 Tree：Branch a (Branch b Empty Empty) (Branch c Empty Empty).

我已经尝试了几次 "soft" 对 monad 的介绍，但都像其他许多人一样失败了。我希望通过理解这个解决方案最终将我带入室内，所以我决定在这里试一试。

问题

谁能简单解释一下解决方案中定义的函数stringToTree :: (Monad m) => String -> m (Tree Char)是什么？为了使这个问题独立，我从那里复制了代码

stringToTree :: (Monad m) => String -> m (Tree Char)
stringToTree "" = return Empty
stringToTree [x] = return $ Branch x Empty Empty
stringToTree str = tfs str >>= \ ("", t) -> return t
    where tfs a@(x:xs) | x == ',' || x == ')' = return (a, Empty)
          tfs (x:y:xs)
                | y == ',' || y == ')' = return (y:xs, Branch x Empty Empty)
                | y == '(' = do (',':xs', l) <- tfs xs
                                (')':xs'', r) <- tfs xs'
                                return $ (xs'', Branch x l r)
          tfs _ = fail "bad parse"

为什么 monad 在这里有用？我希望看到 monads 如何大大减少困难，当然只有在理解它之后，同时定义这个函数。

Answer 1

简而言之，定义让调用者选择使用哪个monad。这让我们可以定制我们处理失败的方式。例如，我们可以使用 Maybe:

>>> stringToTree "" :: Maybe (Tree Char)
Just Empty
>>> stringToTree "9 +" :: Maybe (Tree Char)
Nothing

或[]:

>>> stringToTree "" :: [Tree Char]
[Empty]
>>> stringToTree "9 +" :: [Tree Char]
[]

代码本身不假设使用了哪个 monad；它仅使用 >>=、return 和 fail 来处理递归调用的结果。

将类型设置为String -> Tree Char将表明失败根本不可能发生；每个字符串都必须产生一个有效的Tree Char 值（否则我们会引发运行时错误，这是您在Haskell 中应该努力避免的事情）。

但请注意，并非所有 monad 都提供 fail 的定义来避免运行时错误。

>>> stringToTree "" :: Either () (Tree Char)
Right Empty
>>> stringToTree "9 +" :: Either () (Tree Char)
*** Exception: bad parse

Answer 2

为什么 monad 有用？一些更广泛的背景。

Monad 是传统上由不同语言机制处理的几种事物的统一。其中有

排序（如在 IO 或状态中）
非确定性（如列表 monad）
失败和异常（如 Maybe）
保存和恢复计算（以后会遇到的Cont monad）
原子事务（STM monad）
解析（Parsec 及其亲戚）

"unification"我指的是牛顿统一地球和天空的物理定律，或者麦克斯韦将电和磁统一到电磁场时所做的事情；它是一个更深层次的基础理论，将上述所有情况作为特例产生，并展示了如何按照相同的思路创建新事物。

在单子中，"bind" 函数的类型 (>>=) 是理论中的中心方程；它描述了如何将计算中的一个步骤以菊花链方式连接到下一个步骤。 return 是原始的空步骤。这是你在 Haskell 中习惯的东西；一切都有某种零或空或身份价值。 fail 是一个不起作用的步骤，部分函数需要它（正如@chepner 在其他地方的评论中所说）。

monad 初体验 (Haskell)

First experience with monads (Haskell)

monads

haskell

问题