Video #60: Composable Parsing: Flat‑Map

Episode: Video #60 Date: Jun 3, 2019 Access: Members Only 🔒 URL: https://www.pointfree.co/episodes/ep60-composable-parsing-flat-map

Description

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.

Video

Cloudflare Stream video ID: 280b18ae94791f712398177ac9ef4d87 Local file: video_60_composable-parsing-flat-map.mp4 *(download with --video 60)*

References

Transcript

— 1:15

Recall that the general shape of flatMap looks something like this: flatMap: ((A) -> M) -> (M<A>) -> M

— 1:25

This says that if you have a function that transforms values into the generic container, then you can lift it to a function between generic containers. This signature is the essence of what it means to chain computations together. For example, when dealing with optionals it allows you to chain together multiple transformations that may fail by returning nil . Or if dealing with asynchronous values it allows you to chain together multiple computations one after the other.

— 1:50

Let’s try to implement this function for our Parser type. Let’s first just get the signature in place: extension Parser { func flatMap(_ f: (A) -> Parser) -> Parser { } }

— 2:09

We know we need to return a Parser , so let’s invoke its initializer, which takes a block representing its run function (inout Substring) -> B? . extension Parser { func flatMap(_ f: (A) -> Parser) -> Parser { return Parser { str -> B? in } } }

— 2:22

What can we do with the pieces that we have at our disposal right now. Well, one simple thing would be to start by running our parser on the input string to get some matching value in A : extension Parser { func flatMap(_ f: (A) -> Parser) -> Parser { return Parser { str in let matchA = self.run(&str) } } }

— 2:33

Now that we have a value in A , though really it’s an optional value, we can try plugging it into our function f which takes values in A . That will give us a parser of things in B : extension Parser { func flatMap(_ f: (A) -> Parser) -> Parser { return Parser { str in let matchA = self.run(&str) let parserB = matchA.map(f) } } }

— 2:47

Now, what can we do with a parser of B values? Well, let’s try running it on our input string again, which will allow us to consume even more of the string: extension Parser { func flatMap(_ f: (A) -> Parser) -> Parser { return Parser { str in let matchA = self.run(&str) let parserB = matchA.map(f) let matchB = parserB?.run(&str) } } }

— 3:00

And because our transform function f is captured by the parser’s run function, we must mark it @escaping since it escapes the lifetime of a call to flatMap . extension Parser { func flatMap(_ f: @escaping (A) -> Parser) -> Parser { return Parser { str in let matchA = self.run(&str) let parserB = matchA.map(f) let matchB = parserB?.run(&str) } } }

— 3:06

And we now have an optional value in B , which is exactly what we need to return from our parser, so maybe we’re done! extension Parser { func flatMap(_ f: @escaping (A) -> Parser) -> Parser { return Parser { str in let matchA = self.run(&str) let parserB = matchA.map(f) let matchB = parserB?.run(&str) return matchB } } } Flat‑map backtracking

— 3:11

However, this is subtly wrong, and it’s an important point to make. We’ve alluded to this a few times so far when building up parsers, but here we are seeing it much more clearly. The problem is that we should not consume any of the input string if parsing fails. This is very important so that if parsing something fails we could potentially back up and try another parser. But that wouldn’t be possible if the first failed parser consumed its input.

— 3:36

So, let’s make flatMap a bit more resilient by not consuming any of the input if any of the parsing fails. To do this we need to keep track of a copy of the input string so that we can reset it in case something fails. Luckily, since we are dealing with the Substring type, this copy should be very cheap: extension Parser { func flatMap(_ f: @escaping (A) -> Parser) -> Parser { return Parser { str in let original = str let matchA = self.run(&str) let parserB = matchA.map(f) let matchB = parserB?.run(&str) return matchB } } }

— 3:58

Then, if the last parser run fails, we can reset the input string back to the copy we made at the beginning of parsing and return nil . This will make sure that the input string is not consumed at all if either of the parsers fail: extension Parser { func flatMap(_ f: @escaping (A) -> Parser) -> Parser { return Parser { str in let original = str let matchA = self.run(&str) let parserB = matchA.map(f) guard let matchB = parserB?.run(&str) else { str = original return nil } return matchB } } }

