cheats.swift

import Cocoa

//typealias Parser<Token, A> = (Tokens) -> (A, Tokens)?

struct Parser<Tokens, A> {
    let parse: (Tokens) -> (A, Tokens)?
}

typealias Stream<A> = Parser<String.CharacterView, A>
typealias Expression = Stream<Int>

func character(satisfy condition: @escaping (Character) -> Bool) -> Stream<Character> {
    return Stream<Character> { input in
        guard let character = input.first,
            condition(character)  else { return nil }
        return (character, input.dropFirst())
    }
}

extension CharacterSet {
    var element: Stream<Character> {
        return character { self.contains($0.unicodeScalar) }
    }
    
    static var digit: Stream<Character> {
        return CharacterSet.decimalDigits.element
    }
}

let digit = CharacterSet.digit
digit.parse("123".characters)

func run<A>(_ parser: Stream<A>, _ string: String) -> (A, String)? {
    guard let (result, remainder) = parser.parse(string.characters) else { return nil }
    return (result, String(remainder))
}

run(digit, "123")

let multiSign = character { $0 == "*" }
let plusSign = character { $0 == "+" }

func token(_ one: Character) -> Stream<Character> {
    return character { $0 == one }
}

run(token("*"), "*")
run(token("+"), "+")

extension Parser {
    var many: Parser<Tokens, [A]> {
        return Parser<Tokens, [A]> { stream in
            var result: [A] = []
            var remainder = stream
            while let (element, newRemainder) = self.parse(remainder) {
                result.append(element)
                remainder = newRemainder
            }
            return (result, remainder)
        }
    }
}

run(digit.many, "123")

extension Parser {
    func map<B>(_ transform: @escaping (A) -> B) -> Parser<Tokens, B> {
        return Parser<Tokens, B> { stream in
            guard let (result, remainder) = self.parse(stream) else { return nil }
            return (transform(result), remainder)
        }
    }
}

let int0 = digit.many.map{ Int(String($0))! }
run(int0, "123")

extension Parser {
    func flatMap<B>(_ transform: @escaping (A) -> B?) -> Parser<Tokens, B> {
        return Parser<Tokens, B> { stream in
            guard let (result, remainder) = self.parse(stream) else { return nil }
            guard let transformedResult = transform(result) else { return nil }
            return (transformedResult, remainder)
        }
    }
}

let int = digit.many.flatMap{ Int(String($0)) }
run(int, "123")

extension Parser {
    func followed<B>(by other: Parser<Tokens, B>) -> Parser<Tokens, (A, B)> {
        return Parser<Tokens, (A, B)> { input in
            guard let (result1, remainder1) = self.parse(input) else { return nil }
            guard let (result2, remainder2) = other.parse(remainder1) else { return nil }
            return ((result1, result2), remainder2)
        }
    }
}

let multiplication1 = int
        .followed(by: token("*"))
        .followed(by: int)
        .map { lhs, rhs in lhs.0 * rhs }

run(multiplication1, "3*60")

func multiply(_ x: Int, _ op: Character, _ y: Int) -> Int {
    return x * y
}

curry(multiply)(3)("*")(60)

let multiplication2 =
    int.map(curry(multiply))
        .followed(by: token("*")).map { f, op in f(op) }
        .followed(by: int).map { f, y in f(y) }

run(multiplication2, "3*60")

precedencegroup SequencePrecedence {
    associativity: left
    higherThan: AdditionPrecedence
}

infix operator <*>: SequencePrecedence
func <*><A, B, Tokens>(lhs: Parser<Tokens, (A) -> B>, rhs: Parser<Tokens, A>) -> Parser<Tokens, B> {
    return lhs.followed(by: rhs).map { f, x in f(x) }
}

let multiplication3 = int.map(curry(multiply)) <*> token("*") <*> int

run(multiplication3, "3*60")

infix operator <^>: SequencePrecedence
func <^><A, B, Tokens>(lhs: @escaping (A) -> B, rhs: Parser<Tokens, A>) -> Parser<Tokens, B> {
    return rhs.map(lhs)
}

let multiplication4 = curry(multiply) <^> int <*> token("*") <*> int

infix operator <*: SequencePrecedence
func <*<A, B, Tokens>(lhs: Parser<Tokens, A>, rhs: Parser<Tokens, B>) -> Parser<Tokens, A> {
    return lhs.followed(by: rhs).map { x, _ in x }
}

infix operator *>: SequencePrecedence
func *><A, B, Tokens>(lhs: Parser<Tokens, A>, rhs: Parser<Tokens, B>) -> Parser<Tokens, B> {
    return lhs.followed(by: rhs).map { _, y in y }
}

let multiplication = curry(*) <^> int <* token("*") <*> int
run(multiplication, "6*7")

let addition = curry(+) <^> int <* token("+") <*> int
run(addition, "2+40")

//test(addition.parse("2+40")!.0, equalTo: 42)

// multiplication: int | int * multiplicatio

// expression = multiply + multiply | multiply
// multiply = int * int | int

extension Parser {
    func or(_ other: Parser<Tokens, A>) -> Parser<Tokens, A> {
        return Parser { input in
            guard let result = self.parse(input) else {
                return other.parse(input)
            }
            return result
        }
    }
}

run(token("a").or(token("b")), "bcd")

infix operator <|>: SequencePrecedence
func <|><A, Tokens>(lhs: Parser<Tokens, A>, rhs: Parser<Tokens, A>) -> Parser<Tokens, A> {
    return lhs.or(rhs)
}

run(token("a") <|> token("b"), "bcd")

let multiply: Expression = multiplication <|> int
let add: Expression = curry(+) <^> multiply <* token("+") <*> multiply

let expression: Expression = add <|> multiply

test(run(token("*"), "*")!.0, equalTo: "*")
test(run(token("+"), "+")!.0, equalTo: "+")
test(run(int, "456")!.0, equalTo: 456)
test(run(expression, "3*60")!.0, equalTo: 180)
test(run(expression, "2+40")!.0, equalTo: 42)
test(run(expression, "2+4*10")!.0, equalTo: 42)
test(run(expression, "4*10+2")!.0, equalTo: 42)

helpers.swift

import Cocoa

public func test<A: Equatable>(_ f: @autoclosure () -> A, equalTo value: A) -> NSColor {
    if f() == value {
        return .green
    }
    return .red
}

extension Character {
    public var unicodeScalar: UnicodeScalar {
        return String(self).unicodeScalars.first!
    }
}

public func curry<A, B, C, Result>(_ f: @escaping (A, B, C) -> Result) -> (A) -> (B) -> (C) -> Result {
    return { a in { b in { c in f(a, b, c) } } }
}

public func curry<A, B, Result>(_ f: @escaping (A, B) -> Result) -> (A) -> (B) -> Result {
    return { a in { b in f(a, b) } }
}

references.md

Further Reading

• Functional Swift
• Building Parser Combinators (Part 1)
• Building Parser Combinators (Part 2)

About Me Guanshan Liu 刘冠杉

• Twitter: @guanshanliu
• Medium: @guanshanliu
• Zhihu 知乎 刘冠杉
• Jianshu 简书 guanshanliu
• WeChat Official Account: 果酱