用树简化 Haskell 中的正则表达式

Question

我有这个正则表达式 (RE) 的数据结构，到目前为止我没有任何修改 RE 的函数:

data Regex a = Letter a | Emptyword | Concat (Regex a) (Regex a) | Emptyset | Or (Regex a) (Regex a) | Star (Regex a)
    deriving (Show, Eq)

我想为我的 RE 实施简化算法。为此，我认为我应该首先将 RE 表示为树，根据一些等价更新树，然后将其转换回 RE。我的理由是，对于树，我将具有查找、提取和附加子树、更新值等的功能。

但是，我很难找到一个树模块提供这些功能并且足够简单以供初学者学习。我找到了这个 avl-tree package 但是，它看起来很大。

我想对我的树方法和支持上述功能的简单树模块的建议提出替代建议。请注意，我是 Haskell 的初学者，我还不了解 monad，而且我对简化 RE 的实现不感兴趣。

编辑1：我们知道下面两个RE是等价的，其中L b代表Letter b，C代表Concat:

    Or                          Or
   /  \                        / \
  L b  C            =        L b  L a
      /  \                        
    L a  Emptyword

所以给定左边的 RE，我想用 L a 标记的节点替换其根标记为 C 的子树。正如所指出的，我的数据结构是树结构。但是，目前我没有功能，例如用节点替换子树，或找到我可以替换的结构的子树。

Answer 1

如评论中所述，您已经有一棵树。你可以马上简化：

simplify :: Regex a -> Regex a
simplify (Star Emptyset)   = Emptyword
simplify (Star (Star x))   = Star (simplify x)
simplify (Concat x Emptyword) = simplify x
simplify (Concat Emptyword y) = simplify y
simplify (Or x y) | x == y = x
-- or rather simplify (Or x y) | simplify x == simplify y = simplify x
-- more sophisticated rules here
-- ...
-- otherwise just push down
simplify (Or x y) = simplify (Or (simplify x) (simplify y)
-- ...
simplify x@(Letter _) = x

这只是表面现象，例如第一条规则应该是 simplify (Star x) | simplify x == Emptyset = emptyword.

AVL 树

AVL树是为了平衡，这里不太适用。平衡唯一有意义的地方是关联操作

Or (x (Or y z) == Or (Or x y) y

我建议对这些操作使用列表

data Regex' a = Letter' a | Concat' [Regex a]  | Or [Regex a] | Star (Regex a)
deriving (Show, Eq)

（没有Emptyword'因为是Concat' []；同Emptyset'和Or。） Regex 和 Regex' 之间的转换是 reader.

的常用练习

一般硬度

请注意，正则表达式等价并不容易：

(a|b)* = (a*b)*a*

优化 Or "(a|b)*" "(a*b)*a*" 很难...

用树简化 Haskell 中的正则表达式

Simplifying regex in Haskell with trees

regex

tree

haskell

AVL 树

一般硬度