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


-- | Constructing, analyzing and destructing annotated trees
--   
--   <tt>Annotations</tt> provides utility functions to make working with
--   annotated trees easier. There are two implementations: one for working
--   with open datatypes that explicitly make their child positions
--   accessible through a type argument, and one for working with MultiRec
--   datatypes.
--   
--   Parser combinators make it easy to construct trees annotated with
--   position information. For the MultiRec implementation, there is the
--   <tt>Yield</tt> monad that allows construction of trees in postorder.
--   
--   Error algebras allow destruction of trees using catamorphisms. The
--   algebra is allowed to indicate failure in which case the error is
--   automatically coupled with the annotation at the position at which the
--   error occurred.
@package Annotations
@version 0.2


-- | The generic zipper.
module Annotations.MultiRec.Zipper

-- | Abstract type of locations. A location contains the current focus and
--   its context. A location is parameterized over the family of datatypes
--   and over the type of the complete value.
data Loc :: (* -> *) -> ((* -> *) -> * -> *) -> (* -> *) -> * -> *
Loc :: phi ix -> r ix -> Ctxs phi f ix r a -> Loc phi f r a

-- | Abstract type of context frames. Not required for the high-level
--   navigation functions.
data Ctxs :: (* -> *) -> ((* -> *) -> * -> *) -> * -> (* -> *) -> * -> *
Empty :: Ctxs phi f a r a
Push :: phi ix -> Ctx f b r ix -> Ctxs phi f ix r a -> Ctxs phi f b r a

