I am writing an applicative parser, which you can think of as a minimal Parsec, just to educate myself. I got started with the excellent tutorial from this StackOverflow answer. Here is the relevant code:

type Error = String
newtype Parser a = P { unP :: String -> (String, Either Error a) }

instance Functor Parser where
  fmap f (P st) = P $ \stream -> case st stream of
    (res, Left err) -> (res, Left err)
    (res, Right a ) -> (res, Right (f a))

instance Applicative Parser where
  pure a = P (\stream -> (stream, Right a))
  P ff <*> P xx = P $ \stream0 -> case ff stream0 of   -- produce an f
    (stream1, Left err) -> (stream1, Left err)
    (stream1, Right f ) -> case xx stream1 of          -- produce an x
      (stream2, Left err) -> (stream2, Left err)
      (stream2, Right x ) -> (stream2, Right (f x))    -- return (f x)

orElse :: Parser a -> Parser a -> Parser a
orElse (P f1) (P f2) = P $ \stream0 -> case f1 stream0 of
  (stream1, Left err) -> f2 stream1
  (stream1, Right a ) -> (stream1, Right a)

instance Alternative Parser where
  empty = P $ \stream -> (stream, Left "empty")
  (<|>) = orElse

To make the challenge more interesting, I implemented basically the same code (except that Either is replaced by Maybe) using point-free style and here is what I came up with:

-- A minimal applicative parsing library

module Aarsec where

import Data.Functor
import Control.Applicative
import Control.Monad (join)
import Control.Arrow ((***))

newtype Parser a = Parser { parse :: String -> Maybe (a, String) }

instance Functor Parser where
    fmap f (Parser p) = Parser (fmap (f *** id) . p)

instance Applicative Parser where
    pure x = Parser (Just . ((,) x))
    Parser pf <*> q = Parser (join . fmap g . pf) where
        g (f, input) = parse (fmap f q) input

instance Alternative Parser where
    empty = Parser (const Nothing)
    (Parser p) <|> (Parser q) = Parser (foldl1 (<|>) . (<*>) [p, q] . (: []))

It type-checks just fine and I believe it is correct. I am just curious whether there is anything I can improve regarding readability. I am quite satisfied with the definition of fmap, but those of <*> and <|> do seem a bit cryptic.

Full source

  • \$\begingroup\$ While every expression can be made point-free, I'd say that readability is far more important, so I'd be completely happy with readable expressions that aren't point-free.. That said, perhaps somebody will be able to find more readable point-free expression of these operations. \$\endgroup\$ – Petr Pudlák Nov 7 '14 at 21:24
  • 1
    \$\begingroup\$ One way how to simplify the code would be to define newtype Parser a = P { unP :: StateT String (Either Error) a }. Then you get all the above operations for free (in particular if you use GeneralizedNewtypeDeriving). The benefit is that the behavior is then obvious to everybody who knows StateT, without having to inspect the implementation. \$\endgroup\$ – Petr Pudlák Nov 7 '14 at 21:35
  • \$\begingroup\$ Thanks, I'll check out StateT. Just to be clear, I wouldn't write in this style in production code. \$\endgroup\$ – Seri Nov 8 '14 at 14:57

Your Answer

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

Browse other questions tagged or ask your own question.