Safe Haskell	Safe
Language	Haskell2010

Data.Fix

Contents

Simple recursion
Monadic recursion

Description

Fix-point type. It allows to define generic recursion schemes.

Fix f = f (Fix f)

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.

Little example:

type List a = Fix (L a)

data L a b = Nil | Cons a b

instance Functor (L a) where
   fmap f x = case x of
       Nil      -> Nil
       Cons a b -> Cons a (f b)

length :: List a -> Int
length = cata $ \x -> case x of
   Nil      -> 0
   Cons _ n -> n + 1

sum :: Num a => List a -> a
sum = cata $ \x -> case x of
   Nil      -> 0
   Cons a s -> a + s

Synopsis

newtype Fix f = Fix {
- unFix :: f (Fix f)
}
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
(~>) :: Functor f => (a -> f a) -> (f b -> b) -> a -> b
cataM :: (Applicative m, Monad m, Traversable t) => (t a -> m a) -> Fix t -> m a
anaM :: (Applicative m, Monad m, Traversable t) => (a -> m (t a)) -> a -> m (Fix t)
hyloM :: (Applicative m, Monad m, Traversable t) => (t b -> m b) -> (a -> m (t a)) -> a -> m b

Documentation

newtype Fix f Source #

A fix-point type.

Constructors

Fix
Fields unFix :: f (Fix f)

Instances

Eq (f (Fix f)) => Eq (Fix f) Source #
Instance details Defined in Data.Fix Methods (==) :: Fix f -> Fix f -> Bool # (/=) :: Fix f -> Fix f -> Bool #
(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) # 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 :: (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) #
Ord (f (Fix f)) => Ord (Fix f) Source #
Instance details 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 #
Read (f (Fix f)) => Read (Fix f) Source #
Instance details Defined in Data.Fix Methods readsPrec :: Int -> ReadS (Fix f) # readList :: ReadS [Fix f] # readPrec :: ReadPrec (Fix f) # readListPrec :: ReadPrec [Fix f] #
Show (f (Fix f)) => Show (Fix f) Source #
Instance details Defined in Data.Fix Methods showsPrec :: Int -> Fix f -> ShowS # show :: Fix f -> String # showList :: [Fix f] -> ShowS #
Generic (Fix f) Source #
Instance details 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 #
type Rep (Fix f) Source #
Instance details Defined in Data.Fix type Rep (Fix f) = D1 (MetaData "Fix" "Data.Fix" "data-fix-0.2.1-DMgQ7LCHzUM8GYJtw0mzwV" True) (C1 (MetaCons "Fix" PrefixI True) (S1 (MetaSel (Just "unFix") NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 (f (Fix f)))))

Simple recursion

Type f should be a Functor. They transform non-recursive functions to recursive ones.

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

Catamorphism or generic function fold.

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

Anamorphism or generic function unfold.

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

Hylomorphism is anamorphism followed by catamorphism.

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

Infix version of hylo.

Monadic recursion

Type f should be a Traversable.

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

Monadic catamorphism.

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

Monadic anamorphism.

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

Monadic hylomorphism.