Haskell 程序以 "loop"中止，但我认为它不应该

Question

我有这个 Haskell 代码，当使用 GHC 编译并运行时，它会因检测到循环而中止。

data Foo = Foo ()
 deriving (Eq,Show)

type Foop = Foo -> ((),Foo)

noOp :: Foop
noOp st = ((),st)

someOp :: Foop
someOp st@(Foo x) = ((),st)

(<+>) :: Foop -> Foop -> Foop
(<+>) f g st = let ((_,st'),(_,st'')) = ((f st),(g st')) in ((),st'')

main = print $ (noOp <+> someOp) $ Foo ()

我认为不应该，这里有一些修改。他们每个人都使循环消失:

更改 data Foo至newtype Foo

更改 (noOp <+> someOp)至(someOp <+> noOp)

删除解构@(Foo x)

这是 GHC 中的错误还是我对评估过程缺乏了解？

Answer 1

模式匹配 (_, _)要求 (f st, g st') 的 WHNF .简单的。

模式匹配 (_, (_,_))要求 g st' 的 WHNF .这就是问题所在，因为 g是严格的，因此它首先需要 st'在 WHNF 中也是如此。运行时发现 st'在模式((_,st'), (_,_)) , 所以在它实际上可以向下遍历到 st' 之前它需要 WHNF 两个元组。因为g然而是严格的，这首先需要st' ... 等等。

如果匹配 g 的结果懒惰的无可辩驳的模式

(<+>) f g st = let ((_,st'), ~(_,st'')) = (f st, g st') in ((),st'')

然后问题就消失了，因为这是这样评估的:

模式匹配 (_, _)要求 (f st, g st') 的 WHNF .简单的。

模式匹配 (_, ~(_,_))暂时没有什么要求了。

模式匹配 ((_,st'), ~(_,_))要求 f st 的 WHNF .幸运的是，我们可以实现这一点，因为 st不依赖于模式。

现在我们已经满足了模式匹配，运行时已经可以继续 in ((),st'') .只有在这一点上是无可辩驳的模式~(_,st'')强制，但这现在不再是问题了，因为 st'在这里可用，因此只需计算g一次。

您尝试的所有修复都相当于制作 g非严格:

remove the deconstruction @(Foo _)

没有那个， g并不真的需要查看它的参数来构造结果骨架，即元组匹配 (_,st'')然后可以在不首先要求 st' 的 WHNF 的情况下成功.

change data Foo to newtype Foo

这具有 Foo 的效果。构造函数在运行时实际上并不存在，所以没有任何模式 st@(Foo _)会强制。

change noOp <+> someOp to someOp <+> noOp

正如我所说，循环的出现只是因为 g是严格的。如果你把 f在它不严格的位置，那么没有问题。