-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/


-- | A purely functional E-Graph library
--   
--   Please see the README on GitHub at
--   <a>https://github.com/ejconlon/overeasy#readme</a>
@package overeasy
@version 0.2.0


-- | See <a>EquivFind</a>.
module Overeasy.EquivFind

-- | A "Union-Find" implementation using explicit equivalence classes.
--   Sure, the asympotics aren't as good, but we eventually have to
--   construct these classes, so we might as well just do it as we go!
data EquivFind x

-- | Map of root to equivalent leaves Invariant: Map keys are only roots
--   Invariant: Sets only contain leaf keys (and not the root itself)
efFwd :: EquivFind x -> IntLikeMap x (IntLikeSet x)

-- | Map of leaf to root Invariant: Map keys are only leaves, values are
--   only roots
efBwd :: EquivFind x -> IntLikeMap x x

-- | Number of roots in the equiv.
efRootsSize :: EquivFind x -> Int

-- | Number of leaves in the equiv.
efLeavesSize :: EquivFind x -> Int

-- | Total number of keys in the equiv.
efTotalSize :: EquivFind x -> Int

-- | Canonicalize the given expression functor by replacing leaves with
--   roots. If any elements are missing, the first is returned.
efCanonicalize :: (Traversable f, Coercible x Int) => f x -> EquivFind x -> Either x (f x)

-- | Canonicalize the given expression functor by replacing leaves with
--   roots. If any elements are missing, they are simply skipped.
efCanonicalizePartial :: (Functor f, Coercible x Int) => f x -> EquivFind x -> f x

-- | Creates an empty equiv
efNew :: EquivFind x

-- | Creates a singleton equiv
efSingleton :: Coercible x Int => x -> EquivFind x

-- | Is the key in the equiv?
efMember :: Coercible x Int => x -> EquivFind x -> Bool

-- | List all roots in the equiv.
efRoots :: Coercible x Int => EquivFind x -> [x]

-- | List all leaves in the equiv.
efLeaves :: Coercible x Int => EquivFind x -> [x]

-- | List all members (roots and leaves) in the equiv.
efMembers :: Coercible x Int => EquivFind x -> [x]

-- | Result of adding something to the equiv, if you're interested.
data EquivAddRes x
EquivAddResAlreadyRoot :: EquivAddRes x
EquivAddResAlreadyLeafOf :: !x -> EquivAddRes x
EquivAddResNewRoot :: EquivAddRes x

-- | Add the given key to the equiv (raw version).
efAddInc :: Coercible x Int => x -> EquivFind x -> (EquivAddRes x, EquivFind x)

-- | Add the given key to the equiv (raw version).
efAdd :: Coercible x Int => x -> State (EquivFind x) (EquivAddRes x)

-- | All keys equivalent to the given key in the equiv. Always returns a
--   set with the given key, even if it's not present.
efEquivs :: Coercible x Int => x -> EquivFind x -> IntLikeSet x

-- | Set of all keys equivalent to the given keys in the equiv.
efClosure :: Coercible x Int => [x] -> EquivFind x -> IntLikeSet x

-- | Find the root equivalent to the given key (if it exists).
efFindRoot :: Coercible x Int => x -> EquivFind x -> Maybe x

-- | Find the leaves equivalent to the given key (if they exist).
efFindLeaves :: Coercible x Int => x -> EquivFind x -> Maybe (IntLikeSet x)

-- | Returns an EquivFind subset representing the given list of keys.
efSubset :: Coercible x Int => [x] -> EquivFind x -> EquivFind x

-- | Like <a>efFindRoot</a> but returns same key if not found - does not
--   guarantee presence in map.
efLookupRoot :: Coercible x Int => x -> EquivFind x -> x

-- | Like <a>efFindLeaves</a> but returns empty set if not found - does not
--   guarantee presence in map.
efLookupLeaves :: Coercible x Int => x -> EquivFind x -> IntLikeSet x

-- | Returns the set of roots for the given set of keys, or an error with
--   the first key not found in the equiv.
efFindAll :: Coercible x Int => [x] -> EquivFind x -> Either x (IntLikeSet x)

-- | The result of trying to merge two keys, if you care.
data EquivMergeRes x
EquivMergeResMissing :: !x -> EquivMergeRes x
EquivMergeResUnchanged :: !x -> EquivMergeRes x
EquivMergeResChanged :: !x -> !IntLikeSet x -> !EquivFind x -> EquivMergeRes x

-- | Don't even think about it, it's got unsafe in the name.
efUnsafeMerge :: (Coercible x Int, Ord x) => x -> x -> EquivFind x -> (x, IntLikeSet x, EquivFind x)

-- | Merge two keys (raw version).
efMergeInc :: (Coercible x Int, Ord x) => x -> x -> EquivFind x -> EquivMergeRes x

-- | Merge two keys (state version).
efMerge :: (Coercible x Int, Ord x) => x -> x -> State (EquivFind x) (Maybe (x, IntLikeSet x))

