Safe Haskell	Safe-Inferred
Language	Haskell2010

Overeasy.Matching

Description

Methods to match patterns in EGraphs (aka e-matching)

Synopsis

type Pat = Free
patVars :: (Foldable f, Eq v, Hashable v) => Pat f v -> HashSet v
type PatGroup g f v = g (Pat f v)
type Subst c v = HashMap v c
substVars :: Subst a v -> HashSet v
newtype VarId = VarId {
- unVarId :: Int
}
type PatGraphC f v = (Traversable f, Traversable f, Eq v, Eq (f VarId), Hashable v, Hashable (f VarId))
data PatGraph g f v = PatGraph {
- pgRoots :: !(g VarId)
- pgNodes :: !(IntLikeMap VarId (PatF f v VarId))
- pgVars :: !(HashMap v VarId)
}
patGraph :: (Traversable g, PatGraphC f v) => PatGroup g f v -> PatGraph g f v
singlePatGraph :: PatGraphC f v => Pat f v -> PatGraph Identity f v
data Match c f v = Match {
- matchAnno :: !c
- matchPat :: !(MatchPat c f v)
}
data MatchPat c f v
- = MatchPatPure !v
- | MatchPatEmbed !(f (Match c f v))
data MatchF c f v r = MatchF {
- matchClassF :: !c
- matchPatF :: !(MatchPatF f v r)
}
data MatchPatF f v r
- = MatchPatPureF !v
- | MatchPatEmbedF !(f r)
matchVars :: (Foldable f, Eq v, Hashable v) => Match c f v -> HashSet v
matchClasses :: (Coercible c Int, Functor f, Foldable f) => Match c f v -> IntLikeSet c
data MatchSubst c f v = MatchSubst {
- msMatch :: !(Match c f v)
- msSubst :: !(Subst c v)
}
type SolGraphC f = (Functor f, Foldable f, Eq (f ()), Hashable (f ()))
data SolGraph c f = SolGraph {
- sgByVar :: !(IntLikeMap VarId (IntLikeSet c))
- sgNodes :: !(HashMap (f c) c)
}
solGraph :: SolGraphC f => PatGraph g f v -> EGraph d f -> SolGraph EClassId f
type SolStream c g f v z = Stream (SolEnv c g f v) (SolState c) z
type SolveC c f v = (Traversable f, Coercible c Int, Eq v, Hashable v, Eq (f c), Hashable (f c))
solve :: (Foldable g, SolveC c f v) => SolStream c g f v (MatchSubst c f v)
match :: (PatGraphC f v, SolGraphC f, SolveC EClassId f v) => Pat f v -> EGraph d f -> [MatchSubst EClassId f v]

Documentation

type Pat = Free Source #

A pattern is exactly the free monad over the expression functor It has spots for var names (FreePure) and spots for structural pieces (FreeEmbed)

patVars :: (Foldable f, Eq v, Hashable v) => Pat f v -> HashSet v Source #

The set of vars for a pattern.

type PatGroup g f v = g (Pat f v) Source #

A pattern group is some container with patterns inside. This container might be Identity for one pattern, or a list or map for many patterns.

type Subst c v = HashMap v c Source #

A substitution.

substVars :: Subst a v -> HashSet v Source #

The set of vars for a substitution.

newtype VarId Source #

An opaque var id Constructor exported for coercibility

Constructors

VarId
Fields unVarId :: Int

Instances

Instances details

Enum VarId Source #
Instance details Defined in Overeasy.Matching Methods succ :: VarId -> VarId # pred :: VarId -> VarId # toEnum :: Int -> VarId # fromEnum :: VarId -> Int # enumFrom :: VarId -> [VarId] # enumFromThen :: VarId -> VarId -> [VarId] # enumFromTo :: VarId -> VarId -> [VarId] # enumFromThenTo :: VarId -> VarId -> VarId -> [VarId] #
Show VarId Source #
Instance details Defined in Overeasy.Matching Methods showsPrec :: Int -> VarId -> ShowS # show :: VarId -> String # showList :: [VarId] -> ShowS #
NFData VarId Source #
Instance details Defined in Overeasy.Matching Methods rnf :: VarId -> () #
Eq VarId Source #
Instance details Defined in Overeasy.Matching Methods (==) :: VarId -> VarId -> Bool # (/=) :: VarId -> VarId -> Bool #
Ord VarId Source #
Instance details Defined in Overeasy.Matching Methods compare :: VarId -> VarId -> Ordering # (<) :: VarId -> VarId -> Bool # (<=) :: VarId -> VarId -> Bool # (>) :: VarId -> VarId -> Bool # (>=) :: VarId -> VarId -> Bool # max :: VarId -> VarId -> VarId # min :: VarId -> VarId -> VarId #
Hashable VarId Source #
Instance details Defined in Overeasy.Matching Methods hashWithSalt :: Int -> VarId -> Int # hash :: VarId -> Int #

