Goal: Write a function for testing any given “module” that provides a specific set of functions for creating and manipulating lists. This is trivial in JavaScript but tricky in Kotlin due to the lack of higher-kinded types.

ListLike.js

import {deepStrictEqual as eq} from "node:assert";

//  class ListLike f where
//    empty  :: f a
//    cons   :: a -> f a -> f a
//    fold   :: f a -> b -> (b -> a -> b) -> b
//    map    :: f a -> (a -> b) -> f b
//    length :: f a -> Int

const Array = {
  empty:  [],
  cons:   (head, tail) => [head, ...tail],
  fold:   (array, init, f) => array.reduce((k, x) => f(k, x), init),
  map:    (array, f) => array.map(x => f(x)),
  length: (array) => array.length,
};

const List = {
  empty:  Object.create(null),
  cons:   (head, tail) => ({head, tail}),
  fold:   (list, init, f) => list === List.empty ? init : List.fold(list.tail, f(init, list.head), f),
  map:    (list, f) => list === List.empty ? List.empty : List.cons(f(list.head), List.map(list.tail, f)),
  length: (list) => List.fold(list, 0, (n, _) => n + 1),
};

const test = ({empty, cons, fold, map, length}) => {
  eq(length(empty), 0);
  eq(length(cons("foo", empty)), 1);
  eq(length(cons("foo", cons("bar", empty))), 2);
  eq(length(cons("foo", cons("bar", cons("baz", empty)))), 3);
  eq(fold(cons("foo", cons("bar", cons("baz", empty))), "", (k, s) => k + s), "foobarbaz");
  eq(map(cons("Java", cons("Kotlin", cons("Scala", empty))), s => s.length), cons(4, cons(6, cons(5, empty))));
};

test(Array);
test(List);

ListLike.kt

import org.junit.jupiter.api.Assertions.assertEquals
import org.junit.jupiter.api.Test

interface Hk<W, A>

interface ListLike<W> {
    fun <A> empty(): Hk<W, A>
    fun <A> prepend(head: A, tail: Hk<W, A>): Hk<W, A>
    fun <A, B> fold(list: Hk<W, A>, init: B, f: (B, A) -> B): B
    fun <A, B> map(list: Hk<W, A>, f: (A) -> B): Hk<W, B>
    fun <A> length(list: Hk<W, A>): Int
}

object WrappedList : ListLike<WrappedList.W> {
    object W  // witness for WrappedList

    data class Wrap<A>(val list: List<A>) : Hk<W, A>

    private fun <A> unwrap(list: Hk<W, A>): List<A> = (list as Wrap<A>).list

    override fun <A> empty(): Hk<W, A> = Wrap(emptyList())

    override fun <A> prepend(head: A, tail: Hk<W, A>): Hk<W, A> {
        return Wrap(listOf(head) + unwrap(tail))
    }

    override fun <A, B> fold(list: Hk<W, A>, init: B, f: (B, A) -> B): B {
        return unwrap(list).fold(init, f)
    }

    override fun <A, B> map(list: Hk<W, A>, f: (A) -> B): Hk<W, B> {
        return Wrap(unwrap(list).map(f))
    }

    override fun <A> length(list: Hk<W, A>): Int {
        return unwrap(list).size
    }
}

object LinkedList : ListLike<LinkedList.W> {
    object W  // witness for LinkedList

    sealed class MyList<A> : Hk<W, A>
    data object Nil : MyList<Nothing>()
    data class Cons<A>(val head: A, val tail: MyList<A>) : MyList<A>()

    private fun <A> fix(list: Hk<W, A>) = list as MyList<A>

    @Suppress("UNCHECKED_CAST")
    override fun <A> empty(): Hk<W, A> = Nil as MyList<A>

    override fun <A> prepend(head: A, tail: Hk<W, A>): Hk<W, A> {
        return Cons(head, fix(tail))
    }

    override fun <A, B> fold(list: Hk<W, A>, init: B, f: (B, A) -> B): B {
        return when (val unwrapped = fix(list)) {
            is Nil -> init
            is Cons -> fold(unwrapped.tail, f(init, unwrapped.head), f)
        }
    }

    override fun <A, B> map(list: Hk<W, A>, f: (A) -> B): Hk<W, B> {
        return when (val unwrapped = fix(list)) {
            is Nil -> empty()
            is Cons -> prepend(f(unwrapped.head), map(unwrapped.tail, f))
        }
    }

    override fun <A> length(list: Hk<W, A>): Int {
        return fold(list, 0) { n, _ -> n + 1 }
    }
}

fun <W> test(M: ListLike<W>) {
    assertEquals(0, M.length(M.empty<String>()))
    assertEquals(1, M.length(M.prepend("foo", M.empty())))
    assertEquals(2, M.length(M.prepend("foo", M.prepend("bar", M.empty()))))
    assertEquals(3, M.length(M.prepend("foo", M.prepend("bar", M.prepend("baz", M.empty())))))
    assertEquals("foobarbaz", M.fold(M.prepend("foo", M.prepend("bar", M.prepend("baz", M.empty()))), "") { k, s -> k + s })
    assertEquals(M.prepend(4, M.prepend(6, M.prepend(5, M.empty()))), M.map(M.prepend("Java", M.prepend("Kotlin", M.prepend("Scala", M.empty())))) { s -> s.length })
}

class Tests {
    @Test
    fun `WrappedList test suite`() {
        test(WrappedList)
    }
    @Test
    fun `LinkedList test suite`() {
        test(LinkedList)
    }
}