-- | The result of trying to merge multiple sets of keys, if you care.
data EquivMergeSetsRes x
EquivMergeSetsResEmptySet :: EquivMergeSetsRes x
EquivMergeSetsResMissing :: !x -> EquivMergeSetsRes x
EquivMergeSetsResUnchanged :: !IntLikeSet x -> EquivMergeSetsRes x
EquivMergeSetsResChanged :: !IntLikeSet x -> !IntLikeSet x -> !EquivFind x -> EquivMergeSetsRes x

-- | Merge sets of keys (raw version).
efMergeSetsInc :: Coercible x Int => [IntLikeSet x] -> EquivFind x -> EquivMergeSetsRes x

-- | Merge sets of keys (state version).
efMergeSets :: Coercible x Int => [IntLikeSet x] -> State (EquivFind x) (Maybe (IntLikeSet x, IntLikeSet x))

-- | Are they compactible keys?
efCanCompact :: EquivFind x -> Bool

-- | See <a>efCompact</a> (this is the raw version).
efCompactInc :: Coercible x Int => EquivFind x -> (IntLikeMap x (IntLikeSet x), EquivFind x)

-- | Removes leaves and returns map of root to deleted leaf.
efCompact :: Coercible x Int => State (EquivFind x) (IntLikeMap x (IntLikeSet x))

-- | See <a>efRemoveAll</a> (this is the raw version).
efRemoveAllInc :: Coercible x Int => [x] -> EquivFind x -> (IntLikeMap x x, EquivFind x)

-- | Removes the given keys from the equiv map. If a key is a leaf or
--   singleton root, simply remove it. If it is a root of a larger class,
--   select the min leaf and make it root. Returns a map of old roots to
--   new roots (only those changed in the process - possibly empty). If a
--   key is not found, it is simply ignored.
efRemoveAll :: Coercible x Int => [x] -> State (EquivFind x) (IntLikeMap x x)

-- | Given root, add leaf. Requires that root be present in the map and
--   that leaf would be picked as a leaf. (Therefore, unsafe.) Exposed for
--   efficient merging.
efUnsafeAddLeafInc :: Coercible x Int => x -> x -> EquivFind x -> EquivFind x
instance Control.DeepSeq.NFData x => Control.DeepSeq.NFData (Overeasy.EquivFind.EquivFind x)
instance GHC.Generics.Generic (Overeasy.EquivFind.EquivFind x)
instance GHC.Show.Show x => GHC.Show.Show (Overeasy.EquivFind.EquivFind x)
instance GHC.Classes.Eq x => GHC.Classes.Eq (Overeasy.EquivFind.EquivFind x)
instance Control.DeepSeq.NFData x => Control.DeepSeq.NFData (Overeasy.EquivFind.EquivAddRes x)
instance GHC.Generics.Generic (Overeasy.EquivFind.EquivAddRes x)
instance GHC.Show.Show x => GHC.Show.Show (Overeasy.EquivFind.EquivAddRes x)
instance GHC.Classes.Eq x => GHC.Classes.Eq (Overeasy.EquivFind.EquivAddRes x)
instance Control.DeepSeq.NFData x => Control.DeepSeq.NFData (Overeasy.EquivFind.EquivMergeRes x)
instance GHC.Generics.Generic (Overeasy.EquivFind.EquivMergeRes x)
instance GHC.Show.Show x => GHC.Show.Show (Overeasy.EquivFind.EquivMergeRes x)
instance GHC.Classes.Eq x => GHC.Classes.Eq (Overeasy.EquivFind.EquivMergeRes x)
instance Control.DeepSeq.NFData x => Control.DeepSeq.NFData (Overeasy.EquivFind.EquivMergeManyRes x)
instance GHC.Generics.Generic (Overeasy.EquivFind.EquivMergeManyRes x)
instance GHC.Show.Show x => GHC.Show.Show (Overeasy.EquivFind.EquivMergeManyRes x)
instance GHC.Classes.Eq x => GHC.Classes.Eq (Overeasy.EquivFind.EquivMergeManyRes x)
instance Control.DeepSeq.NFData x => Control.DeepSeq.NFData (Overeasy.EquivFind.EquivMergeSetsRes x)
instance GHC.Generics.Generic (Overeasy.EquivFind.EquivMergeSetsRes x)
instance GHC.Show.Show x => GHC.Show.Show (Overeasy.EquivFind.EquivMergeSetsRes x)
instance GHC.Classes.Eq x => GHC.Classes.Eq (Overeasy.EquivFind.EquivMergeSetsRes x)


-- | See <a>Assoc</a>.
module Overeasy.Assoc

-- | Associates keys and values in such a way that inserting duplicate
--   values induces equivalences on their keys. Invariant: fwd and bwd maps
--   contain only root keys.
data Assoc x a

-- | Map from id to element
assocFwd :: Assoc x a -> IntLikeMap x a

-- | Map from element to id
assocBwd :: Assoc x a -> HashMap a x

-- | Equivalence classes of ids
assocEquiv :: Assoc x a -> EquivFind x

-- | How many values are in the map?
assocSize :: Assoc x a -> Int

-- | Creates an empty assoc
assocNew :: Assoc x a

-- | Creates a singleton assoc
assocSingleton :: (Coercible x Int, Hashable a) => x -> a -> Assoc x a