type PatGraphC f v = (Traversable f, Traversable f, Eq v, Eq (f VarId), Hashable v, Hashable (f VarId)) Source #

The set of constraints necessary to build a pattern graph.

data PatGraph g f v Source #

A pattern graph - can be created once for each pattern and reused for many iterations of search. g is the pattern group functor. f is the language functor.

Constructors

PatGraph
Fields pgRoots :: !(g VarId) pgNodes :: !(IntLikeMap VarId (PatF f v VarId)) pgVars :: !(HashMap v VarId)

Instances

Instances details

(Show v, Show (g VarId), Show (f VarId)) => Show (PatGraph g f v) Source #
Instance details Defined in Overeasy.Matching Methods showsPrec :: Int -> PatGraph g f v -> ShowS # show :: PatGraph g f v -> String # showList :: [PatGraph g f v] -> ShowS #
(Eq v, Eq (g VarId), Eq (f VarId)) => Eq (PatGraph g f v) Source #
Instance details Defined in Overeasy.Matching Methods (==) :: PatGraph g f v -> PatGraph g f v -> Bool # (/=) :: PatGraph g f v -> PatGraph g f v -> Bool #

patGraph :: (Traversable g, PatGraphC f v) => PatGroup g f v -> PatGraph g f v Source #

Builds a pattern graph from a group of patterns.

singlePatGraph :: PatGraphC f v => Pat f v -> PatGraph Identity f v Source #

Builds a pattern graph from a single pattern. If you have more than one pattern, building the group all at once is going to make finding solutions more efficient.

data Match c f v Source #

A match is a pattern annotated with classes (or other data).

Constructors

Match
Fields matchAnno :: !c matchPat :: !(MatchPat c f v)

Instances

Instances details

