| Safe Haskell | Safe-Inferred |
|---|---|
| Language | Haskell2010 |
Data.Equality.Extraction
Contents
Description
Given an e-graph representing expressions of our language, we might want to
extract, out of all expressions represented by some equivalence class, the best
expression (according to a CostFunction) represented by that class
The function extractBest allows us to do exactly that: get the best
expression represented in an e-class of an e-graph given a CostFunction
Synopsis
- extractBest :: forall lang. Language lang => EGraph lang -> CostFunction lang -> ClassId -> Fix lang
- type CostFunction l = l Cost -> Cost
- type Cost = Int
- depthCost :: Language l => CostFunction l
Extraction
Arguments
| :: forall lang. Language lang | |
| => EGraph lang | The e-graph out of which we are extracting an expression |
| -> CostFunction lang | The cost function to define best |
| -> ClassId | The e-class from which we'll extract the expression |
| -> Fix lang | The resulting best expression, in its fixed point form. |
Extract the best expression from an equivalence class according to a
CostFunction
(i, egr) = ...
i <- represent expr
...
bestExpr = extractBest egr depthCost i
For a real example you might want to check out the source code of equalitySaturation'
Cost
type CostFunction l = l Cost -> Cost Source #
A cost function is used to attribute a cost to representations in the e-graph and to extract the best one.
Example
symCost :: Expr Cost -> Cost
symCost = case
BinOp Integral e1 e2 -> e1 + e2 + 20000
BinOp Diff e1 e2 -> e1 + e2 + 500
BinOp x e1 e2 -> e1 + e2 + 3
UnOp x e1 -> e1 + 30
Sym _ -> 1
Const _ -> 1
depthCost :: Language l => CostFunction l Source #
Simple cost function: the deeper the expression, the bigger the cost