-- | The result of inserting into the assoc, if you're interested.
data AssocInsertRes x
AssocInsertResUnchanged :: AssocInsertRes x
AssocInsertResCreated :: AssocInsertRes x
AssocInsertResUpdated :: AssocInsertRes x
AssocInsertResMerged :: !IntLikeSet x -> AssocInsertRes x

-- | Insert into the assoc (raw version)
assocInsertInc :: (Coercible x Int, Ord x, Eq a, Hashable a) => x -> a -> Assoc x a -> ((x, AssocInsertRes x), Assoc x a)

-- | Insert into the assoc (the state version)
assocInsert :: (Coercible x Int, Ord x, Eq a, Hashable a) => x -> a -> State (Assoc x a) (x, AssocInsertRes x)

-- | Build an assoc from a list of pairs
assocFromList :: (Coercible x Int, Ord x, Eq a, Hashable a) => [(x, a)] -> Assoc x a

-- | Turn an assoc into a list of pairs (NOTE - emits only root keys!)
assocToList :: Coercible x Int => Assoc x a -> [(x, a)]

-- | Is the given key in the assoc?
assocMember :: Coercible x Int => x -> Assoc x a -> Bool

-- | Forward lookup
assocLookupByKey :: Coercible x Int => x -> Assoc x a -> Maybe a

-- | PARTIAL forward lookup
assocPartialLookupByKey :: Coercible x Int => x -> Assoc x a -> a

-- | Backward lookup
assocLookupByValue :: (Eq a, Hashable a) => a -> Assoc x a -> Maybe x

-- | PARTIAL backward lookup
assocPartialLookupByValue :: (Eq a, Hashable a) => a -> Assoc x a -> x

-- | Finds the root for the given key (id if not found)
assocLookupRoot :: Coercible x Int => x -> Assoc x a -> x

-- | List all root (live, non-compactible) keys
assocRoots :: Coercible x Int => Assoc x a -> [x]

-- | List all leaf (dead, compactible) keys
assocLeaves :: Coercible x Int => Assoc x a -> [x]

-- | List all entries (root and leaf)
assocMembers :: Coercible x Int => Assoc x a -> [x]

-- | Are there dead keys in the equiv from <a>assocInsert</a>?
assocCanCompact :: Assoc x a -> Bool

-- | Removes all dead keys in the equiv (raw version).
assocCompactInc :: Coercible x Int => Assoc x a -> (IntLikeMap x x, Assoc x a)

-- | Removes all dead keys in the equiv (state version). Returns map of
--   dead leaf node -&gt; live root node
assocCompact :: Coercible x Int => State (Assoc x a) (IntLikeMap x x)

-- | Removes the given keys from the assoc (raw version)
assocRemoveAllInc :: (Coercible x Int, Eq a, Hashable a) => [x] -> Assoc x a -> Assoc x a

-- | Removes the given keys from the assoc (state version). Values will
--   only be removed from the assoc if the key is a singleton root. If a
--   key is not found, it is simply ignored.
assocRemoveAll :: (Coercible x Int, Eq a, Hashable a) => [x] -> State (Assoc x a) ()

-- | Join two assocs (uses the first as the base)
assocUnion :: (Coercible x Int, Ord x, Eq a, Hashable a) => Assoc x a -> Assoc x a -> Assoc x a

-- | Returns the footprint of the given value - all keys that map to it
--   (root and leaf)
assocFootprint :: (Coercible x Int, Eq a, Hashable a) => a -> Assoc x a -> IntLikeSet x
instance (Control.DeepSeq.NFData a, Control.DeepSeq.NFData x) => Control.DeepSeq.NFData (Overeasy.Assoc.Assoc x a)
instance GHC.Generics.Generic (Overeasy.Assoc.Assoc x a)
instance (GHC.Show.Show a, GHC.Show.Show x) => GHC.Show.Show (Overeasy.Assoc.Assoc x a)
instance (GHC.Classes.Eq a, GHC.Classes.Eq x) => GHC.Classes.Eq (Overeasy.Assoc.Assoc x a)
instance GHC.Show.Show (Overeasy.Assoc.AssocInsertRes x)
instance GHC.Classes.Eq (Overeasy.Assoc.AssocInsertRes x)


-- | See <a>Source</a>.
module Overeasy.Source

-- | A source of unique ids
data Source x

-- | How many ids have ever been created?
sourceSize :: Source x -> Int

-- | Creates a new <a>Source</a> from a starting id
sourceNew :: Coercible x Int => x -> Source x

-- | Generates the next id from the source (purely)
sourceAddInc :: Coercible x Int => Source x -> (x, Source x)

-- | Generates the next id from the source (statefully)
sourceAdd :: Coercible x Int => State (Source x) x

-- | Skips past the given id (purely)
sourceSkipInc :: Coercible x Int => x -> Source x -> Source x

-- | Skips past the given id (statefully)
sourceSkip :: Coercible x Int => x -> State (Source x) ()

-- | Peek at the next id
sourcePeek :: Coercible x Int => Source x -> x
instance Control.DeepSeq.NFData (Overeasy.Source.Source x)
instance GHC.Generics.Generic (Overeasy.Source.Source x)
instance GHC.Show.Show (Overeasy.Source.Source x)
instance GHC.Classes.Eq (Overeasy.Source.Source x)


