是否有通用算法可以在函数式编程语言中展平嵌套 lhs 案例？

Question

函数式编程语言（如 Haskell）允许用户使用等式表示法来定义函数，其中左侧有多个可以匹配的模式参数，具有任意多个嵌套。例如：

(fun (Ctr A A) (Foo (Tic X)) a b c d e) = a
(fun (Ctr A B) (Foo (Tac Y)) a b c d e) = b
(fun (Ctr B A) (Bar (Tic X)) a b c d e) = c
(fun (Ctr B B) (Bar (Tac Y)) a b c d e) = d
(fun x         y             a b c d e) = (df x y a b c d e)

不过，假设您想要将该函数编译为不允许嵌套模式匹配的语言。也就是说，您必须将这些子句扁平化为一系列函数，这些函数组合在一起，相当于fun. 例如，在上面的情况下，您可以按如下方式将其展平：

(fun (Ctr x1 x2) (Foo x3) a b c d e) = (fun_0 x1 x2 x3 a b c d e)
(fun (Ctr x1 x2) (Bar x3) a b c d e) = (fun_1 x1 x2 x3 a b c d e)
(fun x           y        a b c d e) = (df x y a b c d e)

(fun_0 A A (Tic x0) a b c d e) = (fun_0_0 x0 a b c d e)
(fun_0 A B (Tac x0) a b c d e) = (fun_0_1 x0 a b c d e)
(fun_0 x y z        a b c d e) = (df (Ctr x y) (Foo z) a b c d e)

(fun_1 B A (Tic x0) a b c d e) = (fun_1_0 x0 a b c d e)
(fun_1 B B (Tac x0) a b c d e) = (fun_1_1 x0 a b c d e)
(fun_1 x y z        a b c d e) = (df (Ctr x y) (Bar z) a b c d e)

(fun_0_0 X a b c d e) = a
(fun_0_0 x a b c d e) = (df (Ctr A A) (Foo (Tic x)) a b c d e)
(fun_0_1 Y a b c d e) = b
(fun_0_1 x a b c d e) = (df (Ctr A B) (Foo (Tac x)) a b c d e)
(fun_1_0 X a b c d e) = c
(fun_1_0 x a b c d e) = (df (Ctr B A) (Bar (Tic x)) a b c d e)
(fun_1_1 Y a b c d e) = d
(fun_1_1 x a b c d e) = (df (Ctr B B) (Bar (Tac x)) a b c d e)

我的问题是：是否有一种通用算法可以将嵌套的 lhs 模式匹配展平为非嵌套子句，并尽可能减少子句数量？

Answer 1

Simon PJ 的《函数式编程语言的实现》的第 4 章专门讨论了这个主题。请参阅此处的 pdf：https://www.microsoft.com/en-us/research/wp-content/uploads/1987/01/slpj-book-1987-small.pdf

本章由 Haskell 的设计者之一 Phil Wadler 合着。

虽然本书使用了 Haskell 之前的风格语法，但其中的思想仍然保留下来。当涉及 GADT、模式匹配完整性等时，您需要查看较新的论文；但基本思想/算法保持不变。