Project Inquiry
Published on

many1Till: Custom Generic Combinator for Parsec

Haskell’s Parsec library ships with a generic combinator named manyTill:

manyTill :: (Stream s m t) =>
             ParsecT s u m a ->
             ParsecT s u m end ->
             ParsecT s u m [a]
manyTill p end = scan
  where scan =  do { end; return [] }
            <|> do { x <- p; xs <- scan; return (x:xs) }

According the Parsec’s documentation, manyTill applies the parser p (first argument) zero or more times until parser end (second argument) succeeds.

manyTill is a valuable tool to implement common language patterns. But, there are situations in which manyTill is not sufficient – imagine an imperative language that supports the following construct: if [condition] then [statements] endif, where [statements] signifies a non-empty list of statements (i.e., valid if constructs must contain at least one statement). It would be nice, to have another generic combinator to encapsulate this pattern.

This is where many1Till comes in:

module Text.Parsec.Custom (many1Till) where
import Control.Monad
import Text.Parsec.Prim
import Text.Parsec.Combinator

many1Till :: (Stream s m t, Show end) =>
              ParsecT s u m a ->
              ParsecT s u m end ->
              ParsecT s u m [a]
many1Till p end = do
  notFollowedBy end
  first <- p
  rest <- manyTill p end
  return (first:rest)

Unfortunately, the many1Till combinator isn’t included in the Parsec package. However, as you can see from the code above, it isn’t too difficult to implement it on your own!

Other developers have implemented variants of many1Till before I wrote this article. However, I wasn’t able to get any of the existing implementations to work with the current version (3.1.2) of Parsec.