Copyright	(c) Fabricio Olivetti 2021 - 2024
License	BSD3
Maintainer	[email protected]
Stability	experimental
Portability
Safe Haskell	None
Language	Haskell2010

Algorithm.EqSat.DB

Description

Pattern matching and rule application functions Heavily based on hegg (https:/github.comalt-romes/hegg by alt-romes)

Synopsis

data Pattern
- = Fixed (SRTree Pattern)
- | VarPat Char
data Rule
- = Pattern :=> Pattern
- | Pattern :==: Pattern
- | Rule :| Condition
type Query = [Atom]
type Condition = Map ClassOrVar ClassOrVar -> EGraph -> Bool
type ClassOrVar = Either EClassId Int
data Atom = Atom ClassOrVar (SRTree ClassOrVar)
unFixPat :: Pattern -> SRTree Pattern
target :: Rule -> Pattern
source :: Rule -> Pattern
getConditions :: Rule -> [Condition]
cleanDB :: forall (m :: Type -> Type). Monad m => EGraphST m ()
match :: forall (m :: Type -> Type). Monad m => Pattern -> EGraphST m [(Map ClassOrVar ClassOrVar, ClassOrVar)]
compileToQuery :: Pattern -> (Query, ClassOrVar)
getInt :: ClassOrVar -> Int
getElems :: SRTree a -> [a]
genericJoin :: forall (m :: Type -> Type). Monad m => Query -> ClassOrVar -> EGraphST m [Map ClassOrVar ClassOrVar]
domainX :: forall (m :: Type -> Type). Monad m => ClassOrVar -> Query -> ClassOrVar -> EGraphST m [ClassOrVar]
intersectAtoms :: forall (m :: Type -> Type). Monad m => ClassOrVar -> Query -> ClassOrVar -> EGraphST m [EClassId]
intersectTries :: ClassOrVar -> Map ClassOrVar EClassId -> IntTrie -> [ClassOrVar] -> Maybe (HashSet EClassId)
updateVar :: ClassOrVar -> ClassOrVar -> Query -> Query
isDiffFrom :: Int -> ClassOrVar -> Bool
elemOfAtom :: ClassOrVar -> Atom -> Bool
orderedVars :: Query -> [ClassOrVar]

Documentation

data Pattern Source #

Constructors

Fixed (SRTree Pattern)
VarPat Char

Instances

Instances details

IsString Pattern Source #
Instance details Defined in Algorithm.EqSat.DB Methods fromString :: String -> Pattern #
Floating Pattern Source #
Instance details Defined in Algorithm.EqSat.DB Methods pi :: Pattern # exp :: Pattern -> Pattern # log :: Pattern -> Pattern # sqrt :: Pattern -> Pattern # (**) :: Pattern -> Pattern -> Pattern # logBase :: Pattern -> Pattern -> Pattern # sin :: Pattern -> Pattern # cos :: Pattern -> Pattern # tan :: Pattern -> Pattern # asin :: Pattern -> Pattern # acos :: Pattern -> Pattern # atan :: Pattern -> Pattern # sinh :: Pattern -> Pattern # cosh :: Pattern -> Pattern # tanh :: Pattern -> Pattern # asinh :: Pattern -> Pattern # acosh :: Pattern -> Pattern # atanh :: Pattern -> Pattern # log1p :: Pattern -> Pattern # expm1 :: Pattern -> Pattern # log1pexp :: Pattern -> Pattern # log1mexp :: Pattern -> Pattern #
Num Pattern Source #
Instance details Defined in Algorithm.EqSat.DB Methods (+) :: Pattern -> Pattern -> Pattern # (-) :: Pattern -> Pattern -> Pattern # (*) :: Pattern -> Pattern -> Pattern # negate :: Pattern -> Pattern # abs :: Pattern -> Pattern # signum :: Pattern -> Pattern # fromInteger :: Integer -> Pattern #
Fractional Pattern Source #
Instance details Defined in Algorithm.EqSat.DB Methods (/) :: Pattern -> Pattern -> Pattern # recip :: Pattern -> Pattern # fromRational :: Rational -> Pattern #
Show Pattern Source #
Instance details Defined in Algorithm.EqSat.DB Methods showsPrec :: Int -> Pattern -> ShowS # show :: Pattern -> String # showList :: [Pattern] -> ShowS #

data Rule Source #

Constructors

Pattern :=> Pattern infix 3
Pattern :==: Pattern infix 3
Rule :\| Condition infixl 2

Instances

Instances details

Show Rule Source #
Instance details Defined in Algorithm.EqSat.DB Methods showsPrec :: Int -> Rule -> ShowS # show :: Rule -> String # showList :: [Rule] -> ShowS #

type Query = [Atom] Source #

type Condition = Map ClassOrVar ClassOrVar -> EGraph -> Bool Source #

type ClassOrVar = Either EClassId Int Source #

data Atom Source #

Constructors

Atom ClassOrVar (SRTree ClassOrVar)

Instances

Instances details

Show Atom Source #
Instance details Defined in Algorithm.EqSat.DB Methods showsPrec :: Int -> Atom -> ShowS # show :: Atom -> String # showList :: [Atom] -> ShowS #

unFixPat :: Pattern -> SRTree Pattern Source #

target :: Rule -> Pattern Source #

source :: Rule -> Pattern Source #

getConditions :: Rule -> [Condition] Source #

cleanDB :: forall (m :: Type -> Type). Monad m => EGraphST m () Source #

match :: forall (m :: Type -> Type). Monad m => Pattern -> EGraphST m [(Map ClassOrVar ClassOrVar, ClassOrVar)] Source #

Returns the substitution rules for every match of the pattern source inside the e-graph.

compileToQuery :: Pattern -> (Query, ClassOrVar) Source #

Returns a Query (list of atoms) of a pattern

getInt :: ClassOrVar -> Int Source #

getElems :: SRTree a -> [a] Source #

returns the list of the children values

genericJoin :: forall (m :: Type -> Type). Monad m => Query -> ClassOrVar -> EGraphST m [Map ClassOrVar ClassOrVar] Source #

Creates the substituion map for the pattern variables for each one of the matched subgraph

domainX :: forall (m :: Type -> Type). Monad m => ClassOrVar -> Query -> ClassOrVar -> EGraphST m [ClassOrVar] Source #

returns the e-class id for a certain variable that matches the pattern described by the atoms

intersectAtoms :: forall (m :: Type -> Type). Monad m => ClassOrVar -> Query -> ClassOrVar -> EGraphST m [EClassId] Source #

returns all e-class id that can matches this sequence of atoms

intersectTries :: ClassOrVar -> Map ClassOrVar EClassId -> IntTrie -> [ClassOrVar] -> Maybe (HashSet EClassId) Source #

searches for the intersection of e-class ids that matches each part of the query. Returns Nothing if the intersection is empty.

var is the current variable being investigated xs is the map of ids being investigated and their corresponding e-class id trie is the current trie of the pattern (i:ids) sequence of root : children of the atom to investigate NOTE: it must be Maybe Set to differentiate between empty set and no answer

updateVar :: ClassOrVar -> ClassOrVar -> Query -> Query Source #

updates all occurrence of var with the new id x

isDiffFrom :: Int -> ClassOrVar -> Bool Source #

checks whether two ClassOrVar are different only check if it is a pattern variable, else returns true

elemOfAtom :: ClassOrVar -> Atom -> Bool Source #

checks if v is an element of an atom

orderedVars :: Query -> [ClassOrVar] Source #

sorts the variables in a query by the most frequently occurring