Video #59: Composable Parsing: Map

Episode: Video #59 Date: May 27, 2019 Access: Members Only 🔒 URL: https://www.pointfree.co/episodes/ep59-composable-parsing-map

Description

We now have a precise, efficient definition for parsing, but we haven’t even scratched the surface of its relation to functional programming. In this episode we begin to show how all of the functional operators we know and love come into play, starting with map.

Video

Cloudflare Stream video ID: 099e24ad10819a345e5d8272c0fe2409 Local file: video_59_composable-parsing-map.mp4 *(download with --video 59)*

References

Transcript

— 0:05

In the last three episodes ( part 1 , part 2 , part 3 ) we set the stage for parsing.

— 0:09

First we showed that parsing is such a common and important task that Apple provides multiple solutions for parsing in both Swift and Foundation. Everything from initializers that will parse a string into a specific type, such as integers, doubles, UUIDs and URLs, to general purpose parsers like the Scanner type, which allows us to incrementally parse various types off the beginning of strings, to regular expressions.

— 0:45

All of those parsers are handy and powerful, but they have some serious drawbacks, such as they are not really defined for code reusability or composability. So we took a step back, and provided a precise definition of what a parser is. It was literally a function that takes an in-out substring as input and returns an optional, first class value as output.

— 1:13

With that simple definition we had a succinct, efficient description of parsing, and we even made a few domain-specific parsers that did just a little bit of parsing, but did it well. Then we pieced those parsers together and made a pretty complicated parser yet the code was very descriptive and straightforward. It even fixed some subtle edges cases that a hand rolled parser had missed.

— 1:35

But even though we accomplished a lot in the last 3 episodes, it doesn’t even scrape the surface of what functional programming has to say about parsing. Today we’ll really start to dig into that topic by seeing precisely how one glues together parsers to form ever more complex parsers. Once we unlock a few of the basic shapes we will be able to create incredibly powerful parsers with very little work, and the sky will be the limit! Recap

— 2:02

Let’s take a look at what we’ve built so far.

— 2:08

We first defined the Parser type, which is merely a wrapper around a parsing function. struct Parser<A> { let run: (inout Substring) -> A? }

— 2:16

And then we defined some very simple parsers for parsing integers and doubles. let int = Parser<Int> { str in let prefix = str.prefix(while: { $0.isNumber }) guard let int = Int(prefix) else { return nil } str.removeFirst(prefix.count) return int } let double = Parser<Double> { str in let prefix = str.prefix(while: { $0.isNumber || $0 == "." }) guard let match = Double(prefix) else { return nil } str.removeFirst(prefix.count) return match }

— 2:28

And a “literal” parser, which is a function that, given a string, produces a parser of Void , which attempts to parse an exact string off the beginning of another string. func literal(_ literal: String) -> Parser<Void> { return Parser<Void> { str in guard str.hasPrefix(literal) else { return nil } str.removeFirst(literal.count) return () } }

— 2:52

We also defined some really weird parsers: an always parser that always parses a given value when run, and a never parser that always fails. func always<A>(_ a: A) -> Parser<A> { return Parser<A> { _ in a } } extension Parser { static var never: Parser { return Parser { _ in nil } } }

— 3:08

With these basic building blocks, we built a parser of latitude longitude coordinate strings into a first-class Coordinate struct. struct Coordinate { let latitude: Double let longitude: Double } let northSouth = Parser<Double> { str in guard let cardinal = str.first, cardinal == "N" || cardinal == "S" else { return nil } str.removeFirst() return cardinal == "N" ? 1 : -1 } let eastWest = Parser<Double> { str in guard let cardinal = str.first, cardinal == "E" || cardinal == "W" else { return nil } str.removeFirst() return cardinal == "E" ? 1 : -1 } func parseLatLong(_ str: String) -> Coordinate? { var str = str[...] guard let lat = double.run(&str), literal("° ").run(&str) != nil, let latSign = northSouth.run(&str), literal(", ").run(&str) != nil, let long = double.run(&str), literal("° ").run(&str) != nil, let longSign = eastWest.run(&str) else { return nil } return Coordinate( latitude: lat * latSign, longitude: long * longSign ) }

