Demo.kt

object Demo {
    interface List {
        fun <T> foldRight(f: (value: Int, tail: T) -> T, last: T): T
        fun <T> foldLeft(f: (tail: T, value: Int) -> T, accumulator: T): T
        fun toBinaryRight(previous: Binary): Binary
        fun toBinaryLeft(accumulator: Binary): Binary
    }

    class Cell(private val value: Int, private val tail: List): List {
        override fun toString(): String =
            "($value, $tail)"

        override fun <T> foldRight(f: (value: Int, tail: T) -> T, last: T): T =
            f(value, tail.foldRight(f, last))

        override fun <T> foldLeft(f: (tail: T, value: Int) -> T, accumulator: T): T =
            tail.foldLeft(f, f(accumulator, value))

        override fun toBinaryRight(previous: Binary): Binary =
            Branch(previous, tail.toBinaryRight(Leaf(value)))

        override fun toBinaryLeft(accumulator: Binary): Binary =
            tail.toBinaryLeft(Branch(accumulator, Leaf(value)))
    }

    object End: List {
        override fun toString(): String =
            "nil"

        override fun <T> foldRight(f: (value: Int, accumulator: T) -> T, last: T): T =
            last

        override fun <T> foldLeft(f: (tail: T, value: Int) -> T, accumulator: T): T =
            accumulator

        override fun toBinaryRight(previous: Binary): Binary =
            previous

        override fun toBinaryLeft(accumulator: Binary): Binary =
            accumulator
    }

    interface RevList {
        fun <T> foldLeft(f: (tail: T, value: Int) -> T, first: T): T
        fun <T> foldRight(f: (value: Int, tail: T) -> T, accumulator: T): T
    }

    class RevCell(private val tail: RevList, private val value: Int): RevList {
        override fun toString(): String =
            "($tail, $value)"

        override fun <T> foldLeft(f: (tail: T, value: Int) -> T, first: T): T =
            f(tail.foldLeft(f, first), value)

        override fun <T> foldRight(f: (value: Int, tail: T) -> T, accumulator: T): T =
            tail.foldRight(f, f(value, accumulator))
    }

    object RevEnd: RevList {
        override fun toString(): String =
            "nil"

        override fun <T> foldLeft(f: (tail: T, value: Int) -> T, first: T): T =
            first

        override fun <T> foldRight(f: (value: Int, tail: T) -> T, accumulator: T): T =
            accumulator
    }

    interface Binary {
        fun rotateRight(): Binary
        fun rotateLeft(): Binary
        fun rotateRightHelper(rootRight: Binary): Binary
        fun rotateLeftHelper(rootLeft: Binary): Binary
    }

    class Branch(private val left: Binary, private val right: Binary): Binary {
        override fun toString(): String =
            "($left, $right)"

        override fun rotateRight(): Binary =
            left.rotateRightHelper(right)

        override fun rotateRightHelper(rootRight: Binary): Binary =
            Branch(left, Branch(right, rootRight))

        override fun rotateLeft(): Binary =
            right.rotateLeftHelper(left)

        override fun rotateLeftHelper(rootLeft: Binary): Binary =
            Branch(Branch(rootLeft, left), right)
    }

    class Leaf(private val value: Int): Binary {
        override fun toString(): String =
            "$value"

        override fun rotateRight(): Binary = this

        override fun rotateLeft(): Binary = this

        override fun rotateRightHelper(rootRight: Binary): Binary = Branch(this, rootRight)

        override fun rotateLeftHelper(rootLeft: Binary): Binary = Branch(rootLeft, this)
    }

    class NonEmpty(private val first: Int, private val rest: List) {
        override fun toString(): String =
            "($first; $rest)"

        fun toBinaryRight(): Binary =
            rest.toBinaryRight(Leaf(first))

        fun toBinaryLeft(): Binary =
            rest.toBinaryRight(Leaf(first))
    }
}

fun main(args: Array<String>) {
    val list = Demo.Cell(1, Demo.Cell(2, Demo.Cell(3, Demo.End)))
    println(list.foldRight(Demo::Cell, Demo.End))
    println(list.foldLeft(Demo::RevCell, Demo.RevEnd))
    println(list.foldLeft(Demo::RevCell, Demo.RevEnd).foldRight(Demo::Cell, Demo.End))
    println(list.foldLeft({tail: Demo.List, value -> Demo.Cell(value, tail)}, Demo.End))

    println(list.toBinaryLeft(Demo.Leaf(0)))
    println(list.toBinaryRight(Demo.Leaf(0)))

    val nelist = Demo.NonEmpty(0, Demo.Cell(1, Demo.Cell(2, Demo.Cell(3, Demo.End))))

    println(nelist.toBinaryLeft())
    println(nelist.toBinaryRight())
}