Ensure that AST contains a specific constructor recursively

Question

Take this simple data type (from the Uniplate documentation ):

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

I want to check if the expression tree contains a certain operation (in our case, Negand Add).

If we get Uniplatefor Expr, we can use universeto write these two simple functions:

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

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

I would like to extract the general code and write some “general” function that will take some information about the constructor, but I can’t even think of a signature of the appropriate type, which is usually a bad sign. Does this function make any sense and what is its correct way?

Thank!

Answer 1

Control.Lens.Plated API uniplate ( ), 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))