-- | It is in general not necessary to use the generic navigation functions
--   directly. The functions listed in the `<tt>Interface'</tt> section
--   below are more user-friendly.
class HFunctor phi f => Zipper phi f
cmapA :: (Zipper phi f, Applicative a) => (forall ix. phi ix -> r ix -> a (r' ix)) -> phi ix -> Ctx f b r ix -> a (Ctx f b r' ix)
fill :: Zipper phi f => phi b -> Ctx f b r ix -> r b -> f r ix
first, last :: Zipper phi f => (forall b. phi b -> r b -> Ctx f b r ix -> a) -> f r ix -> Maybe a
next, prev :: Zipper phi f => (forall b. phi b -> r b -> Ctx f b r ix -> a) -> phi b -> Ctx f b r ix -> r b -> Maybe a

-- | Start navigating a datastructure. Returns a location that focuses the
--   entire value and has an empty context.
enter :: Zipper phi f => phi ix -> r ix -> Loc phi f r ix

-- | Operate on the current focus. This function can be used to extract the
--   current point of focus.
on :: (forall xi. phi xi -> r xi -> a) -> Loc phi f r ix -> a

-- | Update the current focus without changing its type.
update :: (forall xi. phi xi -> r xi -> r xi) -> Loc phi f r ix -> Loc phi f r ix
instance (Constructor c, Zipper phi f) => Zipper phi (C c f)
instance Zipper phi f => Zipper phi (f :>: xi)
instance (Zipper phi f, Zipper phi g) => Zipper phi (f :*: g)
instance (Zipper phi f, Zipper phi g) => Zipper phi (f :+: g)
instance Zipper phi U
instance Zipper phi (K a)
instance El phi xi => Zipper phi (I xi)
instance Zipper phi f => HFunctor phi (Loc phi f)
instance Zipper phi f => HFunctor phi (Ctxs phi f b)
instance Zipper phi f => HFunctor phi (Ctx f b)


-- | Zipper functions specialised to work on fixpoints of pattern functors.
module Annotations.MultiRec.ZipperFix

-- | A navigation step in a fixpoint.
type Nav = forall phi f ix. Zipper phi f => FixZipper phi f ix -> Maybe (FixZipper phi f ix)

-- | A location within a fixpoint.
type FixZipper phi f = Loc phi f (HFix f)

-- | Move down to the leftmost child. Returns <a>Nothing</a> if the current
--   focus is a leaf.
down :: Nav

-- | Move down to the rightmost child. Returns <a>Nothing</a> if the
--   current focus is a leaf.
down' :: Nav

-- | Move up to the parent. Returns <a>Nothing</a> if the current focus is
--   the root.
up :: Nav

-- | Move to the right sibling. Returns <a>Nothing</a> if the current focus
--   is the rightmost sibling.
right :: Nav

-- | Move to the left sibling. Returns <a>Nothing</a> if the current focus
--   is the leftmost sibling.
left :: Nav

-- | Move through all positions in depth-first left-to-right order.
dfnext :: Nav

-- | Move through all positions in depth-first right-to-left order.
dfprev :: Nav

-- | Return the entire value, independent of the current focus.
leave :: Zipper phi f => Loc phi f (HFix f) ix -> HFix f ix


-- | A Show-like type class for families of data types.
module Annotations.MultiRec.ShowFam
class ShowFam fam
showFam :: ShowFam fam => fam a -> a -> String


-- | Pattern functors existentially quantified in their top-level index
--   type <tt>ix</tt>.
module Annotations.MultiRec.Any

-- | A value of some type in data family <tt>s</tt>, together with its
--   witness.
data Any s
Any :: s ix -> ix -> Any s

-- | Helper constructor.
mkAny :: El s ix => ix -> Any s

-- | Unify an <a>Any</a> with an <tt>a</tt>.
matchAny :: EqS s => s a -> Any s -> Maybe a

-- | A value of some type in data family <tt>s</tt> wrapped in an
--   <tt>f</tt>, together with its witness.
data AnyF s f
AnyF :: s ix -> f ix -> AnyF s f

-- | Helper constructor.
mkAnyF :: El s ix => r ix -> AnyF s r

-- | Unify an <a>AnyF</a> with an <tt>f a</tt>.
matchAnyF :: EqS s => s a -> AnyF s f -> Maybe (f a)

-- | Removes the value from its functor <tt>f</tt>.
unwrapAnyF :: (forall ix. f ix -> ix) -> AnyF s f -> Any s

-- | Unwrap an <a>AnyF</a> and pass it to a function.
($?) :: (forall b. s b -> f b -> a) -> AnyF s f -> a
instance ShowFam s => Show (Any s)

module Annotations.ExploreHints

-- | Captures hints for the exploration of annotated trees.
data ExploreHints
ExploreHints :: Bool -> Bool -> Bool -> ExploreHints

-- | Whether the current focus matches.
matchHere :: ExploreHints -> Bool

-- | Whether to explore the children.
exploreDown :: ExploreHints -> Bool

-- | Whether to explore further to the right.
exploreRight :: ExploreHints -> Bool

module Annotations.MultiRec.Annotated

-- | A fully annotated tree.
type AnnFix x s = HFix (K x :*: PF s)

-- | A functor with fully annotated children.
type AnnFix1 x s = (PF s) (AnnFix x s)

-- | Supply a tree with an annotation at the top level.
mkAnnFix :: x -> AnnFix1 x s ix -> AnnFix x s ix

-- | A fixpoint of a data family <tt>s</tt> annotated with an <tt>x</tt> at
--   every recursive position, with existentially quantified top-level
--   index.
type AnyAnnFix x s = AnyF s (AnnFix x s)

-- | Removes all annotations from a recursively annotated fixpoint.
unannotate :: HFunctor s (PF s) => s ix -> AnnFix x s ix -> HFix (PF s) ix

-- | Collects the direct children of a functor in a list.
children :: HFunctor s f => s ix -> f r ix -> [AnyF s r]

-- | Flatten an annotated tree to a list of subtrees coupled with their
--   annotations.
flatten :: (HFunctor s (PF s), Fam s) => s ix -> AnnFix x s ix -> [(x, Any s)]

-- | Yield all subtrees whose annotation matches the predicate.
filterAnnFix :: (Fam s, HFunctor s (PF s)) => s ix -> (x -> Bool) -> AnnFix x s ix -> [(x, Any s)]

-- | Flatten an annotated tree and print all subtrees to stdout.
debugFlatten :: (HFunctor s (PF s), ShowFam s, Show x, Fam s) => s ix -> AnnFix x s ix -> IO ()

-- | Recursively yield all annotations in the tree in preorder.
allAnnotations :: HFunctor phi (PF phi) => phi ix -> AnnFix x phi ix -> [x]
type AnnZipper phi x = FixZipper phi (K x :*: PF phi)

-- | Extract the annotation of the current focus.
focusAnn :: Loc phi f (HFix (K x :*: g)) ix -> x

-- | Explore an annotated tree. Starting with the root of the tree, at each
--   position the annotation at that position is matched against the
--   <a>ExploreHints</a> predicates and all the selections where
--   <a>matchHere</a> was positive are collected. The <a>exploreRight</a>
--   and <a>exploreDown</a> allow pruning of the tree, preventing entire
--   parts from being visited.
explore :: Zipper phi (PF phi) => phi ix -> (x -> ExploreHints) -> (AnnFix x phi) ix -> [AnnZipper phi x ix]

-- | Find the deepest node in an annotated tree that matches the predicate.
--   Starting with the root, the predicate tells whether a node's
--   annotation matches. If so, the search continues at the node's children
--   and the node's siblings to the right are excluded from further
--   exploration. If no child matches, the node itself is returned.
findLeftmostDeepest :: Zipper phi (PF phi) => phi ix -> (x -> Bool) -> AnnFix x phi ix -> Maybe (AnnZipper phi x ix)

module Annotations.MultiRec.Yield

-- | Monads that allow yielding recursively annotated values.
class Monad m => MonadYield m where type family YieldFam m :: * -> * type family AnnType m :: *
yield :: MonadYield m => (YieldFam m) ix -> AnnType m -> ix -> m ix

-- | The Yield transformer. Allows yielding generic values in family
--   <tt>fam</tt> with annotations of type <tt>x</tt>.
data YieldT x fam m a

-- | Yield over the identity monad.
type Yield x fam = YieldT x fam Identity
runYield :: EqS fam => fam a -> Yield x fam a -> Maybe (AnnFix x fam a)
runYieldG :: Yield x fam a -> (a, Maybe (AnyAnnFix x fam))
runYieldT :: (Monad m, EqS fam) => fam a -> YieldT x fam m a -> m (Maybe (AnnFix x fam a))
runYieldTG :: Monad m => YieldT x fam m a -> m (a, Maybe (AnyAnnFix x fam))
instance Functor m => Functor (YieldT x fam m)
instance Monad m => Monad (YieldT x fam m)
instance (Monad m, HFunctor fam (PF fam), EqS fam, Fam fam) => MonadYield (YieldT x fam m)
instance MonadTrans (YieldT x fam)


-- | The <a>Except</a> datatype captures monoidal exceptions in applicative
--   computations.
module Annotations.Except

-- | <tt>Except</tt> is like <tt>Either</tt> but is meant to be used only
--   in applicative computations. When two exceptions are sequenced, their
--   sum (using <a>mappend</a>) is computed.
data Except e a
Failed :: e -> Except e a
OK :: a -> Except e a
instance (Eq e, Eq a) => Eq (Except e a)
instance (Show e, Show a) => Show (Except e a)
instance Monoid e => Applicative (Except e)
instance Functor (Except e)

module Annotations.F.Fixpoints

-- | Fixpoint of functors.
newtype Fix fT
In :: fT (Fix fT) -> Fix fT
out :: Fix fT -> fT (Fix fT)

-- | Apply a transformation to a tree's direct children.
compos :: Functor f => (Fix f -> Fix f) -> Fix f -> Fix f

-- | Algebras for catamorphisms.
type Algebra fT aT = fT aT -> aT

-- | Reduces a tree to a value according to the algebra.
cata :: Functor fT => Algebra fT aT -> Fix fT -> aT

-- | Coalgebras for anamorphisms.
type Coalgebra fT aT = aT -> fT aT

-- | Constructs a tree from a value according to the coalgebra.
ana :: Functor fT => Coalgebra fT aT -> aT -> Fix fT

-- | Algebras for error catamorphisms.
type ErrorAlgebra fT eT aT = fT aT -> Either eT aT

-- | Reduces a tree to a value according to the algebra, propagating
--   potential errors.
cascade :: (Traversable fT, Monoid eT) => ErrorAlgebra fT eT aT -> Algebra fT (Except eT aT)
instance Eq (f (Fix f)) => Eq (Fix f)
instance Show (f (Fix f)) => Show (Fix f)

module Annotations.F.Zipper

-- | A quasi-zipper, meant for O(1), fixed-memory stepping through a tree
--   structure, but not meant for updates.
data Zipper a
Zipper :: a -> Maybe (Zipper a) -> Maybe (Zipper a) -> Maybe (Zipper a) -> Maybe (Zipper a) -> Zipper a

-- | The current focus of this zipper.
zFocus :: Zipper a -> a

-- | Move up to the parent.
zUp :: Zipper a -> Maybe (Zipper a)

-- | Move to the left sibling.
zLeft :: Zipper a -> Maybe (Zipper a)

-- | Move to the right sibling.
zRight :: Zipper a -> Maybe (Zipper a)

-- | Move down into the leftmost child.
zDown :: Zipper a -> Maybe (Zipper a)

-- | Move into the root of the fixed point. The returned zipper builds a
--   data structure with optimal sharing and fixed memory usage. For
--   example, <tt>zLeft &gt;=&gt; zRight</tt> (if successful) returns to
--   the same node in memory.
enter :: Foldable f => Fix f -> Zipper (Fix f)

-- | Walk back up to the root of the fixed point and leave the zipper
--   structure.
leave :: Zipper a -> a

-- | Move down into a specific child.
child :: Int -> Zipper a -> Maybe (Zipper a)

-- | Traverses the tree in preorder, yielding all possible tree selections.
allFoci :: Foldable f => Fix f -> [Zipper (Fix f)]

-- | Captures navigation steps in a <a>Zipper</a>. Its <a>Monoid</a>
--   instance specifies the identity step (<a>mempty</a>) and step
--   composition (<a>mappend</a>).
newtype Nav
Nav :: (forall a. Zipper a -> Maybe (Zipper a)) -> Nav
nav :: Nav -> forall a. Zipper a -> Maybe (Zipper a)
instance Monoid Nav

module Annotations.F.Annotated

-- | Lifted annotation of functors.
data Ann x f a
Ann :: x -> (f a) -> Ann x f a

-- | A fully annotated tree.
type AnnFix xT fT = Fix (Ann xT fT)

-- | Yields the annotation at the root of the tree.
rootAnn :: AnnFix x f -> x

-- | A functor with fully annotated children.
type AnnFix1 xT fT = fT (AnnFix xT fT)

-- | Supply a tree with an annotation at the top level.
mkAnnFix :: x -> AnnFix1 x f -> AnnFix x f

-- | Recursively discard annotations.
unannotate :: Functor f => AnnFix x f -> Fix f

-- | Reduces a tree to a value according to the algebra, collecting
--   potential errors. The errors are combined with the annotations in the
--   tree at the positions at which the errors occurred.
errorCata :: Traversable fT => ErrorAlgebra fT eT aT -> AnnFix xT fT -> Except [(eT, xT)] aT

-- | Explore an annotated tree. Starting with the root of the tree, at each
--   position the annotation at that position is matched against the
--   <a>ExploreHints</a> predicates and all the selections where
--   <a>matchHere</a> was positive are collected. The <a>exploreRight</a>
--   and <a>exploreDown</a> allow pruning of the tree, preventing entire
--   parts from being visited.
explore :: Foldable f => (x -> ExploreHints) -> AnnFix x f -> [Zipper (AnnFix x f)]

-- | Find the deepest node in an annotated tree that matches the predicate.
--   Starting with the root, the predicate tells whether a node's
--   annotation matches. If so, the search continues at the node's children
--   and the node's siblings to the right are excluded from further
--   exploration. If no child matches, the node itself is returned.
findLeftmostDeepest :: Foldable f => (x -> Bool) -> AnnFix x f -> Maybe (Zipper (AnnFix x f))
instance (Eq x, Eq (f a)) => Eq (Ann x f a)
instance (Show x, Show (f a)) => Show (Ann x f a)
instance Traversable f => Traversable (Ann x f)
instance Foldable f => Foldable (Ann x f)
instance Functor f => Functor (Ann x f)

module Annotations.MultiRec.ErrorAlg

-- | Type family that converts pattern functors to convenient algebra
--   types.

-- | An error algebra over pattern functors.
type ErrorAlg_PF f e a = forall ix. f (K0 a) ix -> Either e a

-- | Converts convenient algebras to algebras that are able to work with
--   pattern functors.
class MkErrorAlg f
mkErrorAlg :: MkErrorAlg f => ErrorAlg f e a -> ErrorAlg_PF f e a

-- | Reduces a tree to a value according to the algebra, collecting
--   potential errors. The errors are combined with the annotations in the
--   tree at the positions at which the errors occurred.
errorCata :: HFunctor phi f => ErrorAlg_PF f e r -> phi ix -> HFix (K x :*: f) ix -> Except [(e, x)] r

-- | For constructing algebras that are made of nested pairs rather than
--   n-ary tuples, it is helpful to use this pairing combinator.
(&) :: a -> b -> (a, b)
instance (MkErrorAlg f, MkErrorAlg g) => MkErrorAlg (f :+: g)
instance MkErrorAlg f => MkErrorAlg (f :>: xi)
instance MkErrorAlg f => MkErrorAlg (I xi :*: f)
instance MkErrorAlg f => MkErrorAlg (K a :*: f)
instance MkErrorAlg U


-- | Types and utility functions for expression text selections.
module Annotations.Bounds

-- | A simple textual selection: starting offset and ending offset,
--   respectively. Offsets are 0-based.
type Range = (Int, Int)

-- | A structural selection expressed as a textual selection. The margins
--   indicate the whitespace directly around the selected structure.
data Bounds
Bounds :: Range -> Range -> Bounds
leftMargin :: Bounds -> Range
rightMargin :: Bounds -> Range

-- | A <tt>Bounds</tt>' inner range does not include the whitespace around
--   the selected structure.
innerRange :: Bounds -> Range

-- | A <tt>Bounds</tt>' outer range includes the whitespace around the
--   selected structure.
outerRange :: Bounds -> Range

-- | Tells whether the offset falls within the given range.
posInRange :: Int -> Range -> Bool

-- | Tells whether the first range is enclosed by the second range.
rangeInRange :: Range -> Range -> Bool

-- | A range is within certain bounds if its left offset is within the
--   bounds' left margin and its right offset is within the bounds' right
--   margin.
rangeInBounds :: Range -> Bounds -> Bool

-- | <tt>rangesInBounds b</tt> yields all those ranges <tt>r</tt> for which
--   <tt>rangeInBounds r b</tt>.
rangesInBounds :: Bounds -> [Range]

-- | A measure for the dissimilarity between two ranges.
--   
--   <pre>
--   distRange (l1, r1) (l2, r2) = |l1 - l2| + |r1 - r2|
--   </pre>
distRange :: Range -> Range -> Int
instance Eq Bounds
instance Show Bounds


-- | A Parsec parser type that parses <a>Symbol</a>s and keeps track of the
--   position within the input stream. Unlike Parsec's default position
--   tracking, this parser keeps track of the range of whitespace between
--   two tokens.
module Annotations.BoundsParser

-- | Symbols form input for parsers. Minimal complete definition:
--   <a>unparse</a>.
class Symbol s where symbolSize = length . unparse
unparse :: Symbol s => s -> String
symbolSize :: Symbol s => s -> Int

-- | Given a predicate that tells what tokens to discard, keeps only the
--   meaningful tokens and couples them with position information.
collapse :: Symbol s => (s -> Bool) -> [s] -> [(s, Bounds)]

-- | A parser that works on symbols coupled with token information. The
--   state maintains the current position in the stream. This position is
--   the range of whitespace between two tokens.
type P s = ParsecT [(s, Bounds)] Range

-- | Recognise a symbol matching a predicate.
satisfy :: (Monad m, Symbol s) => (s -> Bool) -> P s m s

-- | Recognise a specific symbol.
pToken :: (Monad m, Symbol s, Eq s) => s -> P s m s

-- | Yield the current position in the input.
getPos :: Monad m => P s m Range
instance Symbol s => Symbol [s]


-- | Queries on trees annotated with position information.
module Annotations.F.Positional

-- | Find the deepest node whose bounds match the given range. See
--   <a>rangeInBounds</a>.
selectByRange :: Foldable f => Range -> AnnFix Bounds f -> Maybe (Zipper (AnnFix Bounds f))

-- | Find the deepest node whose bounds contain the given position.
selectByPos :: Foldable f => Int -> AnnFix Bounds f -> Maybe (Zipper (AnnFix Bounds f))

-- | Find all selections in the tree and return their bounds. The tree is
--   traversed in preorder. Consequently, the bounds are returned in
--   lexicographical order.
validBounds :: Foldable f => AnnFix Bounds f -> [Bounds]

-- | <tt>repairBy cost tree range</tt> finds the the closest valid text
--   selection to <tt>range</tt>, where ''closest'' is determined by the
--   specified cost function.
repairBy :: (Foldable f, Ord dist) => (Range -> Range -> dist) -> AnnFix Bounds f -> Range -> Bounds

-- | Defined as <tt><a>repairBy</a> <a>distRange</a></tt>.
repair :: Foldable f => AnnFix Bounds f -> Range -> Bounds

-- | Move around in a tree according to the <a>Nav</a>, expressed in tree
--   selections. Although a <a>Range</a> is required as input, a
--   <a>Bounds</a> is returned, providing information about all the valid
--   text selections that would select the particular tree node.
moveSelection :: Foldable f => AnnFix Bounds f -> Nav -> Range -> Maybe Bounds

module Annotations.F.ParserCombinators

-- | Given the left margin of a structure, asks the parser for the right
--   margin and wraps the position information around the root of the tree.
mkBounded :: Monad m => Range -> AnnFix1 Bounds f -> P s m (AnnFix Bounds f)

-- | Wrap an unnotated tree with position information from the parse state.
unit :: Monad m => P s m (AnnFix1 Bounds f) -> P s m (AnnFix Bounds f)

-- | Parse right-recursive structures.
chainr :: Monad m => P s m (AnnFix Bounds f) -> P s m (AnnFix Bounds f -> AnnFix Bounds f -> AnnFix1 Bounds f) -> P s m (AnnFix Bounds f)

-- | Parse left-recursive structures.
chainl :: Monad m => P s m (AnnFix Bounds f) -> P s m (AnnFix Bounds f -> AnnFix Bounds f -> AnnFix1 Bounds f) -> P s m (AnnFix Bounds f)

module Annotations.MultiRec.ParserCombinators

-- | A parser that yields its components, annotated with <a>Bounds</a>.
type YP s fam m = P s (YieldT Bounds fam m)

-- | Given the left margin of a structure, asks the parser for the right
--   margin and wraps the position information around the root of the tree.
mkBounded :: (Fam fam, EqS fam, HFunctor fam (PF fam), Monad m) => fam a -> Range -> a -> YP s fam m a

-- | Wrap an unnotated tree with position information from the parse state.
unit :: (Fam fam, EqS fam, HFunctor fam (PF fam), Monad m) => fam a -> YP s fam m a -> YP s fam m a

-- | Parse right-recursive structures.
chainr :: (Fam fam, EqS fam, HFunctor fam (PF fam), Monad m, Show a) => fam a -> YP s fam m a -> YP s fam m (a -> a -> a) -> YP s fam m a

-- | Parse left-recursive structures.
chainl :: (Fam fam, EqS fam, HFunctor fam (PF fam), Monad m, Show a) => fam a -> YP s fam m a -> YP s fam m (a -> a -> a) -> YP s fam m a

module Annotations.MultiRec.Positional

-- | Find the deepest node whose bounds match the given range. See
--   <a>rangeInBounds</a>.
selectByRange :: Zipper phi (PF phi) => phi ix -> Range -> AnnFix Bounds phi ix -> Maybe (AnnZipper phi Bounds ix)
selectByPos :: Zipper phi (PF phi) => phi ix -> Int -> AnnFix Bounds phi ix -> Maybe (AnnZipper phi Bounds ix)
repairBy :: (Ord dist, HFunctor phi (PF phi)) => phi ix -> (Range -> Range -> dist) -> AnnFix Bounds phi ix -> Range -> Bounds

-- | Defined as <tt><a>repairBy</a> <a>distRange</a></tt>.
repair :: HFunctor phi (PF phi) => phi ix -> AnnFix Bounds phi ix -> Range -> Bounds
sortOn :: Ord b => (a -> b) -> [a] -> [a]

-- | Move around in a tree according to the <a>Nav</a>, expressed in tree
--   selections. Although a <a>Range</a> is required as input, a
--   <a>Bounds</a> is returned, providing information about all the valid
--   text selections that would select the particular tree node.
moveSelection :: Zipper phi (PF phi) => phi ix -> AnnFix Bounds phi ix -> Nav -> Range -> Maybe Bounds