Data.Functor.Fixedpoint

This module provides a backwards compatibility shim for users of older versions of unification-fd, before we switched over to using data-fix. New users should prefer calling data-fix functions directly, whenever possible. If you use any of the functions that aren't deprecated (hoistFixM, ymap, ymapM, ycata, ycataM, build), please let the maintainer know, so she can focus on getting those incorporated into data-fix. Returning users should beware that this module used to provide rewrite rules for fusing redundant traversals of data structures (which data-fix does not). If you notice version >=0.12.0 introducing any performance loss compared to earlier versions, please let the maintainer know, so she can focus on getting those incorporated into data-fix.

This abstract nonsense is helpful in conjunction with other category theoretic tricks like Swierstra's functor coproducts (not provided by this package). For more on the utility of two-level recursive types, see:

• Tim Sheard (2001) Generic Unification via Two-Level Types and Parameterized Modules, Functional Pearl, ICFP.
• Tim Sheard & Emir Pasalic (2004) Two-Level Types and Parameterized Modules. JFP 14(5): 547--587. This is an expanded version of Sheard (2001) with new examples.
• Wouter Swierstra (2008) Data types a la carte, Functional Pearl. JFP 18: 423--436.

Fixed point operator for functors

newtype Fix (f :: Type -> Type)

A fix-point type.

Constructors

Fix

Fields

• unFix :: f (Fix f)

Instances

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

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

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

NFData1 f => NFData (Fix f)

Defined in Data.Fix

Methods

rnf :: Fix f -> ()

Eq1 f => Eq (Fix f)

Defined in Data.Fix

Methods

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

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

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

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.4-K7JE0OEEv4j2xBAazQ5HZv" 'True) (C1 ('MetaCons "Fix" 'PrefixI 'True) (S1 ('MetaSel ('Just "unFix") 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 (f (Fix f)))))

Maps

hmap :: (Functor f, Functor g) => (forall a. f a -> g a) -> Fix f -> Fix g

Deprecated: Use Data.Fix.hoistFix'

A higher-order map taking a natural transformation (f -> g) and lifting it to operate on Fix.

NOTE: The implementation of hmap prior to version 0.12 was based on ana, and therefore most closely matches the behavior of hoistFix'. However, this definition is extensionally equivalent to an implementation using cata (and therefore most closely matches the behavior of hoistFix) instead.

hmapM :: (Functor f, Traversable g, Monad m) => (forall a. f a -> m (g a)) -> Fix f -> m (Fix g)

Deprecated: Use hoistFixM'

A monadic variant of hmap.

hoistFixM' :: (Functor f, Traversable g, Monad m) => (forall a. f a -> m (g a)) -> Fix f -> m (Fix g)

A monadic variant of hoistFix'.

NOTE: The implementation of hmapM prior to version 0.12 was based on anaM, and therefore most closely matches the behavior of unfoldFixM. However, there is another function of the same type which is instead implemented via cataM, which has different semantics for many monads.

ymap :: Functor f => (Fix f -> Fix f) -> Fix f -> Fix f

A version of fmap for endomorphisms on the fixed point. That is, this maps the function over the first layer of recursive structure.

ymapM :: (Traversable f, Monad m) => (Fix f -> m (Fix f)) -> Fix f -> m (Fix f)

A monadic variant of ymap.

Builders

build :: Functor f => (forall r. (f r -> r) -> r) -> Fix f

Take a Church encoding of a fixed point into the data representation of the fixed point.

Catamorphisms

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

Deprecated: Use Data.Fix.foldFix

A pure catamorphism over the least fixed point of a functor. This function applies the f-algebra from the bottom up over Fix f to create some residual value.

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

Deprecated: Use Data.Fix.foldFixM

A catamorphism for monadic f-algebras. Alas, this isn't wholly generic to Functor since it requires distribution of f over m (provided by sequence or mapM in Traversable).

N.B., this orders the side effects from the bottom up.

ycata :: Functor f => (Fix f -> Fix f) -> Fix f -> Fix f

A variant of cata which restricts the return type to being a new fixpoint. Though more restrictive, it can be helpful when you already have an algebra which expects the outermost Fix.

If you don't like either fmap or cata, then maybe this is what you were thinking?

ycataM :: (Traversable f, Monad m) => (Fix f -> m (Fix f)) -> Fix f -> m (Fix f)

Monadic variant of ycata.

Anamorphisms

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

Deprecated: Use Data.Fix.unfoldFix

A pure anamorphism generating the greatest fixed point of a functor. This function applies an f-coalgebra from the top down to expand a seed into a Fix f.

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

Deprecated: Use Data.Fix.unfoldFixM

An anamorphism for monadic f-coalgebras. Alas, this isn't wholly generic to Functor since it requires distribution of f over m (provided by sequence or mapM in Traversable).

N.B., this orders the side effects from the top down.

Hylomorphisms

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

Deprecated: Use Data.Fix.refold

hylo phi psi == cata phi . ana psi

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

Deprecated: Use Data.Fix.refoldM

hyloM phiM psiM == cataM phiM <=< anaM psiM