haskell - Wadler, "Monads for Functional Programming,"第 2.8 节

编辑二: 啊，好吧:我不明白在 eval 的定义中 a 和 b 是如何绑定(bind)的!现在我知道了。如果有人感兴趣，这是一个跟踪 a 和 b 的图表。我是图表的忠实粉丝。我发誓，绘制箭头确实改善了我的 Haskell。

A Diagram of an eval call (PDF)

有时我觉得真的很浓。

在 Wadler 的“Monads for Functional Programming”的 2.8 节中，他将状态引入到一个简单的评估函数中。原始(非 monadic)函数使用一系列 let 表达式跟踪状态，并且很容易理解:

data Term = Con Int | Div Term Term
 deriving (Eq, Show)

type M a = State -> (a, State)
type State = Int

eval' :: Term -> M Int
eval' (Con a) x   = (a, x)
eval' (Div t u) x = let (a, y) = eval' t x in
                    let (b, z) = eval' u y in
                    (a `div` b, z + 1)

monadic 评估器的 unit 和 bind 定义同样简单:

unit :: a -> M a
unit a = \x -> (a, x)

(>>=) :: M a -> (a -> M b) -> M b
m >>= k = \x -> let (a, y) = m x in
                let (b, z) = k a y in
                 (b, z)

这里， (>>=) 接受一个单值 m::M a，一个函数 k::a -> M b，并输出一个单值 M b。 m 的值取决于在 lambda 表达式中替换 x 的值。

Wadler 然后介绍了函数 tick:

tick :: M ()
tick = \x -> ((), x + 1)

再次，直截了当。然而，并不简单的是如何将这些函数链接在一起以生成一个评估函数，该函数返回执行的除法运算符的数量。具体来说，我不明白:

(1) 如何实现滴答。例如，以下是一个有效的函数调用:

(tick >>= \() -> unit (div 4 2)) 0
 ~> (2, 1)

但是，我无法手动对其进行正确评估(表明我误解了某些内容)。特别是: (a) 在 0 处计算 tick 的结果是 ((), 0)，那么 lambda 表达式如何接受 ()？ (b) 如果 a 是通过在 0 处调用 tick 返回的元素对的第一个元素，则如何计算 unit？

(2) 如何结合刻度和单位来跟踪执行的除法运算符的数量。虽然非 monadic 评估器没有问题，但在这里使用 bind 使我感到困惑。

编辑: 谢谢大家。我认为我的误解是 lambda 表达式的作用，'() -> unit (div 4 2)'。如果我理解正确的话

(tick >>= (\() -> unit (div m n)) x

扩展到

(\x -> let (a, y) = tick x in
       let (b, z) = (\() -> unit (div m n) a y) in
       (b, z)) x

当“a”应用于“() -> unit (div m n) a y”时，不会产生“实际结果”。通过将任何变量与 lambda 运算符绑定(bind)并替换它的值，可以实现相同的效果。在这种情况下，bind 的多功能性在于可以将任何值 M a 传递给它。如上所述，值M a 表示计算，例如“eval”。因此:

eval (Con a) = unit a

eval (Div t u) = eval t >>= (\a ->
                  eval u >>= (\b ->
                   tick >>= (\c -> unit (a `div` b))))

如果我理解正确，'eval t' 被替换为 m 和表达式的其余部分，函数

'(\a -> eval u >>= (\b -> tick >>= (\c -> unit (a `div` b))))'

代替k。评估 'eval t' 的结果绑定(bind)到 (a, y)，评估 k 的结果绑定(bind)到 (b, z)。我还有很长的路要走，但这在某种程度上清除了它。谢谢。

最佳答案

您可以像这样手动评估表达式:

(tick >>= \() -> unit (div 4 2)) 0

如果将 tick 和 \() -> unit (div 4 2) 插入到 >>= 的定义中，则变为:

(\x -> let (a, y) = tick x in
       let (b, z) = (\() -> unit (div 4 2)) a y in
       (b, z)) 0

如果您现在通过将 0 替换为 x 来应用该函数，您将得到:

let (a, y) = tick 0 in
let (b, z) = (\() -> unit (div 4 2)) a y in
(b, z)

现在让我们将刻度应用于 0:

let (a, y) = ((), 0 + 1) in
let (b, z) = (\() -> unit (div 4 2)) a y in
(b, z)

所以 a 变成 () ， y 变成 0+1 ，也就是 1 。所以我们有

let (b, z) = (\() -> unit (div 4 2)) () 1 in
(b, z)

如果我们将该函数应用于 () 我们得到

let (b,z) = unit (div 4 2) 1 in
(b,z)

如果我们申请单位，我们得到

 let (b,z) = (div 4 2, 1) in
 (b,z)

div 4 2 是 2，所以结果是 (2,1) 。

关于haskell - Wadler, "Monads for Functional Programming,"第 2.8 节，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/3422632/