CODEWITHSUNDEEP
haskell
Kris
Kris

Reputation: 23

Write a function that returns true for regular expressions that match the empty string in Haskell

This is the code: 

import Data.List
data RE sym
    = Never             -- match no strings
    | Empty             -- match empty string
    | Symbol sym        -- match singleton string
    | RE sym :+ RE sym  -- choice
    | RE sym :* RE sym  -- concatenation
    | Repeat (RE sym)   -- repeat zero or more times
    | Plus (RE sym)     -- repeat one or more times
    deriving (Show, Eq)

infixr 6 :+, .+.
infixr 7 :*, .*.

data ABC = A | B | C deriving (Show, Eq, Ord)

Write a function matchEmpty that returns true for regular expressions that match the empty string.

matchEmpty :: RE sym -> Bool
matchEmpty = ???

This is What I write: 

matchEmpty (Empty :+ _) = True
matchEmpty Empty = True
matchEmpty Never = False
matchEmpty (_) = False
matchEmpty(Repeat(_)) = True

but i still got error for some cases: 

Testing matchEmpty
INCORRECT: A*
       wanted: True
       got:    False

INCORRECT: (A|e)+
       wanted: True
       got:    False

INCORRECT: (AB)*
       wanted: True
       got:    False

I am so lost for this one, Please help me to do this one, I am a beginner in Haskell and try to learn it by myself. Does there need recursion or something else to do this problem?

Upvotes: 0

Views: 508

Answers (1)

that other guy
that other guy

Reputation: 123580

It looks like the problems you have are that:

  1. Repeat (Symbol A) is incorrectly marked false.

    This is because patterns are matched from top to bottom, so matchEmpty (_) = False catches it instead of matchEmpty(Repeat(_)) = True

  2. Plus (x) is incorrectly always marked as false.

    This should be true when x matches the empty string (yes, this would be a recursive check).

  3. x :- y is correctly marked as true when x is Empty, but incorrectly fails these cases:

    Symbol A :+ Empty -- the other side is empty

    (Repeat _) :+ (Empty :+ Empty) -- neither side is Empty itself, but still matches the empty string (this would also be a recursive check)

  4. x :* y is always incorrectly marked false. This should be true when both sides can match the empty string (also recursive).

You can give it another go now with those observations.

For a spoiler, here's my suggestion:

matchEmpty Empty = True
matchEmpty (Repeat _) = True
matchEmpty (Plus x) = matchEmpty x
matchEmpty (x :+ y) = matchEmpty x || matchEmpty y
matchEmpty (x :* y) = matchEmpty x && matchEmpty y
matchEmpty _ = False

Upvotes: 2

Related Questions