Safe Haskell	Trustworthy
Language	Haskell2010

Data.Fix

Contents

Fix
Mu - least fixed point
Nu - greatest fixed point
Refolding
Monadic variants
Deprecated aliases

Description

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.

Synopsis

newtype Fix f = Fix {
- unFix :: f ( Fix f)
}
hoistFix :: Functor f => ( forall a. f a -> g a) -> Fix f -> Fix g
hoistFix' :: Functor g => ( forall a. f a -> g a) -> Fix f -> Fix g
foldFix :: Functor f => (f a -> a) -> Fix f -> a
unfoldFix :: Functor f => (a -> f a) -> a -> Fix f
wrapFix :: f ( Fix f) -> Fix f
unwrapFix :: Fix f -> f ( Fix f)
newtype Mu f = Mu {
- unMu :: forall a. (f a -> a) -> a
}
hoistMu :: ( forall a. f a -> g a) -> Mu f -> Mu g
foldMu :: (f a -> a) -> Mu f -> a
unfoldMu :: Functor f => (a -> f a) -> a -> Mu f
wrapMu :: Functor f => f ( Mu f) -> Mu f
unwrapMu :: Functor f => Mu f -> f ( Mu f)
data Nu f = forall a. Nu (a -> f a) a
hoistNu :: ( forall a. f a -> g a) -> Nu f -> Nu g
foldNu :: Functor f => (f a -> a) -> Nu f -> a
unfoldNu :: (a -> f a) -> a -> Nu f
wrapNu :: Functor f => f ( Nu f) -> Nu f
unwrapNu :: Functor f => Nu f -> f ( Nu f)
refold :: Functor f => (f b -> b) -> (a -> f a) -> a -> b
foldFixM :: ( Monad m, Traversable t) => (t a -> m a) -> Fix t -> m a
unfoldFixM :: ( Monad m, Traversable t) => (a -> m (t a)) -> a -> m ( Fix t)
refoldM :: ( Monad m, Traversable t) => (t b -> m b) -> (a -> m (t a)) -> a -> m b
cata :: Functor f => (f a -> a) -> Fix f -> a
ana :: Functor f => (a -> f a) -> a -> Fix f
hylo :: Functor f => (f b -> b) -> (a -> f a) -> a -> b
cataM :: ( Monad m, Traversable t) => (t a -> m a) -> Fix t -> m a
anaM :: ( Monad m, Traversable t) => (a -> m (t a)) -> a -> m ( Fix t)
hyloM :: ( Monad m, Traversable t) => (t b -> m b) -> (a -> m (t a)) -> a -> m b

Fix

newtype Fix f Source #

A fix-point type.

Constructors

Fix
Fields unFix :: f ( Fix f)

Instances

Instances details

