首页 文章

Wadler，“功能编程的Monads”，第2.8节

提问于
浏览 次
4

Edit II: 啊，好吧：我不明白a和b是如何绑定在eval的定义中的！现在我做 . 如果有人感兴趣，这是跟踪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 :: 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)

这里，（>> =）接受monadic值m :: M a，函数k :: a - > M b，并输出monadic值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返回的对中的第一个元素，那么如何评估单位？

(2) 如何组合tick和unit来跟踪执行的除法运算符的数量 . 虽然非monadic评估器没有问题，但bind的使用让我感到困惑 .

Edit: 谢谢大家 . 我认为我的误解是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'时，不会产生'practical result' . 通过将任何变量与lambda运算符绑定，并用值替换它，可以实现相同的效果 . 在这种情况下，绑定的多功能性是任何值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'的结果绑定到（a，y），并且评估k的结果绑定到（b，z） . 我有办法去，但这有点清除它 . 谢谢 .

haskell state monads

3 回答

  • 4

    1A）

    在0处评估tick的结果是（（），1） - 再次查看代码，它将输入值递增1 .

    lambda表达式接受（）因为它是绑定操作的右侧，这意味着它的类型应该是（（） - > M b） . 因此它将（）作为其第一个参数，然后使用“unit”作为M b项 .

    图1b）

    我在这里问这个问题 . 绑定运算符被定义为将结果和状态从第一个操作（分别是（）和1）传递到第二个操作，因此单元最终被传递1作为当前状态（结果，（）被吞下lambda表达式） . 当前状态由单位函数保持原样，结果是4 div 2的结果，即2 .

    2）

    大概你会想要一些类型的功能：

    divCounted :: Int -> Int -> M Int

    其中要么结合了tick和单位（类似于你的方式），要确保勾选一次以增加计数，并使用单位来回馈结果 .

    回复于
  • 2

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

    (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)

    现在让我们将tick应用于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) .

    回复于
  • 4

    1a）在0处评估tick的结果是（（），1），那么lambda表达式如何接受（）？

    关于状态monad的关键是bind处理该对的第二个组成部分，即状态 . lambda表达式只需要处理 () ，该对的第一个组成部分是返回值 .

    一般来说，关于monad M 的关键在于它抽象了整个国家的线索 . 您应该将 M a 类型的值视为一个计算机程序，它返回类型为 a 的值，同时还会弄乱状态 . 洞察力是两个操作 unit 和 >>= 足以编写任何此类程序;构建和解构对的整个业务可以在这两个函数中捕获 .

    回复于

相关问题