For some context, I'm trying to write a streaming tokenizer in Haskell and noticed that I was writing a lot of functions with the type signature String -> Maybe Int that attempted to consume the longest possible token matching a particular pattern from the input stream. The pattern might be something like a quoted string literal in JSON.I tried using Parsec for a while to get a prefix matcher, but I kept getting tripped up over what the appropriate userstate is supposed, and what the m argument in ParsecT means. Parsec is probably a strict superset of the functionality that this little library exposes.A Matcher is anything with the type String -> Maybe Int. Matchers are supposed to be greedy and produce the longest prefix that they possibly can. There's also an unenforced property that, in cases where the match is a proper prefix of the input string, adding more characters to the end of a string doesn't extend the prefix. The library also encourages / permits users to write sloppy grammars (for instance using symOrExn) that fail in ugly ways.I could use some helping figuring out how to generalize String -> Maybe Int. I don't know what class I should insist on for the input Eq a => [a] is the first thing that comes to mind, but it might be possible to make something more general than that. As for the output type maybe a type that's constrained to be a monoid or a group? I really just need a notion of zero and the ability to increment for the index. ... although it might also be possible to generalize the notion of a prefix to tree-like structures.I'm hoping to structure this library eventually as a collection of really concrete implementations for a handful of commonly-used text-like types, as well as a generic implementation that can be used in other circumstances. Advice on how to generalize the library is much appreciated.module Text.PrefixMatcher.String whereimport Data.List-- A simple non-generic prefix matching library-- with a few simple combinators---- a Matcher has type (String -> Maybe Int)---- It takes a String and returns a number corresponding-- to the length of the matched prefix.---- The intended use case here is to provide a simple utility-- to help in converting a string to a stream of tokens.---- makeMatcher -- make a matcher for a constant string-- type Matcher = String -> Maybe IntidentityMatcher :: MatcheridentityMatcher str = Just 0makeMatcher :: String -> MatchermakeMatcher spec str = case isPrefixOf spec str of    True -> Just (length spec)    False -> NothingandThen :: Matcher -> Matcher -> MatcherandThen m1 m2 str = ltotal where    l1 = m1 str    ltotal = case l1 of        Nothing -> Nothing        (Just l1) ->            let rest = drop l1 str in            let l2 = m2 str in            case l2 of                Nothing -> Nothing                (Just l2) -> Just (l1 + l2)symOrExn :: Matcher -> Matcher -> MatchersymOrExn m1 m2 str = res where    l1 = m1 str    l2 = m2 str    res = case (l1, l2) of        -- good cases        (Just l1, Nothing) -> Just l1        (Nothing, Just l2) -> Just l2        -- bad cases        (Nothing, Nothing) -> Nothing        -- if you reach this case, the grammar was        -- constructed badly        (Just l1, Just l2) -> error ambiguous matchleftOr :: Matcher -> Matcher -> MatcherleftOr m1 m2 str = result where    l1 = m1 str    l2 = m2 str    result = case (l1, l2) of        (Just l1, _) -> Just l1        (Nothing, Just l2) -> Just l2        (Nothing, Nothing) -> NothingandThenList :: [Matcher] -> MatcherandThenList [] = identityMatcherandThenList [x] = xandThenList (x:xs) = andThen x (andThenList xs)leftOrList :: [Matcher] -> MatcherleftOrList [] = identityMatcherleftOrList [x] = xleftOrList (x:xs) = leftOr x (leftOrList xs)
Simple Prefix Matching Library in Haskell
haskell
Looks like you're on the right track, and this might eventually evolve into a parser, or converge to an existing one.From software engineering point of view, I'd suggest to make Matcher a newtype. This better separates its API from the implementation, and allows to do changes later without breaking the API.Notice these two functions:identityMatcher :: MatcherandThen :: Matcher -> Matcher -> MatcherThis looks very much like a monoid (see also Monoid on Haskell Wiki). And this is what you indeed want from your parser - to be compositional, and to adhere to certain laws: associativity and identity. So it'd make sense to have a Monoid instance for Matcher. Note that then andThenList becomes just mconcat.Another Monoid instance would be leftOr, whose identity would be a matcher that's always failing const Nothing. This is very much like there are two monoids for natural numbers - multiplication with 1 (andThen) and addition with 0 (leftOr). We'll back to this later.The next thing you might consider is to return a value from your matcher. For constant matchers this isn't that useful, but there are multiple reasons why this can be useful:The matchers can optionally parse the input, for example when matching numbers, they can already return the parsed number.Some matchers might match multiple strings, and then it's useful to be able to provide more information about the outcome (for example, regex matched groups).A simple example of the previous point is when calling leftOr, you might want to know which of the matchers matched. Returning a value allows you to distinguish that.Sometimes it's useful if a matcher can depend on the result of the previous match.When you don't need a value, it's easy to disregard/discard it, by using  () as the result.This leads you to creating a monadic interface of your parser. So your type could be something like:newtype Matcher a = Matcher (String -> Maybe (a, Int))`.Interestingly, the inner type is already a monad, corresponding to ReaderT String (WriterT (Sum Int) Maybe a), or alternatively RWST String (Sum Int) () Maybe a. Now standard monadic >> should correspond to andThen and return to the identity matcher. And also mplus to leftOr. Such an interface will give your matchers all the power monads offer with very little effort.Regarding your paragraphI tried using Parsec for a while to get a prefix matcher, but I kept getting tripped up over what the appropriate userstate is supposed, and what the m argument in ParsecT means. Parsec is probably a strict superset of the functionality that this little library exposes.If you don't need any user state, you can just ignore it. And the m argument allows you to run your parser in another monad - ParsecT is a monad transformer. If you don't need it, just use Identity, which is exactly how Parsec is defined.You might be interested in using ReadP, a conceptually simpler parser bundled with GHC.Also this blog post about writing your own, simple parser, might be useful for you.