Eq1 f => Eq ( Fix f) Source #
Instance details Defined in Data.Fix Methods (==) :: Fix f -> Fix f -> Bool Source # (/=) :: Fix f -> Fix f -> Bool Source #
( Typeable f, Data (f ( Fix f))) => Data ( Fix f) Source #
Instance details Defined in Data.Fix Methods gfoldl :: ( forall d b. Data d => c (d -> b) -> d -> c b) -> ( forall g. g -> c g) -> Fix f -> c ( Fix f) Source # gunfold :: ( forall b r. Data b => c (b -> r) -> c r) -> ( forall r. r -> c r) -> Constr -> c ( Fix f) Source # toConstr :: Fix f -> Constr Source # dataTypeOf :: Fix f -> DataType Source # dataCast1 :: Typeable t => ( forall d. Data d => c (t d)) -> Maybe (c ( Fix f)) Source # dataCast2 :: Typeable t => ( forall d e. ( Data d, Data e) => c (t d e)) -> Maybe (c ( Fix f)) Source # gmapT :: ( forall b. Data b => b -> b) -> Fix f -> Fix f Source # gmapQl :: (r -> r' -> r) -> r -> ( forall d. Data d => d -> r') -> Fix f -> r Source # gmapQr :: forall r r'. (r' -> r -> r) -> r -> ( forall d. Data d => d -> r') -> Fix f -> r Source # gmapQ :: ( forall d. Data d => d -> u) -> Fix f -> [u] Source # gmapQi :: Int -> ( forall d. Data d => d -> u) -> Fix f -> u Source # gmapM :: Monad m => ( forall d. Data d => d -> m d) -> Fix f -> m ( Fix f) Source # gmapMp :: MonadPlus m => ( forall d. Data d => d -> m d) -> Fix f -> m ( Fix f) Source # gmapMo :: MonadPlus m => ( forall d. Data d => d -> m d) -> Fix f -> m ( Fix f) Source #
Ord1 f => Ord ( Fix f) Source #
Instance details Defined in Data.Fix Methods compare :: Fix f -> Fix f -> Ordering Source # (<) :: Fix f -> Fix f -> Bool Source # (<=) :: Fix f -> Fix f -> Bool Source # (>) :: Fix f -> Fix f -> Bool Source # (>=) :: Fix f -> Fix f -> Bool Source # max :: Fix f -> Fix f -> Fix f Source # min :: Fix f -> Fix f -> Fix f Source #
Read1 f => Read ( Fix f) Source #
Instance details Defined in Data.Fix Methods readsPrec :: Int -> ReadS ( Fix f) Source # readList :: ReadS [ Fix f] Source # readPrec :: ReadPrec ( Fix f) Source # readListPrec :: ReadPrec [ Fix f] Source #
Show1 f => Show ( Fix f) Source #
Instance details Defined in Data.Fix Methods showsPrec :: Int -> Fix f -> ShowS Source # show :: Fix f -> String Source # showList :: [ Fix f] -> ShowS Source #
Generic ( Fix f) Source #
Instance details Defined in Data.Fix Associated Types type Rep ( Fix f) :: Type -> Type Source # Methods from :: Fix f -> Rep ( Fix f) x Source # to :: Rep ( Fix f) x -> Fix f Source #
NFData1 f => NFData ( Fix f) Source #
Instance details Defined in Data.Fix Methods rnf :: Fix f -> () Source #
Hashable1 f => Hashable ( Fix f) Source #
Instance details Defined in Data.Fix Methods hashWithSalt :: Int -> Fix f -> Int Source # hash :: Fix f -> Int Source #
type Rep ( Fix f) Source #
Instance details Defined in Data.Fix type Rep ( Fix f) = D1 (' MetaData "Fix" "Data.Fix" "data-fix-0.3.2-LpD4EKXxVVUJR8w9NGWPdd" ' True ) ( C1 (' MetaCons "Fix" ' PrefixI ' True ) ( S1 (' MetaSel (' Just "unFix") ' NoSourceUnpackedness ' NoSourceStrictness ' DecidedLazy ) ( Rec0 (f ( Fix f)))))

hoistFix :: Functor f => ( forall a. f a -> g a) -> Fix f -> Fix g Source #

Change base functor in Fix .

hoistFix' :: Functor g => ( forall a. f a -> g a) -> Fix f -> Fix g Source #

Like hoistFix but fmap ping over g .

foldFix :: Functor f => (f a -> a) -> Fix f -> a Source #

Fold Fix .

>>> let fp = unfoldFix (\i -> if i < 4 then Cons i (i + 1) else Nil) (0 :: Int)
>>> foldFix (elimListF 0 (+)) fp
6

unfoldFix :: Functor f => (a -> f a) -> a -> Fix f Source #

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

wrapFix :: f ( Fix f) -> Fix f Source #

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

Since: 0.3.2

unwrapFix :: Fix f -> f ( Fix f) Source #

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

Since: 0.3.2

Mu - least fixed point

newtype Mu f Source #

Least fixed point. Efficient folding.

Constructors

Mu
Fields unMu :: forall a. (f a -> a) -> a

Instances

Instances details

( Functor f, Eq1 f) => Eq ( Mu f) Source #
Instance details Defined in Data.Fix Methods (==) :: Mu f -> Mu f -> Bool Source # (/=) :: Mu f -> Mu f -> Bool Source #
( Functor f, Ord1 f) => Ord ( Mu f) Source #
Instance details Defined in Data.Fix Methods compare :: Mu f -> Mu f -> Ordering Source # (<) :: Mu f -> Mu f -> Bool Source # (<=) :: Mu f -> Mu f -> Bool Source # (>) :: Mu f -> Mu f -> Bool Source # (>=) :: Mu f -> Mu f -> Bool Source # max :: Mu f -> Mu f -> Mu f Source # min :: Mu f -> Mu f -> Mu f Source #
( Functor f, Read1 f) => Read ( Mu f) Source #
Instance details Defined in Data.Fix Methods readsPrec :: Int -> ReadS ( Mu f) Source # readList :: ReadS [ Mu f] Source # readPrec :: ReadPrec ( Mu f) Source # readListPrec :: ReadPrec [ Mu f] Source #
( Functor f, Show1 f) => Show ( Mu f) Source #
Instance details Defined in Data.Fix Methods showsPrec :: Int -> Mu f -> ShowS Source # show :: Mu f -> String Source # showList :: [ Mu f] -> ShowS Source #

