|
Data.Relation.MapFromPairs | Portability | portable | Stability | experimental | Maintainer | joost.visser@di.uminho.pt |
|
|
|
|
|
Description |
An implementation of labeled relations as map from pairs to values.
|
|
Synopsis |
|
type LRel a b c = Map (a, b) c | | rel :: (Ord a, Ord b) => (c -> Bool) -> LRel a b c -> Rel a b | | lrel :: (Ord a, Ord b) => c -> Rel a b -> LRel a b c | | entities :: Ord a => LRel a a c -> Set a | | labels :: (Ord a, Ord b, Ord c) => LRel a b c -> Set c | | extremal :: Ord a => b -> (b -> b -> b) -> (b -> b -> b) -> LRel a a b -> LRel a a b | | reach :: Ord a => LRel a a Bool -> LRel a a Bool | | leastcost :: (Num cost, Ord cost, Ord a) => cost -> LRel a a cost -> LRel a a cost | | worstcost :: (Ord a, Num cost, Ord cost) => cost -> LRel a a cost -> LRel a a cost | | bottleneck :: (Ord height, Num height, Ord a) => LRel a a height -> LRel a a height | | leastcost' :: (Num cost, Ord cost, Bounded cost, Ord a) => LRel a a cost -> LRel a a cost | | height :: Ord a => Rel a a -> Integer |
|
|
|
Representation
|
|
type LRel a b c = Map (a, b) c |
The type of labeled relations.
|
|
rel |
:: (Ord a, Ord b) | | => (c -> Bool) | Predicate on labels.
| -> LRel a b c | | -> Rel a b | | Convert labeled relation to one without labels. The first argument
is a predicate that determines, based on the label, which pairs are
to be included in the result relation.
|
|
|
lrel |
:: (Ord a, Ord b) | | => c | Initialization label
| -> Rel a b | | -> LRel a b c | | Convert relation to a labeled one. The first argument is the
label with which all pairs in the result relation will be labeled.
|
|
|
entities :: Ord a => LRel a a c -> Set a |
Carrier set.
|
|
labels :: (Ord a, Ord b, Ord c) => LRel a b c -> Set c |
Label set.
|
|
Extremal paths.
|
|
extremal |
:: Ord a | | => b | Zero of multiplication.
| -> (b -> b -> b) | Multiplication.
| -> (b -> b -> b) | Addition.
| -> LRel a a b | | -> LRel a a b | | Generic extremal path algorithm, based on Roland Backhouse's
lecture notes, page 192 (draft version).
|
|
|
reach :: Ord a => LRel a a Bool -> LRel a a Bool |
Reachability. This is transitive closure following Roy-Warshall.
|
|
leastcost |
:: (Num cost, Ord cost, Ord a) | | => cost | Maximum bound.
| -> LRel a a cost | Cost labels must be non-negative.
| -> LRel a a cost | | Least cost, or shortest path.
|
|
|
worstcost :: (Ord a, Num cost, Ord cost) => cost -> LRel a a cost -> LRel a a cost |
Worst cost, or longest path. UNTESTED.
|
|
bottleneck |
:: (Ord height, Num height, Ord a) | | => LRel a a height | Height labels must be non-negative.
| -> LRel a a height | | Bottle neck.
|
|
|
leastcost' :: (Num cost, Ord cost, Bounded cost, Ord a) => LRel a a cost -> LRel a a cost |
Least cost, or shortest path. DOES NOT WORK, because it relies on
maxBound from the Bounded class, leading to erroneous arithmetic.
|
|
height :: Ord a => Rel a a -> Integer |
Not quite right when cycles are present.
|
|
Produced by Haddock version 0.7 |