monadic 评估中的 `bind` 运算符

Question

我已经阅读了几次 the article of Dan Friedman about monadic evaluation 在 Scheme 中的实现，但我对 State monad 的子章节末尾的练习感到困扰。

文章讲的很清楚，边做边学，理论很少，但是这个练习真的很模糊。恐怕我错过了一些重要的方面，这就是我在这里问的原因。

练习是这样的：

In remberevensXcountevens, the increment takes place before the tail recursive call, but we are free to reorder these events. Implement this reordered-events variant by having the body of the sequel become the ﬁrst argument to bind state and make the appropriate adjustments to the sequel. Is this new ﬁrst argument to bind state a tail call?

它要求首先从 >>= 运算符调用 sequel，然后调用作为参数传递给绑定的 ma。

我不明白如何先进行递归调用，然后再调用 ma 来更改状态值。我只是切换了 >>= 的参数，但没有切换评估顺序。

如果我先尝试评估 sequel，我不知道要传递什么 value。

我的代码是这样的：

(define return
  (lambda (a)
    (lambda (s)
      (cons a s))))

(define >>=
  (lambda (sequel ma)
    (lambda (s)
      (let ((pair (ma s)))
        (let ((value (car pair))
              (state (cdr pair)))
          (let ((mb (sequel value)))
            (mb state)))))))

(define rember/count
  (lambda (l)
    (cond ((null? l) (return '()))
          ((list? (car l))
           (>>= (lambda (a)
                  (>>= (lambda (d)
                         (return (cons a d)))
                       (rember/count (cdr l))))
                (rember/count (car l))))
          ((even? (car l))
           (>>= (lambda (_) (rember/count (cdr l)))
                ;;  here I want to evaluate the addition AFTER the `(rember/count (cdr l))`.
                (lambda (s) (cons '_ (+ 1 s)))))
          (else
           (>>= (lambda (d)
                  (return (cons (car l) d)))
                (rember/count (cdr l)))))))

((rember/count '(1 2 3 4 (7 8 9 10 11) 5 6)) 0)

Answer 1

原始函数是

...
    (bind (λ (s) `(_ . ,(add1 s)))
                 (λ (_) (remberevensXcountevens d)))
...

现在，首先要做的是得到sequel的正文，也就是(rXc d)，成为第一个参数绑定。所以我们有

(bind (remberevensXcountevens d)
      (λ (d) ...))

注意我们需要d来保存递归调用的结果。

而且我们知道我们有一个偶数，我们必须将 1 添加到状态。

(bind (remberevensXcountevens d) 
      (λ (d) (... (λ (s) (cons '_ (add1 s))) ...)))

(λ (s) ...) 是一个没有纯值的单子。我们需要绑定它以使其成为我们计算的一部分。所以

(bind (remberevensXcountevens d)
      (λ (d) (bind (λ (s) (cons '_ (add1 s))) 
                   (λ (_) ...))))

现在状态更新了，我们有了一个方便的纯值。自然是：

(bind (remberevensXcountevens d)
      (λ (d) (bind (λ (s) (cons '_ (add1 s))) 
                   (λ (_) (unit d)))))

monadic 评估中的 `bind` 运算符

The `bind` operator in monadic evaluation

monads

scheme