A new Swift video series exploring functional programming and more.
#60 • Monday Jun 3, 2019 • Subscriber-only

Composable Parsing: Flat-Map

The map function on parsers is powerful, but there are still a lot of things it cannot do. We will see that in trying to solve some of its limitations we are naturally led to our old friend the flatMap function.

This episode builds on concepts introduced previously:

#60 • Monday Jun 3, 2019 • Subscriber-only

Composable Parsing: Flat-Map

The map function on parsers is powerful, but there are still a lot of things it cannot do. We will see that in trying to solve some of its limitations we are naturally led to our old friend the flatMap function.

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!

See subscription optionsorLog in

Sign up for our weekly newsletter to be notified of new episodes, and unlock access to any subscriber-only episode of your choosing!

Sign up for free episode

Introduction

Hopefully this is tickling something in the back of your mind because it’s something we devoted 5 entire Point-Free episodes to. We really hammered on the idea of having generic types that are capable of chaining their computations together. We found out that the natural solution to this “chaining” or “sequencing” was none other than flatMap, which is defined on arrays and optionals in the standard library, but the idea goes far, far beyond just what Swift gives us. So, let’s see what it would look like for our Parser type.

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. We have previously devoted 3 entire episodes (part 1, part 2, part 3) to zip. In those episodes we showed that those operations are very general, and go far beyond what Swift gives us in the standard library for arrays and optionals.

    Define zip and flatMap on the Parser type. Start by defining what their signatures should be, and then figure out how to implement them in the simplest way possible. What gotcha to be on the look out for is that you do not want to consume any of the input string if the parser fails.

  2. Use the zip function defined in the previous exercise to construct a Parser<Coordinate> for parsing strings of the form "40.446° N, 79.982° W". You may want to define zip overloads that work on more than 2 parsers at a time.


References

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

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

  • 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
Flat-map on Parser
01:15
Flat-map backtracking
03:11
A flat-map nesting problem
06:16
Till next time
13:40