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.

Recall that the general shape of flatMap looks something like this:

flatMap: ((A) -> M<B>) -> (M<A>) -> M<B>

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.

Let’s try to implement this function for our Parser type. Let’s first just get the signature in place:

extension Parser {
  func flatMap<B>(_ f: (A) -> Parser<B>) -> Parser<B> {

  }
}

We know we need to return a Parser<B>, so let’s invoke its initializer, which takes a block representing its run function (inout Substring) -> B?.

extension Parser {
  func flatMap<B>(_ f: (A) -> Parser<B>) -> Parser<B> {
    return Parser<B> { str -> B? in

    }
  }
}

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<B>(_ f: (A) -> Parser<B>) -> Parser<B> {
    return Parser<B> { str in
      let matchA = self.run(&str)
    }
  }
}

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<B>(_ f: (A) -> Parser<B>) -> Parser<B> {
    return Parser<B> { str in
      let matchA = self.run(&str)
      let parserB = matchA.map(f)
    }
  }
}

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<B>(_ f: (A) -> Parser<B>) -> Parser<B> {
    return Parser<B> { str in
      let matchA = self.run(&str)
      let parserB = matchA.map(f)
      let matchB = parserB?.run(&str)
    }
  }
}

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<B>(_ f: @escaping (A) -> Parser<B>) -> Parser<B> {
    return Parser<B> { str in
      let matchA = self.run(&str)
      let parserB = matchA.map(f)
      let matchB = parserB?.run(&str)
    }
  }
}

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<B>(_ f: @escaping (A) -> Parser<B>) -> Parser<B> {
    return Parser<B> { str in
      let matchA = self.run(&str)
      let parserB = matchA.map(f)
      let matchB = parserB?.run(&str)
      return matchB
    }
  }
}