Foldable f => Foldable (Match c f) Source #
Instance details Defined in Overeasy.Matching Methods fold :: Monoid m => Match c f m -> m # foldMap :: Monoid m => (a -> m) -> Match c f a -> m # foldMap' :: Monoid m => (a -> m) -> Match c f a -> m # foldr :: (a -> b -> b) -> b -> Match c f a -> b # foldr' :: (a -> b -> b) -> b -> Match c f a -> b # foldl :: (b -> a -> b) -> b -> Match c f a -> b # foldl' :: (b -> a -> b) -> b -> Match c f a -> b # foldr1 :: (a -> a -> a) -> Match c f a -> a # foldl1 :: (a -> a -> a) -> Match c f a -> a # toList :: Match c f a -> [a] # null :: Match c f a -> Bool # length :: Match c f a -> Int # elem :: Eq a => a -> Match c f a -> Bool # maximum :: Ord a => Match c f a -> a # minimum :: Ord a => Match c f a -> a # sum :: Num a => Match c f a -> a # product :: Num a => Match c f a -> a #
Traversable f => Traversable (Match c f) Source #
Instance details Defined in Overeasy.Matching Methods traverse :: Applicative f0 => (a -> f0 b) -> Match c f a -> f0 (Match c f b) # sequenceA :: Applicative f0 => Match c f (f0 a) -> f0 (Match c f a) # mapM :: Monad m => (a -> m b) -> Match c f a -> m (Match c f b) # sequence :: Monad m => Match c f (m a) -> m (Match c f a) #
Functor f => Functor (Match c f) Source #
Instance details Defined in Overeasy.Matching Methods fmap :: (a -> b) -> Match c f a -> Match c f b # (<$) :: a -> Match c f b -> Match c f a #
(Show c, Show v, Show (f (Match c f v))) => Show (Match c f v) Source #
Instance details Defined in Overeasy.Matching Methods showsPrec :: Int -> Match c f v -> ShowS # show :: Match c f v -> String # showList :: [Match c f v] -> ShowS #
(Eq c, Eq v, Eq (f (Match c f v))) => Eq (Match c f v) Source #
Instance details Defined in Overeasy.Matching Methods (==) :: Match c f v -> Match c f v -> Bool # (/=) :: Match c f v -> Match c f v -> Bool #
Functor f => Corecursive (Match c f v) Source #
Instance details Defined in Overeasy.Matching Methods embed :: Base (Match c f v) (Match c f v) -> Match c f v # ana :: (a -> Base (Match c f v) a) -> a -> Match c f v # apo :: (a -> Base (Match c f v) (Either (Match c f v) a)) -> a -> Match c f v # postpro :: Recursive (Match c f v) => (forall b. Base (Match c f v) b -> Base (Match c f v) b) -> (a -> Base (Match c f v) a) -> a -> Match c f v # gpostpro :: (Recursive (Match c f v), Monad m) => (forall b. m (Base (Match c f v) b) -> Base (Match c f v) (m b)) -> (forall c0. Base (Match c f v) c0 -> Base (Match c f v) c0) -> (a -> Base (Match c f v) (m a)) -> a -> Match c f v #
Functor f => Recursive (Match c f v) Source #
Instance details Defined in Overeasy.Matching Methods project :: Match c f v -> Base (Match c f v) (Match c f v) # cata :: (Base (Match c f v) a -> a) -> Match c f v -> a # para :: (Base (Match c f v) (Match c f v, a) -> a) -> Match c f v -> a # gpara :: (Corecursive (Match c f v), Comonad w) => (forall b. Base (Match c f v) (w b) -> w (Base (Match c f v) b)) -> (Base (Match c f v) (EnvT (Match c f v) w a) -> a) -> Match c f v -> a # prepro :: Corecursive (Match c f v) => (forall b. Base (Match c f v) b -> Base (Match c f v) b) -> (Base (Match c f v) a -> a) -> Match c f v -> a # gprepro :: (Corecursive (Match c f v), Comonad w) => (forall b. Base (Match c f v) (w b) -> w (Base (Match c f v) b)) -> (forall c0. Base (Match c f v) c0 -> Base (Match c f v) c0) -> (Base (Match c f v) (w a) -> a) -> Match c f v -> a #
type Base (Match c f v) Source #
Instance details Defined in Overeasy.Matching type Base (Match c f v) = MatchF c f v

data MatchPat c f v Source #

Tie the knot - the inner layer of a match.

Constructors

MatchPatPure !v
MatchPatEmbed !(f (Match c f v))

Instances

Instances details

Foldable f => Foldable (MatchPat c f) Source #
Instance details Defined in Overeasy.Matching Methods fold :: Monoid m => MatchPat c f m -> m # foldMap :: Monoid m => (a -> m) -> MatchPat c f a -> m # foldMap' :: Monoid m => (a -> m) -> MatchPat c f a -> m # foldr :: (a -> b -> b) -> b -> MatchPat c f a -> b # foldr' :: (a -> b -> b) -> b -> MatchPat c f a -> b # foldl :: (b -> a -> b) -> b -> MatchPat c f a -> b # foldl' :: (b -> a -> b) -> b -> MatchPat c f a -> b # foldr1 :: (a -> a -> a) -> MatchPat c f a -> a # foldl1 :: (a -> a -> a) -> MatchPat c f a -> a # toList :: MatchPat c f a -> [a] # null :: MatchPat c f a -> Bool # length :: MatchPat c f a -> Int # elem :: Eq a => a -> MatchPat c f a -> Bool # maximum :: Ord a => MatchPat c f a -> a # minimum :: Ord a => MatchPat c f a -> a # sum :: Num a => MatchPat c f a -> a # product :: Num a => MatchPat c f a -> a #
Traversable f => Traversable (MatchPat c f) Source #
Instance details Defined in Overeasy.Matching Methods traverse :: Applicative f0 => (a -> f0 b) -> MatchPat c f a -> f0 (MatchPat c f b) # sequenceA :: Applicative f0 => MatchPat c f (f0 a) -> f0 (MatchPat c f a) # mapM :: Monad m => (a -> m b) -> MatchPat c f a -> m (MatchPat c f b) # sequence :: Monad m => MatchPat c f (m a) -> m (MatchPat c f a) #
Functor f => Functor (MatchPat c f) Source #
Instance details Defined in Overeasy.Matching Methods fmap :: (a -> b) -> MatchPat c f a -> MatchPat c f b # (<$) :: a -> MatchPat c f b -> MatchPat c f a #
(Show v, Show (f (Match c f v))) => Show (MatchPat c f v) Source #
Instance details Defined in Overeasy.Matching Methods showsPrec :: Int -> MatchPat c f v -> ShowS # show :: MatchPat c f v -> String # showList :: [MatchPat c f v] -> ShowS #
(Eq v, Eq (f (Match c f v))) => Eq (MatchPat c f v) Source #
Instance details Defined in Overeasy.Matching Methods (==) :: MatchPat c f v -> MatchPat c f v -> Bool # (/=) :: MatchPat c f v -> MatchPat c f v -> Bool #

