Safe Haskell | None |
---|---|

Language | Haskell2010 |

A vague analog of free monads for invariant monoidals. This can provide a simple basis for things like invertible parsers.

## Synopsis

- data Free f a where
- showsFree :: (forall a'. f a' -> ShowS) -> Free f a -> ShowS
- mapFree :: (forall a'. f a' -> m a') -> Free f a -> Free m a
- foldFree :: Monoid b => (forall a'. f a' -> a' -> b) -> Free f a -> a -> b
- produceFree :: Alternative m => (forall a'. f a' -> a' -> b) -> Free f a -> a -> m b
- runFree :: Alternative f => Free f a -> f a
- parseFree :: MonadPlus m => (forall a'. f a' -> b -> m a') -> Free f a -> [b] -> m (a, [b])
- reverseFree :: Free f a -> Free f a
- freeTNF :: Free f a -> Free f a
- freeTDNF :: Free f a -> Free f a
- sortFreeTDNF :: (forall a' b'. f a' -> f b' -> Ordering) -> Free f a -> Free f a

# Documentation

Produce a `MonoidalAlt`

out of any type constructor, simply by converting each monoidal operation into a constructor.
Although a version more analogous to a free monad could be defined for instances of `Functor`

and restricted to `Monoidal`

, including the Yoneda transform makes this the more general case.

Void :: Free f Void | |

Empty :: Free f () | |

Free :: !(f a) -> Free f a | |

Join :: Free f a -> Free f b -> Free f (a, b) | |

Choose :: Free f a -> Free f b -> Free f (Either a b) | |

Transform :: (a <-> b) -> Free f a -> Free f b |

showsFree :: (forall a'. f a' -> ShowS) -> Free f a -> ShowS Source #

Construct a string representation of a `Free`

structure, given a way to show any `f a`

.

mapFree :: (forall a'. f a' -> m a') -> Free f a -> Free m a Source #

Transform the type constructor within a `Free`

.

produceFree :: Alternative m => (forall a'. f a' -> a' -> b) -> Free f a -> a -> m b Source #

`foldFree`

over Alternative rather than Monoid.

runFree :: Alternative f => Free f a -> f a Source #

Evaluate a `Free`

into an underlying `Alternative`

, by evaluating `>|<`

with `<|>`

.

parseFree :: MonadPlus m => (forall a'. f a' -> b -> m a') -> Free f a -> [b] -> m (a, [b]) Source #

Given a way to convert `b`

elements into any `f a`

, use a `Free`

to parse a list of `b`

elements into a value.
This just uses `unconsState`

with `runFree`

, and is the inverse of `produceFree`

, provided the given conversions are themselves inverses.

reverseFree :: Free f a -> Free f a Source #

freeTDNF :: Free f a -> Free f a Source #

Convert a `Free`

to Transform Disjunctive Normal Form: reorder the terms so thet at most one `Transform`

is on the outside, followed by `Choose`

terms, which are above all `Join`

terms', with `Empty`

and `Free`

as leaves.
Since each `Join`

above a `Choose`

creates a duplicate `Join`

term, the complexity and result size can be exponential (just as with boolean logic DNF).