Copyright	(c) Alexandre Moine 2019
Maintainer	alexandre@moine.me
Stability	experimental
Safe Haskell	None
Language	Haskell2010

Tungsten.Fix

Contents

The fixed-point operator
Recursion-schemes
Tools for rewriting

Description

This module provides the Fix operator which can be used to define fixed-point structures (see examples in Tungsten.Structure.List, Tungsten.Structure.Tree ord Tungsten.Structure.Graph).

Defining a type in term of Fix gives access to cata and buildR and the "cata/buildR" rewrite rule (see comment for buildR for how to use it).

To use efficiently this module, compile with rewrite rules enabled and the -fspec-constr flag.

A part of this module was inspired by the Data.Functor.Foldable module from the recursion-schemes package.

Synopsis

newtype Fix f = Fix (f (Fix f))
fix :: f (Fix f) -> Fix f
unfix :: Fix f -> f (Fix f)
cata :: Functor f => (f a -> a) -> Fix f -> a
para :: Functor f => (f (Fix f, a) -> a) -> Fix f -> a
ana :: Functor f => (a -> f a) -> a -> Fix f
apo :: Functor f => (a -> f (Either (Fix f) a)) -> a -> Fix f
hylo :: Functor f => (f b -> b) -> (a -> f a) -> a -> b
type Cata f = forall a. (f a -> a) -> a
buildR :: Cata f -> Fix f

The fixed-point operator

newtype Fix f Source #

Operator to define fixed-point types.

Constructors

Fix (f (Fix f))

Instances

Eq1 f => Eq (Fix f) Source #
Instance details Defined in Tungsten.Fix Methods (==) :: Fix f -> Fix f -> Bool # (/=) :: Fix f -> Fix f -> Bool #
Ord1 f => Ord (Fix f) Source #
Instance details Defined in Tungsten.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) Source #
Instance details Defined in Tungsten.Fix Methods readsPrec :: Int -> ReadS (Fix f) # readList :: ReadS [Fix f] # readPrec :: ReadPrec (Fix f) # readListPrec :: ReadPrec [Fix f] #
(Functor f, Show1 f) => Show (Fix f) Source #	`show` is a good consumer.
Instance details Defined in Tungsten.Fix Methods showsPrec :: Int -> Fix f -> ShowS # show :: Fix f -> String # showList :: [Fix f] -> ShowS #

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

A synonym for Fix.

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

Remove one level of fixed-point.

Recursion-schemes

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

Catamorphism. Functions defined in terms of cata (or "good consumers") are subject to fusion with functions exprimed in terms of buildR (or "good producers").

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

Paramorphism. Functions defined in terms of para are not subject to fusion.

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

Anamorphism. Defined in terms of buildR, so subject to fusion with cata.

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

Apomorphism. Functions defined in terms of apo are not subject to fusion.

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

Hylomorphism.

hylo f g == cata f . ana g

Tools for rewriting

type Cata f = forall a. (f a -> a) -> a Source #

Type of arguments of buildR.

buildR :: Cata f -> Fix f Source #

buildR abstracts the build of a structure with respect to the fixed-point combinator, such that we have the following rewrite rule (named "cata/buildR"):

cata f (buildR g) = g f

When firing, this remove the build of an intermediate structure. A function expressed with buildR is called a good producer.

Note 1. Without rewriting, buildR is just:

buildR g = g Fix

Note 2. The validity of the "cata/buildR" rule is guaranteed by free theorems of Wadler. They are known to fail in presence of seq and undefined, be careful.

Note 3. If g = cata and a rewriting did not happen, then the "cata/id" rule will replace the cata Fix obtained with the inlining of buildR by id.