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


-- | 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 <tt>f</tt> should be a <a>Functor</a> if you want to use simple
--   recursion schemes or <a>Traversable</a> 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 <tt>b</tt> are recursion
--   points.
--   
--   <pre>
--   &gt;&gt;&gt; data ListF a b = Nil | Cons a b deriving (Show, Functor)
--   </pre>
--   
--   The list is then a fixed point of <tt>ListF</tt>
--   
--   <pre>
--   &gt;&gt;&gt; type List a = Fix (ListF a)
--   </pre>
--   
--   We can write <tt>length</tt> function. Note that the function we give
--   to <a>foldFix</a> is not recursive. Instead the results of recursive
--   calls are in <tt>b</tt> positions, and we need to deal only with one
--   layer of the structure.
--   
--   <pre>
--   &gt;&gt;&gt; :{
--   let length :: List a -&gt; Int
--       length = foldFix $ \x -&gt; case x of
--           Nil      -&gt; 0
--           Cons _ n -&gt; n + 1
--   :}
--   </pre>
--   
--   If you already have recursive type, like '[Int]', you can first
--   convert it to `Fix (ListF a)` and then <a>foldFix</a>. Alternatively
--   you can use <tt>recursion-schemes</tt> 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 <a>Fix</a>.
hoistFix :: Functor f => (forall a. () => f a -> g a) -> Fix f -> Fix g

-- | Like <a>hoistFix</a> but <a>fmap</a>ping over <tt>g</tt>.
hoistFix' :: Functor g => (forall a. () => f a -> g a) -> Fix f -> Fix g

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

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

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

-- | Unwrap <a>Fix</a>.
--   
--   <pre>
--   &gt;&gt;&gt; let x = unfoldFix (\i -&gt; if i &lt; 3 then Cons i (i + 1) else Nil) (0 :: Int)
--   
--   &gt;&gt;&gt; unwrapFix x
--   Cons 0 (Fix (Cons 1 (Fix (Cons 2 (Fix Nil)))))
--   </pre>
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 <a>Mu</a>.
hoistMu :: (forall a. () => f a -> g a) -> Mu f -> Mu g

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

-- | Unfold <a>Mu</a>.
--   
--   <pre>
--   &gt;&gt;&gt; unfoldMu (\i -&gt; if i &lt; 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)))))))))
--   </pre>
unfoldMu :: Functor f => (a -> f a) -> a -> Mu f

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

-- | Unwrap <a>Mu</a>.
--   
--   <pre>
--   &gt;&gt;&gt; let x = unfoldMu (\i -&gt; if i &lt; 3 then Cons i (i + 1) else Nil) (0 :: Int)
--   
--   &gt;&gt;&gt; unwrapMu x
--   Cons 0 (unfoldMu unFix (Fix (Cons 1 (Fix (Cons 2 (Fix Nil))))))
--   </pre>
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 <a>Nu</a>.
hoistNu :: (forall a. () => f a -> g a) -> Nu f -> Nu g

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

-- | Unfold <a>Nu</a>.
--   
--   <pre>
--   &gt;&gt;&gt; unfoldNu (\i -&gt; if i &lt; 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)))))))))
--   </pre>
unfoldNu :: (a -> f a) -> a -> Nu f

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

-- | Unwrap <a>Nu</a>.
--   
--   <pre>
--   &gt;&gt;&gt; let x = unfoldNu (\i -&gt; if i &lt; 3 then Cons i (i + 1) else Nil) (0 :: Int)
--   
--   &gt;&gt;&gt; unwrapNu x
--   Cons 0 (unfoldNu unFix (Fix (Cons 1 (Fix (Cons 2 (Fix Nil))))))
--   </pre>
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 <a>foldFix</a>.
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.

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

-- | Anamorphism or generic function unfold.

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

-- | Hylomorphism is anamorphism followed by catamorphism.

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

-- | Monadic catamorphism.

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

-- | Monadic anamorphism.

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

-- | Monadic hylomorphism.

-- | <i>Deprecated: Use refoldM</i>
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)