-- | Stuff for streaming search results.
module Overeasy.Streams

-- | Choose one of many alteratives and process it with the given function.
chooseWith :: (Foldable f, Alternative m) => f a -> (a -> m b) -> m b

-- | Choose one of many alteratives.
choose :: (Foldable f, Alternative m) => f a -> m a

-- | A stream of results. Just a wrapper around <a>LogicT</a> to keep
--   things tidy.
data Stream r s a

-- | Produces all results from the stream.
streamAll :: Stream r s a -> r -> s -> [a]
instance Control.Monad.State.Class.MonadState s (Overeasy.Streams.M r s)
instance Control.Monad.Reader.Class.MonadReader r (Overeasy.Streams.M r s)
instance GHC.Base.Monad (Overeasy.Streams.M r s)
instance GHC.Base.Applicative (Overeasy.Streams.M r s)
instance GHC.Base.Functor (Overeasy.Streams.M r s)
instance GHC.Base.Monoid (Overeasy.Streams.Stream r s a)
instance GHC.Base.Semigroup (Overeasy.Streams.Stream r s a)
instance GHC.Base.MonadPlus (Overeasy.Streams.Stream r s)
instance GHC.Base.Alternative (Overeasy.Streams.Stream r s)
instance Control.Monad.Logic.Class.MonadLogic (Overeasy.Streams.Stream r s)
instance Control.Monad.State.Class.MonadState s (Overeasy.Streams.Stream r s)
instance Control.Monad.Reader.Class.MonadReader r (Overeasy.Streams.Stream r s)
instance GHC.Base.Monad (Overeasy.Streams.Stream r s)
instance GHC.Base.Applicative (Overeasy.Streams.Stream r s)
instance GHC.Base.Functor (Overeasy.Streams.Stream r s)


-- | A grab bag of fun stuff.
module Overeasy.Util

-- | Often <tt>f</tt> is primary, not <tt>t</tt>. Relate them with this
--   constraint.
type Whole t f = (f ~ Base t)

-- | Constraint for recursive structures
type RecursiveWhole t f = (Recursive t, Whole t f)

-- | Traverses a recursive structure
foldWholeM :: (RecursiveWhole t f, Traversable f, Monad m) => (f a -> m a) -> t -> m a

-- | A nicely-named <a>Bool</a> for tracking state changes
data Changed
ChangedNo :: Changed
ChangedYes :: Changed

-- | Embeds a function that may fail in a stateful context
stateFail :: (s -> Maybe (b, s)) -> State s (Maybe b)

-- | Embeds a function that may fail in a stateful context
stateOption :: (s -> (b, Maybe s)) -> State s b

-- | Embeds a function that may fail in a stateful context with change
--   tracking
stateFailChanged :: (s -> Maybe s) -> State s Changed

-- | <a>foldM</a> specialized and flipped.
stateFold :: Foldable t => b -> t a -> (b -> a -> State s b) -> State s b
instance Control.DeepSeq.NFData Overeasy.Util.Changed
instance Data.Hashable.Class.Hashable Overeasy.Util.Changed
instance GHC.Generics.Generic Overeasy.Util.Changed
instance GHC.Show.Show Overeasy.Util.Changed
instance GHC.Classes.Ord Overeasy.Util.Changed
instance GHC.Classes.Eq Overeasy.Util.Changed
instance GHC.Base.Semigroup Overeasy.Util.Changed
instance GHC.Base.Monoid Overeasy.Util.Changed


-- | See <a>EGraph</a>.
module Overeasy.EGraph

-- | An opaque class id. Constructor exported for coercibility. Num
--   instance for literals only.
newtype EClassId
EClassId :: Int -> EClassId
[unEClassId] :: EClassId -> Int

-- | An opaque node id Constructor exported for coercibility. Num instance
--   for literals only.
newtype ENodeId
ENodeId :: Int -> ENodeId
[unENodeId] :: ENodeId -> Int

-- | The definition of an <a>EGraph</a> analysis. <tt>d</tt> must be a join
--   semilattice. This function must be monotonic.
type EAnalysis d f = f d -> d

-- | A disabled analysis
noAnalysis :: EAnalysis () f

-- | Info stored for every class: analysis data, class members (nodes), and
--   parent nodes.
data EClassInfo d f
EClassInfo :: !d -> !Assoc ENodeId (f ()) -> !IntLikeSet ENodeId -> EClassInfo d f
[eciData] :: EClassInfo d f -> !d
[eciNodes] :: EClassInfo d f -> !Assoc ENodeId (f ())
[eciParents] :: EClassInfo d f -> !IntLikeSet ENodeId

-- | An E-Graph implementation
data EGraph d f

-- | A set of class ids to merge
type WorkItem = IntLikeSet EClassId

-- | A sequences of groups of class ids to mrege
type WorkList = Seq WorkItem

-- | An invertible multimap of new root class to the sets of old classes it
--   subsumes Can be used to externally recanonicalize any structures that
--   reference class ids after merges.
type ClassReplacements = EquivFind EClassId

-- | Merging classes can result in a few outcomes:
data MergeResult a

-- | All classes already merged, no change
MergeResultUnchanged :: MergeResult a

