# Readability of a point-free applicative parser

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.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

• 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. – Petr Pudlák Nov 7 '14 at 21:24
• 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. – Petr Pudlák Nov 7 '14 at 21:35
• Thanks, I'll check out StateT. Just to be clear, I wouldn't write in this style in production code. – Seri Nov 8 '14 at 14:57