semiring 0.2 → 0.3

raw patch · 21 files changed

+388/−306 lines, 21 filesdep ~base

Dependency ranges changed: base

Files

• Data/Semiring.hs +70/−0
• Data/Semiring/Boolean.hs +17/−0
• Data/Semiring/Counting.hs +21/−0
• Data/Semiring/Derivation.hs +95/−0
• Data/Semiring/Helpers.hs +4/−0
• Data/Semiring/LogProb.hs +28/−0
• Data/Semiring/Max.hs +18/−0
• Data/Semiring/Prob.hs +19/−0
• Data/Semiring/Viterbi.hs +18/−0
• Data/Semiring/ViterbiNBest.hs +50/−0
• Data/Semiring/ViterbiNBestDerivation.hs +34/−0
• NLP/Semiring.hs +0/−68
• NLP/Semiring/Boolean.hs +0/−17
• NLP/Semiring/Counting.hs +0/−21
• NLP/Semiring/Derivation.hs +0/−70
• NLP/Semiring/Helpers.hs +0/−4
• NLP/Semiring/Prob.hs +0/−19
• NLP/Semiring/Viterbi.hs +0/−18
• NLP/Semiring/ViterbiNBest.hs +0/−50
• NLP/Semiring/ViterbiNBestDerivation.hs +0/−27
• semiring.cabal +14/−12

