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

-- | Fixpoint data types
--   
--   Fixpoint types and recursion schemes. If you define your AST as
--   fixpoint type, you get fold and unfold operations for free.
--   
--   Thanks for contribution to: Matej Kollar, Herbert Valerio Riedel
@package data-fix
@version 0.3.4

-- | Fixed points of a functor.
--   
--   Type f should be a Functor if you want to use simple
--   recursion schemes or Traversable if you want to use monadic
--   recursion schemes. This style allows you to express recursive
--   functions in non-recursive manner. You can imagine that a
--   non-recursive function holds values of the previous iteration.
--   
--   An example:
--   
--   First we define a base functor. The arguments b are recursion
--   points.
--   
--   
--   >>> data ListF a b = Nil | Cons a b deriving (Show, Functor)
--   
--   
--   The list is then a fixed point of ListF
--   
--   
--   >>> type List a = Fix (ListF a)
--   
--   
--   We can write length function. Note that the function we give
--   to foldFix is not recursive. Instead the results of recursive
--   calls are in b positions, and we need to deal only with one
--   layer of the structure.
--   
--   
--   >>> :{
--   let length :: List a -> Int
--       length = foldFix $ \x -> case x of
--           Nil      -> 0
--           Cons _ n -> n + 1
--   :}
--   
--   
--   If you already have recursive type, like '[Int]', you can first
--   convert it to `Fix (ListF a)` and then foldFix. Alternatively
--   you can use recursion-schemes combinators which work directly
--   on recursive types.
module Data.Fix

-- | A fix-point type.
newtype Fix (f :: Type -> Type)
Fix :: f (Fix f) -> Fix (f :: Type -> Type)
[unFix] :: Fix (f :: Type -> Type) -> f (Fix f)

-- | Change base functor in Fix.
hoistFix :: Functor f => (forall a. () => f a -> g a) -> Fix f -> Fix g

-- | Like hoistFix but fmapping over g.
hoistFix' :: Functor g => (forall a. () => f a -> g a) -> Fix f -> Fix g

-- | Fold Fix.
--   
--   
--   >>> let fp = unfoldFix (\i -> if i < 4 then Cons i (i + 1) else Nil) (0 :: Int)
--   
--   >>> foldFix (elimListF 0 (+)) fp
--   6
--   
foldFix :: Functor f => (f a -> a) -> Fix f -> a

-- | Unfold Fix.
--   
--   
--   >>> unfoldFix (\i -> if i < 4 then Cons i (i + 1) else Nil) (0 :: Int)
--   Fix (Cons 0 (Fix (Cons 1 (Fix (Cons 2 (Fix (Cons 3 (Fix Nil))))))))
--   
unfoldFix :: Functor f => (a -> f a) -> a -> Fix f

-- | Wrap Fix.
--   
--   
--   >>> let x = unfoldFix (\i -> if i < 3 then Cons i (i + 1) else Nil) (0 :: Int)
--   
--   >>> wrapFix (Cons 10 x)
--   Fix (Cons 10 (Fix (Cons 0 (Fix (Cons 1 (Fix (Cons 2 (Fix Nil))))))))
--   
wrapFix :: f (Fix f) -> Fix f

-- | Unwrap Fix.
--   
--   
--   >>> let x = unfoldFix (\i -> if i < 3 then Cons i (i + 1) else Nil) (0 :: Int)
--   
--   >>> unwrapFix x
--   Cons 0 (Fix (Cons 1 (Fix (Cons 2 (Fix Nil)))))
--   
unwrapFix :: Fix f -> f (Fix f)

-- | Least fixed point. Efficient folding.
newtype Mu (f :: Type -> Type)
Mu :: (forall a. () => (f a -> a) -> a) -> Mu (f :: Type -> Type)
[unMu] :: Mu (f :: Type -> Type) -> forall a. () => (f a -> a) -> a

-- | Change base functor in Mu.
hoistMu :: (forall a. () => f a -> g a) -> Mu f -> Mu g

-- | Fold Mu.
--   
--   
--   >>> let mu = unfoldMu (\i -> if i < 4 then Cons i (i + 1) else Nil) (0 :: Int)
--   
--   >>> foldMu (elimListF 0 (+)) mu
--   6
--   
foldMu :: (f a -> a) -> Mu f -> a

-- | Unfold Mu.
--   
--   
--   >>> unfoldMu (\i -> if i < 4 then Cons i (i + 1) else Nil) (0 :: Int)
--   unfoldMu unFix (Fix (Cons 0 (Fix (Cons 1 (Fix (Cons 2 (Fix (Cons 3 (Fix Nil)))))))))
--   
unfoldMu :: Functor f => (a -> f a) -> a -> Mu f

-- | Wrap Mu.
--   
--   
--   >>> let x = unfoldMu (\i -> if i < 3 then Cons i (i + 1) else Nil) (0 :: Int)
--   
--   >>> wrapMu (Cons 10 x)
--   unfoldMu unFix (Fix (Cons 10 (Fix (Cons 0 (Fix (Cons 1 (Fix (Cons 2 (Fix Nil)))))))))
--   
wrapMu :: Functor f => f (Mu f) -> Mu f

-- | Unwrap Mu.
--   
--   
--   >>> let x = unfoldMu (\i -> if i < 3 then Cons i (i + 1) else Nil) (0 :: Int)
--   
--   >>> unwrapMu x
--   Cons 0 (unfoldMu unFix (Fix (Cons 1 (Fix (Cons 2 (Fix Nil))))))
--   
unwrapMu :: Functor f => Mu f -> f (Mu f)

-- | Greatest fixed point. Efficient unfolding.
data Nu (f :: Type -> Type)
Nu :: (a -> f a) -> a -> Nu (f :: Type -> Type)

