srtree-2.0.0.0: A general library to work with Symbolic Regression expression trees.
Copyright(c) Fabricio Olivetti 2021 - 2024
LicenseBSD3
Maintainerfabricio.olivetti@gmail.com
Stabilityexperimental
Portability
Safe HaskellSafe-Inferred
LanguageHaskell2010

Algorithm.EqSat.Egraph

Description

Equality Graph data structure Heavily based on hegg (https:/github.comalt-romes/hegg by alt-romes)

Synopsis

Documentation

type EClassId = Int #

type ClassIdMap = IntMap #

type ENode = SRTree EClassId #

type EData = () #

type EGraphST a = State EGraph a #

type Cost = Int #

type CostFun = SRTree Cost -> Cost #

data EGraph #

Constructors

EGraph 

Fields

Instances

Instances details
Show EGraph # 
Instance details

Defined in Algorithm.EqSat.Egraph

Methods

showsPrec :: Int -> EGraph -> ShowS #

show :: EGraph -> String #

showList :: [EGraph] -> ShowS #

data EClass #

Constructors

EClass 

Fields

Instances

Instances details
Show EClass # 
Instance details

Defined in Algorithm.EqSat.Egraph

Methods

showsPrec :: Int -> EClass -> ShowS #

show :: EClass -> String #

showList :: [EClass] -> ShowS #

Eq EClass # 
Instance details

Defined in Algorithm.EqSat.Egraph

Methods

(==) :: EClass -> EClass -> Bool #

(/=) :: EClass -> EClass -> Bool #

data Consts #

Constructors

NotConst 
ParamIx Int 
ConstVal Double 

Instances

Instances details
Show Consts # 
Instance details

Defined in Algorithm.EqSat.Egraph

Methods

showsPrec :: Int -> Consts -> ShowS #

show :: Consts -> String #

showList :: [Consts] -> ShowS #

Eq Consts # 
Instance details

Defined in Algorithm.EqSat.Egraph

Methods

(==) :: Consts -> Consts -> Bool #

(/=) :: Consts -> Consts -> Bool #

data Property #

Constructors

Positive 
Negative 
NonZero 
Real 

Instances

Instances details
Show Property # 
Instance details

Defined in Algorithm.EqSat.Egraph

Methods

showsPrec :: Int -> Property -> ShowS #

show :: Property -> String #

showList :: [Property] -> ShowS #

Eq Property # 
Instance details

Defined in Algorithm.EqSat.Egraph

Methods

(==) :: Property -> Property -> Bool #

(/=) :: Property -> Property -> Bool #

data EClassData #

Constructors

EData 

Fields

Instances

Instances details
Show EClassData # 
Instance details

Defined in Algorithm.EqSat.Egraph

Methods

showsPrec :: Int -> EClassData -> ShowS #

show :: EClassData -> String #

showList :: [EClassData] -> ShowS #

Eq EClassData # 
Instance details

Defined in Algorithm.EqSat.Egraph

Methods

(==) :: EClassData -> EClassData -> Bool #

(/=) :: EClassData -> EClassData -> Bool #

worklist :: Lens' EGraph [(EClassId, ENode)] #

nextId :: Lens' EGraph Int #

eNodeToEClass :: Lens' EGraph (Map ENode EClassId) #

eClass :: Lens' EGraph (ClassIdMap EClass) #

canonicalMap :: Lens' EGraph (ClassIdMap EClassId) #

analysis :: Lens' EGraph [(EClassId, ENode)] #

parents :: Lens' EClass [(EClassId, ENode)] #

info :: Lens' EClass EClassData #

height :: Lens' EClass Int #

eNodes :: Lens' EClass (Set ENode) #

eClassId :: Lens' EClass Int #

cost :: Lens' EClassData Cost #

consts :: Lens' EClassData Consts #

best :: Lens' EClassData ENode #

add :: CostFun -> ENode -> EGraphST EClassId #

adds a new or existing e-node (merging if necessary)

rebuild :: CostFun -> EGraphST () #

rebuilds the e-graph after inserting or merging e-classes

repair :: CostFun -> EClassId -> ENode -> EGraphST () #

repairs e-node by canonizing its children if the canonized e-node already exists in e-graph, merge the e-classes

repairAnalysis :: CostFun -> EClassId -> ENode -> EGraphST () #

repair the analysis of the e-class considering the new added e-node

merge :: CostFun -> EClassId -> EClassId -> EGraphST EClassId #

merge to equivalnt e-classes

modifyEClass :: CostFun -> EClassId -> EGraphST EClassId #

joinData :: EClassData -> EClassData -> EClassData #

makeAnalysis :: CostFun -> ENode -> EGraphST EClassData #

Calculate e-node data (constant values and cost)

fromTree :: CostFun -> Fix SRTree -> (EClassId, EGraph) #

Creates an e-graph from an expression tree

fromTrees :: CostFun -> [Fix SRTree] -> ([EClassId], EGraph) #

Builds an e-graph from multiple independent trees

fromTreeWith :: CostFun -> EGraph -> Fix SRTree -> (EClassId, EGraph) #

insert new tree into an existing e-graph

findRootClasses :: EGraph -> [EClassId] #

returns all the root e-classes (e-class without parents)

getExpressionFrom :: EGraph -> EClassId -> Fix SRTree #

returns one expression rooted at e-class eId

getAllExpressionsFrom :: EGraph -> EClassId -> [Fix SRTree] #

returns all expressions rooted at e-class eId

getRndExpressionFrom :: EGraph -> EClassId -> State StdGen (Fix SRTree) #

returns a random expression rooted at e-class eId

calculateHeights :: EGraphST () #

update the heights of each e-class won't work if there's no root

canonical :: EClassId -> EGraphST EClassId #

gets the canonical id of an e-class

canonical' :: EClassId -> EGraph -> EClassId #

canonize :: ENode -> EGraphST ENode #

canonize the e-node children

sequence' :: Applicative f => SRTree (f a) -> f (SRTree a) #

children :: SRTree a -> [a] #

replaceChildren :: [a] -> SRTree b -> SRTree a #

getOperator :: SRTree a -> SRTree () #

getEClass :: EClassId -> EGraphST EClass #

gets an e-class with id c

emptyGraph :: EGraph #

returns an empty e-graph

calculateCost :: CostFun -> SRTree EClassId -> EGraphST Cost #

calculates the cost of a node

calculateConsts :: SRTree EClassId -> EGraphST Consts #

check whether an e-node evaluates to a const

combineConsts :: SRTree Consts -> Consts #