-- | Some classes missing, returns first problematic worklist entry (note
--   that not all classes in worklist item will be missing, only at least
--   one from the set)
MergeResultMissing :: !WorkItem -> MergeResult a

-- | Some classes merged, returns root map or merged class id
MergeResultChanged :: !a -> MergeResult a

-- | Id source for classes
egClassSource :: EGraph d f -> Source EClassId

-- | Id source for nodes
egNodeSource :: EGraph d f -> Source ENodeId

-- | Class equivalences
egEquivFind :: EGraph d f -> EquivFind EClassId

-- | Map of class to info Invariant: Only contains root classes.
egClassMap :: EGraph d f -> IntLikeMap EClassId (EClassInfo d f)

-- | Assoc of node id to node structure Invariant: only contains canonical
--   structures (with root classes).
egNodeAssoc :: EGraph d f -> Assoc ENodeId (f EClassId)

-- | Map of node to class Invariant: only contains root classes.
egHashCons :: EGraph d f -> IntLikeMap ENodeId EClassId

-- | Number of equivalent classes in the <a>EGraph</a> (see
--   <tt>ufSize</tt>)
egClassSize :: EGraph d f -> Int

-- | Number of nodes in the <a>EGraph</a>
egNodeSize :: EGraph d f -> Int

-- | Find the class of the given node, if it exists. Note that you may have
--   to canonicalize first to find it!
egFindNode :: (Eq (f EClassId), Hashable (f EClassId)) => f EClassId -> EGraph d f -> Maybe EClassId

-- | Find the class of the given term, if it exists
egFindTerm :: (RecursiveWhole t f, Traversable f, Eq (f EClassId), Hashable (f EClassId)) => t -> EGraph d f -> Maybe EClassId

-- | Lookup info for the given <tt>EClass</tt>
egClassInfo :: EClassId -> EGraph d f -> Maybe (EClassInfo d f)

-- | Creates a new <a>EGraph</a>
egNew :: EGraph d f

-- | Yields all root classes
egClasses :: State (EGraph d f) (IntLikeSet EClassId)

-- | Find the canonical form of a node. If any classes are missing, the
--   first missing is returned.
egCanonicalize :: Traversable f => f EClassId -> State (EGraph d f) (Either EClassId (f EClassId))

-- | Find the canonical form of a node. If any classes are missing, simply
--   skip them.
egCanonicalizePartial :: Traversable f => f EClassId -> State (EGraph d f) (f EClassId)

-- | Adds a term (recursively) to the graph. If already in the graph,
--   returns <a>ChangedNo</a> and existing class id. Otherwise returns
--   <a>ChangedYes</a> and a new class id.
egAddTerm :: (RecursiveWhole t f, Traversable f, Eq (f EClassId), Hashable (f EClassId), Hashable (f ())) => EAnalysis d f -> t -> State (EGraph d f) (Changed, EClassId)

-- | Merges two classes: Returns <a>Nothing</a> if the classes are not
--   found or if they're already equal. Otherwise returns the class
--   remapping. Note that it's MUCH more efficient to accumulate a
--   <a>WorkList</a> and use <a>egMergeMany</a>.
egMerge :: (Semigroup d, Traversable f, Eq (f EClassId), Hashable (f EClassId), Eq (f ()), Hashable (f ())) => EClassId -> EClassId -> State (EGraph d f) (MergeResult EClassId)

-- | Merges many sets of classes. Returns <a>Nothing</a> if the classes are
--   not found or if they're already equal. Otherwise returns the class
--   remapping (equiv map of root to set of leaf classes). It is important
--   to note that the leaf classes in the returned mapping have been
--   REMOVED from the egraph, so they cannot be used to lookup classes in
--   the future. Therefore, if you have any class ids stored externally,
--   you'll want to (partially) canonicalize with the returned mapping.
--   Also note that the analysis of a given class is going to be an
--   UNDER-APPROXIMATION of the true analysis value, because per-node
--   analyses are not recomputed.
egMergeMany :: (Semigroup d, Traversable f, Eq (f EClassId), Hashable (f EClassId), Eq (f ()), Hashable (f ())) => WorkList -> State (EGraph d f) (MergeResult (ClassReplacements, IntLikeSet EClassId))

-- | Reanalyze a subset of classes - touched roots from merging is
--   sufficient to ensure complete reanalysis. (Note this is implemented in
--   a simplistic way, just taking the fixed point of rounds of analysis.
--   The number of rounds can be no more than the size of the given set.)
--   It may be necessary to call this because merging may leave class
--   analyses in an under-approximating state. This method gives you the
--   true analysis by fixed point.
egReanalyzeSubset :: (Eq d, Semigroup d, Functor f) => EAnalysis d f -> IntLikeSet EClassId -> State (EGraph d f) ()

