data-fix-0.3.2: Fixpoint data types

Data.Fix

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

# Fix

newtype Fix f Source #

A fix-point type.

Constructors

 Fix FieldsunFix :: f (Fix f)

#### Instances

Instances details

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 fmapping 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 FieldsunMu :: forall a. (f a -> a) -> a

#### Instances

Instances details
 (Functor f, Eq1 f) => Eq (Mu f) Source # Instance detailsDefined in Data.Fix Methods(==) :: Mu f -> Mu f -> Bool #(/=) :: Mu f -> Mu f -> Bool # (Functor f, Ord1 f) => Ord (Mu f) Source # Instance detailsDefined in Data.Fix Methodscompare :: 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) Source # Instance detailsDefined in Data.Fix MethodsreadsPrec :: Int -> ReadS (Mu f) #readList :: ReadS [Mu f] #readPrec :: ReadPrec (Mu f) # (Functor f, Show1 f) => Show (Mu f) Source # Instance detailsDefined in Data.Fix MethodsshowsPrec :: Int -> Mu f -> ShowS #show :: Mu f -> String #showList :: [Mu f] -> ShowS #

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 detailsDefined in Data.Fix Methods(==) :: Nu f -> Nu f -> Bool #(/=) :: Nu f -> Nu f -> Bool # (Functor f, Ord1 f) => Ord (Nu f) Source # Instance detailsDefined in Data.Fix Methodscompare :: 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) Source # Instance detailsDefined in Data.Fix MethodsreadsPrec :: Int -> ReadS (Nu f) #readList :: ReadS [Nu f] #readPrec :: ReadPrec (Nu f) # (Functor f, Show1 f) => Show (Nu f) Source # Instance detailsDefined in Data.Fix MethodsshowsPrec :: Int -> Nu f -> ShowS #show :: Nu f -> String #showList :: [Nu f] -> ShowS #

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.

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 #

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

# 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