[−][src]Trait egg::CostFunction

pub trait CostFunction<L: Language> {
    type Cost: PartialOrd + Debug + Clone;
    fn cost<C>(&mut self, enode: &L, costs: C) -> Self::Cost
    where
        C: FnMut(Id) -> Self::Cost;

    fn cost_rec(&mut self, expr: &RecExpr<L>) -> Self::Cost { ... }
}

A cost function that can be used by an Extractor.

To extract an expression from an EGraph, the Extractor requires a cost function to performs its greedy search. egg provides the simple AstSize and AstDepth cost functions.

The example below illustrates a silly but realistic example of implementing a cost function that is essentially AST size weighted by the operator:

struct SillyCostFn;
impl CostFunction<StringLang> for SillyCostFn {
    type Cost = f64;
    // you're passed in an enode whose children are costs instead of eclass ids
    fn cost<C>(&mut self, enode: &StringLang, mut costs: C) -> Self::Cost
    where
        C: FnMut(Id) -> Self::Cost
    {
        let op_cost = match enode.op.as_ref() {
            "foo" => 100.0,
            "bar" => 0.7,
            _ => 1.0
        };
        enode.fold(op_cost, |sum, id| sum + costs(id))
    }
}

let e: RecExpr<StringLang> = "(do_it foo bar baz)".parse().unwrap();
assert_eq!(SillyCostFn.cost_rec(&e), 102.7);
assert_eq!(AstSize.cost_rec(&e), 4);
assert_eq!(AstDepth.cost_rec(&e), 2);

Associated Types

type Cost: PartialOrd + Debug + Clone

The Cost type. It only requires PartialOrd so you can use floating point types, but failed comparisons (NaNs) will result in a panic.

Loading content...

Required methods

fn cost<C>(&mut self, enode: &L, costs: C) -> Self::Cost where
    C: FnMut(Id) -> Self::Cost, 

Calculates the cost of an enode whose children are Costs.

For this to work properly, your cost function should be monotonic, i.e. cost should return a Cost greater than any of the child costs of the given enode.

Loading content...

Provided methods

fn cost_rec(&mut self, expr: &RecExpr<L>) -> Self::Cost

Calculates the total cost of a RecExpr.

As provided, this just recursively calls cost all the way down the RecExpr.

Loading content...

Implementors

impl<L: Language> CostFunction<L> for AstDepth[src]

type Cost = usize

impl<L: Language> CostFunction<L> for AstSize[src]

type Cost = usize

Loading content...