-- | Change base functor in Nu.
hoistNu :: (forall a. () => f a -> g a) -> Nu f -> Nu g

-- | Fold Nu.
--   
--   
--   >>> let nu = unfoldNu (\i -> if i < 4 then Cons i (i + 1) else Nil) (0 :: Int)
--   
--   >>> foldNu (elimListF 0 (+)) nu
--   6
--   
foldNu :: Functor f => (f a -> a) -> Nu f -> a

-- | Unfold Nu.
--   
--   
--   >>> unfoldNu (\i -> if i < 4 then Cons i (i + 1) else Nil) (0 :: Int)
--   unfoldNu unFix (Fix (Cons 0 (Fix (Cons 1 (Fix (Cons 2 (Fix (Cons 3 (Fix Nil)))))))))
--   
unfoldNu :: (a -> f a) -> a -> Nu f

-- | Wrap Nu.
--   
--   
--   >>> let x = unfoldNu (\i -> if i < 3 then Cons i (i + 1) else Nil) (0 :: Int)
--   
--   >>> wrapNu (Cons 10 x)
--   unfoldNu unFix (Fix (Cons 10 (Fix (Cons 0 (Fix (Cons 1 (Fix (Cons 2 (Fix Nil)))))))))
--   
wrapNu :: Functor f => f (Nu f) -> Nu f

-- | Unwrap Nu.
--   
--   
--   >>> let x = unfoldNu (\i -> if i < 3 then Cons i (i + 1) else Nil) (0 :: Int)
--   
--   >>> unwrapNu x
--   Cons 0 (unfoldNu unFix (Fix (Cons 1 (Fix (Cons 2 (Fix Nil))))))
--   
unwrapNu :: Functor f => Nu f -> f (Nu f)

-- | Refold one recursive type into another, one layer at the time.
refold :: Functor f => (f b -> b) -> (a -> f a) -> a -> b

-- | Monadic foldFix.
foldFixM :: (Monad m, Traversable t) => (t a -> m a) -> Fix t -> m a

-- | Monadic anamorphism.
unfoldFixM :: (Monad m, Traversable t) => (a -> m (t a)) -> a -> m (Fix t)

-- | Monadic hylomorphism.
refoldM :: (Monad m, Traversable t) => (t b -> m b) -> (a -> m (t a)) -> a -> m b

-- | Catamorphism or generic function fold.

-- | Deprecated: Use foldFix
cata :: Functor f => (f a -> a) -> Fix f -> a

-- | Anamorphism or generic function unfold.

-- | Deprecated: Use unfoldFix
ana :: Functor f => (a -> f a) -> a -> Fix f

-- | Hylomorphism is anamorphism followed by catamorphism.

-- | Deprecated: Use refold
hylo :: Functor f => (f b -> b) -> (a -> f a) -> a -> b

-- | Monadic catamorphism.

-- | Deprecated: Use foldFixM
cataM :: (Monad m, Traversable t) => (t a -> m a) -> Fix t -> m a

-- | Monadic anamorphism.

-- | Deprecated: Use unfoldFixM
anaM :: (Monad m, Traversable t) => (a -> m (t a)) -> a -> m (Fix t)

-- | Monadic hylomorphism.

-- | Deprecated: Use refoldM
hyloM :: (Monad m, Traversable t) => (t b -> m b) -> (a -> m (t a)) -> a -> m b
instance (GHC.Internal.Data.Typeable.Internal.Typeable f, GHC.Internal.Data.Data.Data (f (Data.Fix.Fix f))) => GHC.Internal.Data.Data.Data (Data.Fix.Fix f)
instance Data.Functor.Classes.Eq1 f => GHC.Classes.Eq (Data.Fix.Fix f)
instance (GHC.Internal.Base.Functor f, Data.Functor.Classes.Eq1 f) => GHC.Classes.Eq (Data.Fix.Mu f)
instance (GHC.Internal.Base.Functor f, Data.Functor.Classes.Eq1 f) => GHC.Classes.Eq (Data.Fix.Nu f)
instance GHC.Internal.Generics.Generic (Data.Fix.Fix f)
instance Data.Hashable.Class.Hashable1 f => Data.Hashable.Class.Hashable (Data.Fix.Fix f)
instance Control.DeepSeq.NFData1 f => Control.DeepSeq.NFData (Data.Fix.Fix f)
instance Data.Functor.Classes.Ord1 f => GHC.Classes.Ord (Data.Fix.Fix f)
instance (GHC.Internal.Base.Functor f, Data.Functor.Classes.Ord1 f) => GHC.Classes.Ord (Data.Fix.Mu f)
instance (GHC.Internal.Base.Functor f, Data.Functor.Classes.Ord1 f) => GHC.Classes.Ord (Data.Fix.Nu f)
instance Data.Functor.Classes.Read1 f => GHC.Internal.Read.Read (Data.Fix.Fix f)
instance (GHC.Internal.Base.Functor f, Data.Functor.Classes.Read1 f) => GHC.Internal.Read.Read (Data.Fix.Mu f)
instance (GHC.Internal.Base.Functor f, Data.Functor.Classes.Read1 f) => GHC.Internal.Read.Read (Data.Fix.Nu f)
instance Data.Functor.Classes.Show1 f => GHC.Internal.Show.Show (Data.Fix.Fix f)
instance (GHC.Internal.Base.Functor f, Data.Functor.Classes.Show1 f) => GHC.Internal.Show.Show (Data.Fix.Mu f)
instance (GHC.Internal.Base.Functor f, Data.Functor.Classes.Show1 f) => GHC.Internal.Show.Show (Data.Fix.Nu f)
