Maintainer	bastiaan.heeren@ou.nl
Stability	provisional
Portability	portable (depends on ghc)
Safe Haskell	None
Language	Haskell98

Ideas.Common.Strategy

Contents

Data types and type classes
Running strategies
Strategy combinators
Configuration combinators
Strategy locations
Prefixes
Misc

Description

A strategy is a context-free grammar with rules as symbols. Strategies can be labeled with strings. A type class is introduced to lift all the combinators that work on strategies, only to prevent that you have to insert these lifting functions yourself.

Synopsis

Data types and type classes

data Strategy a Source

Abstract data type for strategies

Instances

Apply Strategy
LiftView Strategy
IsStrategy Strategy
Show (Strategy a)

data LabeledStrategy a Source

A strategy which is labeled with an identifier

Instances

Apply LabeledStrategy
LiftView LabeledStrategy
IsStrategy LabeledStrategy
Show (LabeledStrategy a)
HasId (LabeledStrategy a)

class IsStrategy f where Source

Type class to turn values into strategies

Methods

toStrategy :: f a -> Strategy a Source

Instances

IsStrategy RewriteRule
IsStrategy Rule
IsStrategy LabeledStrategy
IsStrategy Strategy

Running strategies

derivationList :: IsStrategy f => (Rule a -> Rule a -> Ordering) -> f a -> a -> [Derivation (Rule a, Environment) a] Source

Strategy combinators

Basic combinators

(<*>) :: (IsStrategy f, IsStrategy g) => f a -> g a -> Strategy a infixr 5 Source

Put two strategies in sequence (first do this, then do that)

(<|>) :: (IsStrategy f, IsStrategy g) => f a -> g a -> Strategy a infixr 3 Source

Choose between the two strategies (either do this or do that)

(<%>) :: (IsStrategy f, IsStrategy g) => f a -> g a -> Strategy a infixr 2 Source

Interleave two strategies

succeed :: Strategy a Source

The strategy that always succeeds (without doing anything)

fail :: Strategy a Source

The strategy that always fails

atomic :: IsStrategy f => f a -> Strategy a Source

Makes a strategy atomic (w.r.t. parallel composition)

label :: (IsId l, IsStrategy f) => l -> f a -> LabeledStrategy a Source

Labels a strategy with an identifier. Labels are used to identify substrategies and to specialize feedback messages. The first argument of label can be of type String, in which case the string is used as identifier (and not as description).

sequence :: IsStrategy f => [f a] -> Strategy a Source

Puts a list of strategies into a sequence

alternatives :: IsStrategy f => [f a] -> Strategy a Source

Combines a list of alternative strategies

interleave :: IsStrategy f => [f a] -> Strategy a Source

Merges a list of strategies (in parallel)

permute :: IsStrategy f => [f a] -> Strategy a Source

Allows all permutations of the list

fix :: (Strategy a -> Strategy a) -> Strategy a Source

A fix-point combinator on strategies (to model recursion). Powerful (but dangerous) combinator

EBNF combinators

many :: IsStrategy f => f a -> Strategy a Source

Repeat a strategy zero or more times (non-greedy)

many1 :: IsStrategy f => f a -> Strategy a Source

Apply a certain strategy at least once (non-greedy)

replicate :: IsStrategy f => Int -> f a -> Strategy a Source

Apply a strategy a certain number of times

option :: IsStrategy f => f a -> Strategy a Source

Apply a certain strategy or do nothing (non-greedy)

Negation and greedy combinators

check :: (a -> Bool) -> Strategy a Source

Checks whether a predicate holds for the current term. The check is considered to be a minor step.

not :: IsStrategy f => f a -> Strategy a Source

Check whether or not the argument strategy cannot be applied: the result strategy only succeeds if this is not the case (otherwise it fails).

repeat :: IsStrategy f => f a -> Strategy a Source

Repeat a strategy zero or more times (greedy version of many)

repeat1 :: IsStrategy f => f a -> Strategy a Source

Apply a certain strategy at least once (greedy version of many1)

try :: IsStrategy f => f a -> Strategy a Source

Apply a certain strategy if this is possible (greedy version of option)

(|>) :: (IsStrategy f, IsStrategy g) => f a -> g a -> Strategy a infixr 4 Source

