Maths - Category Theory - Parser

Monadic parsers take a string and return an abstract syntax tree (along with the unused part of the string).

There would typically be many parsers each able to match a particular part of the syntax.

A monadic parser has the type:

String -> (String,ast)

where 'ast' is the abstract syntax tree returned by the parser.

monadic parser

An error is indicated by an empty list.

Ambiguous grammars can return multiple results.

Monadic parsers can be combined in parallel or series.

monadic parsers in series

monadic parsers in series

Parser Monad

We can introduce a functor which takes any type and turns it into a list of that type. parser
We can draw this as an endo-functor. parser

Parser - Natural Transformations

The unit transform creates a single valued list parser unit
The natural way to create a mult transform is a transform which flatterns a list of lists into a flat list. parser mult


metadata block
see also:

The Idris parser is discussed on this page

Correspondence about this page

Book Shop - Further reading.

Where I can, I have put links to Amazon for books that are relevant to the subject, click on the appropriate country flag to get more details of the book or to buy it from them.

flag flag flag flag flag flag The Princeton Companion to Mathematics - This is a big book that attempts to give a wide overview of the whole of mathematics, inevitably there are many things missing, but it gives a good insight into the history, concepts, branches, theorems and wider perspective of mathematics. It is well written and, if you are interested in maths, this is the type of book where you can open a page at random and find something interesting to read. To some extent it can be used as a reference book, although it doesn't have tables of formula for trig functions and so on, but where it is most useful is when you want to read about various topics to find out which topics are interesting and relevant to you.


Terminology and Notation

Specific to this page here:


This site may have errors. Don't use for critical systems.

Copyright (c) 1998-2024 Martin John Baker - All rights reserved - privacy policy.