右紧ArrowLoop定律

Question

根据 Control.Arrow 文档，对于许多单子（>>= 操作严格的单子），instance MonadFix m => ArrowLoop (Kleisli m) 不满足右紧律（loop (f >>> first h) = loop f >>> h) ArrowLoop class 所要求的。为什么会这样？

Answer 1

这是multi-faceted几个不同角度的问题，又回到了Haskell中的value-recursion（mfix/mdo）。有关背景信息，请参阅 here。我将尝试在此处详细解决 right-tightening 问题。

Right-tightening 用于 mfix

这里是 right-tightening 属性 mfix:

mfix (λ(x, y). f x >>= λz. g z >>= λw. return (z, w))
    = mfix f >>= λz. g z >>= λw. return (z, w)

这里是图片形式：

dotted-lines 显示了 "knot-tying" 发生的位置。这与问题中提到的定律本质上是相同的，只是它以 mfix 和 value-recursion 的形式表示。如 Section 3.1 of this work 所示，对于具有严格绑定运算符的 monad，您始终可以编写一个表达式来区分此等式的 left-hand 侧和右侧 hand-side，从而使此属性。（请参阅下面 Haskell 中的实际示例。）

当使用 mfix 通过 Kleisli 构造从 monad 创建箭头时，相应的 loop 运算符以相同的方式使相应的属性失败。

Domain-theory 和近似值

在领域理论术语中，不匹配将始终是一个近似值。

也就是说，左边 hand-side 总是比右边更不明确。（更准确地说，在 PCPO 域中，lhs 将低于 rhs，这是我们用于 Haskell 语义的典型域。）实际上，这意味着右侧将更频繁地终止，并且当这是一个问题时是首选。同样，有关详细信息，请参阅 this 的第 3.1 节。

实践中

这听起来很抽象，在某种意义上确实如此。更直观地说，左侧 有机会 作用于正在生成的递归值，因为 g 在 "loop," 内部，因此能够干扰 fixed-point 计算。这是一个实际的 Haskell 程序来说明：

import Control.Monad.Fix

f :: [Int] -> IO [Int]
f xs = return (1:xs)

g :: [Int] -> IO Int
g [x] = return x
g _   = return 1

lhs = mfix (\(x, y) -> f x >>= \z -> g z >>= \w -> return (z, w))
rhs = mfix f >>= \z -> g z >>= \w -> return (z, w)

如果你计算 lhs 它永远不会终止，而 rhs 会如预期的那样给你无限的 1 列表：

*Main> :t lhs
lhs :: IO ([Int], Int)
*Main> lhs >>= \(xs, y) -> return (take 5 xs, y)
^CInterrupted.
*Main> rhs >>= \(xs, y) -> return (take 5 xs, y)
([1,1,1,1,1],1)

我中断了第一种情况的计算，因为它是non-terminating。虽然这是一个人为的例子，但它最简单地说明了这一点。（请参阅下面使用 mdo 符号对该示例的渲染，这可能更易于阅读。）

单子示例

不满足此法则的单子的典型示例包括 Maybe、List、IO 或任何其他基于在具有多个构造函数的代数类型上。满足此法则的 monad 的典型例子是 State 和 Environment monad。有关 table 对这些结果的总结，请参阅 Section 4.10。

Pure-right缩小

请注意 "weaker" 形式的 right-tightening，其中上式中的函数 g 是纯函数，遵循 value-recursion 定律：

mfix (λ(x, y). f x >>= λz. return (z, h z))
  = mfix f >>= λz. return (z, h z)

这与之前的规律相同，g = return . h。即 g 不能执行任何效果。在这种情况下，无法像您预期的那样区分 left-hand 侧和右侧；结果确实来自 value-recursion 公理。（见 Section 2.6.3 证明。）本例中的图片如下所示：

这个属性遵循滑动属性，它是 value-recursion 的反自然性版本，并且已知被许多感兴趣的单子所满足：Section 2.4.

对mdo-notation

的影响

这项法律的失败影响了 mdo notation was designed in GHC. The translation includes the so called "segmentation" step precisely to avoid the failure of the right-shrinking law. Some people consider that a bit controversial as GHC automatically picks the segments, essentially applying the right-tightening law. If explicit control is needed, GHC provides the rec keyword 如何将决定权留给用户。

使用 mdo 表示法和显式 do rec，上面的示例呈现如下：

{-# LANGUAGE RecursiveDo #-}

f :: [Int] -> IO [Int]
f xs = return (1:xs)

g :: [Int] -> IO Int
g [x] = return x
g _   = return 1


lhs :: IO ([Int], Int)
lhs = do rec x <- f x
             w <- g x
         return (x, w)

rhs :: IO ([Int], Int)
rhs = mdo x <- f x
          w <- g x
          return (x, w)

有人可能会天真地认为上面的lhs和rhs应该是一样的，但是由于right-shrinking定律的失败，它们不是。就像之前一样，lhs 卡住了，而 rhs 成功生成了值：

*Main> lhs >>= \(x, y) -> return (take 5 x, y)
^CInterrupted.
*Main> rhs >>= \(x, y) -> return (take 5 x, y)
([1,1,1,1,1],1)

目视检查代码，我们看到递归只是针对函数 f，这证明由 mdo-notation 自动执行的分割是合理的。

如果首选 rec 表示法，程序员需要将其放在最少的块中以确保终止。例如，上面的表达式 lhs 应该写成：

lhs :: IO ([Int], Int)
lhs = do rec x <- f x
         w <- g x
         return (x, w)

mdo-notation 会处理这个问题并将递归置于最小块上而无需用户干预。

克莱斯利箭失败

在绕了这么长的弯路之后，现在让我们回到关于箭头相应法则的原始问题。类似于 mfix 的情况，我们也可以为 Kleisli 箭头构建一个失败的例子。其实上面的例子直接多多少少翻译一下：

{-# LANGUAGE Arrows #-}
import Control.Arrow

f :: Kleisli IO ([Int], [Int]) ([Int], [Int])
f = proc (_, ys) -> returnA -< (ys, 1:ys)

g :: Kleisli IO [Int] Int
g = proc xs -> case xs of
                 [x] -> returnA -< x
                 _   -> returnA -< 1

lhs, rhs :: Kleisli IO [Int] Int
lhs = loop (f >>> first g)
rhs = loop f >>> g

就像 mfix 的情况一样，我们有：

*Main> runKleisli rhs []
1
*Main> runKleisli lhs []
^CInterrupted.

对于IO-monad的mfix的right-tightening的失败也阻止了Kleisli IO箭头满足[=53=中的right-tightening定律]实例。

右紧ArrowLoop定律

Right-tightening ArrowLoop law

haskell

arrows

typeclass