Wadler 中 tick 方程的问题，»函数式编程的 Monads«，第 3 节

Question

Wadler 的 Monads for functional programming 我在看方程式

tick ✭ λ().m = m ✭ λ().tick

在第 3 节中（在 State Monad 的上下文中）。据称它

holds so long as tick is the only action on state within m.

我不明白怎么会这样。左项的类型不是 m 而右项的类型是 tick : M()?此外，如果 m 的类型不是 M ()，则 ✭ 的操作数类型在右侧不匹配。

我环顾四周，但找不到任何勘误，同样的方程式出现在 2001 年的论文修订版中，所以显然我遗漏了什么……

Answer 1

在Haskell语法中，

tick x  =  ((), x+1)
unitState a x  =  (a, x)
bindState m k  =  uncurry k . m    -- StarOp for State

bindState tick (\() -> m) =
     = uncurry (\() -> m) . (\x -> ((), x+1))
     = (\y -> uncurry (\() -> m) ( (\x -> ((), x+1)) y))
     = (\y -> uncurry (\() -> m)          ((), y+1)    )
     = (\y ->         (\() -> m)           () (y+1)    )
     = (\y ->                 m               (y+1)    )

bindState m (\() -> tick) =
     = uncurry (\() -> tick) . m
     = uncurry (\() -> (\x -> ((), x+1))) . m
     = uncurry (\() x -> ((), x+1)) . m
     = (\y -> uncurry (\() x -> ((), x+1)) (m y))
     = (\y -> let ((),z) = m y in ((), z+1))

只有在 m y returns ((),z) 这样 m (y+1) returns ((),z+1) （即 m y只在初始状态y基础上增加一些固定数量，不依赖于y).

所以我没有看到类型的问题，但那个英语短语的含义也让我难以理解。

顺便说一下，本文提出的通过将 unitState 更改为 unitState a x = (a, x+1) 来将 "execution counts" 添加到其单子求值器的方法，本质上会使它成为非法的单子，因为这个新的 unitState 不会是身份。

类型是，

tick :: M ()
bindState :: M a -> (a -> M b) -> M b
(\() -> tick) :: () -> M () 

bindState (tick :: M ()) ((\() -> m) :: () -> M b ) :: M b
bindState (m :: M ()) ((\() -> tick) :: () -> M ()) :: M ()

所以类型的唯一问题是 m 必须是 m :: M ()，而不是一般的 M b，正如我们在上面的扩展中看到的那样。

Wadler 中 tick 方程的问题，»函数式编程的 Monads«，第 3 节

Trouble with equation for tick in Wadler, »Monads for functional programming«, section 3

monads

functional-programming

state-monad