Data.BreadthFirstCata.Cata

Some combinators to express breadth-first evaluation of catamorphisms, which allows you to stepwise evaluate the results of children. If, during the evaluation of an alternative, a choice needs to be made between taking the results of its children, with these combinators, you can stepwise evaluate the children in parallel, until a choice can be made. Until a choice is made, evaluation proceeds strictly; after a choice is made, evaluation proceeds lazily. What constitutes to be a step is determined by the callee.

Documentation

newtype Sem i n

Semantics of a nonterminal of type n as a function from inherited attributes (Inh n) to a computation Comp i n of synthesized attributes (Syn n).

Constructors

Sem (Inh n -> Comp i n)

data family Inh n

data family Syn n

data Comp i n

Computation of synthesized attributes of nonterminal of type n. It is a trace of Info-effects, that keeps track of the intermediate states of the tree (using Pending), ending ultimately in the synthesized values (using Final). Operationally, we lift Info-values over Pending-values, thereby gradually rewriting the latter, until it results in a Final.

invoke :: Sem i n -> Inh n -> Comp i n

Unwrapper for Sem.

final :: Syn n -> Comp i n

Wrapper for final result.

info :: i -> Comp i n -> Comp i n

Wrapper for an effect.

resume :: Comp i m -> (Syn m -> Comp i n) -> Comp i n

Create a |Pending| computation that waits for the given computation.

inject :: i -> Comp i Inject

sem_Inject :: Sem i Inject

data Inject

Injection of steps as conventional call

lazyEval :: Comp i a -> Syn a

Lazy evaluation of a computation. Note: we cannot inspect the effect-trace, as it would sequentialize the evaluation of children.

oneStep :: Comp i a -> Outcome i a

One step strict evaluation. Reduction proceeds until the computation is either finished or yields an Info-effect.

data Outcome i a

Result of one step evaluation: either the final result or an updated computation. What constitutes to a step depends on the application: evaluation proceeds until an outcome can be given.

Constructors

Fin (Syn a)

Step i (Comp i a)