-- 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.0
-- | 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
Fix :: f (Fix f) -> Fix f
[unFix] :: Fix f -> 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
-- | Least fixed point. Efficient folding.
newtype Mu f
Mu :: (forall a. (f a -> a) -> a) -> Mu f
[unMu] :: Mu f -> 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
-- | Greatest fixed point. Efficient unfolding.
data Nu f
Nu :: (a -> f a) -> a -> Nu f
-- | 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
-- | 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.Generics.Generic (Data.Fix.Fix f)
instance (Data.Typeable.Internal.Typeable f, Data.Data.Data (f (Data.Fix.Fix f))) => Data.Data.Data (Data.Fix.Fix f)
instance (GHC.Base.Functor f, Data.Functor.Classes.Eq1 f) => GHC.Classes.Eq (Data.Fix.Nu f)
instance (GHC.Base.Functor f, Data.Functor.Classes.Ord1 f) => GHC.Classes.Ord (Data.Fix.Nu f)
instance (GHC.Base.Functor f, Data.Functor.Classes.Show1 f) => GHC.Show.Show (Data.Fix.Nu f)
instance (GHC.Base.Functor f, Data.Functor.Classes.Read1 f) => GHC.Read.Read (Data.Fix.Nu f)
instance (GHC.Base.Functor f, Data.Functor.Classes.Eq1 f) => GHC.Classes.Eq (Data.Fix.Mu f)
instance (GHC.Base.Functor f, Data.Functor.Classes.Ord1 f) => GHC.Classes.Ord (Data.Fix.Mu f)
instance (GHC.Base.Functor f, Data.Functor.Classes.Show1 f) => GHC.Show.Show (Data.Fix.Mu f)
instance (GHC.Base.Functor f, Data.Functor.Classes.Read1 f) => GHC.Read.Read (Data.Fix.Mu f)
instance Data.Functor.Classes.Eq1 f => GHC.Classes.Eq (Data.Fix.Fix f)
instance Data.Functor.Classes.Ord1 f => GHC.Classes.Ord (Data.Fix.Fix f)
instance Data.Functor.Classes.Show1 f => GHC.Show.Show (Data.Fix.Fix f)
instance Data.Functor.Classes.Read1 f => GHC.Read.Read (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)