    -- ------------------------------------------------------------

    {- |
       Module     : Text.XML.HXT.DTDValidation.RE
       Copyright  : Copyright (C) 2008 Uwe Schmidt
       License    : MIT

       Maintainer : Uwe Schmidt (uwe@fh-wedel.de)
       Stability  : experimental
       Portability: portable

       A module for regular expression matching based on derivatives of regular expressions.

       The code was taken from Joe English (<http://www.flightlab.com/~joe/sgml/validate.html>).
       Tested and extended by Martin Schmidt.

       Further references for the algorithm:

       Janusz A. Brzozowski.

            Derivatives of Regular Expressions. Journal of the ACM, Volume 11, Issue 4, 1964.

       Mark Hopkins.

            Regular Expression Package. Posted to comp.compilers, 1994.
            Available per FTP at <ftp://iecc.com/pub/file/regex.tar.gz>.
    -}

    -- ------------------------------------------------------------

    module Text.XML.HXT.DTDValidation.RE
        ( RE(..)

        , re_unit
        , re_zero
        , re_sym
        , re_rep
        , re_plus
        , re_opt
        , re_seq
        , re_alt
        , re_dot

        , checkRE
        , matches
        , nullable
        , printRE
      )
    where

    import           Data.List (foldl')

    -- |
    -- Data type for regular expressions.

    data RE a =
            RE_ZERO String          --' L(0)   = {} (empty set)
            | RE_UNIT               --' L(1)   = { [] } (empty sequence)
            | RE_SYM a              --' L(x)   = { [x] }
            | RE_DOT                --' accept any single symbol
            | RE_REP (RE a)         --' L(e*)  = { [] } `union` L(e+)
            | RE_PLUS (RE a)        --' L(e+)  = { x ++ y | x <- L(e), y <- L(e*) }
            | RE_OPT (RE a)         --' L(e?)  = L(e) `union` { [] }
            | RE_SEQ (RE a) (RE a)  --' L(e,f) = { x ++ y | x <- L(e), y <- L(f) }
            | RE_ALT (RE a) (RE a)  --' L(e|f) = L(e) `union` L(f)
            deriving (Int -> RE a -> ShowS
    [RE a] -> ShowS
    RE a -> String
    (Int -> RE a -> ShowS)
    -> (RE a -> String) -> ([RE a] -> ShowS) -> Show (RE a)
    forall a. Show a => Int -> RE a -> ShowS
    forall a. Show a => [RE a] -> ShowS
    forall a. Show a => RE a -> String
    forall a.
    (Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
    $cshowsPrec :: forall a. Show a => Int -> RE a -> ShowS
    showsPrec :: Int -> RE a -> ShowS
    $cshow :: forall a. Show a => RE a -> String
    show :: RE a -> String
    $cshowList :: forall a. Show a => [RE a] -> ShowS
    showList :: [RE a] -> ShowS
    Show, RE a -> RE a -> Bool
    (RE a -> RE a -> Bool) -> (RE a -> RE a -> Bool) -> Eq (RE a)
    forall a. Eq a => RE a -> RE a -> Bool
    forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
    $c== :: forall a. Eq a => RE a -> RE a -> Bool
    == :: RE a -> RE a -> Bool
    $c/= :: forall a. Eq a => RE a -> RE a -> Bool
    /= :: RE a -> RE a -> Bool
    Eq, Eq (RE a)
    Eq (RE a) =>
    (RE a -> RE a -> Ordering)
    -> (RE a -> RE a -> Bool)
    -> (RE a -> RE a -> Bool)
    -> (RE a -> RE a -> Bool)
    -> (RE a -> RE a -> Bool)
    -> (RE a -> RE a -> RE a)
    -> (RE a -> RE a -> RE a)
    -> Ord (RE a)
    RE a -> RE a -> Bool
    RE a -> RE a -> Ordering
    RE a -> RE a -> RE a
    forall a.
    Eq a =>
    (a -> a -> Ordering)
    -> (a -> a -> Bool)
    -> (a -> a -> Bool)
    -> (a -> a -> Bool)
    -> (a -> a -> Bool)
    -> (a -> a -> a)
    -> (a -> a -> a)
    -> Ord a
    forall a. Ord a => Eq (RE a)
    forall a. Ord a => RE a -> RE a -> Bool
    forall a. Ord a => RE a -> RE a -> Ordering
    forall a. Ord a => RE a -> RE a -> RE a
    $ccompare :: forall a. Ord a => RE a -> RE a -> Ordering
    compare :: RE a -> RE a -> Ordering
    $c< :: forall a. Ord a => RE a -> RE a -> Bool
    < :: RE a -> RE a -> Bool
    $c<= :: forall a. Ord a => RE a -> RE a -> Bool
    <= :: RE a -> RE a -> Bool
    $c> :: forall a. Ord a => RE a -> RE a -> Bool
    > :: RE a -> RE a -> Bool
    $c>= :: forall a. Ord a => RE a -> RE a -> Bool
    >= :: RE a -> RE a -> Bool
    $cmax :: forall a. Ord a => RE a -> RE a -> RE a
    max :: RE a -> RE a -> RE a
    $cmin :: forall a. Ord a => RE a -> RE a -> RE a
    min :: RE a -> RE a -> RE a
    Ord)

    -- ------------------------------------------------------------
    -- Constructor functions to simplify regular expressions when constructing them.

    -- |
    -- Constructs a regular expression for an empty set.
    --
    --    * 1.parameter errMsg :  error message
    --
    --    - returns : regular expression for an empty set

    re_zero                 :: String -> RE a
    re_zero :: forall a. String -> RE a
    re_zero String
    m               = String -> RE a
    forall a. String -> RE a
    RE_ZERO String
    m

    -- |
    -- Constructs a regular expression for an empty sequence.
    --
    --    - returns : regular expression for an empty sequence

    re_unit                 :: RE a
    re_unit :: forall a. RE a
    re_unit                 = RE a
    forall a. RE a
    RE_UNIT

    -- |
    -- Constructs a regular expression for accepting a symbol
    --
    --    * 1.parameter sym :  the symbol to be accepted
    --
    --    - returns : regular expression for accepting a symbol

    re_sym                  :: a -> RE a
    re_sym :: forall a. a -> RE a
    re_sym a
    x                = a -> RE a
    forall a. a -> RE a
    RE_SYM a
    x

    -- |
    -- Constructs a regular expression for accepting any singel symbol
    --
    --    - returns : regular expression for accepting any singel symbol

    re_dot                  :: RE a
    re_dot :: forall a. RE a
    re_dot                  = RE a
    forall a. RE a
    RE_DOT

    -- |
    -- Constructs an optional repetition (*) of a regular expression
    --
    --    * 1.parameter re_a :  regular expression to be repeted
    --
    --    - returns : new regular expression

    re_rep                  :: RE a -> RE a
    re_rep :: forall a. RE a -> RE a
    re_rep RE a
    RE_UNIT          = RE a
    forall a. RE a
    RE_UNIT
    re_rep (RE_ZERO String
    _)      = RE a
    forall a. RE a
    RE_UNIT
    re_rep e :: RE a
    e@(RE_REP RE a
    _)     = RE a -> RE a
    forall a. RE a -> RE a
    RE_REP (RE a -> RE a
    forall a. RE a -> RE a
    rem_rep RE a
    e)            -- remove nested reps
    re_rep e :: RE a
    e@(RE_ALT RE a
    _ RE a
    _)   = RE a -> RE a
    forall a. RE a -> RE a
    RE_REP (RE a -> RE a
    forall a. RE a -> RE a
    rem_rep RE a
    e)            -- remove nested reps in alternatives
    re_rep RE a
    e                = RE a -> RE a
    forall a. RE a -> RE a
    RE_REP RE a
    e

    -- |
    -- remove redundant nested *'s in RE
    -- theoretically this is unneccessary,
    -- but without this simplification the runtime can increase exponentally
    -- when computing deltas, e.g. for a** or (a|b*)* which is the same as (a|b)*

    rem_rep                     :: RE a -> RE a
    rem_rep :: forall a. RE a -> RE a
    rem_rep (RE_ALT RE a
    RE_UNIT RE a
    e2) = RE a
    e2
    rem_rep (RE_ALT RE a
    e1 RE a
    e2)      = RE a -> RE a -> RE a
    forall a. RE a -> RE a -> RE a
    RE_ALT (RE a -> RE a
    forall a. RE a -> RE a
    rem_rep RE a
    e1) (RE a -> RE a
    forall a. RE a -> RE a
    rem_rep RE a
    e2)
    rem_rep (RE_REP RE a
    e1)         = RE a -> RE a
    forall a. RE a -> RE a
    rem_rep RE a
    e1
    rem_rep RE a
    e1                  = RE a
    e1

    -- |
    -- Constructs a repetition (+) of a regular expression
    --
    --    * 1.parameter re_a :  regular expression to be repeted
    --
    --    - returns : new regular expression

    re_plus                 :: RE a -> RE a
    re_plus :: forall a. RE a -> RE a
    re_plus RE a
    RE_UNIT         = RE a
    forall a. RE a
    RE_UNIT
    re_plus (RE_ZERO String
    m)     = String -> RE a
    forall a. String -> RE a
    RE_ZERO String
    m
    re_plus RE a
    e
        | RE a -> Bool
    forall a. RE a -> Bool
    nullable RE a
    e        = RE a -> RE a
    forall a. RE a -> RE a
    re_rep RE a
    e            -- nullable e => e+ == e*
        | Bool
    otherwise         = RE a -> RE a -> RE a
    forall a. RE a -> RE a -> RE a
    re_seq RE a
    e (RE a -> RE a
    forall a. RE a -> RE a
    re_rep RE a
    e)

    -- |
    -- Constructs an option (?) of a regular expression
    --
    --    * 1.parameter re_a :  regular expression to be optional
    --
    --    - returns : new regular expression

    re_opt                  :: (Ord a) => RE a -> RE a
    re_opt :: forall a. Ord a => RE a -> RE a
    re_opt RE a
    RE_UNIT          = RE a
    forall a. RE a
    RE_UNIT
    re_opt (RE_ZERO String
    _)      = RE a
    forall a. RE a
    RE_UNIT
    re_opt RE a
    e                = RE a -> RE a -> RE a
    forall a. Ord a => RE a -> RE a -> RE a
    re_alt RE a
    forall a. RE a
    RE_UNIT RE a
    e

    -- |
    -- Constructs a sequence (,) of two regular expressions
    --
    --    * 1.parameter re_a :  first regular expression in sequence
    --
    --    - 2.parameter re_b :  second regular expression in sequence
    --
    --    - returns : new regular expression

    re_seq                                 :: RE a -> RE a -> RE a
    re_seq :: forall a. RE a -> RE a -> RE a
    re_seq e1 :: RE a
    e1@(RE_ZERO String
    _)   RE a
    _              = RE a
    e1                         -- simplification
    re_seq RE a
    RE_UNIT          RE a
    e2             = RE a
    e2                         -- simplification
    re_seq RE a
    _                e2 :: RE a
    e2@(RE_ZERO String
    _) = RE a
    e2                         -- simplification
    re_seq RE a
    e1               RE a
    RE_UNIT        = RE a
    e1                         -- simplification
    re_seq (RE_SEQ RE a
    e11 RE a
    e12) RE a
    e2             = RE a -> RE a -> RE a
    forall a. RE a -> RE a -> RE a
    re_seq RE a
    e11 (RE a -> RE a -> RE a
    forall a. RE a -> RE a -> RE a
    re_seq RE a
    e12 RE a
    e2) -- right assoc.
    re_seq RE a
    e1               RE a
    e2             = RE a -> RE a -> RE a
    forall a. RE a -> RE a -> RE a
    RE_SEQ RE a
    e1 RE a
    e2

    -- |
    -- Constructs an alternative (|) of two regular expressions
    --
    --    * 1.parameter re_a :  first regular expression of alternative
    --
    --    - 2.parameter re_b :  second regular expression of alternative
    --
    --    - returns : new regular expression

    re_alt                                      :: (Ord a) => RE a -> RE a -> RE a
    re_alt :: forall a. Ord a => RE a -> RE a -> RE a
    re_alt (RE_ZERO String
    _)      RE a
    e2                  = RE a
    e2
    re_alt RE a
    e1               (RE_ZERO String
    _)         = RE a
    e1
    re_alt (RE_ALT RE a
    e11 RE a
    e12) RE a
    e2                  = RE a -> RE a -> RE a
    forall a. Ord a => RE a -> RE a -> RE a
    re_alt RE a
    e11 (RE a -> RE a -> RE a
    forall a. Ord a => RE a -> RE a -> RE a
    re_alt RE a
    e12 RE a
    e2)  -- is right assoc
    re_alt RE a
    e1               e2 :: RE a
    e2@(RE_ALT RE a
    e21 RE a
    e22)
        | RE a
    e1 RE a -> RE a -> Bool
    forall a. Eq a => a -> a -> Bool
    == RE a
    e21                             = RE a
    e2             -- duplicates removed, the effective rule
        | RE a
    e1 RE a -> RE a -> Bool
    forall a. Ord a => a -> a -> Bool
    >  RE a
    e21                             = RE a -> RE a -> RE a
    forall a. Ord a => RE a -> RE a -> RE a
    re_alt RE a
    e21 (RE a -> RE a -> RE a
    forall a. Ord a => RE a -> RE a -> RE a
    re_alt RE a
    e1 RE a
    e22)  -- sort alternatives
        | Bool
    otherwise                             = RE a -> RE a -> RE a
    forall a. RE a -> RE a -> RE a
    RE_ALT RE a
    e1 RE a
    e2
    re_alt RE a
    e1               RE a
    e2
        | RE a
    e1 RE a -> RE a -> Bool
    forall a. Eq a => a -> a -> Bool
    == RE a
    e2                              = RE a
    e2             -- simplification, the effective rule
        | RE a
    e1 RE a -> RE a -> Bool
    forall a. Ord a => a -> a -> Bool
    >  RE a
    e2                              = RE a -> RE a -> RE a
    forall a. Ord a => RE a -> RE a -> RE a
    re_alt RE a
    e2 RE a
    e1   -- sort alts for unique repr.
        | Bool
    otherwise                             = RE a -> RE a -> RE a
    forall a. RE a -> RE a -> RE a
    RE_ALT RE a
    e1 RE a
    e2

    -- ------------------------------------------------------------

    -- |
    -- Checks if a regular expression matches the empty sequence.
    --
    -- nullable e == [] `in` L(e)
    --
    -- This check indicates if a regular expression fits to a sentence or not.
    --
    --    * 1.parameter re :  regular expression to be checked
    --
    --    - returns : true if regular expression matches the empty sequence,
    --                otherwise false

    nullable                ::  RE a -> Bool
    nullable :: forall a. RE a -> Bool
    nullable (RE_ZERO String
    _)    = Bool
    False
    nullable RE a
    RE_UNIT        = Bool
    True
    nullable (RE_SYM a
    _)     = Bool
    False
    nullable (RE_REP RE a
    _)     = Bool
    True
    nullable (RE_PLUS RE a
    e)    = RE a -> Bool
    forall a. RE a -> Bool
    nullable RE a
    e
    nullable (RE_OPT RE a
    _)     = Bool
    True
    nullable (RE_SEQ RE a
    e RE a
    f)   = RE a -> Bool
    forall a. RE a -> Bool
    nullable RE a
    e Bool -> Bool -> Bool
    && RE a -> Bool
    forall a. RE a -> Bool
    nullable RE a
    f
    nullable (RE_ALT RE a
    e RE a
    f)   = RE a -> Bool
    forall a. RE a -> Bool
    nullable RE a
    e Bool -> Bool -> Bool
    || RE a -> Bool
    forall a. RE a -> Bool
    nullable RE a
    f
    nullable RE a
    RE_DOT         = Bool
    False

    -- |
    -- Derives a regular expression with respect to one symbol.
    --
    -- L(delta e x) = x \ L(e)
    --
    --    * 1.parameter re :  regular expression to be derived
    --
    --    - 2.parameter sym :  the symbol on which the regular expression is applied
    --
    --    - returns : the derived regular expression

    delta :: (Ord a, Show a) => RE a -> a -> RE a
    delta :: forall a. (Ord a, Show a) => RE a -> a -> RE a
    delta RE a
    re a
    x = case RE a
    re of
            RE_ZERO String
    _               -> RE a
    re                                   -- re_zero m
            RE a
    RE_UNIT                 -> String -> RE a
    forall a. String -> RE a
    re_zero (String
    "Symbol " String -> ShowS
    forall a. [a] -> [a] -> [a]
    ++ a -> String
    forall a. Show a => a -> String
    show a
    x String -> ShowS
    forall a. [a] -> [a] -> [a]
    ++ String
    " unexpected.")
            RE_SYM a
    sym
                    | a
    x a -> a -> Bool
    forall a. Eq a => a -> a -> Bool
    == a
    sym      -> RE a
    forall a. RE a
    re_unit
                    | Bool
    otherwise     -> String -> RE a
    forall a. String -> RE a
    re_zero (String
    "Symbol " String -> ShowS
    forall a. [a] -> [a] -> [a]
    ++ a -> String
    forall a. Show a => a -> String
    show a
    sym String -> ShowS
    forall a. [a] -> [a] -> [a]
    ++ String
    " expected, but symbol " String -> ShowS
    forall a. [a] -> [a] -> [a]
    ++ a -> String
    forall a. Show a => a -> String
    show a
    x String -> ShowS
    forall a. [a] -> [a] -> [a]
    ++ String
    " found.")
            RE_REP  RE a
    e               -> RE a -> RE a -> RE a
    forall a. RE a -> RE a -> RE a
    re_seq (RE a -> a -> RE a
    forall a. (Ord a, Show a) => RE a -> a -> RE a
    delta RE a
    e a
    x) RE a
    re                -- (re_rep e)
            RE_PLUS RE a
    e               -> RE a -> RE a -> RE a
    forall a. RE a -> RE a -> RE a
    re_seq (RE a -> a -> RE a
    forall a. (Ord a, Show a) => RE a -> a -> RE a
    delta RE a
    e a
    x) (RE a -> RE a
    forall a. RE a -> RE a
    re_rep RE a
    e)
            RE_OPT  RE a
    e               -> RE a -> a -> RE a
    forall a. (Ord a, Show a) => RE a -> a -> RE a
    delta RE a
    e a
    x
            RE_SEQ  RE a
    e RE a
    f
                    | RE a -> Bool
    forall a. RE a -> Bool
    nullable RE a
    e    -> RE a -> RE a -> RE a
    forall a. Ord a => RE a -> RE a -> RE a
    re_alt (RE a -> RE a -> RE a
    forall a. RE a -> RE a -> RE a
    re_seq (RE a -> a -> RE a
    forall a. (Ord a, Show a) => RE a -> a -> RE a
    delta RE a
    e a
    x) RE a
    f) (RE a -> a -> RE a
    forall a. (Ord a, Show a) => RE a -> a -> RE a
    delta RE a
    f a
    x)
                    | Bool
    otherwise     -> RE a -> RE a -> RE a
    forall a. RE a -> RE a -> RE a
    re_seq (RE a -> a -> RE a
    forall a. (Ord a, Show a) => RE a -> a -> RE a
    delta RE a
    e a
    x) RE a
    f
            RE_ALT  RE a
    e RE a
    f             -> RE a -> RE a -> RE a
    forall a. Ord a => RE a -> RE a -> RE a
    re_alt (RE a -> a -> RE a
    forall a. (Ord a, Show a) => RE a -> a -> RE a
    delta RE a
    e a
    x) (RE a -> a -> RE a
    forall a. (Ord a, Show a) => RE a -> a -> RE a
    delta RE a
    f a
    x)
            RE a
    RE_DOT                  -> RE a
    forall a. RE a
    re_unit

    -- |
    -- Derives a regular expression with respect to a sentence.
    --
    --    * 1.parameter re :  regular expression
    --
    --    - 2.parameter s :  sentence to which the regular expression is applied
    --
    --    - returns : the derived regular expression

    matches :: (Ord a, Show a) => RE a -> [a] -> RE a
    matches :: forall a. (Ord a, Show a) => RE a -> [a] -> RE a
    matches RE a
    e = (RE a -> a -> RE a) -> RE a -> [a] -> RE a
    forall b a. (b -> a -> b) -> b -> [a] -> b
    forall (t :: * -> *) b a.
    Foldable t =>
    (b -> a -> b) -> b -> t a -> b
    foldl' RE a -> a -> RE a
    forall a. (Ord a, Show a) => RE a -> a -> RE a
    delta RE a
    e

    -- |
    -- Checks if an input matched a regular expression. The function should be
    -- called after matches.
    --
    -- Was the sentence used in @matches@ in the language of the regular expression?
    -- -> matches e s == s `in` L(e)?
    --
    --    * 1.parameter re :  the derived regular expression
    --
    --    - returns : empty String if input matched the regular expression, otherwise
    --               an error message is returned

    checkRE :: (Eq a, Show a) => RE a -> String
    checkRE :: forall a. (Eq a, Show a) => RE a -> String
    checkRE (RE a
    RE_UNIT)       = String
    ""
    checkRE (RE_ZERO String
    m)     = String
    m
    checkRE RE a
    re
            | RE a -> Bool
    forall a. RE a -> Bool
    nullable RE a
    re   = String
    ""
            | Bool
    otherwise     = String
    "Input must match " String -> ShowS
    forall a. [a] -> [a] -> [a]
    ++ RE a -> String
    forall a. (Eq a, Show a) => RE a -> String
    printRE RE a
    re

    -- ------------------------------------------------------------

    -- |
    -- Constructs a string representation of a regular expression.
    --
    --    * 1.parameter re :  a regular expression
    --
    --    - returns : the string representation of the regular expression

    printRE :: (Eq a, Show a) => RE a -> String
    printRE :: forall a. (Eq a, Show a) => RE a -> String
    printRE RE a
    re'
        = String
    "( " String -> ShowS
    forall a. [a] -> [a] -> [a]
    ++ RE a -> String
    forall {a}. (Show a, Eq a) => RE a -> String
    printRE1 RE a
    re' String -> ShowS
    forall a. [a] -> [a] -> [a]
    ++ String
    " )"
          where
          -- printRE1 :: (Eq a, Show a) => RE a -> String
          printRE1 :: RE a -> String
    printRE1 RE a
    re = case RE a
    re of
              RE_ZERO String
    m                             -> String
    "ERROR: " String -> ShowS
    forall a. [a] -> [a] -> [a]
    ++ String
    m
              RE a
    RE_UNIT                               -> String
    ""
              RE_SYM a
    sym                            -> a -> String
    forall a. Show a => a -> String
    show a
    sym
              RE a
    RE_DOT                                -> String
    "."
              RE_REP RE a
    e
                  | RE a -> Bool
    forall a. RE a -> Bool
    isSingle RE a
    e                      -> RE a -> String
    printRE1 RE a
    e String -> ShowS
    forall a. [a] -> [a] -> [a]
    ++ String
    "*"
                  | Bool
    otherwise                       -> String
    "(" String -> ShowS
    forall a. [a] -> [a] -> [a]
    ++ RE a -> String
    printRE1 RE a
    e String -> ShowS
    forall a. [a] -> [a] -> [a]
    ++ String
    ")*"
              RE_PLUS RE a
    e
                  | RE a -> Bool
    forall a. RE a -> Bool
    isSingle RE a
    e                      -> RE a -> String
    printRE1 RE a
    e String -> ShowS
    forall a. [a] -> [a] -> [a]
    ++ String
    "+"
                  | Bool
    otherwise                       -> String
    "(" String -> ShowS
    forall a. [a] -> [a] -> [a]
    ++ RE a -> String
    printRE1 RE a
    e String -> ShowS
    forall a. [a] -> [a] -> [a]
    ++ String
    ")+"
              RE_OPT RE a
    e
                  | RE a -> Bool
    forall a. RE a -> Bool
    isSingle RE a
    e                      -> RE a -> String
    printRE1 RE a
    e String -> ShowS
    forall a. [a] -> [a] -> [a]
    ++ String
    "?"
                  | Bool
    otherwise                       -> String
    "(" String -> ShowS
    forall a. [a] -> [a] -> [a]
    ++ RE a -> String
    printRE1 RE a
    e String -> ShowS
    forall a. [a] -> [a] -> [a]
    ++ String
    ")?"
              RE_SEQ RE a
    e1 (RE_REP RE a
    e2)
                  | RE a
    e1 RE a -> RE a -> Bool
    forall a. Eq a => a -> a -> Bool
    == RE a
    e2                        -> RE a -> String
    printRE1 (RE a -> RE a
    forall a. RE a -> RE a
    RE_PLUS RE a
    e1)
              RE_SEQ RE a
    e1 (RE_SEQ (RE_REP RE a
    e2) RE a
    e3)
                  | RE a
    e1 RE a -> RE a -> Bool
    forall a. Eq a => a -> a -> Bool
    == RE a
    e2                        -> RE a -> String
    printRE1 (RE a -> RE a -> RE a
    forall a. RE a -> RE a -> RE a
    RE_SEQ (RE a -> RE a
    forall a. RE a -> RE a
    RE_PLUS RE a
    e1) RE a
    e3)
              RE_SEQ RE a
    e RE a
    f
                  | RE a -> Bool
    forall a. RE a -> Bool
    isAlt RE a
    e  Bool -> Bool -> Bool
    && Bool -> Bool
    not (RE a -> Bool
    forall a. RE a -> Bool
    isAlt RE a
    f)       -> String
    "(" String -> ShowS
    forall a. [a] -> [a] -> [a]
    ++ RE a -> String
    printRE1 RE a
    e String -> ShowS
    forall a. [a] -> [a] -> [a]
    ++ String
    ") , " String -> ShowS
    forall a. [a] -> [a] -> [a]
    ++ RE a -> String
    printRE1 RE a
    f
                  | Bool -> Bool
    not (RE a -> Bool
    forall a. RE a -> Bool
    isAlt RE a
    e) Bool -> Bool -> Bool
    && RE a -> Bool
    forall a. RE a -> Bool
    isAlt RE a
    f        -> RE a -> String
    printRE1 RE a
    e String -> ShowS
    forall a. [a] -> [a] -> [a]
    ++ String
    " , (" String -> ShowS
    forall a. [a] -> [a] -> [a]
    ++ RE a -> String
    printRE1 RE a
    f String -> ShowS
    forall a. [a] -> [a] -> [a]
    ++ String
    ")"
                  | RE a -> Bool
    forall a. RE a -> Bool
    isAlt RE a
    e  Bool -> Bool -> Bool
    && RE a -> Bool
    forall a. RE a -> Bool
    isAlt RE a
    f             -> String
    "(" String -> ShowS
    forall a. [a] -> [a] -> [a]
    ++ RE a -> String
    printRE1 RE a
    e String -> ShowS
    forall a. [a] -> [a] -> [a]
    ++ String
    ") , (" String -> ShowS
    forall a. [a] -> [a] -> [a]
    ++ RE a -> String
    printRE1 RE a
    f String -> ShowS
    forall a. [a] -> [a] -> [a]
    ++ String
    ")"
                  | Bool
    otherwise                       -> RE a -> String
    printRE1 RE a
    e String -> ShowS
    forall a. [a] -> [a] -> [a]
    ++ String
    " , " String -> ShowS
    forall a. [a] -> [a] -> [a]
    ++ RE a -> String
    printRE1 RE a
    f
              RE_ALT RE a
    RE_UNIT RE a
    f                      -> RE a -> String
    printRE1 (RE a -> RE a
    forall a. RE a -> RE a
    RE_OPT RE a
    f)
              RE_ALT RE a
    e RE a
    f
                  | RE a -> Bool
    forall a. Eq a => RE a -> Bool
    isSeq RE a
    e  Bool -> Bool -> Bool
    && Bool -> Bool
    not (RE a -> Bool
    forall a. Eq a => RE a -> Bool
    isSeq RE a
    f)       -> String
    "(" String -> ShowS
    forall a. [a] -> [a] -> [a]
    ++ RE a -> String
    printRE1 RE a
    e String -> ShowS
    forall a. [a] -> [a] -> [a]
    ++ String
    ") | " String -> ShowS
    forall a. [a] -> [a] -> [a]
    ++ RE a -> String
    printRE1 RE a
    f
                  | Bool -> Bool
    not (RE a -> Bool
    forall a. Eq a => RE a -> Bool
    isSeq RE a
    e) Bool -> Bool -> Bool
    && RE a -> Bool
    forall a. Eq a => RE a -> Bool
    isSeq RE a
    f        -> RE a -> String
    printRE1 RE a
    e String -> ShowS
    forall a. [a] -> [a] -> [a]
    ++ String
    " | (" String -> ShowS
    forall a. [a] -> [a] -> [a]
    ++ RE a -> String
    printRE1 RE a
    f String -> ShowS
    forall a. [a] -> [a] -> [a]
    ++ String
    ")"
                  | RE a -> Bool
    forall a. Eq a => RE a -> Bool
    isSeq RE a
    e  Bool -> Bool -> Bool
    && RE a -> Bool
    forall a. Eq a => RE a -> Bool
    isSeq RE a
    f             -> String
    "(" String -> ShowS
    forall a. [a] -> [a] -> [a]
    ++ RE a -> String
    printRE1 RE a
    e String -> ShowS
    forall a. [a] -> [a] -> [a]
    ++ String
    ") | (" String -> ShowS
    forall a. [a] -> [a] -> [a]
    ++ RE a -> String
    printRE1 RE a
    f String -> ShowS
    forall a. [a] -> [a] -> [a]
    ++ String
    ")"
                  | Bool
    otherwise                       -> RE a -> String
    printRE1 RE a
    e String -> ShowS
    forall a. [a] -> [a] -> [a]
    ++ String
    " | " String -> ShowS
    forall a. [a] -> [a] -> [a]
    ++ RE a -> String
    printRE1 RE a
    f

          isSingle :: RE a -> Bool
          isSingle :: forall a. RE a -> Bool
    isSingle (RE_ZERO String
    _)    = Bool
    True
          isSingle RE a
    RE_UNIT        = Bool
    True
          isSingle (RE_SYM a
    _)     = Bool
    True
          isSingle RE a
    _              = Bool
    False

          isSeq :: (Eq a) => RE a -> Bool
          isSeq :: forall a. Eq a => RE a -> Bool
    isSeq (RE_SEQ RE a
    e1 (RE_REP RE a
    e2))
              | RE a
    e1 RE a -> RE a -> Bool
    forall a. Eq a => a -> a -> Bool
    == RE a
    e2          = Bool
    False  -- is transformed back into RE_PLUS
          isSeq (RE_SEQ RE a
    _ RE a
    _)      = Bool
    True
          isSeq RE a
    _                 = Bool
    False

          isAlt :: RE a -> Bool
          isAlt :: forall a. RE a -> Bool
    isAlt (RE_ALT RE a
    RE_UNIT RE a
    _)= Bool
    False  -- is transformed back into a RE_OPT
          isAlt (RE_ALT RE a
    _ RE a
    _)      = Bool
    True
          isAlt RE a
    _                 = Bool
    False