| Safe Haskell | None |
|---|---|
| Language | Haskell98 |
TreeShapedOrder
Synopsis
- newtype TSO a = TSO {}
- empty :: TSO a
- insert :: (Ord a, Eq a) => a -> (Int, a) -> TSO a -> TSO a
- fromList :: (Ord a, Eq a) => [(a, (Int, a))] -> TSO a
- parents :: (Ord a, Eq a) => a -> TSO a -> [(Int, a)]
- parent :: (Ord a, Eq a) => a -> TSO a -> Maybe (Int, a)
- isAncestor :: (Ord a, Eq a) => a -> a -> TSO a -> Maybe Int
- diff :: (Ord a, Eq a) => a -> a -> TSO a -> Maybe Int
- invert :: (Ord a, Eq a) => TSO a -> Map a [(Int, a)]
- height :: (Ord a, Eq a) => a -> TSO a -> Maybe Int
- increasesHeight :: (Ord a, Eq a) => a -> (Int, a) -> TSO a -> Bool
- leaves :: (Ord a, Eq a) => TSO a -> [a]
- pathesToForest :: (Ord a, Eq a) => [[(Int, a)]] -> Forest (Int, a)
- toForest :: (Ord a, Eq a) => TSO a -> Forest (Int, a)
- l1 :: [(String, (Int, String))]
- o1 :: TSO String
- t1 :: Maybe Int
- t2 :: Maybe Int
- t3 :: Maybe Int
- t4 :: Maybe Int
- t5 :: Maybe Int
Documentation
Tree-structured partial orders. Represented as maps from children to parents plus a non-negative distance.
insert :: (Ord a, Eq a) => a -> (Int, a) -> TSO a -> TSO a Source #
insert a b o inserts a with parent b into order o.
It does not check whether the tree structure is preserved.
fromList :: (Ord a, Eq a) => [(a, (Int, a))] -> TSO a Source #
Construction from a list of child-distance-parent tuples.
parents :: (Ord a, Eq a) => a -> TSO a -> [(Int, a)] Source #
parents a0 o = [(d1,a1),..,(dn,an)] lists the parents of a0 in order,
i.e., a(i+1) is parent of a(i) with distance d(i+1).
parent :: (Ord a, Eq a) => a -> TSO a -> Maybe (Int, a) Source #
parent a o returns the immediate parent, if it exists.
isAncestor :: (Ord a, Eq a) => a -> a -> TSO a -> Maybe Int Source #
isAncestor a b o = Just n if there are n steps up from a to b.
diff :: (Ord a, Eq a) => a -> a -> TSO a -> Maybe Int Source #
diff a b o = Just k if there are k steps up from a to b
or (-k) steps down from b to a.
invert :: (Ord a, Eq a) => TSO a -> Map a [(Int, a)] Source #
create a map from parents to list of sons, leaves have an empty list
height :: (Ord a, Eq a) => a -> TSO a -> Maybe Int Source #
height a t = Just k if $k$ is the length of the
longest path from a to a leaf. Nothing if a not in t.
increasesHeight :: (Ord a, Eq a) => a -> (Int, a) -> TSO a -> Bool Source #
increasesHeight a (n,b) t = True if n > height b t, i.e., if
the insertion of a with parent b will destroy an existing
minimal valuation of t