模式绑定：为什么允许递归模式？

Question

Prelude> let (Just x) = Just (x - 1) in x
*** Exception: <<loop>>

为什么编译器接受那个 decl？它可以在语法上告诉它绑定到循环（？）

GHC 知道：

Prelude> :set -XBangPatterns
Prelude> let !(Just x) = Just (x - 1) in x
    Recursive bang-pattern or unboxed-tuple bindings aren't allowed:

[ ExceptionGHCi 7.10.2 上的那个和编译器失败消息。在 GHC 8.10 没有有用的消息，只是循环。]

递归模式绑定是否有一些合理的用途？我认为对于模式绑定 decl，lhs 的自由变量应该与 rhs(?)

我所说的“模式绑定”是指根据 Haskell 语言报告 2010 的第 4.4.3.2 节，特别是从数据构造函数/最外层范围开始的 lhs。

（我希望有比 lhs 上的单个 var 更令人兴奋的东西。这仍然算作“模式绑定”，请参阅评论。）

当然对于函数decls，编译器必须允许递归，因为它无法从语法上判断函数是否会循环：

Prelude> let { f 0 = 0;
               f x = f (x - 1) }           -- will terminate (for positive inputs)
             in f 5

在我看来，lhs 上的裸变量更像是 niladic 函数而不是实际模式。

Answer 1

数据可以像 Haskell 中的函数一样懒惰。因此，递归绑定肯定有用例。例如，考虑以下定义fix：

fix :: (a -> a) -> a
fix f = let x = f x in x

twoOnes :: [Int]
twoOnes = take 2 $ fix (1 :)

请注意，由于 let 绑定的右侧在左侧是非严格的，因此绑定可以产生结果。

考虑到一些同样愚蠢的Num情况，即使是你原来的、“明显愚蠢”的表达也可能会终止：

instance Num () where
  fromInteger x = ()
  x - y = ()

loop :: ()
loop = let (Just x) = Just (x - 1) in x

显然对于这种特定类型不是非常有用，但 GHC 不负责决定哪些法律表达式是有用的，而且通过更多的工作，可以想象更多有用的 Num 实例可能会在此处终止。

Answer 2

有关使用带有构造函数的递归模式而不仅仅是单个变量的有用代码的示例，请参阅此广度优先重新标记函数：

data Tree a
  = Leaf a
  | Node (Tree a) (Tree a)
  deriving Show

bfl :: forall a b. [b] -> Tree a -> Tree b
bfl l t = result
  where
    go :: Tree a -> [[b]] -> ([[b]], Tree b)
    go (Node l r) (xs:xss0) = 
      let (xss1, l') = go l xss0
          (xss2, r') = go r xss1
      in (xs:xss2, Node l' r')
    go (Leaf _) ((x:xs):xss) = (xs:xss, Leaf x)
    (xss, result) = go t (l:xss)

在最后一行，我们使用了一个元组(xss, result)，它是通过将xss自身传递给go辅助函数来定义的。这对于将树的每个级别的结果列表传递到下一个级别是必要的。