Kotlin parser combinator

Parser.kt

sealed class Result<out A> {
    data class Success<A>(val value: A) : Result<A>()
    data class Failure(val msg: String) : Result<Nothing>()

    companion object {

        fun <A> success(value: A): Result<A> = Success(value)

        fun <A> failure(msg: String): Result<A> = Failure(msg)
    }
}


class Parser<A>(val run: (String) -> Result<Pair<A, String>>) {

    infix fun <B> andThen(next: Parser<B>): Parser<Pair<A, B>> = Parser { input ->
        // run first parser with input
        when (val res1 = run(input)) {
            is Result.Success -> {
                val (value1, remaining1) = res1.value
                // run the next parser with remaining input
                when (val res2 = next.run(remaining1)) {
                    is Result.Success -> {
                        val (value2, remaining2) = res2.value
                        success(Pair(Pair(value1, value2), remaining2))
                    }
                    is Result.Failure -> res2
                }
            }
            is Result.Failure -> res1
        }
    }

    infix fun orElse(alt: Parser<A>): Parser<A> = Parser { input ->
        when (val run1 = run(input)) {
            is Result.Success -> run1
            is Result.Failure -> alt.run(input)
        }
    }

    infix fun <B> map(f: (A) -> B): Parser<B> = Parser { input ->
        when (val res1 = run(input)) {
            is Result.Success -> {
                val (value, remaining) = res1.value
                success(Pair(f(value), remaining))
            }
            is Result.Failure -> res1
        }
    }

    companion object {

        fun parseChar(charToMatch: Char, input: String): Result<Pair<Char, String>> =
            when {
                input.isBlank() -> failure("No more input")
                input.first() == charToMatch -> success(Pair(charToMatch, input.drop(1)))
                else -> failure("Expecting: `$charToMatch`. Got: `${input.first()}` first")
            }

        fun create(charToMatch: Char): Parser<Char> = Parser { input -> parseChar(charToMatch, input) }

        fun <A> choice(parsers: List<Parser<A>>): Parser<A> =
            parsers.reduce { acc, parser -> acc orElse parser }

        fun anyOf(chars: List<Char>): Parser<Char> =
            choice(chars.map { create(it) })

        fun <A> List<Parser<A>>.sequence(): Parser<List<A>> =
            when (val head = this.firstOrNull()) {
                null -> Parser { success(Pair(emptyList<A>(), it)) }
                else -> head map { listOf(it) } andThen this.drop(1).sequence() map { it.first + it.second }
            }

        fun string(string: String): Parser<String> =
            string.map { create(it) }
                .sequence() map { it.joinToString("") }

        private fun <A> Parser<A>.zeroOrMore(input: String): Pair<List<A>, String> {
            return when (val res = run(input)) {
                is Result.Success -> {
                    val (value, remaining) = res.value
                    val (nextValues, remainingInput) = zeroOrMore(remaining)
                    Pair(listOf(value) + nextValues, remainingInput)
                }
                is Result.Failure -> Pair(emptyList(), input)
            }
        }

        fun <A> Parser<A>.many(): Parser<List<A>> = Parser { success(zeroOrMore(it)) }

        fun <A> Parser<A>.many1(): Parser<List<A>> = Parser {
            val (list, remaining) = zeroOrMore(it)
            if (list.isEmpty()) failure("Could not find at least one item")
            else success(Pair(list, remaining))
        }

        fun <A> Parser<A>.opt(): Parser<A?> = Parser {
            val (list, _) = zeroOrMore(it)
            if (list.isEmpty()) success(Pair(null, it))
            else success(Pair(list.first(), it.drop(1)))
        }

        infix fun <A, B> Parser<A>.zipLeft(other: Parser<B>): Parser<A> = this andThen other map { it.first }

        infix fun <A, B> Parser<A>.zipRight(other: Parser<B>): Parser<B> = this andThen other map { it.second }

        fun <A, B, C> between(p1: Parser<A>, p2: Parser<B>, p3: Parser<C>): Parser<B> =
            p1 zipRight p2 zipLeft p3

        infix fun <A> Parser<A>.sepBy1(sep: Parser<A>): Parser<List<A>> {
            val sepThenP = sep zipRight this
            val many = this andThen sepThenP.many()
            return many.map { listOf(it.first) + it.second }
        }

        infix fun <A> Parser<A>.sepBy(sep: Parser<A>): Parser<List<A>> =
            sepBy1(sep) orElse Parser { success(Pair(emptyList<A>(), it)) }
    }

usage.kt

import Parser.Companion.create

fun main() {
    val parse1 = create('1')
    val parse2 = create('2')
    val parse12 = parse1 andThen parse2
    val parse12AsInt = parse12 map { (one, two) -> ("$one$two").toInt() }

    println(parse12AsInt.run("1234"))
    // Success(value=(12, 34))
    println(parse12AsInt.run("1s234"))
    // Failure(msg=Expecting: `2`. Got: `s` first)

    val parseDigit = Parser.anyOf((0..9).toList().map { "$it".first() })

    println(parseDigit.run("1"))
    // Success(value=(1, ))
    println(parseDigit.run("52"))
    // Success(value=(5, 2))
    println(parseDigit.run("stojan"))
    // Failure(msg=Expecting: `9`. Got: `s` first)

    val parseLowercase = Parser.anyOf(('a'..'z').toList())
    println(parseLowercase.run("a"))
    // Success(value=(a, ))
    println(parseLowercase.run("stojan"))
    // Success(value=(s, tojan))
    println(parseLowercase.run("15"))
    // Failure(msg=Expecting: `z`. Got: `1` first)

    println(Parser.sequence(listOf(create('S'), create('T'), create('O'))).run("STOJAN"))
    // Success(value=([S, T, O], JAN))
}