Data.Fix

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.

Fix

newtype Fix f

A fix-point type.

Constructors

Fix

Fields

• unFix :: f (Fix f)

Instances

Eq1 f => Eq (Fix f)

Defined in Data.Fix

Methods

(==) :: Fix f -> Fix f -> Bool

(/=) :: Fix f -> Fix f -> Bool

(Typeable f, Data (f (Fix f))) => Data (Fix f)

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)

gunfold :: (forall b r. Data b => c (b -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c (Fix f)

toConstr :: Fix f -> Constr

dataTypeOf :: Fix f -> DataType

dataCast1 :: Typeable t => (forall d. Data d => c (t d)) -> Maybe (c (Fix f))

dataCast2 :: Typeable t => (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c (Fix f))

gmapT :: (forall b. Data b => b -> b) -> Fix f -> Fix f

gmapQl :: (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> Fix f -> r

gmapQr :: forall r r'. (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> Fix f -> r

gmapQ :: (forall d. Data d => d -> u) -> Fix f -> [u]

gmapQi :: Int -> (forall d. Data d => d -> u) -> Fix f -> u

gmapM :: Monad m => (forall d. Data d => d -> m d) -> Fix f -> m (Fix f)

gmapMp :: MonadPlus m => (forall d. Data d => d -> m d) -> Fix f -> m (Fix f)

gmapMo :: MonadPlus m => (forall d. Data d => d -> m d) -> Fix f -> m (Fix f)

Ord1 f => Ord (Fix f)

Defined in Data.Fix

Methods

compare :: Fix f -> Fix f -> Ordering

(<) :: Fix f -> Fix f -> Bool

(<=) :: Fix f -> Fix f -> Bool

(>) :: Fix f -> Fix f -> Bool

(>=) :: Fix f -> Fix f -> Bool

max :: Fix f -> Fix f -> Fix f

min :: Fix f -> Fix f -> Fix f

Read1 f => Read (Fix f)

Defined in Data.Fix

Methods

readsPrec :: Int -> ReadS (Fix f)

readList :: ReadS [Fix f]

readPrec :: ReadPrec (Fix f)

readListPrec :: ReadPrec [Fix f]

Show1 f => Show (Fix f)

Defined in Data.Fix

Methods

showsPrec :: Int -> Fix f -> ShowS

show :: Fix f -> String

showList :: [Fix f] -> ShowS

Generic (Fix f)

Defined in Data.Fix

Associated Types

type Rep (Fix f) :: Type -> Type

Methods

from :: Fix f -> Rep (Fix f) x

to :: Rep (Fix f) x -> Fix f

NFData1 f => NFData (Fix f)

Defined in Data.Fix

Methods

rnf :: Fix f -> ()

Hashable1 f => Hashable (Fix f)

Defined in Data.Fix

Methods

hashWithSalt :: Int -> Fix f -> Int

hash :: Fix f -> Int

type Rep (Fix f)

Defined in Data.Fix

type Rep (Fix f) = D1 ('MetaData "Fix" "Data.Fix" "data-fix-0.3.2-6AFfWRuoaaT2TCICN3gbwV" '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

Change base functor in Fix.

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

Like hoistFix but fmapping over g.

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

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

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

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)

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

Least fixed point. Efficient folding.

Constructors

Mu

Fields

• unMu :: forall a. (f a -> a) -> a

Instances

(Functor f, Eq1 f) => Eq (Mu f)

Defined in Data.Fix

Methods

(==) :: Mu f -> Mu f -> Bool

(/=) :: Mu f -> Mu f -> Bool

(Functor f, Ord1 f) => Ord (Mu f)

Defined in Data.Fix

Methods

compare :: Mu f -> Mu f -> Ordering

(<) :: Mu f -> Mu f -> Bool

(<=) :: Mu f -> Mu f -> Bool

(>) :: Mu f -> Mu f -> Bool

(>=) :: Mu f -> Mu f -> Bool

max :: Mu f -> Mu f -> Mu f

min :: Mu f -> Mu f -> Mu f

(Functor f, Read1 f) => Read (Mu f)

Defined in Data.Fix

Methods

readsPrec :: Int -> ReadS (Mu f)

readList :: ReadS [Mu f]

readPrec :: ReadPrec (Mu f)

readListPrec :: ReadPrec [Mu f]

(Functor f, Show1 f) => Show (Mu f)

Defined in Data.Fix

Methods

showsPrec :: Int -> Mu f -> ShowS

show :: Mu f -> String

showList :: [Mu f] -> ShowS

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

Change base functor in Mu.

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

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

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

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)

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

Greatest fixed point. Efficient unfolding.

Constructors

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

Instances

(Functor f, Eq1 f) => Eq (Nu f)

Defined in Data.Fix

Methods

(==) :: Nu f -> Nu f -> Bool

(/=) :: Nu f -> Nu f -> Bool

(Functor f, Ord1 f) => Ord (Nu f)

Defined in Data.Fix

Methods

compare :: Nu f -> Nu f -> Ordering

(<) :: Nu f -> Nu f -> Bool

(<=) :: Nu f -> Nu f -> Bool

(>) :: Nu f -> Nu f -> Bool

(>=) :: Nu f -> Nu f -> Bool

max :: Nu f -> Nu f -> Nu f

min :: Nu f -> Nu f -> Nu f

(Functor f, Read1 f) => Read (Nu f)

Defined in Data.Fix

Methods

readsPrec :: Int -> ReadS (Nu f)

readList :: ReadS [Nu f]

readPrec :: ReadPrec (Nu f)

readListPrec :: ReadPrec [Nu f]

(Functor f, Show1 f) => Show (Nu f)

Defined in Data.Fix

Methods

showsPrec :: Int -> Nu f -> ShowS

show :: Nu f -> String

showList :: [Nu f] -> ShowS

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

Change base functor in Nu.

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

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

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

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)

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

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

Monadic foldFix.

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

Monadic anamorphism.

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

Monadic hylomorphism.

Deprecated aliases

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

Deprecated: Use foldFix

Catamorphism or generic function fold.

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

Deprecated: Use unfoldFix

Anamorphism or generic function unfold.

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

Deprecated: Use refold

Hylomorphism is anamorphism followed by catamorphism.

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

Deprecated: Use foldFixM

Monadic catamorphism.

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

Deprecated: Use unfoldFixM

Monadic anamorphism.

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

Deprecated: Use refoldM

Monadic hylomorphism.