data MatchF c f v r Source #

The base functor of Match

Constructors

MatchF
Fields matchClassF :: !c matchPatF :: !(MatchPatF f v r)

Instances

Instances details

Foldable f => Foldable (MatchF c f v) Source #
Instance details Defined in Overeasy.Matching Methods fold :: Monoid m => MatchF c f v m -> m # foldMap :: Monoid m => (a -> m) -> MatchF c f v a -> m # foldMap' :: Monoid m => (a -> m) -> MatchF c f v a -> m # foldr :: (a -> b -> b) -> b -> MatchF c f v a -> b # foldr' :: (a -> b -> b) -> b -> MatchF c f v a -> b # foldl :: (b -> a -> b) -> b -> MatchF c f v a -> b # foldl' :: (b -> a -> b) -> b -> MatchF c f v a -> b # foldr1 :: (a -> a -> a) -> MatchF c f v a -> a # foldl1 :: (a -> a -> a) -> MatchF c f v a -> a # toList :: MatchF c f v a -> [a] # null :: MatchF c f v a -> Bool # length :: MatchF c f v a -> Int # elem :: Eq a => a -> MatchF c f v a -> Bool # maximum :: Ord a => MatchF c f v a -> a # minimum :: Ord a => MatchF c f v a -> a # sum :: Num a => MatchF c f v a -> a # product :: Num a => MatchF c f v a -> a #
Traversable f => Traversable (MatchF c f v) Source #
Instance details Defined in Overeasy.Matching Methods traverse :: Applicative f0 => (a -> f0 b) -> MatchF c f v a -> f0 (MatchF c f v b) # sequenceA :: Applicative f0 => MatchF c f v (f0 a) -> f0 (MatchF c f v a) # mapM :: Monad m => (a -> m b) -> MatchF c f v a -> m (MatchF c f v b) # sequence :: Monad m => MatchF c f v (m a) -> m (MatchF c f v a) #
Functor f => Functor (MatchF c f v) Source #
Instance details Defined in Overeasy.Matching Methods fmap :: (a -> b) -> MatchF c f v a -> MatchF c f v b # (<$) :: a -> MatchF c f v b -> MatchF c f v a #

data MatchPatF f v r Source #

Tie the knot - the inner part of MatchF.

Constructors

MatchPatPureF !v
MatchPatEmbedF !(f r)

Instances

Instances details

