Control.DeepSeq.Bounded.PatAlg

Basic operations on Patterns

unionPats :: [Pattern] -> Pattern

Compute the union of a list of Patterns.

intersectPats :: [Pattern] -> Pattern

Compute the intersection of a list of Patterns.

XXX This doesn't yet handle type-constrained PatNodes (TI, TR, TN or TW).

isSubPatOf :: Pattern -> Pattern -> Bool

Return True if the first pattern matches the second (and False otherwise).

Note that matching does not imply spanning. Equality (==) or flip isSubPatOf will work there, depending on your intentions.

XXX This doesn't yet handle type-constrained PatNodes (TI, TR, TN or TW), because intersectPats doesn't.

Operations for obtaining and modifying Patterns based on a term

mkPat :: forall d. Data d => d -> Pattern

Obtain a lazy pattern, matching the shape of an arbitrary term (value expression). Interior nodes will be WR, and leaves will be WS.

Note this gives counter-intuitive results when used on Rose a. For example, a rose tree with a single node will have a 3-node /\ shape.) Formally, mkPat is not idempotent on Patterns, but rather grows without bound when iterated. This shouldn't be an issue in practise.

mkPatN :: forall d. Data d => Int -> d -> Pattern

Obtain a lazy pattern, matching the shape of an arbitrary term, but only down to at most depth n. Interior nodes will be WR. Leaf nodes will be WS if they were leaves in the host value; otherwise (i.e. if they are at depth n) they will be WR.

Satisfies forcep . mkPatN n = forcen n.

See caveat in the comment to mkPat.

growPat :: forall d. Data d => Pattern -> d -> Pattern

Grow all leaves by one level within the shape of the provided value.

Operations for obtaining subpatterns (in the isSubPatOf sense)

truncatePat :: Int -> Pattern -> Pattern

Given an integer depth and a pattern, truncate the pattern to extend to at most this requested depth.

shrinkPat :: Pattern -> Pattern

Elide all leaves which have no non-leaf sibling. We want the pattern to still match the same value, only less of it. Merely eliding all leaves would, in most cases, cause match failure, so we have to be a bit more subtle. There are some arbitrary decisions about the relaxation route through the lattice. (Refer to the source for details.)

shrinkPat_old :: Pattern -> Pattern

Old version, for temporary compatibility of seqaid demo mode.

Operations for the direct construction and perturbation of Patterns

emptyPat :: Pattern

There is no Nil in the Pattern type, but a single WI node as empty pattern is a dependable way to assure the empty pattern never forces anything.

liftPats :: [Pattern] -> Pattern

This creates a new WR node, the common root. The argument patterns become the children of the root (order is preserved).

splicePats :: Pattern -> [Int] -> [(Int, Pattern)] -> Pattern

Introduce siblings at a node (interior or leaf) of the target. The first argument is target, the second is a path, and the third is a list of subpatterns for insertion, along with the indices of the child before which to insert. If this index is negative, it counts from the right. Indices are always relative to the original target as it was received.

elidePats :: Pattern -> [Int] -> [Int] -> Pattern

Elide siblings at a node (interior or leaf) of the target. The first argument is target, the second is a path, and the third is a list of child indices for elision. If this index is negative, it counts from the right. Indices are always relative to the original target as it was received.

erodePat :: StdGen -> [Int] -> Pattern -> (Pattern, StdGen)

Select a leaf at random, and elide it. In order to achieve fairness, the node probabilities are weighted by nodes in branch. The path arg can "focus" the stochastic erosion to only consider leaves beneath a given node.

Re-exported for convenience

module Control.DeepSeq.Bounded.Pattern