-- 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.3 -- | 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 -- | 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 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 -- | 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 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 -- | 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.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)