-- Application of the deep selection patterns -- Michael and Sergio -- Mon Apr 18 15:47:00 PDT 2011 -- updated Thu Jul 6 10:51:06 PDT 2017 -- Examples: -- 1. Find all the vairable of an expression -- 2. Find some common subexpression of an expressio import SetFunctions data Exp = Lit Int | Var [Char] | Add Exp Exp | Mul Exp Exp -- return expressions with a given subexpression withSub exp = exp ? op (withSub exp) unknown ? op unknown (withSub exp) where op = Add ? Mul -- Examples: exp1 = Add (Mul (Lit 42) (Add (Lit 0) (Var "z"))) (Add (Var "x") (Var "y")) exp2 = Add (Mul (Lit 42) (Add (Lit 42) (Var "y"))) (Add (Var "x") (Var "y")) -- get some variable occurring in an expression varOf (withSub (Var v)) = v -- get the set of the variables (identifiers) of an expression allVariablesOf exp = sortValues (set1 varOf exp) -- Sometimes we would like to know the position of the subterm. -- Thus, we return only expressions with a given subexpression at some position: withSubAt [] exp = exp withSubAt (1:ps) exp = (Add ? Mul) (withSubAt ps exp) unknown withSubAt (2:ps) exp = (Add ? Mul) unknown (withSubAt ps exp) -- Return a subterm and each position: subAt (withSubAt p exp) = (p,exp) -- Return a common subterm and its positions: commonSub exp | p1 < p2 && e1==e2 = (e1,p1,p2) where (p1,e1) = subAt exp (p2,e2) = subAt exp -- all the common subexpressions ctest1 = set1 commonSub exp1 ctest2 = set1 commonSub exp2