@@ -0,0 +1,70 @@+{-# LANGUAGE GeneralizedNewtypeDeriving #-}+module Data.Semiring(+  -- * Semiring+  --                    +  -- $SemiringDesc+++  Semiring, +  WeightedSemiring, +  Weighted(..), +  getWeight, getInfo,                   +  module Data.Monoid,+  module Data.Monoid.Multiplicative+) where+ +import Data.Monoid+import Data.Monoid.Multiplicative +import Data.Monoid.Additive +import Data.Function (on)++++-- $SemiringDesc+-- Semirings (rings without additive inverses, <http://en.wikipedia.org/wiki/Semiring>) are +-- a commonly used structure for performing computations over finite state machines, +-- parsers, and other dynamic programmy-systems. This library extends the basic structures  +-- defined for Monoids to Semirings and includes implementations of the major semirings +-- for parsing. +--+-- This work is based largely on "Semiring Parsing" by Joshua Goodman. (<http://www.ldc.upenn.edu/acl/J/J99/J99-4004.pdf>)  +-- which describes many of the interesting parsing semirings.++++-- | A 'Semiring' is made up of an additive Monoid and a Multiplicative.+--   It must also satisfy several other algebraic properties checked by quickcheck. +class (Multiplicative a, Monoid a) => Semiring a+++-- | A 'WeightedSemiring' also includes a sensical ordering over choices. +--   i.e. out of two choices which is better. This is used for Viterbi selection.   +class (Semiring a, Ord a) => WeightedSemiring a++   +instance (Multiplicative a, Multiplicative b) => Multiplicative (a,b) where +    one = (one, one)+    times (a, b) (a', b') = (a `times` a', b `times` b')+++-- | Dual semirings can be useful. For instance combining the  +--   Prob semiring and the MultiDerivation ring gives the total likelihood of +--   a derivation along with the paths to get there. +instance (Semiring a, Semiring b) => Semiring (a,b)  +++-- | The 'Weighted' type is the main type of WeightedSemiring.+--   It combines scoring semiring with a history semiring.+-- +--   The best example of this is the ViterbiDerivation semiring.+newtype Weighted semi1 semi2 = Weighted (semi1, semi2)+    deriving (Eq, Show, Monoid, Multiplicative, Semiring)++getWeight (Weighted (semi1, _))= semi1 +getInfo (Weighted (_, semi2))= semi2 +++instance (Ord semi1, Eq semi2) => Ord (Weighted semi1 semi2) where +    compare (Weighted s1) (Weighted s2) = (compare `on` fst) s1 s2 ++instance (WeightedSemiring a, Eq b, Semiring b) => WeightedSemiring (Weighted a b)

@@ -0,0 +1,17 @@+{-# LANGUAGE GeneralizedNewtypeDeriving #-}+module Data.Semiring.Boolean where+import Data.Semiring+import qualified Data.Boolean as B+import Data.Boolean ((&&*),(||*)) +newtype Boolean = Boolean Bool+    deriving (Eq, Show, B.Boolean) ++instance Multiplicative Boolean where+    one = B.true+    times = (&&*)++instance Monoid Boolean where +    mempty = B.false+    mappend = (||*)++instance Semiring Boolean 

@@ -0,0 +1,21 @@+{-# LANGUAGE GeneralizedNewtypeDeriving #-}+module Data.Semiring.Counting where+import Data.Semiring++-- | The 'Counting' semiring keeps track of the number of paths +--   or derivations led to a given output.+newtype Counting = Counting Integer+    deriving (Eq, Show, Num, Ord, Enum, Real, Integral) ++instance Multiplicative Counting where+    one = 1+    times = (*) ++instance Monoid Counting where +    mempty = 0+    mappend = (+)+++instance Semiring Counting +instance WeightedSemiring Counting +

@@ -0,0 +1,95 @@+{-# LANGUAGE GeneralizedNewtypeDeriving, FlexibleContexts, UndecidableInstances #-}+module Data.Semiring.Derivation (Derivation(..), MultiDerivation(..), DualDerivation(..), mkDerivation, fromDerivation, mkDualDerivation, fromDualDerivation) where+import Data.Semiring+import Data.Semiring.Helpers+import qualified Data.Set as S +import Data.Monoid+import Data.Maybe (isNothing)+import Control.Exception++-- | The 'Derivation' semiring keeps track of a single path or derivation +--   that led to the known output. If there are more than one path it discards +--   in favor the lesser path (based on ord). The main purpose of this semiring +--   is to track derivations for ViterbiNBestDerivation. If you want to keep all paths, +--   use 'MultiDerivation'.+--+--   Derivation takes a Monoid as an argument that describes how to build up paths or +--   more complicated structures.  +newtype Derivation m = Derivation (Maybe m)+    deriving (Eq, Ord) ++instance (Monoid m) => Multiplicative (Derivation m) where+    one = Derivation $ Just mempty+    times (Derivation d1) (Derivation d2) = Derivation $ do +        d1' <- d1+        d2' <- d2+        return $ mappend d1' d2'++instance Monoid (Derivation m) where +    mempty = Derivation Nothing+    mappend (Derivation s1) (Derivation s2) = +        Derivation $ case (s1,s2) of +                       (Nothing, s2) -> s2+                       (s1, Nothing) -> s1+                       (s1, s2) -> s1++instance (Monoid m) => Semiring (Derivation m)++instance (Show m) => Show (Derivation m) where +    show (Derivation (Just m)) = show m +    show (Derivation Nothing) = "[]" ++mkDerivation :: (Monoid m ) => m -> Derivation m +mkDerivation = Derivation . Just  ++fromDerivation :: (Monoid m ) => Derivation m -> m +fromDerivation (Derivation (Just m)) = m  +fromDerivation (Derivation Nothing) = throw $ AssertionFailed "no derivation"  +++-- | The 'MultiDerivation' semiring keeps track of a all paths or derivations +--   that led to the known output. This can be useful for debugging output.+-- +--  Keeping all these paths around can be expensive. 'MultiDerivation' leaves open +--  the implementation of the internal path monoid for more compact representations. +newtype MultiDerivation m = MultiDerivation (S.Set m)+    deriving (Eq, Show, Ord) ++instance (Monoid m, Ord m) => Multiplicative (MultiDerivation m) where+    one = MultiDerivation $ S.fromList [mempty]+    times (MultiDerivation d1) (MultiDerivation d2) = MultiDerivation $ +        S.fromList $ +        map (uncurry mappend) $ +        cartesian (S.toList d1) (S.toList d2) ++instance (Ord m) => Monoid (MultiDerivation m) where +    mempty = MultiDerivation S.empty+    mappend (MultiDerivation s1) (MultiDerivation s2) = MultiDerivation $ S.union s1 s2++instance (Ord m, Monoid m, Eq m) => Semiring (MultiDerivation m)++++newtype DualDerivation m1 m2 = DualDerivation (m1 m2)+    deriving (Eq, Show, Ord) ++instance (Monad m1, Monoid (m1 m2), Monoid m2) => Multiplicative (DualDerivation m1 m2) where+    one = DualDerivation $ return mempty+    times (DualDerivation d1) (DualDerivation d2) = +        DualDerivation $ do+          d1' <- d1+          d2' <- d2+          return $ mappend d1' d2'++instance (Monoid (m1 m2), Monoid m2) => Monoid (DualDerivation m1 m2) where +    mempty = DualDerivation mempty+    mappend (DualDerivation s1) (DualDerivation s2) = DualDerivation $ s1 `mappend` s2++instance (Monad m1, Monoid (m1 m2), Monoid m2) => Semiring (DualDerivation m1 m2)++++mkDualDerivation = DualDerivation   ++fromDualDerivation (DualDerivation m) = m  +

@@ -0,0 +1,4 @@+module Data.Semiring.Helpers where ++cartesian as bs = [(a,b) | a <- as, b <- bs] +

@@ -0,0 +1,28 @@+{-# LANGUAGE GeneralizedNewtypeDeriving #-}+module Data.Semiring.LogProb where +import Data.Semiring+++-- log prob, should only be used in viterbi semiring (add not defined)+newtype LogProb = LogProb Double+    deriving (Eq, Ord) ++convertToProb (LogProb p) = exp(p)++convertToDouble (LogProb p) = p++fromProb p = LogProb $ log p ++instance Show LogProb where +    show (LogProb p) = show p++instance Multiplicative LogProb where+    one = LogProb 0.0+    times (LogProb a) (LogProb b) = LogProb (a + b)++instance Monoid LogProb where +    mempty = undefined+    mappend = undefined++instance Semiring LogProb +instance WeightedSemiring LogProb 

@@ -0,0 +1,18 @@+{-# LANGUAGE GeneralizedNewtypeDeriving #-}+module Data.Semiring.Max where+import Data.Semiring++newtype Max n = Max n+    deriving (Eq, Show, Ord, Bounded, Num) ++instance (Num n) => Multiplicative (Max n)  where+    one = 0+    times = (+) ++instance (Ord n, Bounded n) =>Monoid (Max n) where +    mempty = minBound+    mappend = (max)+++instance (Bounded n, Ord n, Num n) => Semiring (Max n)+instance (Bounded n, Ord n, Num n) => WeightedSemiring (Max n) 

@@ -0,0 +1,19 @@+{-# LANGUAGE GeneralizedNewtypeDeriving #-}+module Data.Semiring.Prob where +import Data.Semiring++-- | The 'Prob' semiring keeps track of the likelihood of the known output +--   by keeping track of the probability of all paths. +newtype Prob = Prob Double+    deriving (Eq, Show, Num, Real, Fractional, Ord) ++instance Multiplicative Prob where+    one = 1.0+    times = (*) ++instance Monoid Prob where +    mempty = 0.0+    mappend = (+)++instance Semiring Prob +instance WeightedSemiring Prob 

@@ -0,0 +1,18 @@++{-# LANGUAGE GeneralizedNewtypeDeriving #-}+module Data.Semiring.Viterbi where+import Data.Semiring+import Data.Semiring.ViterbiNBest++data One = One  +instance N One where +    mkN = One+    n _ = 1++type Viterbi semi = ViterbiNBest One semi++mkViterbi v = ViterbiNBest [v]++fromViterbi :: (Semiring semi) => Viterbi semi -> semi +fromViterbi (ViterbiNBest []) = mempty +fromViterbi (ViterbiNBest [v]) =  v

@@ -0,0 +1,50 @@+{-# LANGUAGE ExistentialQuantification, ScopedTypeVariables #-}+module Data.Semiring.ViterbiNBest where+import Data.Semiring+import Data.Semiring.Helpers+import Data.List +++class N a where +    mkN :: a+    n :: a -> Int+    +-- | The 'ViterbiNBest' semiring keeps track of the n best scoring path to a known+--   output. This score is determined by a user defined 'WeightedSemiring'. +-- +--   The value of n (the number of of values to rank) is included in the type to prevent +--   combining mismatching values. To create a new n, make a new unary type and an instance+--   of N.+-- +-- @+--   data Ten = Ten  +--   instance N Ten where +--    mkN = Ten+--    n _ = 10+-- @+-- +data ViterbiNBest n semi = ViterbiNBest [semi] +  deriving (Eq, Show)++instance (N n, Ord semi, WeightedSemiring semi) => Multiplicative (ViterbiNBest n semi) where+    one = ViterbiNBest [one]+    times (ViterbiNBest a) (ViterbiNBest b) = +        ViterbiNBest $+        take (n (mkN::n)) $+        reverse $ sort $+        map (uncurry times) $ cartesian a b ++instance (N n, WeightedSemiring semi, Ord semi) => Monoid (ViterbiNBest n semi) where +    mempty = ViterbiNBest []+    mappend (ViterbiNBest a) (ViterbiNBest b) = +        ViterbiNBest $ take (n (mkN::n)) $ reverse $ sort (a ++ b)++instance (N n, WeightedSemiring semi, Ord semi) => Semiring (ViterbiNBest n semi)+++data Ten = Ten  +instance N Ten where +    mkN = Ten+    n _ = 10++type Viterbi10Best semi = ViterbiNBest Ten semi

@@ -0,0 +1,34 @@+{-# LANGUAGE MultiParamTypeClasses, FunctionalDependencies, TypeSynonymInstances, FlexibleInstances #-}+module Data.Semiring.ViterbiNBestDerivation where+import Data.Semiring+import Data.List +import Data.Semiring.Viterbi+import Data.Semiring.ViterbiNBest+import Data.Semiring.Prob+import Data.Semiring.Derivation++-- | The 'ViterbiNBestDerivation' is an example of a more complicated semiring+--   built up from smaller components. It keeps track of the top N scoring paths +--   along with their derivations.+-- +-- > type ViterbiNBestDerivation n m = ViterbiNBest n (Weighted Prob (Derivation m))+type ViterbiNBestDerivation n m = ViterbiNBest n (Weighted Prob (Derivation m))+++-- | The 'ViterbiDerivation' is a simpler semiring. It just keeps track of the best +--   scoring path and it's derivation.+--  +-- > type ViterbiDerivation m  = Viterbi (Weighted Prob (Derivation m))+type ViterbiDerivation p m  = Viterbi (Weighted p (Derivation m))++class BestScorer d s a | a -> d, a -> s where +    getBestDerivation :: a -> d +    getBestScore :: a -> s++instance (Monoid m, WeightedSemiring p) => BestScorer m p (ViterbiDerivation p m) where+    getBestDerivation = fromDerivation . getInfo . fromViterbi+    getBestScore = getWeight . fromViterbi+--getBestDerivation :: (Monoid m, WeightedSemiring p) => ViterbiDerivation p m -> m+++--getBestScore :: (Monoid m, WeightedSemiring p) => ViterbiDerivation p m -> p

@@ -1,68 +0,0 @@-{-# LANGUAGE GeneralizedNewtypeDeriving #-}-module NLP.Semiring(-  -- * Semiring-  --                    -  -- $SemiringDesc--  Multiplicative(..), -  Monoid(..), -  Semiring, -  WeightedSemiring, -  Weighted(..), -  getWeight, getInfo                   ) where- -import Data.Monoid-import Data.Monoid.Multiplicative -import Data.Monoid.Additive -import Data.Function (on)------ $SemiringDesc--- Semirings (rings without additive inverses, <http://en.wikipedia.org/wiki/Semiring>) are --- a commonly used structure for performing computations over finite state machines, --- parsers, and other dynamic programmy-systems. This library extends the basic structures  --- defined for Monoids to Semirings and includes implementations of the major semirings --- for parsing. ------ This work is based largely on "Semiring Parsing" by Joshua Goodman. (<http://www.ldc.upenn.edu/acl/J/J99/J99-4004.pdf>)  --- which describes many of the interesting parsing semirings.------ | A 'Semiring' is made up of an additive Monoid and a Multiplicative.---   It must also satisfy several other algebraic properties checked by quickcheck. -class (Multiplicative a, Monoid a) => Semiring a----- | A 'WeightedSemiring' also includes a sensical ordering over choices. ---   i.e. out of two choices which is better. This is used for Viterbi selection.   -class (Semiring a, Ord a) => WeightedSemiring a--   -instance (Multiplicative a, Multiplicative b) => Multiplicative (a,b) where -    one = (one, one)-    times (a, b) (a', b') = (a `times` a', b `times` b')----- | Dual semirings can be useful. For instance combining the  ---   Prob semiring and the MultiDerivation ring gives the total likelihood of ---   a derivation along with the paths to get there. -instance (Semiring a, Semiring b) => Semiring (a,b)  ----- | The 'Weighted' type is the main type of WeightedSemiring.---   It combines scoring semiring with a history semiring.--- ---   The best example of this is the ViterbiDerivation semiring.-newtype Weighted semi1 semi2 = Weighted (semi1, semi2)-    deriving (Eq, Show, Monoid, Multiplicative, Semiring)--getWeight (Weighted (semi1, _))= semi1 -getInfo (Weighted (_, semi2))= semi2 ---instance (Ord semi1, Eq semi2) => Ord (Weighted semi1 semi2) where -    compare (Weighted s1) (Weighted s2) = (compare `on` fst) s1 s2 --instance (WeightedSemiring a, Eq b, Semiring b) => WeightedSemiring (Weighted a b)

@@ -1,17 +0,0 @@-{-# LANGUAGE GeneralizedNewtypeDeriving #-}-module NLP.Semiring.Boolean where-import NLP.Semiring-import qualified Data.Boolean as B-import Data.Boolean ((&&*),(||*)) -newtype Boolean = Boolean Bool-    deriving (Eq, Show, B.Boolean) --instance Multiplicative Boolean where-    one = B.true-    times = (&&*)--instance Monoid Boolean where -    mempty = B.false-    mappend = (||*)--instance Semiring Boolean 

@@ -1,21 +0,0 @@-{-# LANGUAGE GeneralizedNewtypeDeriving #-}-module NLP.Semiring.Counting where-import NLP.Semiring---- | The 'Counting' semiring keeps track of the number of paths ---   or derivations led to a given output.-newtype Counting = Counting Integer-    deriving (Eq, Show, Num, Ord) --instance Multiplicative Counting where-    one = 1-    times = (*) --instance Monoid Counting where -    mempty = 0-    mappend = (+)---instance Semiring Counting -instance WeightedSemiring Counting -

@@ -1,70 +0,0 @@-{-# LANGUAGE GeneralizedNewtypeDeriving #-}-module NLP.Semiring.Derivation (Derivation(..), MultiDerivation(..), mkDerivation, fromDerivation) where-import NLP.Semiring-import NLP.Semiring.Helpers-import qualified Data.Set as S -import Data.Monoid-import Data.Maybe (isNothing)-import Control.Exception---- | The 'Derivation' semiring keeps track of a single path or derivation ---   that led to the known output. If there are more than one path it discards ---   in favor the lesser path (based on ord). The main purpose of this semiring ---   is to track derivations for ViterbiNBestDerivation. If you want to keep all paths, ---   use 'MultiDerivation'.------   Derivation takes a Monoid as an argument that describes how to build up paths or ---   more complicated structures.  -newtype Derivation m = Derivation (Maybe m)-    deriving (Eq, Ord) --instance (Monoid m) => Multiplicative (Derivation m) where-    one = Derivation $ Just mempty-    times (Derivation d1) (Derivation d2) = Derivation $ do -        d1' <- d1-        d2' <- d2-        return $ mappend d1' d2'--instance Monoid (Derivation m) where -    mempty = Derivation Nothing-    mappend (Derivation s1) (Derivation s2) = -        Derivation $ case (s1,s2) of -                       (Nothing, s2) -> s2-                       (s1, Nothing) -> s1-                       (s1, s2) -> s1--instance (Monoid m) => Semiring (Derivation m)--instance (Show m) => Show (Derivation m) where -    show (Derivation (Just m)) = show m -    show (Derivation Nothing) = "[]" --mkDerivation :: (Monoid m ) => m -> Derivation m -mkDerivation = Derivation . Just  --fromDerivation :: (Monoid m ) => Derivation m -> m -fromDerivation (Derivation (Just m)) = m  -fromDerivation (Derivation Nothing) = throw $ AssertionFailed "no derivation"  ----- | The 'MultiDerivation' semiring keeps track of a all paths or derivations ---   that led to the known output. This can be useful for debugging output.--- ---  Keeping all these paths around can be expensive. 'MultiDerivation' leaves open ---  the implementation of the internal path monoid for more compact representations. -newtype MultiDerivation m = MultiDerivation (S.Set m)-    deriving (Eq, Show, Ord) --instance (Monoid m, Ord m) => Multiplicative (MultiDerivation m) where-    one = MultiDerivation $ S.fromList [mempty]-    times (MultiDerivation d1) (MultiDerivation d2) = MultiDerivation $ -        S.fromList $ -        map (uncurry mappend) $ -        cartesian (S.toList d1) (S.toList d2) --instance (Ord m) => Monoid (MultiDerivation m) where -    mempty = MultiDerivation S.empty-    mappend (MultiDerivation s1) (MultiDerivation s2) = MultiDerivation $ S.union s1 s2--instance (Ord m, Monoid m, Eq m) => Semiring (MultiDerivation m)-

@@ -1,4 +0,0 @@-module NLP.Semiring.Helpers where --cartesian as bs = [(a,b) | a <- as, b <- bs] -

@@ -1,19 +0,0 @@-{-# LANGUAGE GeneralizedNewtypeDeriving #-}-module NLP.Semiring.Prob where -import NLP.Semiring---- | The 'Prob' semiring keeps track of the likelihood of the known output ---   by keeping track of the probability of all paths. -newtype Prob = Prob Double-    deriving (Eq, Show, Num, Real, Fractional, Ord) --instance Multiplicative Prob where-    one = 1.0-    times = (*) --instance Monoid Prob where -    mempty = 0.0-    mappend = (+)--instance Semiring Prob -instance WeightedSemiring Prob 

@@ -1,18 +0,0 @@--{-# LANGUAGE GeneralizedNewtypeDeriving #-}-module NLP.Semiring.Viterbi where-import NLP.Semiring-import NLP.Semiring.ViterbiNBest--data One = One  -instance N One where -    mkN = One-    n _ = 1--type Viterbi semi = ViterbiNBest One semi--mkViterbi v = ViterbiNBest [v]--fromViterbi :: (Semiring semi) => Viterbi semi -> semi -fromViterbi (ViterbiNBest []) = mempty -fromViterbi (ViterbiNBest [v]) =  v

@@ -1,50 +0,0 @@-{-# LANGUAGE ExistentialQuantification, ScopedTypeVariables #-}-module NLP.Semiring.ViterbiNBest where-import NLP.Semiring-import NLP.Semiring.Helpers-import Data.List ---class N a where -    mkN :: a-    n :: a -> Int-    --- | The 'ViterbiNBest' semiring keeps track of the n best scoring path to a known---   output. This score is determined by a user defined 'WeightedSemiring'. --- ---   The value of n (the number of of values to rank) is included in the type to prevent ---   combining mismatching values. To create a new n, make a new unary type and an instance---   of N.--- --- @---   data Ten = Ten  ---   instance N Ten where ---    mkN = Ten---    n _ = 10--- @--- -data ViterbiNBest n semi = ViterbiNBest [semi] -  deriving (Eq, Show)--instance (N n, Ord semi, WeightedSemiring semi) => Multiplicative (ViterbiNBest n semi) where-    one = ViterbiNBest [one]-    times (ViterbiNBest a) (ViterbiNBest b) = -        ViterbiNBest $-        take (n (mkN::n)) $-        reverse $ sort $-        map (uncurry times) $ cartesian a b --instance (N n, WeightedSemiring semi, Ord semi) => Monoid (ViterbiNBest n semi) where -    mempty = ViterbiNBest []-    mappend (ViterbiNBest a) (ViterbiNBest b) = -        ViterbiNBest $ take (n (mkN::n)) $ reverse $ sort (a ++ b)--instance (N n, WeightedSemiring semi, Ord semi) => Semiring (ViterbiNBest n semi)---data Ten = Ten  -instance N Ten where -    mkN = Ten-    n _ = 10--type Viterbi10Best semi = ViterbiNBest Ten semi

@@ -1,27 +0,0 @@-module NLP.Semiring.ViterbiNBestDerivation where-import NLP.Semiring-import Data.List -import NLP.Semiring.Viterbi-import NLP.Semiring.ViterbiNBest-import NLP.Semiring.Prob-import NLP.Semiring.Derivation---- | The 'ViterbiNBestDerivation' is an example of a more complicated semiring---   built up from smaller components. It keeps track of the top N scoring paths ---   along with their derivations.--- --- > type ViterbiNBestDerivation n m = ViterbiNBest n (Weighted Prob (Derivation m))-type ViterbiNBestDerivation n m = ViterbiNBest n (Weighted Prob (Derivation m))----- | The 'ViterbiDerivation' is a simpler semiring. It just keeps track of the best ---   scoring path and it's derivation.---  --- > type ViterbiDerivation m  = Viterbi (Weighted Prob (Derivation m))-type ViterbiDerivation m  = Viterbi (Weighted Prob (Derivation m))--getBestDerivation :: (Monoid m) => ViterbiDerivation m -> m-getBestDerivation = fromDerivation . getInfo . fromViterbi--getBestScore :: (Monoid m) => ViterbiDerivation m -> Prob-getBestScore = getWeight . fromViterbi

@@ -1,10 +1,10 @@ name:                semiring-version:             0.2+version:             0.3 synopsis:            Semirings, ring-like structures used for dynamic programming applications  description:         This provides a type class for semirings and                       implementations of the common semirings used in natural language                       processing.-category:            Natural Language Processing+category:            Math, Natural Language Processing license:             BSD3 license-file:        LICENSE author:              Sasha Rush@@ -18,19 +18,21 @@     default: False  library-    exposed-modules:     NLP.Semiring-                         NLP.Semiring.Boolean-                         NLP.Semiring.Prob-                         NLP.Semiring.Viterbi-                         NLP.Semiring.ViterbiNBest-                         NLP.Semiring.Counting-                         NLP.Semiring.Derivation-                         NLP.Semiring.ViterbiNBestDerivation-    other-modules:       NLP.Semiring.Helpers+    exposed-modules:     Data.Semiring+                         Data.Semiring.Boolean+                         Data.Semiring.Prob+                         Data.Semiring.LogProb+                         Data.Semiring.Viterbi+                         Data.Semiring.ViterbiNBest+                         Data.Semiring.Counting+                         Data.Semiring.Max+                         Data.Semiring.Derivation+                         Data.Semiring.ViterbiNBestDerivation+    other-modules:       Data.Semiring.Helpers     if flag(testing)         buildable: False -    build-Depends:   base       >= 3   && < 4,+    build-Depends:   base      <= 4.0,                      containers >= 0.1 && < 0.3,                      monoids    >= 0.2.0.2 && < 0.3,                      Boolean