araqnid's solution to List Ops on the Kotlin track

Instructions

Test suite

Solution

Note:

This solution was written on an old version of Exercism. The tests below might not correspond to the solution code, and the exercise may have changed since this code was written.

Implement basic list operations.

In functional languages list operations like length, map, and reduce are very common. Implement a series of basic list operations, without using existing functions.

Hints

The tests for this exercise require you to use extensions, a mechanism for adding new functionality to an existing class whose source you do not directly control without having to subclass it. To learn more about Kotlin's implementations of extensions, check out the official documentation.

The customFoldLeft and customFoldRight methods are "fold" functions, which is a concept well-known in the functional programming world, but less so in the object-oriented one. If you'd like more background information, check out this fold page.

Submitting Incomplete Solutions

It's possible to submit an incomplete solution so you can see how others have completed the exercise.

ListExtensionsTest.kt

import org.junit.Ignore
import org.junit.Test
import kotlin.test.assertEquals

class ListExtensionsTest {

    @Test
    fun testAppendingEmptyLists() {
        assertEquals(
                emptyList(),
                emptyList<Int>().customAppend(emptyList()))
    }

    @Ignore
    @Test
    fun testAppendingNonEmptyListOnEmptyList() {
        assertEquals(
                listOf('1', '2', '3', '4'),
                emptyList<Char>().customAppend(listOf('1', '2', '3', '4')))
    }

    @Ignore
    @Test
    fun testAppendingNonEmptyListOnNonEmptyList() {
        assertEquals(
                listOf("1", "2", "2", "3", "4", "5"),
                listOf("1", "2").customAppend(listOf("2", "3", "4", "5")))
    }

    @Ignore
    @Test
    fun testConcatOnEmptyListOfLists() {
        assertEquals(
                emptyList(),
                emptyList<List<Int>>().customConcat())
    }

    @Ignore
    @Test
    fun testConcatOnNonEmptyListOfLists() {
        assertEquals(
                listOf('1', '2', '3', '4', '5', '6'),
                listOf(listOf('1', '2'), listOf('3'), emptyList(), listOf('4', '5', '6')).customConcat())
    }

    @Ignore
    @Test
    fun testFilteringEmptyList() {
        assertEquals(
                emptyList(),
                emptyList<Int>().customFilter { it % 2 == 1 })
    }

    @Ignore
    @Test
    fun testFilteringNonEmptyList() {
        assertEquals(
                listOf(1, 3, 5),
                listOf(1, 2, 3, 5).customFilter { it % 2 == 1 })
    }

    @Ignore
    @Test
    fun testSizeOfEmptyList() {
        assertEquals(0, emptyList<Int>().customSize)
    }

    @Ignore
    @Test
    fun testSizeOfNonEmptyList() {
        assertEquals(4, listOf("one", "two", "three", "four").customSize)
    }

    @Ignore
    @Test
    fun testTransformingEmptyList() {
        assertEquals(
                emptyList(),
                emptyList<Int>().customMap { it -> it + 1 })
    }

    @Ignore
    @Test
    fun testTransformingNonEmptyList() {
        assertEquals(
                listOf(2, 4, 6, 8),
                listOf(1, 3, 5, 7).customMap { it -> it + 1 })
    }

    @Ignore
    @Test
    fun testFoldLeftOnEmptyList() {
        assertEquals(
                2.0,
                emptyList<Int>().customFoldLeft(2.0, Double::times))
    }

    @Ignore
    @Test
    fun testFoldLeftWithDirectionIndependentOperationOnNonEmptyList() {
        assertEquals(
                15,
                listOf(1, 2, 3, 4).customFoldLeft(5, Int::plus))
    }

    @Ignore
    @Test
    fun testFoldLeftWithDirectionDependentOperationOnNonEmptyList() {
        assertEquals(
                0,
                listOf(2, 5).customFoldLeft(5, Int::div))
    }

    @Ignore
    @Test
    fun testFoldRightOnEmptyList() {
        assertEquals(
                2.0,
                emptyList<Double>().customFoldRight(2.0, Double::times))
    }

    @Ignore
    @Test
    fun testFoldRightWithDirectionIndependentOperationOnNonEmptyList() {
        assertEquals(
                15,
                listOf(1, 2, 3, 4).customFoldRight(5, Int::plus))
    }

    @Ignore
    @Test
    fun testFoldRightWithDirectionDependentOperationOnNonEmptyList() {
        assertEquals(
                2,
                listOf(2, 5).customFoldRight(5, Int::div))
    }

    @Ignore
    @Test
    fun testReversingEmptyList() {
        assertEquals(
                emptyList(),
                emptyList<Int>().customReverse())
    }

    @Ignore
    @Test
    fun testReversingNonEmptyList() {
        assertEquals(
                listOf('7', '5', '3', '1'),
                listOf('1', '3', '5', '7').customReverse())
    }

}

fun <T> List<T>.customAppend(other: List<T>): List<T> {
    if (isEmpty()) return other
    if (other.isEmpty()) return this
    return ArrayList<T>(size + other.size).apply {
        addAll(this@customAppend)
        addAll(other)
    }
}

fun <T> List<List<T>>.customConcat(): List<T> {
    if (isEmpty()) return emptyList()
    if (size == 1) return first()
    return ArrayList<T>(sumBy { it.size }).apply {
        this@customConcat.forEach { addAll(it) }
    }
}

fun <T> List<T>.customFilter(predicate: (T) -> Boolean): List<T> {
    if (isEmpty()) return emptyList()
    return ArrayList<T>(size).apply {
        this@customFilter.forEach {
            if (predicate(it)) add(it)
        }
    }
}

val <T> List<T>.customSize: Int
    get() {
        var result = 0
        forEach { result++ }
        return result
    }

fun <T, U> List<T>.customMap(mapper: (T) -> U): List<U> {
    if (isEmpty()) return emptyList()
    return ArrayList<U>(size).apply {
        this@customMap.forEach {
            add(mapper(it))
        }
    }
}

fun <T, U> List<T>.customFoldLeft(initial: U, folder: (U, T) -> U): U {
    if (isEmpty()) return initial
    var state = initial
    val iter = listIterator()
    while (iter.hasNext()) {
        state = folder(state, iter.next())
    }
    return state
}

fun <T, U> List<T>.customFoldRight(initial: U, folder: (T, U) -> U): U {
    if (isEmpty()) return initial
    var state = initial
    val iter = listIterator(size)
    while (iter.hasPrevious()) {
        state = folder(iter.previous(), state)
    }
    return state
}

fun <T> List<T>.customReverse(): List<T> {
    if (isEmpty()) return emptyList()
    return ArrayList<T>(size).apply {
        for (idx in this@customReverse.size-1 downTo 0) {
            add(this@customReverse[idx])
        }
    }
}

Community comments

Find this solution interesting? Ask the author a question to learn more.

What can you learn from this solution?

A huge amount can be learned from reading other people’s code. This is why we wanted to give exercism users the option of making their solutions public.

Here are some questions to help you reflect on this solution and learn the most from it.

What compromises have been made?
Are there new concepts here that you could read more about to improve your understanding?

araqnid's solution

to List Ops in the Kotlin Track