protocol Parser {
  associatedtype Input
  associatedtype Output
  func parse(_ input: inout Input) -> Output?
}

struct Prefix<Input>: Parser
where
  Input: Collection,
  Input.SubSequence == Input
{
  let predicate: (Input.Element) -> Bool
  func parse(_ input: inout Input) -> Input? {
    let output = input.prefix(while: predicate)
    input.removeFirst(output.count)
    return output
  }
}

extension Prefix where Input == Substring {
  init(predicate: @escaping (Character) -> Bool) {
    self.predicate = predicate
  }
}

struct Map<Upstream, Output>: Parser
where
  Upstream: Parser
{
  let upstream: Upstream
  let transform: (Upstream.Output) -> Output
  func parse(_ input: inout Upstream.Input) -> Output? {
    self.upstream.parse(&input).map(transform)
  }
}

extension Parser {
  func map<NewOutput>(
    _ transform: @escaping (Output) -> NewOutput
  ) -> Map<Self, NewOutput> {
    .init(upstream: self, transform: transform)
  }
}

struct Zip<A, B>: Parser where A: Parser, B: Parser, A.Input == B.Input {
  let a: A
  let b: B

  init(_ a: A, _ b: B) {
    self.a = a
    self.b = b
  }

  func parse(_ input: inout A.Input) -> (A.Output, B.Output)? {
    let original = input
    guard
      let a = self.a.parse(&input),
      let b = self.b.parse(&input)
    else {
      input = original
      return nil
    }
    return (a, b)
  }
}

func f() {
  // Expression took 9680ms to type-check
  _ = Zip(Prefix { $0 != "-" }, Prefix { $0 != "-" })
    .map { (String($0), String($1)) }

  // Expression took 12457ms to type-check
  _ = Zip(
    Prefix { $0 != "-" }.map(String.init),
    Prefix { $0 != "-" }.map(String.init)
  )
}