Example of a simple functional data structure in Kotlin.

FunctionalStack.kt

package com.example.funcstack

import java.util.NoSuchElementException

public trait FunctionalStack<out T> {
    public val size: Int
    public fun pop(): Pair<T, FunctionalStack<T>>
}

/**
 * This has to be an extension method so we can specify the lower bound of the stack's type parameter.
 * Kotlin's type inferencer will correctly bind E to the most-specific-common-superclass of
 * <code>T</code> and whatever is being passed in.
 *
 * Kotlin does not (as of M10) support using out-types as lower bounds for method type parameters.
 * Ideally, we could define something like this on FunctionalStack:
 * <code>
 *     public fun &lt;E :&gt; T&gt; push(obj: E): FunctionalStack&lt;E&gt;
 * </code>
 */
public fun <E, T : E> FunctionalStack<T>.push(obj: E): FunctionalStack<E> {
    return Node(size + 1, obj, this)
}

public object Empty : FunctionalStack<Nothing> {
    override val size = 0

    override fun pop(): Pair<Nothing, FunctionalStack<Nothing>> {
        throw NoSuchElementException()
    }
}

private class Node<T>(
        override val size: Int,
        val head: T,
        val tail: FunctionalStack<T>
) : FunctionalStack<T> {
    override fun pop(): Pair<T, FunctionalStack<T>> {
        return Pair(head, tail)
    }
}

FunctionalStackTest.kt

package com.example.funcstack

import org.junit.Test

trait Animal
class Dog : Animal
class Cat : Animal

class FunctionalStackTest {
    Test fun invariant() {
        val stack: FunctionalStack<Int> = Empty

        test.assertEquals(0, stack.size);
        test.assertEquals(1, stack.push(1).size);
        test.assertEquals(1, stack.push(1).pop().first)

        // === is identity equality.
        test.assertTrue(Empty === stack.push(1).pop().second)
    }

    Test fun variant() {
        val stack = Empty
        val dogStack = stack.push(Dog())
        val catStack = dogStack.push(Cat())

        test.assertTrue(stack is FunctionalStack<Nothing>)
        test.assertTrue(dogStack is FunctionalStack<Dog>)
        test.assertTrue(catStack is FunctionalStack<Animal>)

        test.assertTrue(popAnimal(dogStack) is Dog)
    }

    fun popAnimal(s: FunctionalStack<Animal>): Animal {
        return s.pop().first
    }
}