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