— 4:17

And this is the final form of our flatMap ! It was a bit tricky, but this is the correct way to implement it. So, how can we use it? Well, immediately it gives us a super nice way to implement our northSouth parser in the technically correct way. Currently we have a Parser<Optional<Double>> , which isn’t correct: let northSouth = char .map { $0 == "N" ? Optional(1.0) : $0 == "S" ? -1 : nil } // Parser<Optional<Double>>

— 4:27

We can fix this very easily by updating our logic to return parsers instead of optionals, and change our map into a flatMap : let northSouth = char .flatMap { $0 == "N" ? always(1.0) : $0 == "S" ? always(-1) : .never } // Parser<Double>

— 4:53

And now we get an honest parser of doubles where previously, with map , we were seeing a nested parser.

— 5:04

When we compare our new northSouth parser with our from-scratch eastWest parser the difference is clear. let northSouth = char .flatMap { $0 == "N" ? always(1.0) : $0 == "S" ? always(-1) : .never } // Parser<Double> let eastWest = Parser<Double> { str in guard let cardinal = str.first, cardinal == "E" || cardinal == "W" else { return nil } str.removeFirst(1) return cardinal == "E" ? 1 : -1 } // Parser<Double>

— 5:12

Let’s update eastWest in the same manner. let eastWest = char .flatMap { $0 == "E" ? always(1.0) : $0 == "W" ? always(-1) : .never } // Parser<Double>

— 5:43

The from-scratch parser did a lot more work that the flatMap -based parser because the flatMap -based parser can leverage all the work the char parser does and focus just on whether or not the character matched is a cardinal value. And the always and never parsers, which previously seemed like absurd ideas, naturally allow us to flatMap into success or failure.

— 6:04

There is a ton more that flatMap can do, and we’ll be seeing it more and more as we build up complex parsers, but that right there is a pretty good example that was motivated by a real world example. A flat‑map nesting problem

— 6:16

But even with the super useful map and flatMap there are things that we can’t do, or well we can do them but they are super cumbersome.

— 6:49

To see this, let’s go back to our example from past episodes where we were trying to parse some latitude and longitude coordinates: "40.446° N, 79.982° W"

— 7:04

We can technically parse this with map and flatMap , but it’s going to be really messy. Let’s try it out.

— 7:13

First we parse off a double for the latitude: double

— 7:19

Then we parse off a literal for the degree sign. The fact that we are describing this as “then” should make it clear that flatMap can help us since flatMap is specifically tuned for chaining things together. So let’s try that: double .flatMap { lat in literal("° ") }

— 8:01

Then we want to parse off the northSouth sign for the latitude, so again we can use flatMap : double .flatMap { lat in literal("° ") .flatMap { _ in northSouth } }

— 8:35

Starting to see some nesting now, but let’s power through. Next we want to parse off a literal for the comma that comes after the latitude coordinate: double .flatMap { lat in literal("° ") .flatMap { _ in northSouth .flatMap { latSign in literal(", ") } } }

— 8:56

And then we basically repeat the whole thing again, but this time for the longitude coordinate: let coord = double .flatMap { lat in literal("° ") .flatMap { _ in northSouth .flatMap { latSign in literal(", ") .flatMap { _ in double .flatMap { long in literal("° ") .flatMap { _ in eastWest .map { longSign in Coordinate( latitude: lat * latSign, longitude: long * longSign ) } } } } } } } // Parser<Coordinate>

— 9:57

We’ve done it! We now have a parser of coordinates. And when we use it with some valid data: coord.run("40.6782° N, 73.9442° W") // ( // match Coordinate(latitude: 40.6782, longitude: -73.9442), // rest "" // ) We get a value back.

— 10:14

And if we feed it invalid data: coord.run("40.6782° Z, 73.9442° W") // (nil, rest "40.6782° Z, 73.9442° W")

