检查AST是否递归地包含特定的构造函数

Question

取这个简单的数据类型(来自Uniplate文档):

data Expr = Val Int
          | Neg Expr
          | Add Expr Expr

我想检查表达式树是否包含特定的操作(在我们的例子中是Neg和Add)。

如果我们为Expr导出Uniplate，我们将能够使用universe来编写这两个简单的函数:

hasNeg :: Expr -> Bool
hasNeg e = not $ null [() | Neg{} <- universe e]
hasAdd :: Expr -> Bool
hasAdd e = not $ null [() | Add{} <- universe e]

我想提取公共代码并编写一些"泛型"函数，它将接受有关构造函数的一些信息，但我甚至无法想到匹配的类型签名，这通常是一个不好的迹象。这个函数有意义吗?实现它的正确方法是什么?

谢谢!

Answer 1

Control.Lens.Plated具有与uniplate相似的API(性能也大致相同)，但是对于lens，您可以使用棱镜作为一级构造函数:

{-# LANGUAGE TemplateHaskell #-}
import Control.Applicative
import Control.Lens
import Control.Lens.Extras
data Expr = Val Int
          | Neg Expr
          | Add Expr Expr deriving (Eq, Show)
instance Plated Expr where
    plate f (Val i)   = pure (Val i)
    plate f (Neg e)   = Neg <$> f e
    plate f (Add a b) = Add <$> f a <*> f b 
makePrisms ''Expr -- derives _Val, _Neg and _Add prisms
hasNeg :: Expr -> Bool 
hasNeg = any (is _Neg) . universe
hasPrism :: Prism' Expr a -> Expr -> Bool
hasPrism p = any (is p) . universe
hasAdd :: Expr -> Bool
hasAdd = hasPrism _Add 
hasNegNeg :: Expr -> Bool
hasNegNeg = hasPrism (_Neg . _Neg) -- matches (Neg (Neg x))