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

html5 • • 问答 

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 函数而不是实际模式。

回答

数据可以像 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 实例可能会在此处终止。

  • @AntC You are misreading the Report. The "function binding" has 1 or more arguments, not 0. And `x` is a pattern, of the simplest sort, so `let x = 5` is a pattern binding, not a function binding. There's no such thing as a niladic function.
  • The `fix` function is not recursive. Only the let-binding inside of it, a non-function, is. Also you are being weirdly aggressive, in your comment on my answer but especially on Carsten's deleted answer (which *also* featured a recursive non-function, `fibs`). Consider being more polite to get better results when asking for help.
  • @AntC I gave the relevant quotes in a [comment](https://stackoverflow.com/questions/67733530/pattern-binding-why-are-recursive-patterns-allowed#comment119736235_67733530) under the Q. `p = e` is a _pattern_ binding; `let x = f x` is a _pattern_ binding for the irrefutable pattern `x`, just like @ amalloy is saying above. the binding for `fibs` in Carsten's answer is a _pattern_ binding so your comment there was factually wrong. as for the "patronizing", we really have no way of knowing the asker's level of understanding of various aspects of Haskell and besides, the readership is wider than 1.
  • @AntC wider than just 1 (the asker), so it wasn't patronizing at all. 🙂

回答

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

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辅助函数来定义的。这对于将树的每个级别的结果列表传递到下一个级别是必要的。

以上是模式绑定：为什么允许递归模式？的全部内容。
THE END
分享
二维码
< <上一篇
下一篇>>