hoistMu :: ( forall a. f a -> g a) -> Mu f -> Mu g Source #

Change base functor in Mu .

foldMu :: (f a -> a) -> Mu f -> a Source #

Fold Mu .

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

unfoldMu :: Functor f => (a -> f a) -> a -> Mu f Source #

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

wrapMu :: Functor f => f ( Mu f) -> Mu f Source #

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

Since: 0.3.2

unwrapMu :: Functor f => Mu f -> f ( Mu f) Source #

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

Since: 0.3.2

Nu - greatest fixed point

data Nu f Source #

Greatest fixed point. Efficient unfolding.

Constructors

forall a. Nu (a -> f a) a

Instances

Instances details

( Functor f, Eq1 f) => Eq ( Nu f) Source #
Instance details Defined in Data.Fix Methods (==) :: Nu f -> Nu f -> Bool Source # (/=) :: Nu f -> Nu f -> Bool Source #
( Functor f, Ord1 f) => Ord ( Nu f) Source #
Instance details Defined in Data.Fix Methods compare :: Nu f -> Nu f -> Ordering Source # (<) :: Nu f -> Nu f -> Bool Source # (<=) :: Nu f -> Nu f -> Bool Source # (>) :: Nu f -> Nu f -> Bool Source # (>=) :: Nu f -> Nu f -> Bool Source # max :: Nu f -> Nu f -> Nu f Source # min :: Nu f -> Nu f -> Nu f Source #
( Functor f, Read1 f) => Read ( Nu f) Source #
Instance details Defined in Data.Fix Methods readsPrec :: Int -> ReadS ( Nu f) Source # readList :: ReadS [ Nu f] Source # readPrec :: ReadPrec ( Nu f) Source # readListPrec :: ReadPrec [ Nu f] Source #
( Functor f, Show1 f) => Show ( Nu f) Source #
Instance details Defined in Data.Fix Methods showsPrec :: Int -> Nu f -> ShowS Source # show :: Nu f -> String Source # showList :: [ Nu f] -> ShowS Source #

hoistNu :: ( forall a. f a -> g a) -> Nu f -> Nu g Source #

Change base functor in Nu .

foldNu :: Functor f => (f a -> a) -> Nu f -> a Source #

Fold Nu .

>>> let nu = unfoldNu (\i -> if i < 4 then Cons i (i + 1) else Nil) (0 :: Int)
>>> foldNu (elimListF 0 (+)) nu
6

unfoldNu :: (a -> f a) -> a -> Nu f Source #

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

wrapNu :: Functor f => f ( Nu f) -> Nu f Source #

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

Since: 0.3.2

unwrapNu :: Functor f => Nu f -> f ( Nu f) Source #

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

Since: 0.3.2

Refolding

refold :: Functor f => (f b -> b) -> (a -> f a) -> a -> b Source #

Refold one recursive type into another, one layer at the time.

Monadic variants

foldFixM :: ( Monad m, Traversable t) => (t a -> m a) -> Fix t -> m a Source #

Monadic foldFix .

unfoldFixM :: ( Monad m, Traversable t) => (a -> m (t a)) -> a -> m ( Fix t) Source #

Monadic anamorphism.

refoldM :: ( Monad m, Traversable t) => (t b -> m b) -> (a -> m (t a)) -> a -> m b Source #

Monadic hylomorphism.

Deprecated aliases

cata :: Functor f => (f a -> a) -> Fix f -> a Source #

Deprecated: Use foldFix

Catamorphism or generic function fold.

ana :: Functor f => (a -> f a) -> a -> Fix f Source #

Deprecated: Use unfoldFix

Anamorphism or generic function unfold.

hylo :: Functor f => (f b -> b) -> (a -> f a) -> a -> b Source #

Deprecated: Use refold

Hylomorphism is anamorphism followed by catamorphism.

cataM :: ( Monad m, Traversable t) => (t a -> m a) -> Fix t -> m a Source #

Deprecated: Use foldFixM

Monadic catamorphism.

anaM :: ( Monad m, Traversable t) => (a -> m (t a)) -> a -> m ( Fix t) Source #

Deprecated: Use unfoldFixM

Monadic anamorphism.

hyloM :: ( Monad m, Traversable t) => (t b -> m b) -> (a -> m (t a)) -> a -> m b Source #

Deprecated: Use refoldM

Monadic hylomorphism.