Hacker News Reader

Comment by alexvitkov | Hacker News Reader

No, a parser is not an functor, an applicative or god forbid a monad.

The ratio of the effort academics spend thinking formally about parsers relatively to how often you need to write a parser is probably 50:1. Not as bad as sorting algorithms, where they take up 50% of a CS curriculum, but still pretty bad.

A parser reads an array of tokens and spits out a tree. You can write one for any relatively sane grammar by hand in two hours if you need to, infix operators & precedence rules included, with the added benefits of decent performance, the ability to have good errors and the peace of mind that you're not confined by what can be neatly expressed by parser combinators.

View on HN

> No, a parser is not an functor, an applicative or god forbid a monad.

Here is my Parser and its Functor, Applicative and Monad definitions:

    newtype Parser s a =
        Parser { runParser :: s -> Either String (s, a) }

    instance Functor (Parser s) where
        fmap :: (a -> b) -> Parser s a -> Parser s b
        fmap f (Parser run) = Parser $ \s -> (\(s',a) -> (s', f a)) <$> run s

    instance Applicative (Parser s) where

        pure :: a -> Parser s a
        pure x = Parser $ \s -> Right (s, x)

        (<*>) :: Parser s (a -> b) -> Parser s a -> Parser s b
        pf <*> px = Parser $ \s ->
            case runParser pf s of
                Left l        -> Left l
                Right (s', f) ->
                    case runParser px s' of
                        Left l         -> Left l
                        Right (ss', a) -> Right (ss', f a)

    instance Monad (Parser s) where
        return :: a -> Parser s a
        return = pure

        (>>=) :: Parser s a -> (a -> Parser s b) -> Parser s b
        ma >>= f = Parser $ \s ->
            case runParser ma s of
                Left l        -> Left l
                Right (s', a) -> runParser (f a) s'

> No, a parser is not an functor, an applicative or god forbid a monad.

What? The post gives a proof of how they are, and you just assert the result is wrong with no evidence whatsoever.

GP isn’t actually saying that a parser isn’t a functor. They’re loudly and performatively saying that they don’t care.

Well, the post shows that the given function is a functor.

However, I might argue that calling the function a "parser" is a bit of a stretch. In a toy, abstract sense, sure, and maybe there's a formal definition of "parser" that it conforms to, but just because it's named a "parser" doesn't really mean that's all a "parser" is when we talk about it in other contexts.

Parsers, to me, in a professional software engineering sense, need to have error handling, performance and memory guarantees, the ability to do "best case" parsing and return a number of errors all at once, and so on.

So one interpretation of "No, a parser is not a functor", despite the proof here, is "I reject that the toy example here being called a parser is sufficiently close to what I would call a 'parser', and what a 'parser' is to me is not a functor [because of these other things not captured by the example]".

I tend to agree with that. Haskellers don't have an exclusive claim to terminology, and I don't think "parser" is defined formally enough that we all must agree on it.

A parser is not a functor, you can represent a parser as a frankensteined combination of functors. What I'm saying is that you probably shouldn't.

Can you say why? I'm struggling to understand your point.

My point is that parsers structured as a combination of parser combinators are worse than hand-rolled parsers, because:

1. It's not hard to write a parser, and one you it's a problem you don't have to solve very often, so the ungodly amount of time people spend thinking about their formal properties and attempting to come up with new parsing methodologies is baffling. Just witnessing the literature leads people to believe writing a parser by hand is some Herculean task, they don't attempt it, they pick up a weird parser combinator library and have bad time.

2. You're limited by what can be expressed by your parsing methodology of choice, which usually means a context-free grammar. There's even fairly basic formats that can't be expressed as a CFG (https://en.wikipedia.org/wiki/Bencode). If you're sure your requirements won't change, this is not an issue, but if you're not, a custom parser can give you peace of mind, since it can be extended with literally anything thrown your way.

3. Performance

> ...pick up a weird parser combinator library and have bad time.

> You're limited by what can be expressed by your parsing methodology of choice, which usually means a context-free grammar.

I know those two quotes were from separate points, but parser combinators are not limited to CFGs; pretty much any recursive-descent parser (parser combinators included) will have zero issue with your Bencode example.

I pretty much agree with the rest of your post, except for the fact that it's unusual for an entire year to go by in which I don't write a parser.

Also, some parser libraries (though not parser combinators) can statically find ambiguities in grammar definitions, which can be helpful if you are designing the language.

I agree with this

I struggled with this formal bullshit despite having exp. with handwritten parsers for PL.

This hand-written parser is a functor:

    data Parser a = Parser { actualParser :: HandWrittenParser }
    
    instance Functor Parser where
      fmap _ p = Parser $ actualParser p
    
    instance Applicative Parser where
      pure _ = Parser undefined
      _ <*> p = Parser $ actualParser p
    
    instance Monad Parser where
      p >>= _ = Parser $ actualParser p
      
    parse :: String -> Parser a -> Either ParseError a
    parse str p = fmap unsafeCoerce $ handWrittenParse str $ actualParser p

More things are parsers that that though. Here's an article that gives that kind of perspective, https://lexi-lambda.github.io/blog/2019/11/05/parse-don-t-va...

A parser isn't a functor in much the same way as a list isn't a functor.

The sorting algorithms are just a tool in learning about algorithm complexity.

If that's the case, it would probably be enough to show O(N^2) algorithm, a O(N*logN) one, and maybe throw in Bogo sort for fun.

Even if it's just a learning exercise, if the kids are gonna have to study these algorithms in depth, surely you could pick something more useful as an example to show them, rather than the 10th NlogN sorting algorithm.

That's what we did. If you actually spent 50% of your CS degree on learning every nlogn sort, then you went to a particularly bad CS program.

Have written parsers, can confirm.

(With the maybe one exception that "reads an array of tokens" and "spits out a tree" may be interpreted loosely if sufficiently high performance is required.)

In my experience the output is always a heterogenous tree of nodes, even if sufficient performance is required.

Which is not great since that's quite literally the worst possible data structure imaginable for modern CPUs, but I'm not aware of any other sane way to represent the common outputs of a parser - ASTs, GUI layout trees.

Parsers like simdjson output a sequence of tuples, not trees. You can do a lot with that even if you need a tree in the end because you can filter the stream first, thus using very little memory until you get to the part you're interested in, which you then hydrate by constructing the equivalent tree using just that part of the stream.

https://www.cs.cornell.edu/~asampson/blog/flattening.html

Flattened AST. Not conceptually different, but a much better performance of implementation.

> A parser reads an array of tokens and spits out a tree. [...]

A parser need not perform I/O -- it need not "read" the tokens. It can function with just normal function arguments only -- it can be pure.

"Read" does not imply I/O, you "read" from memory as well

The distinction is important. "Reading from memory" (function arguments) is pure, but doing I/O is not. A pure parser can be a functor, while one that does I/O not so much.

You misspelled "curriculum".

Reply on news.ycombinator.com