— 4:18

We also made use of a helper run function that takes a regular string as input and returns the optional match alongside the remainder of the string being parsed. This gives us a bit nicer feedback in the playground. extension Parser { func run(_ str: String) -> (match: A?, rest: Substring) { var str = str[...] let match = self.run(&str) return (match, str) } } Transforming parsers

— 4:36

Now that we have our base unit of parsing we should search for ways to transform existing parsers into new parsers. This will unlock a whole new world of capabilities that our Parser type cannot currently do.

— 4:47

For example, although we are starting to get comfortable with the idea of parsing small bits at a time, we have no cohesive way of using multiple parsers to parse multiple things from a string. We must resort to manually running a bunch of our parsers and then collecting the results, which is exactly what we did when we were parsing latitude and longitude coordinates from a string: guard let lat = double.run(&str), literal("° ").run(&str) != nil, let latSign = northSouth.run(&str), literal(", ").run(&str) != nil, let long = double.run(&str), literal("° ").run(&str) != nil, let longSign = eastWest.run(&str) else { return nil }

— 5:12

There’s got to be a more cohesive way to do this kind of parsing, and indeed there is!

— 5:16

We’ve even done this kind of thing over-and-over on Point-Free. Such as when we dealt with styling functions , randomness , snapshot testing and many other things. We first defined the base unit of the problem we are trying to solve, and then came up with all types of ways to compose those units together.

— 5:33

Turns out, the Parser type has all of the fun, universal operations that we have discussed on Point-Free, such as map , zip and flatMap , and these operations are exactly what allow us to build complex parsers out of simple parsers. So let’s define em! Defining map on Parser

— 5:47

Let’s start with map . If you remember from our episode on map , this operation allows you to lift a function between types up to a function between generic types. That description translates to the following signature: map: ((A) -> B) -> (F<A>) -> F

— 6:17

In particular, we want to define this for our parser type: F<A> = Parser<A> map: ((A) -> B) -> (Parser<A>) -> Parser

— 6:33

This function must also satisfy a particular property, which is that the map of the identity function is the identity function: map(id) = id

— 6:45

This simply says that when you map on some generic context with the identity function, you don’t change the context at all. For example: [1, 2, 3] .map { $0 } // [1, 2, 3] Optional("Blob") .map { $0 } // some("Blob") Here we mapped on an array and an optional with the identity function, and of course that didn’t change anything about the values we were mapping on, and we’ll see why that’s important in a moment.

— 7:15

This signature of map is really handy to know because it shows how we are simply lifting the function (A) -> B up to (Parser<A>) -> Parser , but it’s more common to work with map as a method, in which it takes the Parser<A> as a first argument: map: (Parser<A>, (A) -> B) -> Parser

— 7:43

Let’s try implementing this. We can start with the signature. extension Parser { func map(_ f: (A) -> B) -> Parser { } }

— 7:57

Next, we know we need to return a parser of B s. extension Parser { func map(_ f: (A) -> B) -> Parser { return Parser { str -> B? in } } } This parsing block needs to optionally return a B if parsing was successful.

— 8:10

But how do we get a B ? Well we have: a function, f , that transforms A s into B s an in-out substring str , and the current parser’s run function, which takes an in-out substring and returns an optional A .

— 8:25

We can pass str along to run to get an optional A . extension Parser { func map(_ f: (A) -> B) -> Parser { return Parser { str in let matchA = self.run(&str) } } }

— 8:34

Now we have an optional A , but our transform function takes a non-optional A , so let’s unwrap it with a guard. extension Parser { func map(_ f: (A) -> B) -> Parser { return Parser { str in guard let matchA = self.run(&str) else { return nil } } } }

— 8:47

