struct Parser<Output> {
  let parse : (_ cs : [Character]) -> (value : Output, remainder : [Character])?

  func parse(_ s : String) -> (value : Output, remainder : String)? {
    if let (v, rem) = parse(Array(s.characters)) {
      return (v, String(rem))
    } else {
      return nil
    }
  }

  static func fail<A>() -> Parser<A> {
    return Parser<A> { _ in
      return nil
    }
  }

  static func success(_ x : Output) -> Parser<Output> {
    return Parser { input in
      return (x, input)
    }
  }

  static func item(_ pred : @escaping (Character) -> Bool) -> Parser<Character> {
    return Parser<Character> { input in
      if let first = input.first, pred(first) {
        return (first, Array(input.dropFirst()))
      } else {
        return nil
      }
    }
  }

  // can be divided in two parts

  static func first() -> Parser<Character> {
    return Parser<Character> { input in
      if let first = input.first {
        return (first, Array(input.dropFirst()))
      } else {
        return nil
      }
    }
  }

  func satisfy(_ pred : @escaping (Output) -> Bool) -> Parser {
    return Parser { input in
      if let (v, rem) = self.parse(input), pred(v) {
        return (v, rem)
      } else {
        return nil
      }
    }
  }

  static func character(_ c : Character) -> Parser<Character> {
    return Parser.first().satisfy({ $0 == c })
  }

  /*
  func then<Output2>(_ p : Parser<Output2>) -> Parser<(Output, Output2)> {
    return Parser<(Output, Output2)> { input in
      if let (v1, rem1) = self.parse(input),
         let (v2, rem2) = p.parse(rem1) {
        return ((v1, v2), rem2)
      } else {
        return nil
      }
    }
  }
  */

  func then<Output2, Output3>(_ p : Parser<Output2>,
                              combine: @escaping (Output, Output2) -> Output3) -> Parser<Output3> {
    return Parser<Output3> { input in
      if let (v1, rem1) = self.parse(input),
         let (v2, rem2) = p.parse(rem1) {
        return (combine(v1, v2), rem2)
      } else {
        return nil
      }
    }
  }

  func bind<Output2>(_ then : @escaping (Output) -> Parser<Output2>) -> Parser<Output2> {
    return Parser<Output2> { input in
      if let (v1, rem1) = self.parse(input) {
        return then(v1).parse(rem1)
      } else {
        return nil
      }
    }
  }

  func or(_ p : Parser) -> Parser {
    return Parser { input in
      self.parse(input) ?? p.parse(input)
    }
  }

  func optional() -> Parser<Output?> {
    return self.bind({ Parser<Output?>.success($0) })
               .or(Parser<Output?>.success(nil))
  }

  func many() -> Parser<[Output]> {
    return Parser<[Output]> { input in
      if let (x, rem) = self.parse(input) {
        return self.many().bind({ Parser<[Output]>.success([x] + $0) }).parse(rem)
      } else {
        return ([Output](), input)
      }
    }
  }
}

func fail<A>() -> Parser<A> {
  return Parser<Any>.fail()
}

func success<A>(_ x : A) -> Parser<A> {
  return Parser<A>.success(x)
}

func character(_ c : Character) -> Parser<Character> {
  return Parser<Any>.character(c)
}

let p1 = (character("a").then(character("b")) { a,b in return String([a,b,a,b]) })
print(p1.parse("abababahello") ?? "unparsed")
print(p1.parse("acababahello") ?? "unparsed")

let p1b = character("a").bind { _ in
    return character("b")
  }
print(p1b.parse("abababahello") ?? "unparsed")
print(p1b.parse("acababahello") ?? "unparsed")

let p2 = (character("a").then(character("b")) { _,_ in return "found" }).many()
print(p2.parse("abababahello") ?? "unparsed")

let p3 = character("a").or(character("b"))