2
\$\begingroup\$

I have a piece of parsec code that parses a unit optionally followed by ?, + or *. Depending on which type I build my Regex (this is a part of a regex parser) as follows:

factor = unit >>= (\x -> (try (char '?' >> return (Or Epsilon x))
                         <|> try (char '+' >> return (Then x (Star x)))
                         <|> try (char '*' >> return (Star x))
                         <|> return x))

This is ugly, so is the do version:

factor = do
    x <- unit
    (try (char '?' >> return (Or Epsilon x))    <|>
     try (char '+' >> return (Then x (Star x))) <|>
     try (char '*' >> return (Star x))          <|>
     return x)

Please help me make it simpler.

\$\endgroup\$
5
\$\begingroup\$

Whenever I find myself using a lambda, I usually replace it with a local definition:

factor = unit >>= factor'
 where
  factor' x
    =  try (char '?' >> return (Or Epsilon x))
   <|> try (char '+' >> return (Then x (Star x)))
   <|> try (char '*' >> return (Star x))
   <|> return x

Since you only need to look at one character to pick the right branch, you don't need to use try everywhere:

factor = unit >>= factor'
 where
  factor' x
    =  (char '?' >> return (Or Epsilon x))
   <|> (char '+' >> return (Then x (Star x)))
   <|> (char '*' >> return (Star x))
   <|> return x

Finally, we can get rid of the extra parens by using *> instead of >>, and we can replace return with pure:

factor = unit >>= factor'
 where
  factor' x
    =  char '?' *> pure (Or Epsilon x)
   <|> char '+' *> pure (Then x (Star x))
   <|> char '*' *> pure (Star x)
   <|> pure x

This works because *> has higher precedence than <|> which has higher precedence than >>.

I find this easier to read. We've restricted the bulk of our code to Applicative operations, and we only need to use Monadic bind at the beginning where factor' has a direct dependency on unit.

EDIT: We don't need try anymore because char x only consumes a character if the next character in the input stream matches x. Furthermore, each of your branches can either completely match or it can completely fail, and there's no danger of overlap between rules. As an example, here's a simple parser that, like yours, has simple match-or-fail parsers that consume only one character and do not overlap:

data Foo = One | Zero
  deriving (Eq, Show)

foo =  char '1' *> pure One
   <|> char '0' *> pure Zero

If we decide to add a new rule that does overlap, we'll have a problem:

data Foo = One | Zero | Ten
  deriving (Eq, Show)

foo =  char '1' *> pure One
   <|> char '0' *> pure Zero
   <|> char '1' *> char '0' *> pure Ten

Now our first and last rule overlap! We can never successfully parse a Ten:

> parse foo "" "1"
Right One
> parse foo "" "10"
Right One

One's first instinct might be to switch the order of the rules, but this just introduces a new problem:

foo =  char '1' *> char '0' *> pure Ten
   <|> char '0' *> pure Zero
   <|> char '1' *> pure One

> parse foo "" "10"
Right Ten
> parse foo "" "1"
Left (line 1, column 2):
unexpected end of input
expecting "0"

Since the first char '1' has already consumed a character, we've committed to that branch. This is the case where you want to use try; where you might need to backtrack after initially committing to some rule that consumes input:

foo =  try (char '1' *> char '0' *> pure Ten)
   <|> char '0' *> pure Zero
   <|> char '1' *> pure One

> parse foo "" "0"
Right Zero
> parse foo "" "1"
Right One
> parse foo "" "10"
Right Ten

Because many parsers are more complicated than char, it can be easy to just add try without thinking. This can make your parser less efficient because it may have to backtrack many times before it makes progress. It can be worth your time to investigate whether a try is really necessary.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.