Now we can plug it into our f to get a non-optional B , which is precisely what we need to return. extension Parser { func map(_ f: (A) -> B) -> Parser { return Parser { str in guard let matchA = self.run(&str) else { return nil } let matchB = f(matchA) return matchB } } } Closure use of non-escaping parameter ‘f’ may allow it to escape

— 9:00

Ah, and we need to mark the transform function as “escaping” because it isn’t called when map is called. We need to capture it so that it can be called later during actual parsing. extension Parser { func map(_ f: @escaping (A) -> B) -> Parser { return Parser { str in guard let matchA = self.run(&str) else { return nil } let matchB = f(matchA) return matchB } } }

— 9:13

One thing we could do to simplify is remember that Optional also has a map function that transforms the optional value. Instead of using guard , we could map on the optional A that gets returned from run . extension Parser { func map(_ f: @escaping (A)-> B) -> Parser { return Parser { str in let matchA = self.run(&str) let matchB = matchA.map(f) return matchB } } }

— 9:32

And now we can even get rid of our temporary variables and write things in a single, succinct expression. We can even get rid of the return . extension Parser { func map(_ f: @escaping (A)-> B) -> Parser { return Parser { str in self.run(&str).map(f) } } }

— 9:45

Quite simple. To map a parser, it simply means to run the parser on the input string, and then transform the parsed value with the function. And since the parsed value is optional itself, we are even using the optional map inside the parser’s map .

— 9:57

Defining map was a matter of identifying the pieces we had and plugging them together where the type system allowed. Map’s universal property

— 10:07

Now, what about that property we mentioned before: the map of the identity function should be the identity function. Does this map on parsers satisfy this property?

— 10:17

Under the hood we are just calling map on an optional value, which we know satisfies the property. So, if we do something like this: int.map { $0 } // Parser<Int>

— 10:53

It doesn’t change the parser at all, which is important because there’s another possible implementation of map that looks like this: extension Parser { func fakeMap(_ f: @escaping (A)-> B) -> Parser { return Parser { _ in return nil } } }

— 11:16

This is a pretty bad implementation, it just always returns nil and makes no use of any of the data we have at hand. But the way we really know this is the wrong implementation is that it does not satisfy the property we want: int.fakeMap { $0 } // Parser<Int>

— 11:28

This parser is not the same as the int parser, and so this implementation of map can’t possibly be what we want. If we run it: int.fakeMap { $0 }.run("123") // (nil, rest "123")

— 11:44

“Fake” mapping with the identity function has changed the parser, whereas real mapping with the identity function leaves the parser unchanged.

— 11:51

There are even more fake maps, like: extension Parser { func fakeMap2(_ f: @escaping (A)-> B) -> Parser { return Parser { str in let b = self.run(&str).map(f) str = "" return b } } } Here we do the parsing like normal, but then we just fully consume the string.

— 12:15

This fake map also does not satisfy the property we want: int.fakeMap2 { $0 }.run("123 Hello World") // (match 123, rest "") It parsed the same value the int parser would have parsed, but we no longer have the rest of the string to parse.

— 12:42

The int parser would have left the rest of the substring to be parsed. int.run("123 Hello World") // (match 123, rest " Hello World")

— 12:50

And there are infinitely many other implementations we could have for these fake maps where we tweak the input strings in all types of different ways.

— 13:04

But the reason we care about this strange property that map preserves the identity function is that it is related to this concept known as “parametricity” and this amazing result in computer science known as “theorems for free.” We explored these ideas in our episode on map , and we highly recommend everyone go watch it if they haven’t already, but in a nutshell it says that the map is uniquely determined by its signature and the property that it preserves the identity function. So this tells us that the map we have defined on the parser type is the one true map , a universal truth.

— 14:01

And this property not only guides us to implementations of map , but helps us instantly understand any map we encounter in the wild. We can know that map will never affect the context. It would be bizarre, for instance, if a map on an array rearranged or removed elements, or if a map on an optional randomly sent some values into nil . Mapping new parsers

— 14:23

Already we can use map to transform existing parsers into new ones. For example, what if we wanted a parser of boolean values that told us when the integer we parse is even or not: let even = int.map { $0 % 2 == 0 } // Parser<Bool>