-- | Reanalyze all classes in the graph.
egReanalyze :: (Eq d, Semigroup d, Functor f) => EAnalysis d f -> State (EGraph d f) ()
instance GHC.Num.Num Overeasy.EGraph.EClassId
instance Control.DeepSeq.NFData Overeasy.EGraph.EClassId
instance Data.Hashable.Class.Hashable Overeasy.EGraph.EClassId
instance GHC.Enum.Enum Overeasy.EGraph.EClassId
instance GHC.Classes.Ord Overeasy.EGraph.EClassId
instance GHC.Classes.Eq Overeasy.EGraph.EClassId
instance GHC.Show.Show Overeasy.EGraph.EClassId
instance GHC.Num.Num Overeasy.EGraph.ENodeId
instance Control.DeepSeq.NFData Overeasy.EGraph.ENodeId
instance Data.Hashable.Class.Hashable Overeasy.EGraph.ENodeId
instance GHC.Enum.Enum Overeasy.EGraph.ENodeId
instance GHC.Classes.Ord Overeasy.EGraph.ENodeId
instance GHC.Classes.Eq Overeasy.EGraph.ENodeId
instance GHC.Show.Show Overeasy.EGraph.ENodeId
instance Control.DeepSeq.NFData d => Control.DeepSeq.NFData (Overeasy.EGraph.ENodeTriple d)
instance GHC.Generics.Generic (Overeasy.EGraph.ENodeTriple d)
instance GHC.Show.Show d => GHC.Show.Show (Overeasy.EGraph.ENodeTriple d)
instance GHC.Classes.Eq d => GHC.Classes.Eq (Overeasy.EGraph.ENodeTriple d)
instance GHC.Generics.Generic (Overeasy.EGraph.EClassInfo d f)
instance Data.Traversable.Traversable Overeasy.EGraph.MergeResult
instance Data.Foldable.Foldable Overeasy.EGraph.MergeResult
instance GHC.Base.Functor Overeasy.EGraph.MergeResult
instance GHC.Show.Show a => GHC.Show.Show (Overeasy.EGraph.MergeResult a)
instance GHC.Classes.Eq a => GHC.Classes.Eq (Overeasy.EGraph.MergeResult a)
instance GHC.Generics.Generic (Overeasy.EGraph.EGraph d f)
instance Control.DeepSeq.NFData d => Control.DeepSeq.NFData (Overeasy.EGraph.AddNodeRes d)
instance GHC.Generics.Generic (Overeasy.EGraph.AddNodeRes d)
instance GHC.Show.Show d => GHC.Show.Show (Overeasy.EGraph.AddNodeRes d)
instance GHC.Classes.Eq d => GHC.Classes.Eq (Overeasy.EGraph.AddNodeRes d)
instance (GHC.Classes.Eq d, GHC.Classes.Eq (f ())) => GHC.Classes.Eq (Overeasy.EGraph.EClassInfo d f)
instance (GHC.Show.Show d, GHC.Show.Show (f ())) => GHC.Show.Show (Overeasy.EGraph.EClassInfo d f)
instance (Control.DeepSeq.NFData d, Control.DeepSeq.NFData (f ())) => Control.DeepSeq.NFData (Overeasy.EGraph.EClassInfo d f)
instance (GHC.Classes.Eq d, GHC.Classes.Eq (f Overeasy.EGraph.EClassId), GHC.Classes.Eq (f ())) => GHC.Classes.Eq (Overeasy.EGraph.EGraph d f)
instance (GHC.Show.Show d, GHC.Show.Show (f Overeasy.EGraph.EClassId), GHC.Show.Show (f ())) => GHC.Show.Show (Overeasy.EGraph.EGraph d f)
instance (Control.DeepSeq.NFData d, Control.DeepSeq.NFData (f Overeasy.EGraph.EClassId), Control.DeepSeq.NFData (f ())) => Control.DeepSeq.NFData (Overeasy.EGraph.EGraph d f)
instance GHC.Base.Semigroup (Overeasy.EGraph.AddNodeRes d)
instance GHC.Base.Monoid (Overeasy.EGraph.AddNodeRes d)


-- | Methods to match patterns in <a>EGraph</a>s (aka e-matching)
module Overeasy.Matching

-- | A pattern is exactly the free monad over the expression functor It has
--   spots for var names (<tt>FreePure</tt>) and spots for structural
--   pieces (<tt>FreeEmbed</tt>)
type Pat = Free

-- | The set of vars for a pattern.
patVars :: (Foldable f, Eq v, Hashable v) => Pat f v -> HashSet v

-- | A pattern group is some container with patterns inside. This container
--   might be <a>Identity</a> for one pattern, or a list or map for many
--   patterns.
type PatGroup g f v = g (Pat f v)

-- | A substitution.
type Subst c v = HashMap v c

-- | The set of vars for a substitution.
substVars :: Subst a v -> HashSet v

-- | An opaque var id Constructor exported for coercibility
newtype VarId
VarId :: Int -> VarId
[unVarId] :: VarId -> Int

-- | The set of constraints necessary to build a pattern graph.
type PatGraphC f v = (Traversable f, Traversable f, Eq v, Eq (f VarId), Hashable v, Hashable (f VarId))

-- | A pattern graph - can be created once for each pattern and reused for
--   many iterations of search. <tt>g</tt> is the pattern group functor.
--   <tt>f</tt> is the language functor.
data PatGraph g f v
PatGraph :: !g VarId -> !IntLikeMap VarId (PatF f v VarId) -> !HashMap v VarId -> PatGraph g f v
[pgRoots] :: PatGraph g f v -> !g VarId
[pgNodes] :: PatGraph g f v -> !IntLikeMap VarId (PatF f v VarId)
[pgVars] :: PatGraph g f v -> !HashMap v VarId