Left-biased choice: if the left-operand strategy can be applied, do so. Otherwise, try the right-operand strategy

(>|>) :: (IsStrategy f, IsStrategy g) => f a -> g a -> Strategy a infixr 4 Source

Choose between the two strategies, with a preference for steps from the left hand-side strategy.

exhaustive :: IsStrategy f => [f a] -> Strategy a Source

Apply the strategies from the list exhaustively (until this is no longer possible)

while :: IsStrategy f => (a -> Bool) -> f a -> Strategy a Source

Repeat the strategy as long as the predicate holds

until :: IsStrategy f => (a -> Bool) -> f a -> Strategy a Source

Repeat the strategy until the predicate holds

multi :: (IsId l, IsStrategy f) => l -> f a -> Strategy a Source

Apply a strategy at least once, but collapse into a single step

Graph

type DependencyGraph node key = (Graph, Vertex -> (node, key, [key]), key -> Maybe Vertex) Source

dependencyGraph :: IsStrategy f => DependencyGraph (f a) key -> Strategy a Source

Create a strategy from a dependency graph with strategies as nodes Does not check for cycles

Traversal combinators

module Ideas.Common.Strategy.Traversal

Configuration combinators

module Ideas.Common.Strategy.Configuration

remove :: IsStrategy f => f a -> Strategy a Source

collapse :: IsStrategy f => f a -> Strategy a Source

hide :: IsStrategy f => f a -> Strategy a Source

Strategy locations

strategyLocations :: LabeledStrategy a -> [([Int], Id)] Source

Returns a list of all strategy locations, paired with the label

checkLocation :: Id -> LabeledStrategy a -> Bool Source

subTaskLocation :: LabeledStrategy a -> Id -> Id -> Id Source

nextTaskLocation :: LabeledStrategy a -> Id -> Id -> Id Source

Prefixes

data Prefix a Source

Instances

Show (Prefix a)
Monoid (Prefix a)
Firsts (Prefix a)
type Elem (Prefix a) = (Step a, a)

emptyPrefix :: IsStrategy f => f a -> a -> Prefix a Source

Construct the empty prefix for a labeled strategy

noPrefix :: Prefix a Source

The error prefix (i.e., without a location in the strategy).

replayPath :: IsStrategy f => Path -> f a -> a -> ([Step a], Prefix a) Source

Construct a prefix for a path and a labeled strategy. The third argument is the current term.

replayPaths :: IsStrategy f => [Path] -> f a -> a -> Prefix a Source

Construct a prefix for a list of paths and a labeled strategy. The third argument is the current term.

replayStrategy :: (Monad m, IsStrategy f) => Path -> f a -> a -> m (a, Prefix a) Source

Construct a prefix for a path and a labeled strategy. The third argument is the initial term.

data Step a Source

The steps during the parsing process: enter (or exit) a labeled sub-strategy, or a rule.

Constructors

Enter Id	Enter a labeled sub-strategy
Exit Id	Exit a labeled sub-strategy
RuleStep Environment (Rule a)	Rule that was applied

Instances

Apply Step
Eq (Step a)
Show (Step a)
Minor (Step a)
HasId (Step a)

stepRule :: Step a -> Rule a Source

stepEnvironment :: Step a -> Environment Source

data Path Source

A path encodes a location in a strategy. Paths are represented as a list of integers.

Instances

Eq Path
Show Path

emptyPath :: Path Source

The empty path.

readPath :: Monad m => String -> m Path Source

readPaths :: Monad m => String -> m [Path] Source

prefixPaths :: Prefix a -> [Path] Source

Returns the current Path.

majorPrefix :: Prefix a -> Prefix a Source

Transforms the prefix such that only major steps are kept in the remaining strategy.

isEmptyPrefix :: Prefix a -> Bool Source

Misc

cleanUpStrategy :: (a -> a) -> LabeledStrategy a -> LabeledStrategy a Source

Use a function as do-after hook for all rules in a labeled strategy, but also use the function beforehand

cleanUpStrategyAfter :: (a -> a) -> LabeledStrategy a -> LabeledStrategy a Source

Use a function as do-after hook for all rules in a labeled strategy

rulesInStrategy :: IsStrategy f => f a -> [Rule a] Source

Returns a list of all major rules that are part of a labeled strategy