The S&D parser I was referring to was based on tracking FIRST sets, and provided a nice linear time parsing bound for (infinite) LL(1) grammars. (You can't really compute FOLLOW sets without knowing the grammar has a finite number of productions, but FIRST sets work perfectly well with infinite grammars.) By doing so you can transform parsing into more or less a series of map lookups for dispatch. You need to carry a set of all characters that a parser will consume in the case of legal parses, and whether or not the parser accepts the empty parse. http://www.cse.chalmers.se/~rjmh/afp-arrows.pdf mentions this style of FIRST-set tracking parser as the original motivation for arrows. Of course, they didn't see fit to stop puttering around with parsers after 1998, so referring to "the S&D parser" is quite ambiguous! =) -Edward On Wed, Dec 21, 2016 at 4:00 AM, Henrik Nilsson < Henrik.Nilsson@nottingham.ac.uk> wrote:

Hi Edward, CC Others,

On 12/21/2016 05:15 AM, Edward Kmett wrote:

...

Arrows haven't seen much love for a while. In part this is because many of the original applications for arrows have been shown to be perfectly suited to being handled by Applicatives. e.g. the Swiestra/Duponcheel parser that sort of kickstarted everything.

Thanks for a very thorough reply.

A quick side-remark: a parser library due to Sweistra (and maybe Dupncheel, I can't remember) used an applicative structure a long time before applicatives became apkicatives and even idioms. (I used a variation of this library myself for the Freja compiler around 1995. Freja was part of my PhD work and was close to what Haskell looked like at the time.)

I've never used arrows for parsing, or seen the need for arrows in that context, but find arrows a very good fit for many EDSLs, including stream-processing/FRP/Yampa of course, along with other circuit-like abstractions, which I'd say were the original motivation for arrows. Altenkirch have also used arrow-like notions in the context of quantum computation. More recently for probabilistic programming and Bayesian inference. Except then that the current hard-wired "pseudo- product" in particular often gets in the way. Along with the fact that there is no good support for constrained arrows (or monads).

Best,

/Henrik

This message and any attachment are intended solely for the addressee and may contain confidential information. If you have received this message in error, please send it back to me, and immediately delete it. Please do not use, copy or disclose the information contained in this message or in any attachment. Any views or opinions expressed by the author of this email do not necessarily reflect the views of the University of Nottingham.

This message has been checked for viruses but the contents of an attachment may still contain software viruses which could damage your computer system, you are advised to perform your own checks. Email communications with the University of Nottingham may be monitored as permitted by UK legislation.