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

Composable Parsing: Zip

While flatMap allowed us to take our parser type to the next level, it introduced a nesting problem. Isn’t flatMap all about solving nesting problems!? Well, we have one more operation at our disposal: zip! Let’s define zip on the parser type, see what it brings to the table, and finally ask, “what’s the point?”

This episode builds on concepts introduced previously:

#61 • Monday Jun 10, 2019 • Subscriber-only

Composable Parsing: Zip

While flatMap allowed us to take our parser type to the next level, it introduced a nesting problem. Isn’t flatMap all about solving nesting problems!? Well, we have one more operation at our disposal: zip! Let’s define zip on the parser type, see what it brings to the table, and finally 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!

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

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.

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. Define an alternate parser that parses coordinates formatted as decimal degree minutes, like "40° 26.767′ N 79° 58.933′ W".

  2. Define an alternate parser that parses coordinates formatted as decimal degree minutes and seconds, like "40° 26′ 46″ N 79° 58′ 56″ W".

  3. Build an ISO-8601 parser that can parse the date string 2018-01-29T12:34:56Z.

  4. Create a parser, oneOrMoreSpaces, that parses one or more spaces off the beginning of a string. Why can’t this parser be defined using map, flatMap, and/or zip?

  5. Create a parser, zeroOrMoreSpaces, that parses zero or more spaces off the beginning of a string. How does it differ from oneOrMoreSpaces?

  6. Define a function that shares the common parsing logic of oneOrMoreSpaces and zeroOrMoreSpaces. It should have the signature ((Character) -> Bool) -> Parser<Substring>. Redefine oneOrMoreSpaces and zeroOrMoreSpaces in terms of this function.

  7. Redefine zip on Parser in terms of flatMap on Parser.


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.

  • 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
Zip on Parser
01:15
Zipped coordinate parsing
07:00
Extracting reusable parsers
13:11
What’s the point?
16:38
Comparing hand-rolled parsing
17:42
Comparing Scanner parsing
19:32
Comparing Parser parsing
21:53