Haskell 向构造函数添加约束

Question

背景：
我正在学习关于“语言和自动机”的课程：目前它是关于正则表达式/语言、DFA 和 NFA。这个问题不是家庭作业，而是我决定为自己做的一些事情在 Haskell 中的实现。回答这个问题只需要 Haskell 的知识

---

我有以下正则表达式的数据类型

data Regex sigma = Eps
    | Phi
    | S sigma
    | Regex sigma :. Regex sigma
    | Regex sigma :| Regex sigma
    deriving (Show,Eq,Read)

有了这个，我们可以定义正则表达式，例如S 'a', or S 'a' :. S 'b', or Eps :| S 'a'。到现在为止还挺好。

现在，Eps（空字符串）应该是 的中性元素:.。即Eps :. e和e :. Eps都应该返回e（e任何其他正则表达式在哪里）。

所以我想将模式匹配应用于构造函数(:.)。这可能吗？如果是这样，我该如何实施？如果没有，还有什么方法可以实现我想要的？

我试图显式定义构造函数以应用模式匹配：

(:.) :: Regex sigma -> Regex sigma -> Regex sigma
(:.) Eps e = e
(:.) e Eps = e
(:.) e f = e :. f       --this line is obviously incorrect, but I don't know how to write it differently

Answer 1

听起来您可能想要使用智能构造函数。基本思想是隐藏数据类型的实际构造函数，并且您具有公开的那些构造函数的特殊版本。这在构造上非常有效，但正如@bradrn 在评论中暗示的那样，对于可能正在解构您的数据类型的用户来说，这可能会造成混淆。

在实践中，使用智能构造函数会是这样的：

module Regex (Regex, eps, phi, s, (.:), (.|)) where

data Regex sigma = Eps
    | Phi
    | S sigma
    | Regex sigma :. Regex sigma
    | Regex sigma :| Regex sigma
    deriving (Show,Eq,Read)

eps :: Regex sigma
eps = Eps

s :: sigma -> Regex sigma
s = S

...

(.:) :: Regex sigma -> Regex sigma -> Regex sigma
(.:) Eps e = e
(.:) e Eps = e
(.:) e f = e :. f

首先，请注意 的实际构造函数Regex没有被导出。另请注意，如果Regex使用智能构造函数创建 a ，那么您正在寻找的简化:.会自动发生。您可以根据需要在这些智能构造函数中添加任意数量的简化。最后，请注意，Eps .: e == e .: Eps就像您想要的那样，无需重新定义Eq Regex实例。

当然，这样做的缺点是用户无法访问实际的Regex构造函数，这意味着用户无法解构Regex. 有很多方法可以解决这个问题，例如使用单向或双向模式，但这可能会令人困惑。例如（正如@bradrn 在评论中指出的那样），该值Eps .: e将与 pattern 不匹配x :. y。

还有一个问题，您的派生Read实例仍可用于创建Regex具有类似内容的值Eps :. e。这里的一个巧妙提示是，现在您拥有智能构造函数，定义变得非常容易simplifyRegex :: Regex ? -> Regex ?：

simplifyRegex :: Regex sigma -> Regex sigma
simplifyRegex Eps = eps
simplifyRegex Phi = phi
simplifyRegex (S x) = s x
simplifyRegex (x :. y) = simplifyRegex x .: simplifyRegex y
simplifyRegex (x :| y) = simplifyRegex x |: simplifyRegex y

有了这个，很容易制作一个新版本read：

readRegex :: Read sigma => String -> Regex sigma
readRegex = simplifyRegex . read

最后一个有趣的注意事项： 的定义simplifyRegex遵循一个看起来很像折叠的标准形式。事实上，我们甚至可以把它抽象一点，把它变成本质上是折叠的东西：

foldRegex :: a -> a -> (sigma -> a) -> (a -> a -> a) -> (a -> a -> a) -> Regex sigma -> a
foldRegex eps phi s (.:) (|:) = go
  where
    go Eps = eps
    go Phi = phi
    go (S x) = s x
    go (x :. y) = go x .: go y
    go (x :| y) = go x |: go y

此函数将要为每个可能的Regex构造函数执行的操作作为参数，然后递归地解构Regex，在每个点应用该操作。我们可以simplifyRegex通过将其定义为

simplifyRegex :: Regex sigma -> Regex sigma
simplifyRegex = foldRegex eps phi s (.:) (|:)

我们调用foldRegex所有智能构造函数的地方。

通过将此函数发布给您的用户，您可以让他们解构任何函数，Regex而无需真正让他们直接访问Regex构造函数。

要了解更多相关信息，请搜索“catamorphisms”和“recursion scheme”。