Avatar of nbanman

nbanman's solution

to List Ops in the Kotlin Track

Published at Jun 23 2019 · 0 comments
Instructions
Test suite
Solution

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.

The precise number and names of the operations to be implemented will be track dependent to avoid conflicts with existing names, but the general operations you will implement include:

  • append (given two lists, add all items in the second list to the end of the first list);
  • concatenate (given a series of lists, combine all items in all lists into one flattened list);
  • filter (given a predicate and a list, return the list of all items for which predicate(item) is True);
  • length (given a list, return the total number of items within it);
  • map (given a function and a list, return the list of the results of applying function(item) on all items);
  • foldl (given a function, a list, and initial accumulator, fold (reduce) each item into the accumulator from the left using function(accumulator, item));
  • foldr (given a function, a list, and an initial accumulator, fold (reduce) each item into the accumulator from the right using function(item, accumulator));
  • reverse (given a list, return a list with all the original items, but in reversed order);

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.

Setup

Go through the setup instructions for Kotlin to install the necessary dependencies:

https://exercism.io/tracks/kotlin/installation

Making the test suite pass

Execute the tests with:

$ gradlew test

Use gradlew.bat if you're on Windows

In the test suites all tests but the first have been skipped.

Once you get a test passing, you can enable the next one by removing the @Ignore annotation.

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> =
        List<T>(this.customSize + other.customSize) {
            if (it < this.customSize) {
                this[it]
            } else {
                other[it - this.customSize]
            }
        }

val Collection<Any?>.customSize: Int
    get() {
        var size = 0

        for (element in this) {
            size++
        }
        return size
    }

// Can probably be deleted
fun Collection<Any?>.customSize(): Int {

    var size = 0

    for (element in this) {
        size++
    }
    return size
}


fun <T, C: List<T>> List<C>.customConcat(): List<T> {
    // Add up sublist sizes to get size of new list
    var size = 0
    for (element in this) {
        size += element.customSize
    }

    // Make new list of proper size and populate
    var superIndex = 0
    var offset = 0
    return List<T>(size) {index ->
        if (index - offset == this[superIndex].customSize) {
            do {
                superIndex++
            } while (this[superIndex].customSize == 0)
            offset = index
        }
        this[superIndex][index - offset]
    }
}

// Helper function in quest to use 0 list functions other than constructors!
fun <T> List<T>.customPlus(element: T): List<T> {
    return List<T>(this.customSize + 1) {index ->
        if (index < this.customSize) this[index] else element
    }
}

fun <T> List<T>.customFilter(predicate: (T) -> Boolean):List<T> {

    var newList = listOf<T>()

    for (element in this) {
        if (predicate(element)) newList = newList.customPlus(element)
    }

    return newList
}

fun <T, R> List<T>.customMap(transform: (T) -> R): List<R> {

    return List<R>(this.customSize) { index ->
        transform(this[index])
    }
}

fun <T, R> List<T>.customFoldLeft(initial: R, operation: (acc: R, T) -> R): R {
    var acc = initial
    for (element in this) {
        acc = operation(acc, element)
    }
    return acc
}

fun <T, R> List<T>.customFoldRight(initial: R, operation: (T, acc: R) -> R): R {
    var acc = initial
    for (i in this.customSize -1 downTo 0) {
        acc = operation(this[i], acc)
    }
    return acc
}

fun <T> List<T>.customReverse(): List<T> {
    return List<T>(this.customSize) { index ->
        this[this.customSize - 1 - index]
    }
}

Community comments

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

nbanman's Reflection

Victory lap: only list functions used were the constructors. I wrote whole library before testing, and testing found only two bugs. I thought this would be my buggiest exercise yet; instead it was one of my least.

One bug was in concat. It did not handle skipping over empty lists. An easy do while loop fixed that.

The other bug was due to my not understanding how foldRight works. I thought you could just reverse the elements; i.e., list.foldRight = list.reversed().foldLeft. But it also reverses the processing of the accumulator. So this was a quick fix once I understood what I was aiming for.