Foldable f => Foldable (MatchPatF f v) Source #
Instance details Defined in Overeasy.Matching Methods fold :: Monoid m => MatchPatF f v m -> m # foldMap :: Monoid m => (a -> m) -> MatchPatF f v a -> m # foldMap' :: Monoid m => (a -> m) -> MatchPatF f v a -> m # foldr :: (a -> b -> b) -> b -> MatchPatF f v a -> b # foldr' :: (a -> b -> b) -> b -> MatchPatF f v a -> b # foldl :: (b -> a -> b) -> b -> MatchPatF f v a -> b # foldl' :: (b -> a -> b) -> b -> MatchPatF f v a -> b # foldr1 :: (a -> a -> a) -> MatchPatF f v a -> a # foldl1 :: (a -> a -> a) -> MatchPatF f v a -> a # toList :: MatchPatF f v a -> [a] # null :: MatchPatF f v a -> Bool # length :: MatchPatF f v a -> Int # elem :: Eq a => a -> MatchPatF f v a -> Bool # maximum :: Ord a => MatchPatF f v a -> a # minimum :: Ord a => MatchPatF f v a -> a # sum :: Num a => MatchPatF f v a -> a # product :: Num a => MatchPatF f v a -> a #
Traversable f => Traversable (MatchPatF f v) Source #
Instance details Defined in Overeasy.Matching Methods traverse :: Applicative f0 => (a -> f0 b) -> MatchPatF f v a -> f0 (MatchPatF f v b) # sequenceA :: Applicative f0 => MatchPatF f v (f0 a) -> f0 (MatchPatF f v a) # mapM :: Monad m => (a -> m b) -> MatchPatF f v a -> m (MatchPatF f v b) # sequence :: Monad m => MatchPatF f v (m a) -> m (MatchPatF f v a) #
Functor f => Functor (MatchPatF f v) Source #
Instance details Defined in Overeasy.Matching Methods fmap :: (a -> b) -> MatchPatF f v a -> MatchPatF f v b # (<$) :: a -> MatchPatF f v b -> MatchPatF f v a #

matchVars :: (Foldable f, Eq v, Hashable v) => Match c f v -> HashSet v Source #

The set of vars in a match.

matchClasses :: (Coercible c Int, Functor f, Foldable f) => Match c f v -> IntLikeSet c Source #

The set of classes in a match.

data MatchSubst c f v Source #

A apri of match and substitution.

Constructors

MatchSubst
Fields msMatch :: !(Match c f v) msSubst :: !(Subst c v)

Instances

Instances details

(Show c, Show v, Show (f (Match c f v))) => Show (MatchSubst c f v) Source #
Instance details Defined in Overeasy.Matching Methods showsPrec :: Int -> MatchSubst c f v -> ShowS # show :: MatchSubst c f v -> String # showList :: [MatchSubst c f v] -> ShowS #
(Eq c, Eq v, Eq (f (Match c f v))) => Eq (MatchSubst c f v) Source #
Instance details Defined in Overeasy.Matching Methods (==) :: MatchSubst c f v -> MatchSubst c f v -> Bool # (/=) :: MatchSubst c f v -> MatchSubst c f v -> Bool #

type SolGraphC f = (Functor f, Foldable f, Eq (f ()), Hashable (f ())) Source #

The set of constraints necessary to build a solution graph.

data SolGraph c f Source #

A solution graph - must be created from an e-graph each merge/rebuild.

Constructors

SolGraph
Fields sgByVar :: !(IntLikeMap VarId (IntLikeSet c)) Map of var -> classes. Contains all vars. If the inner map is empty, that means the pattern was not matched. The inner set will not be empty. sgNodes :: !(HashMap (f c) c) Map of node structures to classes.

Instances

Instances details

(Show c, Show (f c)) => Show (SolGraph c f) Source #
Instance details Defined in Overeasy.Matching Methods showsPrec :: Int -> SolGraph c f -> ShowS # show :: SolGraph c f -> String # showList :: [SolGraph c f] -> ShowS #
(Eq c, Eq (f c)) => Eq (SolGraph c f) Source #
Instance details Defined in Overeasy.Matching Methods (==) :: SolGraph c f -> SolGraph c f -> Bool # (/=) :: SolGraph c f -> SolGraph c f -> Bool #

solGraph :: SolGraphC f => PatGraph g f v -> EGraph d f -> SolGraph EClassId f Source #

Builds a solution graph from an e-graph.

type SolStream c g f v z = Stream (SolEnv c g f v) (SolState c) z Source #

A stream of solutions. Can be demanded all at once or interleaved.

type SolveC c f v = (Traversable f, Coercible c Int, Eq v, Hashable v, Eq (f c), Hashable (f c)) Source #

The set of constraints necessary to search for solutions.

solve :: (Foldable g, SolveC c f v) => SolStream c g f v (MatchSubst c f v) Source #

Produces a stream of solutions (e-matches).

match :: (PatGraphC f v, SolGraphC f, SolveC EClassId f v) => Pat f v -> EGraph d f -> [MatchSubst EClassId f v] Source #

The easiest way to do e-matching: given a pattern and an e-graph, yield the list of matches. Note that it's more efficient to keep a PatGraph and use the same solution graph for multiple patterns.)