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

Question

采用这个简单的数据类型(来自 Uniplate documentation ):

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

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

如果我们推导出 Uniplate对于 Expr ，我们就可以使用 universe 为了编写这两个简单的函数:

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

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

我想提取公共(public)代码并编写一些“通用”函数来接受有关构造函数的一些信息，但我什至想不出匹配的类型签名，这通常是一个不好的迹象。这个功能是否有意义，实现它的正确方法是什么？

谢谢!

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))