Copyright | (c) 2014 Patrick Bahr Emil Axelsson |
---|---|

License | BSD3 |

Maintainer | Patrick Bahr <paba@di.ku.dk> |

Stability | experimental |

Portability | non-portable (GHC Extensions) |

Safe Haskell | None |

Language | Haskell98 |

This module implements a representation of directed acyclic graphs
(DAGs) as compact representations of trees (or `Term`

s).

## Synopsis

- data Dag f
- termTree :: Functor f => Term f -> Dag f
- reifyDag :: Traversable f => Term f -> IO (Dag f)
- unravel :: forall f. Functor f => Dag f -> Term f
- bisim :: forall f. (EqF f, Functor f, Foldable f) => Dag f -> Dag f -> Bool
- iso :: (Traversable f, Foldable f, EqF f) => Dag f -> Dag f -> Bool
- strongIso :: (Functor f, Foldable f, EqF f) => Dag f -> Dag f -> Bool

# Documentation

reifyDag :: Traversable f => Term f -> IO (Dag f) Source #

This function takes a term, and returns a `Dag`

with the implicit
sharing of the input data structure made explicit. If the sharing
structure of the term is cyclic an exception of type
`CyclicException`

is thrown.

unravel :: forall f. Functor f => Dag f -> Term f Source #

This function unravels a given graph to the term it represents.

bisim :: forall f. (EqF f, Functor f, Foldable f) => Dag f -> Dag f -> Bool Source #

Checks whether two dags are bisimilar. In particular, we have the following equality

bisim g1 g2 = (unravel g1 == unravel g2)

That is, two dags are bisimilar iff they have the same unravelling.

iso :: (Traversable f, Foldable f, EqF f) => Dag f -> Dag f -> Bool Source #

Checks whether the two given DAGs are isomorphic.

strongIso :: (Functor f, Foldable f, EqF f) => Dag f -> Dag f -> Bool Source #

Checks whether the two given DAGs are strongly isomorphic, i.e. their internal representation is the same modulo renaming of nodes.