— 10:21

After all of this nesting and flat-mapping we finally parsed everything necessary to construct a coordinate. This is looking really gnarly, but why did it turn out like this? I thought flatMap was supposed to be great for chaining computations together and could even flatten nestings like this down to one level. In fact, you often hear that flatMap is a solution to the dreaded “callback hell” problem.

— 10:59

While it is true that flatMap can help with the nesting problem, it does so in a very specific way. This is something we explored deeply in our 5-part series of episodes on flatMap ( 1 2 3 4 5 ). The core of the idea that while flatMap is a universal way of chaining together computations, it does so in a so-called “context dependent” manner. That is, each computation has access to the data from the previous computation. This is powerful because it allows us customize later computations by the results from earlier computations, but in this case it’s too powerful.

— 11:50

If you look closely, the parsers we chain do not actually depend on the results of previous parsings at all. Only at the very end when we construct our Coordinate value do we need all the values at once. This means we are gluing these parsers together in a so-called “context independent” manner, that is we want to run lots of parsers on some input string, but none of them depend on the results of the others: i.e. , they are independent: let coord = double .flatMap { lat in literal("° ") .flatMap { _ in northSouth .flatMap { latSign in literal(", ") .flatMap { _ in double .flatMap { long in literal("° ") .flatMap { _ in eastWest .map { longSign in Coordinate( latitude: lat * latSign, longitude: long * longSign ) } } } } } } } // Parser<Coordinate>

— 12:30

So, what are we to do? Parsing this string with map and flatMap gets the job done, but it isn’t super nice. Luckily, there’s a third operation that sits right in between map and flatMap . We talked about this very topic over the course of 3 entire episodes on Point-Free ( 1 , 2 , 3 ), and it naturally encompasses the idea of “context independence” computation, and it is none other than zip . It allows you to take multiple generic values and combine them into a single generic value. The Swift standard library defines zip on arrays, but in our previous episodes we showed that it makes sense to define zip on many more types, such as optionals, results, validated values, lazy values, and asynchronous values. Till next time

— 13:40

Turns out there is yet another type that supports a zip operation, and it’s our parser type! We’ll take a look at zip on Parser next time! References Combinators Daniel Steinberg • Sep 14, 2018 Daniel gives a wonderful overview of how the idea of “combinators” infiltrates many common programming tasks. Note 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. https://vimeo.com/290272240 Parser Combinators in Swift Yasuhiro Inami • 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. Note 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. https://academy.realm.io/posts/tryswift-yasuhiro-inami-parser-combinator/ Learning Parser Combinators With Rust Bodil Stokke • 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. https://bodil.lol/parser-combinators/ Sparse John Patrick Morgan • Jan 12, 2017 A parser library built in Swift that uses many of the concepts we cover in our series of episodes on parsers. Note Sparse is a simple parser-combinator library written in Swift. https://github.com/johnpatrickmorgan/Sparse 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. http://hackage.haskell.org/package/parsec Parse, don’t validate Alexis King • Nov 5, 2019 This article demonstrates that parsing can be a great alternative to validating. When validating you often check for certain requirements of your values, but don’t have any record of that check in your types. Whereas parsing allows you to upgrade the types to something more restrictive so that you cannot misuse the value later on. https://lexi-lambda.github.io/blog/2019/11/05/parse-don-t-validate/ Ledger Mac App: Parsing Techniques Chris Eidhof & Florian Kugler • 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. https://talk.objc.io/episodes/S01E13-parsing-techniques Downloads Sample code 0060-composable-parsing-flat-map Point-Free A hub for advanced Swift programming. Brought to you by Brandon Williams and Stephen Celis . Content Become a member The Point-Free Way Beta previews Gifts Videos Collections Free clips Blog More About Us Community Slack Mastodon Twitter BlueSky GitHub Contact Us Privacy Policy © 2026 Point-Free, Inc. All rights are reserved for the videos and transcripts on this site. All other content is licensed under CC BY-NC-SA 4.0 , and the underlying source code to run this site is licensed under the MIT License .