Database.Algebra.Rewrite.DagRewrite

This module provides a monadic interface to rewrites on algebra DAGs.

The Rewrite monad

data Rewrite o e a

A Monad for DAG rewrites, parameterized over the type of algebra operators.

Instances

Monad (Rewrite o e)

Functor (Rewrite o e)

Applicative (Rewrite o e)

runRewrite :: Operator o => Rewrite o e r -> AlgebraDag o -> e -> Bool -> (AlgebraDag o, e, r, Log)

Run a rewrite action on the supplied graph. Returns the rewritten node map, the potentially modified list of root nodes, the result of the rewrite and the rewrite log.

initRewriteState :: (Ord o, Operator o) => AlgebraDag o -> e -> Bool -> RewriteState o e

type Log = Seq String

The log from a sequence of rewrite actions.

logGeneral :: String -> Rewrite o e ()

Log a general message

logRewrite :: String -> AlgNode -> Rewrite o e ()

Log a rewrite

reachableNodesFrom :: AlgNode -> Rewrite o e (Set AlgNode)

Return the set of nodes that are reachable from the specified node.

parents :: AlgNode -> Rewrite o e [AlgNode]

Return the parents of a node

topsort :: Operator o => Rewrite o e [AlgNode]

Return a topological ordering of all reachable nodes in the DAG.

operator :: Operator o => AlgNode -> Rewrite o e o

Return the operator for a node id.

operatorSafe :: AlgNode -> Rewrite o e (Maybe o)

rootNodes :: Rewrite o e [AlgNode]

Returns the root nodes of the DAG.

exposeDag :: Rewrite o e (AlgebraDag o)

Exposes the current state of the DAG

getExtras :: Rewrite o e e

updateExtras :: e -> Rewrite o e ()

condRewrite :: Rewrite o e Bool -> Rewrite o e Bool

Preserve the effects of a rewrite only if the rewrite signals success by returning True. Otherwise, the state before the rewrite is put in place again.

insert :: (Operator o, Show o) => o -> Rewrite o e AlgNode

Insert an operator into the DAG and return its node id. If the operator is already present (same op, same children), reuse it.

insertNoShare :: Operator o => o -> Rewrite o e AlgNode

Insert an operator into the DAG and return its node id WITHOUT reusing an operator if it is already present.

replaceChild :: Operator o => AlgNode -> AlgNode -> AlgNode -> Rewrite o e ()

replaceChildM n old new replaces all links from node n to node old with links to node new

replace :: Operator o => AlgNode -> AlgNode -> Rewrite o e ()

replace old new replaces _all_ links to old with links to new

replaceWithNew :: (Operator o, Show o) => AlgNode -> o -> Rewrite o e AlgNode

Creates a new node from the operator and replaces the old node with it by rewiring all links to the old node.

replaceRoot :: Operator o => AlgNode -> AlgNode -> Rewrite o e ()

infer :: (AlgebraDag o -> b) -> Rewrite o e b

Apply a pure function to the DAG.

collect :: (Show o, Operator o) => Rewrite o e ()