[−][src]Trait egg::CostFunction

pub trait CostFunction<L: Language> {
    type Cost: PartialOrd + Debug + Clone;
    fn cost(&mut self, enode: &ENode<L, Self::Cost>) -> 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:

use egg::{*, recexpr as r};

type Lang = String;

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

let e: RecExpr<Lang> = r!("+", r!("foo"), r!("bar"), r!("baz"));
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(&mut self, enode: &ENode<L, Self::Cost>) -> 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...