-- | Builds a pattern graph from a group of patterns.
patGraph :: (Traversable g, PatGraphC f v) => PatGroup g f v -> PatGraph g f v

-- | 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.
singlePatGraph :: PatGraphC f v => Pat f v -> PatGraph Identity f v

-- | A match is a pattern annotated with classes (or other data).
data Match c f v
Match :: !c -> !MatchPat c f v -> Match c f v
[matchAnno] :: Match c f v -> !c
[matchPat] :: Match c f v -> !MatchPat c f v

-- | Tie the knot - the inner layer of a match.
data MatchPat c f v
MatchPatPure :: !v -> MatchPat c f v
MatchPatEmbed :: !f (Match c f v) -> MatchPat c f v

-- | The base functor of <a>Match</a>
data MatchF c f v r
MatchF :: !c -> !MatchPatF f v r -> MatchF c f v r
[matchClassF] :: MatchF c f v r -> !c
[matchPatF] :: MatchF c f v r -> !MatchPatF f v r

-- | Tie the knot - the inner part of <a>MatchF</a>.
data MatchPatF f v r
MatchPatPureF :: !v -> MatchPatF f v r
MatchPatEmbedF :: !f r -> MatchPatF f v r

-- | The set of vars in a match.
matchVars :: (Foldable f, Eq v, Hashable v) => Match c f v -> HashSet v

-- | The set of classes in a match.
matchClasses :: (Coercible c Int, Functor f, Foldable f) => Match c f v -> IntLikeSet c

-- | A apri of match and substitution.
data MatchSubst c f v
MatchSubst :: !Match c f v -> !Subst c v -> MatchSubst c f v
[msMatch] :: MatchSubst c f v -> !Match c f v
[msSubst] :: MatchSubst c f v -> !Subst c v

-- | The set of constraints necessary to build a solution graph.
type SolGraphC f = (Functor f, Foldable f, Eq (f ()), Hashable (f ()))

-- | A solution graph - must be created from an e-graph each merge/rebuild.
data SolGraph c f
SolGraph :: !IntLikeMap VarId (IntLikeSet c) -> !HashMap (f c) c -> SolGraph c f

-- | Map of var -&gt; classes. Contains all vars. If the inner map is
--   empty, that means the pattern was not matched. The inner set will not
--   be empty.
[sgByVar] :: SolGraph c f -> !IntLikeMap VarId (IntLikeSet c)

-- | Map of node structures to classes.
[sgNodes] :: SolGraph c f -> !HashMap (f c) c

-- | Builds a solution graph from an e-graph.
solGraph :: SolGraphC f => PatGraph g f v -> EGraph d f -> SolGraph EClassId f

-- | A stream of solutions. Can be demanded all at once or interleaved.
type SolStream c g f v z = Stream (SolEnv c g f v) (SolState c) z

-- | The set of constraints necessary to search for solutions.
type SolveC c f v = (Traversable f, Coercible c Int, Eq v, Hashable v, Eq (f c), Hashable (f c))

-- | Produces a stream of solutions (e-matches).
solve :: (Foldable g, SolveC c f v) => SolStream c g f v (MatchSubst c f v)

