A video series exploring functional programming and Swift.
#64 • Monday Jul 8, 2019 • Subscriber-only

# Parser Combinators: Part 3

Now that we’ve looked at how to parse multiple values given a single parser, let’s try to parse a single value using multiple parsers! And after defining a bunch of these parser combinators we’ll finally be able to ask: “what’s the point!?”

This episode builds on concepts introduced previously:

#64 • Monday Jul 8, 2019 • Subscriber-only

# Parser Combinators: Part 3

Now that we’ve looked at how to parse multiple values given a single parser, let’s try to parse a single value using multiple parsers! And after defining a bunch of these parser combinators we’ll finally be able to ask: “what’s the point!?”

This episode builds on concepts introduced previously:

### Subscribe to Point‑Free

This episode is for subscribers only. To access it, and all past and future episodes, become a subscriber today!

## Introduction

The `zeroOrMore` parser combinator is now a function that takes two parsers as input and returns a third parser as output. This higher-order parser is unlocking the ability to parse gigantic strings with very work. This is starting to seem extremely powerful and maybe we’re starting to see “the point” of parser combinators.

#### Subscribe to Point-Free

👋 Hey there! Does this episode sound interesting? Well, then you may want to subscribe so that you get access to this episodes and more!

## Exercises

1. Many higher-order functions on `Array` are also useful to define on `Parser` as parser combinators. As an example, define a `compactMap` with the following signature: `((A) -> B?) -> (Parser<A>) -> Parser<B>`.

2. Define a `filter` parser combinator with the following signature: `((A) -> Bool) -> (Parser<A>) -> Parser<B>`.

3. Define `filter` in terms of `compactMap`.

4. Define an `either` parser combinator with the following signature: `((A) -> Either<B, C>) -> (Parser<A>) -> Parser<Either<B, C>>`.

5. Redefine the `double` parser using parser combinators like `oneOf` to be more resilient than the one we’ve currently defined. It should handle positive and negative numbers and ignore trailing decimals. I.e. it should parse `"1"` as `1.0`, `"-42"` as `-42.0`, `"+50"` as `50.0`, and “-123.456.789” as `-123.456` without consuming `".789"`.

## References

• #### Combinators

Daniel Steinberg • Friday Sep 14, 2018

Daniel gives a wonderful overview of how the idea of “combinators” infiltrates many common programming tasks.

Just as with OO, one of the keys to a functional style of programming is to write very small bits of functionality that can be combined to create powerful results. The glue that combines the small bits are called Combinators. In this talk we’ll motivate the topic with a look at Swift Sets before moving on to infinite sets, random number generators, parser combinators, and Peter Henderson’s Picture Language. Combinators allow you to provide APIs that are friendly to non-functional programmers.

• #### Parser Combinators in Swift

Yasuhiro Inami • Monday May 2, 2016

In the first ever try! Swift conference, Yasuhiro Inami gives a broad overview of parsers and parser combinators, and shows how they can accomplish very complex parsing.

Parser combinators are one of the most awesome functional techniques for parsing strings into trees, like constructing JSON. In this talk from try! Swift, Yasuhiro Inami describes how they work by combining small parsers together to form more complex and practical ones.

• #### Regex

Alexander Grebenyuk • Saturday Aug 10, 2019

This library for parsing regular expression strings into a Swift data type uses many of the ideas developed in our series of episodes on parsers. It’s a great example of how to break a very large, complex problem into many tiny parsers that glue back together.

• #### Learning Parser Combinators With Rust

Bodil Stokke • Thursday Apr 18, 2019

A wonderful article that explains parser combinators from start to finish. The article assumes you are already familiar with Rust, but it is possible to look past the syntax and see that there are many shapes in the code that are similar to what we have covered in our episodes on parsers.

• #### Sparse

John Patrick Morgan • Thursday Jan 12, 2017

A parser library built in Swift that uses many of the concepts we cover in our series of episodes on parsers.

Sparse is a simple parser-combinator library written in Swift.

• #### parsec

Daan Leijen, Paolo Martini, Antoine Latter

Parsec is one of the first and most widely used parsing libraries, built in Haskell. It’s built on many of the same ideas we have covered in our series of episodes on parsers, but using some of Haskell’s most powerful type-level features.

• #### Ledger Mac App: Parsing Techniques

Chris Eidhof & Florian Kugler • Friday Aug 26, 2016

In this free episode of Swift talk, Chris and Florian discuss various techniques for parsing strings as a means to process a ledger file. It contains a good overview of various parsing techniques, including parser grammars.

###### Chapters
Introduction
00:05
Values from multiple parsers
00:30
Values from even more parsers
06:30
What’s the point?
10:57
Parsing a complex, ad hoc format
12:16
Conclusion
18:14