1 {-# LANGUAGE MultiParamTypeClasses, FlexibleInstances #-} 2 3 module Text.RegExp.Matching.LeftLong.Type where 4 5 import Data.Semiring 6 import Text.RegExp.Data 7 8 -- | 9 -- Semiring used for leftmost longest matching. 10 -- 11 -- The `LeftLong` type satisfies the distributive laws only with a 12 -- precondition on all involved multiplications: multiplied matches 13 -- must be adjacent and the start position must be smaller than the 14 -- end position. This precondition is satisfied for all 15 -- multiplications during regular expression matching. 16 -- 17 data LeftLong = Zero | One | LeftLong !Int !Int 18 deriving (Eq,Show) 19 20 instance Semiring LeftLong where 21 zero = Zero; one = One 22 23 Zero .+. y = y 24 x .+. Zero = x 25 One .+. y = y 26 x .+. One = x 27 LeftLong a b .+. LeftLong c d 28 | a<c || a==c && b>=d = LeftLong a b 29 | otherwise = LeftLong c d 30 31 Zero .*. _ = Zero 32 _ .*. Zero = Zero 33 One .*. y = y 34 x .*. One = x 35 LeftLong a _ .*. LeftLong _ b = LeftLong a b 36 37 instance Weight c (Int,c) LeftLong where 38 symWeight p (n,c) = p c .*. LeftLong n n 39