GHC 在编译模式时会进行哪些迭代？

Question

我刚刚写了一个在井字棋中走棋的函数。我想推动模式匹配。所以我写了 9 makeAMove 个子句。每个都有一个 Tic-Tac-Toe 棋盘，上面有不同的 space，由空符号指定。它看起来像这样。

makeAMove [[E,   m12, m13],
           [m21, m22, m23],
           [m31, m32, m33]] X 1 1 = ...

此子句会在板的左上角放置一个 X。 X、O 和 E 定义为标记。

data Mark = X |  O | E deriving (Eq, Show)

加载文件时收到此警告消息。

warning:
    Pattern match checker exceeded (2000000) iterations in
    an equation for ‘mov1’. (Use -fmax-pmcheck-iterations=n
    to set the maximun number of iterations to n)

我的问题是出于好奇。模式匹配器在进行什么样的迭代？为什么需要这么多？

当我将子句的数量限制为 5 个，并将其余部分放在另一个由默认情况链接到的函数中时，没有问题。

Answer 1

这是一个 MCVE：

{-# OPTIONS -Wall #-}
data T = O | A | B | C | D | E

f :: T -> T -> T -> T -> T -> T -> T -> T -> T -> ()
f O _ _ _ _ _ _ _ _ = ()
f _ O _ _ _ _ _ _ _ = ()
f _ _ O _ _ _ _ _ _ = ()
f _ _ _ O _ _ _ _ _ = ()
f _ _ _ _ O _ _ _ _ = ()
f _ _ _ _ _ O _ _ _ = ()
f _ _ _ _ _ _ O _ _ = ()
f _ _ _ _ _ _ _ O _ = ()
f _ _ _ _ _ _ _ _ O = ()

结果：

ExhaustivePattern3.hs:5:5: warning:
    Pattern match checker exceeded (2000000) iterations in
    an equation for ‘f’. (Use -fmax-pmcheck-iterations=n
    to set the maximun number of iterations to n)

我猜检查器过于急切地试图生成反例：有许多不匹配的模式，随着参数的数量呈指数增长。

事实上，在第一次匹配之后，未匹配的情况是

A _ _ _ _ _ _ _ _
B _ _ _ _ _ _ _ _
...
E _ _ _ _ _ _ _ _

然后在第二个之后，扩展为：

A A _ _ _ _ _ _ _
A ...
A E _ _ _ _ _ _ _
B A _ _ _ _ _ _ _
B ...
B E _ _ _ _ _ _ _
...
E A _ _ _ _ _ _ _
E ...
E E _ _ _ _ _ _ _

等等。这呈指数增长。

GHC 在编译模式时会进行哪些迭代？

What sort of iterations does GHC do while compiling patterns?

haskell

pattern-matching

ghc