data-named 0.1.0 → 0.2.0

raw patch · 4 files changed

+158/−53 lines, 4 filesPVP ok

version bump matches the API change (PVP)

API changes (from Hackage documentation)

Files

• Data/Named/Graph.hs +42/−48
• Data/Named/Tree.hs +110/−0
• Text/Named/Enamex.hs +2/−2
• data-named.cabal +4/−3

@@ -1,3 +1,5 @@+{-# LANGUAGE DoAndIfThenElse #-}+ -- | Implementation of a graph with each node identified by a unique key. -- It is a provisional module and it might be replaced by the standard -- graph from containers package in the future.@@ -8,19 +10,15 @@ , node , edges , roots-, toTree-, toKeyTree-, toForestWith-, toForest+, disjointForest ) where  import qualified Data.Set as S import qualified Data.Map as M import qualified Data.Tree as T-import Data.List (mapAccumL, foldl', sortBy)-import Data.Maybe (mapMaybe, fromJust)-import Data.Ord (comparing) +import Data.Named.Tree+ -- | A graph. data Graph k v = Graph     { nodeMap :: M.Map k v@@ -51,49 +49,45 @@ -- | Return all graph roots (i.e. nodes with no parents). roots :: Ord k => Graph k v -> [k] roots g =-    [ k-    | (k, _) <- M.assocs (nodeMap g)-    , not (k `S.member` desc) ]-  where-    desc = S.fromList . concat . M.elems $ edgeMap g+    let desc = S.fromList . concat . M.elems $ edgeMap g+    in  [k | (k, _) <- M.assocs (nodeMap g), not (k `S.member` desc)] --- | Make a tree rooted in the node with respect to the graph.-toTree :: (Show k, Ord k) => Graph k v -> k -> T.Tree v-toTree g = fmap (node g) . toKeyTree g+generate :: (Show k, Ord k) => Graph k v -> k -> T.Tree k+generate g k  = T.Node k (map (generate g) (edges g k)) --- | Make a key tree rooted in the node with respect to the graph.-toKeyTree :: (Show k, Ord k) => Graph k v -> k -> T.Tree k-toKeyTree g k = T.Node k-    [ toKeyTree g k'-    | k' <- edges g k ]+-- | A stateful monad for forest pruning.+newtype RanM a = RanM { runRanM :: Int -> (a, Int) } --- | Transform graph into a forest given the priority function.--- That is, trees with higher priorities will be taken first,--- while those with lower priorities might be trimmed down--- (since we don't want to have nodes with multiple parents in--- the resulting forest).-toForestWith :: (Show k, Ord k, Ord a)-             => (T.Tree v -> a) -> Graph k v -> T.Forest v-toForestWith pr g = map valTr . snd $-    mapAccumL trim S.empty sortedTrees-  where-    valTr = fmap (node g) -- Make value tree from a key tree-    trees = map (toKeyTree g) (roots g)-    sortedTrees =-        let f = pr . valTr-        in  sortBy (comparing f) trees+instance Monad RanM where+    return x     = RanM $ \s -> (x, s)+    RanM v >>= f = RanM $ \s -> case v s of (x, s') -> runRanM (f x) s' --- | Transform graph into a forest. It removes duplicate--- nodes from trees chosing trees in an arbitrary order.-toForest :: (Show k, Ord k) => Graph k v -> T.Forest v-toForest = toForestWith $ const (0 :: Int)+run :: RanM a -> a+run act = fst (runRanM act (-1)) -trim :: Ord k => S.Set k -> T.Tree k -> (S.Set k, T.Tree k)-trim visited tree =-    (visited', tree')-  where-    tree'    = fromJust (doIt tree)-    visited' = foldl' (flip S.insert) visited (T.flatten tree')-    doIt (T.Node x ts)-        | x `S.member` visited = Nothing-        | otherwise = Just $ T.Node x (mapMaybe doIt ts)+contains :: Int -> RanM Bool+contains k = RanM $ \m -> (k <= m, m)++include :: Int -> RanM ()+include k = RanM $ \_ -> ((), k)++chop :: T.Forest (k, Span) -> RanM (T.Forest (k, Span))+chop [] = return []+chop (T.Node (k, s) ts : us) = do+    visited <- contains (end s)+    if visited then+        chop us+    else do+        as <- chop ts+        include (end s)+        bs <- chop us+        return (T.Node (k, s) as : bs)++prune :: (k -> Int) -> T.Forest k -> T.Forest k+prune f = unSpanForest . run . chop . sortForest . spanForest f++-- | Spanning-like forest of a DAG.  Trees in the resulting forest are+-- disjoint with respect to their ranges.  It is not checked if the input+-- graph is actually a DAG.+disjointForest :: (Show k, Ord k) => (k -> Int) -> Graph k v -> T.Forest k+disjointForest f g = prune f . map (generate g) . roots $ g

@@ -0,0 +1,110 @@+-- | Working with NE trees and forests.++module Data.Named.Tree+( +-- * Combine with words+  addWords++-- * Span+, Span (..)+, leafSpan+, (<>)+, spanSet++-- * Trees with span+, span+, spanTree+, spanForest+, unSpanTree+, unSpanForest+, sortTree+, sortForest++-- * Utilities+, mapTrees+) where++import Prelude hiding (span)+import Data.List (sortBy)+import Data.Ord (comparing)+import qualified Data.Tree as T+import qualified Data.IntSet as S+import qualified Data.Map as M++-- | Map function over each tree from the forest.+mapTrees :: (a -> b) -> T.Forest a -> T.Forest b+mapTrees f = map (fmap f)++-- | Spanning of a tree.+data Span = Span+    { beg   :: Int+    , end   :: Int }+    deriving (Show, Eq, Ord)++-- | Make span for a leaf node.+leafSpan :: Int -> Span+leafSpan i = Span i i++-- | Minimum span overlapping both input spans.+(<>) :: Span -> Span -> Span+Span p q <> Span p' q' = Span (min p p') (max q q')++-- | Set of positions covered by the span.+spanSet :: Span -> S.IntSet+spanSet s = S.fromList [beg s .. end s]++-- | Get span of the span-annotated tree.+span :: T.Tree (a, Span) -> Span+span = snd . T.rootLabel++-- | Annotate tree nodes with spanning info given the function+-- which assignes indices to leaf nodes.+spanTree :: (k -> Int) -> T.Tree k -> T.Tree (k, Span)+spanTree f (T.Node k []) = T.Node (k, leafSpan (f k)) []+spanTree f (T.Node k ts) =+    let us = spanForest f ts+        s  = foldl1 (<>) (map span us)+    in  T.Node (k, s) us++-- | Annotate forest nodes with spanning info.+spanForest :: (k -> Int) -> T.Forest k -> T.Forest (k, Span)+spanForest f ts = map (spanTree f) ts++-- | Remove span annotations from the tree.+unSpanTree :: T.Tree (k, Span) -> T.Tree k+unSpanTree = fmap fst++-- | Remove span annotations from the forest.+unSpanForest :: T.Forest (k, Span) -> T.Forest k+unSpanForest = map unSpanTree++-- | Sort the tree with respect to spanning info.+sortTree :: T.Tree (k, Span) -> T.Tree (k, Span)+sortTree (T.Node x ts) = T.Node x (sortForest ts)++-- | Sort the forest with respect to spanning info.+sortForest :: T.Forest (k, Span) -> T.Forest (k, Span)+sortForest = sortBy (comparing span) . map sortTree++-- | Combine the disjoint forest with the list of words.+-- Discontinuities will be patched with no trace.+addWords :: Ord k => T.Forest k -> [k] -> T.Forest k+addWords [] xs = [T.Node x [] | x <- xs]+addWords ts xs+    = unSpanForest . T.subForest+    . sortTree . fillTree+    . dummyRoot+    . spanForest f $ ts+  where+    f = (M.!) $ M.fromList (zip xs [0..])+    g = (M.!) $ M.fromList (zip [0..] xs)++    dummyRoot = T.Node (undefined, bounds)+    bounds = Span 0 (length xs - 1)++    fillForest = map fillTree+    fillTree (T.Node n []) = T.Node n []+    fillTree (T.Node (k, s) us) =+        let m = spanSet s S.\\ S.unions (map (spanSet . span) us)+            mkLeaf i = T.Node (g i, leafSpan i) []+        in  T.Node (k, s) (fillForest us ++ map mkLeaf (S.toList m))

@@ -4,8 +4,8 @@     Parsing text in the Enamex data format.  Each node is enclosed between     opening and closing tags with tag name representing the label and contents     representing children of the node.  Both leaf and label values should be-    escaped by prepending the '\' character before special ' ' (space), '>',-    '<' and '\' characters.+    escaped by prepending the \\ character before special >, <, \\ and space+    characters.      Example: 

@@ -1,5 +1,5 @@ name:               data-named-version:            0.1.0+version:            0.2.0 synopsis:           Data types for named entities description:     The library provides data types which can be used to represent@@ -14,7 +14,7 @@     .     The Data.Named.Graph module can be used to represent more general,     graph structures of entities.  The module provides also a lossy-    conversion from a DAG to a forest of entities.+    conversion from a DAG to a disjoint forest of entities. license:            BSD3 license-file:       LICENSE cabal-version:      >= 1.6@@ -34,7 +34,8 @@       , attoparsec      exposed-modules:-        Data.Named.Graph+        Data.Named.Tree+      , Data.Named.Graph       , Data.Named.IOB       , Text.Named.Enamex