为什么接受递归模式同义词?

Question

这个问题(来自5年前)问"为什么所有递归模式同义词都被拒绝了?"它的榜样至今仍被拒绝。用户指南说"模式同义词不能递归定义"。

我有一个被接受的递归模式同义词(GHC 8.10.2)。我可以调用它，它会循环，不奇怪。那么为什么它可以编译呢?/像这样的东西是否有一个合理的用例?

基于2016年论文第2.3节"多态模式同义词"中的示例的代码。

data JoinList a = JNil | Unit a | JoinList a `JoinTree` JoinList a    deriving (Eq, Read, Show)

我试图定义一个模式同义词Nil。显然JNil是匹配的。还有JNil ``JoinTree`` JNil，以及JoinTree的任意嵌套，只要所有的叶子都是JNil。

pattern Nil :: JoinList a
pattern Nil <- JNil
  where Nil = Nil `JoinTree` Nil      -- huh?
wot = Nil `JoinTree` Nil              -- these all compile
wotwot Nil = ()
wotwotwot = wotwot Nil
wotwotwotwot = wotwot wot

尝试调用wot循环，不奇怪。试图呼叫wotwotwot投诉Non-exhaustive patterns in function wotwot。

完全披露:我正在玩的/我知道这不起作用[见下文]是:

pattern Nil = JNil                     -- base case matcher, and builder
  where Nil <- Nil `JoinTree` Nil      -- recursion on the matcher, not the builder
                                       -- but can't put `<-` equations after where

下面拒绝了Recursive pattern synonym definition——这是我所期望的

pattern NilRec <- NilRec `JoinTree` NilRec 
  where NilRec = JNil    

无论如何，这是行不通的:它需要首先匹配NilRec = JNil作为基本情况。

---

回答@Noughtmare的问题"你有什么建议?"评论他的回答，我想写decl上面的"我在玩什么"(是的，我知道这是目前非法的语法);然后用两种情况将其转换为匹配器，依次尝试:

case arg of
  { JNil -> ...
  ; Nil `JoinTree` Nil -> ...
  }

请注意，每种情况都有最外层的一个来自JoinList类型的数据构造函数。因此，Nil的递归使用是受保护的/中介的，就像任何通过ViewPattern的方法一样。(这也是5年前的问题。)换句话说:我认为编译器可以从pattern ... = ... where ... <- ... .

生成ViewPattern .

Answer 1

只有匹配器不能递归，因为这可能导致无限模式匹配(无限大的程序)。case x of Nil -> y的脱糖过程为:

  case x of
    JNil -> y
    JoinTree x2 x3 -> case x2 of
      JNil -> case x3 of
        JNil -> y
      JoinTree x4 x5 -> case x4 of
        ...

无限延续

使用递归构造器是可以的，因为它们可以包含任意函数。下面是一个更简单的例子，它没有构造函数的混淆:

pattern Foo <- ()
  where Foo = let loop = loop in loop

你可以使用ViewPatterns:

在模式中允许任意函数

normJoinList (JoinTree (normJoinList -> JNil) (normJoinList -> JNil)) = JNil
normJoinList x = x
pattern Nil <- (normJoinList -> JNil)
  where Nil = JNil

我想这就是你想要的:

> case Nil `JoinTree` Nil of Nil -> True; _ -> False
True