时间戳

首页 > 解决方案 > Haskell向构造函数添加约束

haskell - Haskell向构造函数添加约束

问题描述

背景：
我正在学习关于“语言和自动机”的课程：目前是关于正则表达式/语言、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

标签： haskellconstructorformal-languages

解决方案

听起来您可能想使用智能构造函数。基本思想是数据类型的实际构造函数是隐藏的，并且您可以公开这些构造函数的特殊版本。这在构造上非常有用，但正如@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”。

推荐阅读