Haskell tuple monad 太严格了？

Question

我用 Control.Monad.Writer.Lazy 编写我的代码，使用 (,) [String] 作为我的 writer monad。但是我发现 (>>=) 和 (>>) 对幺半群运算符太严格了？它们会导致无限循环，例如：

type Wrtr a = ([String], a)
writer (x, w) = (w, x)

main :: IO ()
main = do
    let one = writer ((), ["goodbye"])
    let w = foldr1 (>>) $ repeat one
    let (log, _) = w
    mapM_ putStrLn . take 5 $ log

这段代码会无限循环，永远不会打印任何东西，这对我来说很糟糕。所以现在我正在使用同一个 monad 的这个天真的实现，它看起来很好而且很懒惰：

data Writer w a = Writer w a
instance Functor (Writer w) where
    fmap f (Writer w x) = Writer w (f x)
instance Monoid w => Applicative (Writer w) where
    pure x = Writer mempty x
    (Writer w1 f) <*> (Writer w2 x) = Writer (w1 <> w2) (f x)
instance Monoid w => Monad (Writer w) where
    return = pure
    (Writer w1 x) >>= f =
        let (Writer w2 y) = f x
        in Writer (w1 <> w2) y
writer (x, w) = Writer w x

（由于幺半群约束，您必须定义仿函数和应用实例）

如果您随后运行具有与上面完全相同的 main 功能的代码，它将打印 "goodbye" 五次并退出。

那么问题来了：为什么元组这么严格？或者，如果它不是严格性，它是什么，为什么会在那里？

顺便说一句，我正在使用 ghc 8.6.4 以及堆栈 lts-13.19 附带的所有其他软件

Answer 1

Hackage says

instance Monoid a => Monad ((,) a) where
    (u, a) >>= k = case k a of (v, b) -> (u <> v, b)

这意味着它们是严格的，因为 case（不像你的 let (Writer w2 y) = f x）：

foldr1 (>>) $ repeat one
= one >> foldr1 (>>) (repeat one)
= (["goodbye"], ()) >>= \_ -> foldr1 (>>) (repeat one)
= case ((\_ -> foldr1 (>>) (repeat one)) ()) of (v, b) -> (["goodbye"] <> v, b)
= case (foldr1 (>>) (repeat one)) of (v, b) -> (["goodbye"] <> v, b)

这实际上会在您访问 ["goodbye"] <> v 部分之前强制嵌套 (foldr1 (>>) ...)。

这是因为 case 模式匹配是强制的，而 let 模式是惰性的。您的代码实际上将上面的内容写为

= let (v, b) = foldr1 (>>) (repeat one) in (["goodbye"] <> v, b)

一切都很好，很懒。

Answer 2

那是因为你的 Writer 违反了 monad 法则。看看这个规律：

-- forall (f :: a -> Writer m b) (x :: a).
return x >>= f = f x
-- basically f (id x) = f x, which we should agree is pretty important!

但是，唉，它不成立！ let f = undefined！（或 f = const undefined；如果您不使用 seq，它们将无法区分）

  return x >>= undefined
= Writer mempty x >>= undefined
= let (Writer m y) = undefined
  in  Writer (mempty <> m) y
= Writer (mempty <> undefined) undefined

然而，根据法律，

  return x >>= undefined
= undefined x
= undefined

这些不等同，因此您的惰性 Monad 实例是非法的（是的，我相信 mtl 中的实例也是如此）。但是，Fast and Loose Reasoning is Morally Correct，所以我们一般也就接受了。这个想法是，惰性 Writer monad 通常会遵循它应该遵循的法则，只要您将无限值或最低值排除在外，但它会在这些边缘情况下崩溃。相比之下，严格实施完全合法，这就是它在 base 中的原因。然而，正如您所发现的，当惰性 Writer 违反法律时，它们会以一种有用的方式做到这一点，因此我们将惰性实现放在 mtl.

中

这是一个demo of this behavior。请注意，惰性版本在爆炸前会在输出中产生一个 Writer "，而严格版本和法律给出的规范都不会这样做。

Haskell tuple monad 太严格了？

Haskell tuple monad is too strict?

monads

haskell

lazy-evaluation