— 14:47

And we can run it on some input. even.run("123 Hello World") // (match false, rest " Hello World") even.run("42 Hello World") // (match true, rest " Hello World")

— 15:11

This is a bit of a toy example, so let’s apply it to something more real-world. We could maybe have used map to make our northSouth parser a bit more succinct. First recall that this is what it looks like: let northSouth = Parser<Double> { str in guard let cardinal = str.first, cardinal == "N" || cardinal == "S" else { return nil } str.removeFirst() return cardinal == "N" ? 1 : -1 }

— 15:40

We parse off the first character of the input string, check if it’s equal to the characters “N” or “S”, and then we convert that into either a + or - one. This parser is doing a lot, and it could be broken down into simpler pieces.

— 16:09

For one, we see we are just peeling off a single character from the input string, so let’s create a character parser: let char = Parser<Character> { str in guard !str.isEmpty else { return nil } return str.removeFirst() }

— 16:51

Note that we can’t merely call removeFirst because it will crash on an empty string ¯_(ツ)_/¯

— 17:03

And now we have a brand new parser whose sole responsibility is to peel off a single character from the start of a string.

— 17:13

We can now remove all of this specific work that deals with parsing of a character from the northSouth parser, and instead focus on its real logic: determining if the character is north or south: let northSouth = char.map { $0 == "N" ? 1.0 : -1 } // Parser<Double>

— 17:35

Now our northSouth parser is super short, succinct and very clear what it is trying to accomplish. It simply wants to parse off a single character from the front of the input string, check if it’s the “N” or “S” character, and return the sign of the cardinal direction.

— 17:58

Now, this isn’t quite right, and in fact we have reintroduced a small bug that we ran into when we were trying to write this parser in a hand rolled style. Basically, it will allow parsing any character, but we don’t want to parse characters that are not “N” or “S”.

— 18:31

To do that we need to be able to have some sense of failability when mapping, maybe something like: let northSouth = char .map { $0 == "N" ? 1.0 : $0 == "S" ? -1 : nil } Result values in ‘? :’ expression have mismatching types ‘Double’ and ‘Int?’

— 19:00

The compiler is getting a little confused here, but if we let it know that we’re explicitly working with optionals, we can get things building. let northSouth = char .map { $0 == "N" ? Optional(1.0) : $0 == "S" ? -1 : nil }

— 19:24

Now technically this is creating a Parser<Double?> , a parser of optional doubles, which is not what we want. And to make matters worse, it will still happily parse any character off the front of our input. We want our parser to fail in this case. Map’s limitations

— 20:09

It turns out, map is not capable of doing this. map is only capable of letting the underlying parsing go uninhibited, and then transforming the value that was produced from the parsing.

— 20:34

In order to affect the success or failure of a parsing operation we need a different operation, one that we are all very familiar with.

— 20:46

Yeah that’s right, we have seen that map has some promise to it, but it can’t quite solve the problem that we have here. The problem is that we want to be able to change the course of parsing inside the body of the map . We’d like the first two logical branches to parse the character and return the respective double value, but in the final else branch we’d like to prevent parsing entirely: let northSouth = char .map { $0 == "N" ? Optional(1.0) // Yes, parse the N : $0 == "S" ? -1 // Yes, parse the S : nil // No, don't parse anything }

— 21:07

This just isn’t possible with map alone. We need another operation that will allow us to chain parsers together. Because we want to first run the character parser, and then with that result run another parser, and only if everything succeeds will we consume from the input string.

— 21:24

In describing it this way, maybe what we want to do is return a parser from this block instead. In fact, the always and never parsers seem to be a perfect fit for describing what we want to parse here. let northSouth = char .map { $0 == "N" ? always(1.0) : $0 == "S" ? always(-1) : .never }

— 22:09

Unfortunately, this still isn’t quite right because we end up with a nested parser. northSouth // Parser<Parser<Double>> Till next time

— 22:33

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. 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 0059-composable-parsing-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 .