Algorithm.EqSat.Egraph

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

Documentation

type EClassId = Int

type ClassIdMap = IntMap

type ENode = SRTree EClassId

type ENodeEnc = (Int, Int, Int, Double)

type EGraphST (m :: Type -> Type) a = StateT EGraph m a

type Cost = Int

type CostFun = SRTree Cost -> Cost

type RangeTree a = Seq (a, EClassId)

encodeEnode :: ENode -> ENodeEnc

this assumes up to 999 variables and params

decodeEnode :: ENodeEnc -> ENode

insertRange :: (Ord a, Show a) => EClassId -> a -> RangeTree a -> RangeTree a

removeRange :: (Ord a, Show a) => EClassId -> a -> RangeTree a -> RangeTree a

getWithinRange :: Ord a => a -> a -> RangeTree a -> [EClassId]

getSmallest :: Ord a => RangeTree a -> (a, EClassId)

getGreatest :: Ord a => RangeTree a -> (a, EClassId)

data EGraph

Constructors

EGraph

Fields

• _canonicalMap :: ClassIdMap EClassId
• _eNodeToEClass :: Map ENode EClassId
• _eClass :: ClassIdMap EClass
• _eDB :: EGraphDB

Instances

Show EGraph

Defined in Algorithm.EqSat.Egraph

Methods

showsPrec :: Int -> EGraph -> ShowS

show :: EGraph -> String

showList :: [EGraph] -> ShowS

data EGraphDB

Constructors

EDB

Fields

• _worklist :: HashSet (EClassId, ENode)
• _analysis :: HashSet (EClassId, ENode)
• _patDB :: DB
• _fitRangeDB :: RangeTree Double
• _sizeDB :: IntMap IntSet
• _sizeFitDB :: IntMap (RangeTree Double)
• _unevaluated :: IntSet
• _nextId :: Int

Instances

Show EGraphDB

Defined in Algorithm.EqSat.Egraph

Methods

showsPrec :: Int -> EGraphDB -> ShowS

show :: EGraphDB -> String

showList :: [EGraphDB] -> ShowS

data EClass

Constructors

EClass

Fields

• _eClassId :: Int
• _eNodes :: HashSet ENodeEnc
• _parents :: HashSet (EClassId, ENode)
• _height :: Int
• _info :: EClassData

Instances

Show EClass

Defined in Algorithm.EqSat.Egraph

Methods

showsPrec :: Int -> EClass -> ShowS

show :: EClass -> String

showList :: [EClass] -> ShowS

Eq EClass

Defined in Algorithm.EqSat.Egraph

Methods

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

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

data Consts

Constructors

NotConst

ParamIx Int

ConstVal Double

Instances

Show Consts

Defined in Algorithm.EqSat.Egraph

Methods

showsPrec :: Int -> Consts -> ShowS

show :: Consts -> String

showList :: [Consts] -> ShowS

Eq Consts

Defined in Algorithm.EqSat.Egraph

Methods

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

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

data Property

Constructors

Positive

Negative

NonZero

Real

Instances

Show Property

Defined in Algorithm.EqSat.Egraph

Methods

showsPrec :: Int -> Property -> ShowS

show :: Property -> String

showList :: [Property] -> ShowS

Eq Property

Defined in Algorithm.EqSat.Egraph

Methods

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

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

data EClassData

Constructors

EData

Fields

• _cost :: Cost
• _best :: ENode
• _consts :: Consts
• _fitness :: Maybe Double
• _theta :: Maybe PVector
• _size :: Int

Instances

Show EClassData

Defined in Algorithm.EqSat.Egraph

Methods

showsPrec :: Int -> EClassData -> ShowS

show :: EClassData -> String

showList :: [EClassData] -> ShowS

Eq EClassData

Defined in Algorithm.EqSat.Egraph

Methods

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

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

type DB = Map (SRTree ()) IntTrie

data IntTrie

Constructors

IntTrie

Fields

• _keys :: HashSet EClassId
• _trie :: IntMap IntTrie

Instances

Show IntTrie

Defined in Algorithm.EqSat.Egraph

Methods

showsPrec :: Int -> IntTrie -> ShowS

show :: IntTrie -> String

showList :: [IntTrie] -> ShowS

canonicalMap :: Lens' EGraph (ClassIdMap EClassId)

eClass :: Lens' EGraph (ClassIdMap EClass)

eDB :: Lens' EGraph EGraphDB

eNodeToEClass :: Lens' EGraph (Map ENode EClassId)

eClassId :: Lens' EClass Int

eNodes :: Lens' EClass (HashSet ENodeEnc)

height :: Lens' EClass Int

info :: Lens' EClass EClassData

parents :: Lens' EClass (HashSet (EClassId, ENode))

best :: Lens' EClassData ENode

consts :: Lens' EClassData Consts

cost :: Lens' EClassData Cost

fitness :: Lens' EClassData (Maybe Double)

size :: Lens' EClassData Int

theta :: Lens' EClassData (Maybe PVector)

analysis :: Lens' EGraphDB (HashSet (EClassId, ENode))

fitRangeDB :: Lens' EGraphDB (RangeTree Double)

nextId :: Lens' EGraphDB Int

patDB :: Lens' EGraphDB DB

sizeDB :: Lens' EGraphDB (IntMap IntSet)

sizeFitDB :: Lens' EGraphDB (IntMap (RangeTree Double))

unevaluated :: Lens' EGraphDB IntSet

worklist :: Lens' EGraphDB (HashSet (EClassId, ENode))

E-Graph basic supporting functions

emptyGraph :: EGraph

returns an empty e-graph

emptyDB :: EGraphDB

returns an empty e-graph DB

createEClass :: EClassId -> ENode -> EClassData -> Int -> EClass

Creates a new e-class from an e-class id, a new e-node, and the info of this e-class

canonical :: forall (m :: Type -> Type). Monad m => EClassId -> EGraphST m EClassId

gets the canonical id of an e-class

canonize :: forall (m :: Type -> Type). Monad m => ENode -> EGraphST m ENode

canonize the e-node children

getEClass :: forall (m :: Type -> Type). Monad m => EClassId -> EGraphST m EClass

gets an e-class with id c

trie :: EClassId -> IntMap IntTrie -> IntTrie

Creates a singleton trie from an e-class id

isConst :: forall (m :: Type -> Type). Monad m => EClassId -> EGraphST m Bool

Check whether an e-class is a constant value

Orphan instances

Hashable ENode

Methods

hashWithSalt :: Int -> ENode -> Int

hash :: ENode -> Int