-- | 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
--   <a>PatGraph</a> and use the same solution graph for multiple
--   patterns.)
match :: (PatGraphC f v, SolGraphC f, SolveC EClassId f v) => Pat f v -> EGraph d f -> [MatchSubst EClassId f v]
instance Data.Traversable.Traversable f => Data.Traversable.Traversable (Overeasy.Matching.Match c f)
instance Data.Foldable.Foldable f => Data.Foldable.Foldable (Overeasy.Matching.Match c f)
instance GHC.Base.Functor f => GHC.Base.Functor (Overeasy.Matching.Match c f)
instance Data.Traversable.Traversable f => Data.Traversable.Traversable (Overeasy.Matching.MatchPat c f)
instance Data.Foldable.Foldable f => Data.Foldable.Foldable (Overeasy.Matching.MatchPat c f)
instance GHC.Base.Functor f => GHC.Base.Functor (Overeasy.Matching.MatchPat c f)
instance Data.Traversable.Traversable f => Data.Traversable.Traversable (Overeasy.Matching.MatchPatF f v)
instance Data.Foldable.Foldable f => Data.Foldable.Foldable (Overeasy.Matching.MatchPatF f v)
instance GHC.Base.Functor f => GHC.Base.Functor (Overeasy.Matching.MatchPatF f v)
instance Data.Traversable.Traversable f => Data.Traversable.Traversable (Overeasy.Matching.MatchF c f v)
instance Data.Foldable.Foldable f => Data.Foldable.Foldable (Overeasy.Matching.MatchF c f v)
instance GHC.Base.Functor f => GHC.Base.Functor (Overeasy.Matching.MatchF c f v)
instance Control.DeepSeq.NFData Overeasy.Matching.VarId
instance Data.Hashable.Class.Hashable Overeasy.Matching.VarId
instance GHC.Enum.Enum Overeasy.Matching.VarId
instance GHC.Classes.Ord Overeasy.Matching.VarId
instance GHC.Classes.Eq Overeasy.Matching.VarId
instance GHC.Show.Show Overeasy.Matching.VarId
instance GHC.Show.Show Overeasy.Matching.Record
instance GHC.Classes.Eq Overeasy.Matching.Record
instance GHC.Show.Show c => GHC.Show.Show (Overeasy.Matching.SolState c)
instance GHC.Classes.Eq c => GHC.Classes.Eq (Overeasy.Matching.SolState c)
instance (GHC.Classes.Eq c, GHC.Classes.Eq v, GHC.Classes.Eq (f (Overeasy.Matching.Match c f v))) => GHC.Classes.Eq (Overeasy.Matching.Match c f v)
instance (GHC.Show.Show c, GHC.Show.Show v, GHC.Show.Show (f (Overeasy.Matching.Match c f v))) => GHC.Show.Show (Overeasy.Matching.Match c f v)
instance (GHC.Classes.Eq v, GHC.Classes.Eq (f (Overeasy.Matching.Match c f v))) => GHC.Classes.Eq (Overeasy.Matching.MatchPat c f v)
instance (GHC.Show.Show v, GHC.Show.Show (f (Overeasy.Matching.Match c f v))) => GHC.Show.Show (Overeasy.Matching.MatchPat c f v)
instance (GHC.Classes.Eq c, GHC.Classes.Eq v, GHC.Classes.Eq (f (Overeasy.Matching.Match c f v))) => GHC.Classes.Eq (Overeasy.Matching.MatchSubst c f v)
instance (GHC.Show.Show c, GHC.Show.Show v, GHC.Show.Show (f (Overeasy.Matching.Match c f v))) => GHC.Show.Show (Overeasy.Matching.MatchSubst c f v)
instance (GHC.Classes.Eq v, GHC.Classes.Eq (g Overeasy.Matching.VarId), GHC.Classes.Eq (f Overeasy.Matching.VarId)) => GHC.Classes.Eq (Overeasy.Matching.PatGraph g f v)
instance (GHC.Show.Show v, GHC.Show.Show (g Overeasy.Matching.VarId), GHC.Show.Show (f Overeasy.Matching.VarId)) => GHC.Show.Show (Overeasy.Matching.PatGraph g f v)
instance (GHC.Classes.Eq c, GHC.Classes.Eq (f c)) => GHC.Classes.Eq (Overeasy.Matching.SolGraph c f)
instance (GHC.Show.Show c, GHC.Show.Show (f c)) => GHC.Show.Show (Overeasy.Matching.SolGraph c f)
instance GHC.Base.Functor f => Data.Functor.Foldable.Recursive (Overeasy.Matching.Match c f v)
instance GHC.Base.Functor f => Data.Functor.Foldable.Corecursive (Overeasy.Matching.Match c f v)


-- | An example using arithmetic expressions.
module Overeasy.Example

-- | Arithmetic expressions. <a>ArithF</a> is the base functor for this
--   type.
data Arith
ArithPlus :: Arith -> Arith -> Arith
ArithTimes :: Arith -> Arith -> Arith
ArithShiftL :: Arith -> !Int -> Arith
ArithShiftR :: Arith -> !Int -> Arith
ArithConst :: !Int -> Arith
data ArithF r_aJ60
ArithPlusF :: r_aJ60 -> r_aJ60 -> ArithF r_aJ60
ArithTimesF :: r_aJ60 -> r_aJ60 -> ArithF r_aJ60
ArithShiftLF :: r_aJ60 -> !Int -> ArithF r_aJ60
ArithShiftRF :: r_aJ60 -> !Int -> ArithF r_aJ60
ArithConstF :: !Int -> ArithF r_aJ60

-- | Creates a simple e-graph with the equality `2 + 2 = 4`.
exampleGraph :: EGraph () ArithF

-- | Creates a simple pattern to match nodes like `x + x`.
examplePat :: Pat ArithF String

-- | Build an e-graph, e-match on it, and print the result.
exampleMain :: IO ()
instance Data.Traversable.Traversable Overeasy.Example.ArithF
instance Data.Foldable.Foldable Overeasy.Example.ArithF
instance GHC.Base.Functor Overeasy.Example.ArithF
instance GHC.Classes.Eq a => GHC.Classes.Eq (Overeasy.Example.ArithF a)
instance GHC.Show.Show a => GHC.Show.Show (Overeasy.Example.ArithF a)
instance GHC.Generics.Generic (Overeasy.Example.ArithF a)
instance Data.Hashable.Class.Hashable a => Data.Hashable.Class.Hashable (Overeasy.Example.ArithF a)
instance Control.DeepSeq.NFData a => Control.DeepSeq.NFData (Overeasy.Example.ArithF a)
instance Data.Functor.Foldable.Recursive Overeasy.Example.Arith
instance Data.Functor.Foldable.Corecursive Overeasy.Example.Arith
instance Control.DeepSeq.NFData Overeasy.Example.Arith
instance Data.Hashable.Class.Hashable Overeasy.Example.Arith
instance GHC.Generics.Generic Overeasy.Example.Arith
instance GHC.Show.Show Overeasy.Example.Arith
instance GHC.Classes.Eq Overeasy.Example.Arith