data-named 0.6.1 → 0.6.2

raw patch · 5 files changed

+205/−57 lines, 5 filesdep ~containersPVP: major bump suggested

API removals or changes: PVP suggests a major version bump

Dependency ranges changed: containers

API changes (from Hackage documentation)

Files

• README.md +18/−0
• changelog +0/−9
• data-named.cabal +42/−47
• src/Data/Named/DAG.hs +144/−0
• src/Data/Named/Tree.hs +1/−1

@@ -0,0 +1,18 @@+Data-named+==========++The library provides data types which can be used to represent forest+structures with labels stored in internal nodes and words kept in leaves.+In particular, those types are well suited for representing the layer of named+entities (NEs).++The IOB method is implemented in the `Data.Named.IOB` module and can be used to+translate between a forest of entities and a sequence of compound IOB labels.+This method can be used together with a sequence classifier to indirectly model+forest structures.++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 disjoint forest of entities.++[![Build Status](https://travis-ci.org/kawu/data-named.svg)](https://travis-ci.org/kawu/data-named)

@@ -1,9 +0,0 @@--*-change-log-*---0.6.1	Jun 2016-        * Add stack.yaml-        * Add README-        * Add `Applicative` instances where needed (as a result of the `Applicative => Monad` proposal)--0.6.0	Jul 2014-	* Add `concatForestLeaves` function (inverse of `groupForestLeaves`)

@@ -1,51 +1,46 @@-name:               data-named-version:            0.6.1-synopsis:           Data types for named entities-description:-    The library provides data types which can be used to represent-    forest structures with labels stored in internal nodes and-    words kept in leaves.  In particular, those types are well suited-    for representing the layer of named entities (NEs).-    .-    The IOB method is implemented in the Data.Named.IOB module and can-    be used to translate between a forest of entities and a sequence-    of compound IOB labels.  This method can be used together with a-    sequence classifier to indirectly model forest structures.-    .-    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 disjoint forest of entities.-license:            BSD3-license-file:       LICENSE-cabal-version:      >= 1.6-copyright:          Copyright (c) 2012 IPI PAN-author:             Jakub Waszczuk-maintainer:         waszczuk.kuba@gmail.com-stability:          experimental-category:           Natural Language Processing-homepage:           https://github.com/kawu/data-named-build-type:         Simple--extra-source-files: changelog--library-    hs-source-dirs: src--    build-depends:-        base                >= 4.8      && < 5-      , containers          >= 0.5      && < 0.6-      , text                >= 1.1      && < 1.3-      , attoparsec          >= 0.12     && < 0.14-      , binary              >= 0.7      && < 0.9+cabal-version: 1.12 -    exposed-modules:-        Data.Named.Tree-      , Data.Named.Graph-      , Data.Named.IOB-      , Text.Named.Enamex+-- This file has been generated from package.yaml by hpack version 0.31.1.+--+-- see: https://github.com/sol/hpack+--+-- hash: 23b5a0797e6af3d7628e695ce2f4d21b4d0ce1c515c5a9419551ccca0db6834e -    ghc-options: -Wall+name:           data-named+version:        0.6.2+synopsis:       Data types for named entities+description:    Please see the README on GitHub at <https://github.com/kawu/data-named#readme>+category:       Natural Language Processing+homepage:       https://github.com/kawu/data-named#readme+bug-reports:    https://github.com/kawu/data-named/issues+author:         Jakub Waszczuk+maintainer:     waszczuk.kuba@gmail.com+copyright:      2012-2019 IPI PAN, Jakub Waszczuk+license:        BSD3+license-file:   LICENSE+build-type:     Simple+extra-source-files:+    README.md  source-repository head-    type: git-    location: git://github.com/kawu/data-named.git+  type: git+  location: https://github.com/kawu/data-named++library+  exposed-modules:+      Data.Named.DAG+      Data.Named.Graph+      Data.Named.IOB+      Data.Named.Tree+      Text.Named.Enamex+  other-modules:+      Paths_data_named+  hs-source-dirs:+      src+  build-depends:+      attoparsec >=0.12 && <0.14+    , base >=4.8 && <5+    , binary >=0.7 && <0.9+    , containers >=0.5 && <0.7+    , text >=1.1 && <1.3+  default-language: Haskell2010

@@ -0,0 +1,144 @@+{-# LANGUAGE RecordWildCards #-}++-- | Implementation of a DAG with each node identified by a unique key.++module Data.Named.DAG+( +-- * DAG+  DAG (..)+, mkDAG+, unDAG++-- * Access by key+, vertex+, node+, edges+, maybeNode+, maybeEdges++-- * Access by vertex (index)+, nodeV+, keyV+, edgesV++-- * Conversion to forest+, toForest+, toForestBy++-- * Utilities+, roots+, leaves+) where++import Control.Applicative ((<$>))+import Data.List (sortBy, minimumBy)+import qualified Data.Set as S+import qualified Data.Tree as T+import qualified Data.Graph as G++-- | A directed acyclic graph.+data DAG k v = DAG {+    -- | The underlying graph.+    graph       :: G.Graph,+    -- | Map vertex identifier to a node description.+    nodeDesc    :: G.Vertex -> (v, k, [k]),+    -- | Map key to a vertex identifier.  Return Nothing if the key is not+    -- a member of the graph.+    maybeVertex :: k -> Maybe G.Vertex }++-- | The node for the given key.  Return Nothing if the key is not+-- a member of the graph.+maybeNode :: DAG k v -> k -> Maybe v+maybeNode DAG{..} k = _1 . nodeDesc <$> maybeVertex k+{-# INLINE maybeNode #-}++-- | The edge list for the given key.  Return Nothing if the key is not+-- a member of the graph.+maybeEdges :: DAG k v -> k -> Maybe [k]+maybeEdges DAG{..} k = _3 . nodeDesc <$> maybeVertex k+{-# INLINE maybeEdges #-}++-- | Map key to a vertex identifier.  Report error if the key is not a member+-- of the graph.+vertex :: Show k => DAG k v -> k -> G.Vertex+vertex dag k = case maybeVertex dag k of+    Nothing -> error $ "vertex: key " ++ show k ++ " not in the graph"+    Just x  -> x++-- | The node for the given key.  Report error if the key is not a member+-- of the graph.+node :: Show k => DAG k v -> k -> v+node dag k = case maybeNode dag k of+    Nothing -> error $ "node: key " ++ show k ++ " not in the graph"+    Just x  -> x++-- | The edge list for the given key.  Report error if the key is not a member+-- of the graph.+edges :: Show k => DAG k v -> k -> [k]+edges dag k = case maybeEdges dag k of+    Nothing -> error $ "edges: key " ++ show k ++ " not in the graph"+    Just x  -> x++nodeV :: DAG k v -> G.Vertex -> v+nodeV DAG{..} = _1 . nodeDesc+{-# INLINE nodeV #-}++keyV :: DAG k v -> G.Vertex -> k+keyV DAG{..} = _2 . nodeDesc+{-# INLINE keyV #-}++edgesV :: DAG k v -> G.Vertex -> [k]+edgesV DAG{..} = _3 . nodeDesc+{-# INLINE edgesV #-}++leaves :: DAG k v -> [k]+leaves dag = [k | (_, k, []) <- unDAG dag]++roots :: Ord k => DAG k v -> [k]+roots dag =+    let desc = S.fromList . concat . map _3 $ unDAG dag+    in  [k | (_, k, _) <- unDAG dag, not (k `S.member` desc)]++-- | Smart constructur which verifies that the graph is actually a DAG.+-- Return Nothing if the input list constitutes a graph with cycles. +mkDAG :: (Show k, Ord k) => [(v, k, [k])] -> Maybe (DAG k v)+mkDAG xs +    | any ((>1) . length . T.flatten) (G.scc _graph) = Nothing+    | otherwise = Just $ DAG+        { graph         = _graph+        , nodeDesc      = _nodeDesc+        , maybeVertex   = _maybeVertex }+  where+    (_graph, _nodeDesc, _maybeVertex) = G.graphFromEdges xs++unDAG :: DAG k v -> [(v, k, [k])]+unDAG DAG{..} = map nodeDesc (G.vertices graph)++-- | Spanning forest of the DAG.  Non-overloaded version of the 'toForest'+-- function.  The comparison function is used to sort the list of leaves+-- and the spanning tree is computed with respect to the resulting order.+toForestBy :: (Show k, Ord k) => (k -> k -> Ordering) -> DAG k v -> T.Forest k+toForestBy cmp dag@DAG{..} =+    let proxy = minimumBy cmp . map (keyV dag)+              . G.reachable graph . vertex dag+        cmpRoots r r' = cmp (proxy r) (proxy r')+        xs = map (vertex dag) . sortBy cmpRoots $ roots dag+    in  map (fmap (_2 . nodeDesc)) (G.dfs graph xs)++-- | Spanning forest of the DAG using the standard 'compare' function to+-- compare keys kept in DAG leaves.  Overloaded version of the 'toForestBy'+-- function.+toForest :: (Show k, Ord k) => DAG k v -> T.Forest k+toForest = toForestBy compare++_1 :: (a, b, c) -> a+_1 (x, _, _) = x+{-# INLINE _1 #-}++_2 :: (a, b, c) -> b+_2 (_, x, _) = x+{-# INLINE _2 #-}++_3 :: (a, b, c) -> c+_3 (_, _, x) = x+{-# INLINE _3 #-}

@@ -36,7 +36,7 @@ , module Data.Tree ) where -import Prelude hiding (span)+import Prelude hiding (span, (<>)) import Data.List (sortBy, groupBy) import Data.Either (rights) import Data.Ord (comparing)