ðŸŽ‰ Exercism Research is now launched. Help Exercism, help science and have some fun at research.exercism.io ðŸŽ‰

Ric0chet's solution

to List Ops in the Kotlin Track

Published at Jun 21 2019 · 2 comments
Instructions
Test suite
Solution

Note:

This exercise has changed since this solution 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.

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())
}

}``````
``````//  06-19-19

// All using (recursive) customFoldLeft or customFoldRight functions
val <T> List<T>.customSize: Int
get() = this.customFoldLeft(0) { acc, _ -> acc + 1 }

fun <T> List<T>.customAppend(that: List<T>): List<T> =
that.customFoldLeft(this) { acc, it -> acc + it }

fun <T> List<List<T>>.customConcat() =
this.customFoldLeft(emptyList<T>()) { acc, it -> acc + it }

fun <T> List<T>.customFilter(cond: (T) -> Boolean): List<T> =
this.customFoldLeft(emptyList()) { acc, it -> if (cond(it)) acc + it else acc }

fun <T, U> List<T>.customMap(func: (T) -> U) =
this.customFoldLeft(emptyList<U>()) { acc, it -> acc + func(it) }

fun <T, U> List<T>.customFoldLeft(acc: U, func: (U, T) -> U): U =
if (this.isEmpty()) acc else this.drop(1).customFoldLeft(func(acc, this.first()), func)

fun <T, U> List<T>.customFoldRight(acc: U, func: (T, U) -> U): U =
if (this.isEmpty()) acc else this.dropLast(1).customFoldRight(func(this.last(), acc), func)

fun <T> List<T>.customReverse(): List<T> =
this.customFoldRight(emptyList()) { it, acc -> acc + it }

//-----------------------------------
//     Less elegant solutions...
//-----------------------------------

// Custom Size Solutions
val <T> List<T>.customSize2: Int
get() {
var ret = 0
this.forEach { ret++ }
return ret
}

val <T> List<T>.customSize3: Int
get() = this.fold(0) { acc, _ -> acc + 1 }  // using built-in fold (here & below), might be "cheating"

// Custom Append Solutions
fun <T> List<T>.customAppend2(that: List<T>): List<T> {
val retList = this.toMutableList()
return retList
}

fun <T> List<T>.customAppend3(that: List<T>): List<T> =
that.fold(this.toMutableList()) { acc, it ->
acc
}

// Custom Concat Solutions
fun <T> List<List<T>>.customConcat2(): List<T> {
val retList = mutableListOf<T>()
return retList
}

fun <T> List<List<T>>.customConcat3(): List<T> =
this.fold(mutableListOf()) { acc, it ->
acc
}

fun <T> List<List<T>>.customConcat4() = flatMap { it }  // more "cheating"

// Custom Filter Solutions
fun <T> List<T>.customFilter2(cond: (T) -> Boolean): List<T> {
val retList = mutableListOf<T>()
this.forEach { if (cond(it)) retList.add(it) }
return retList
}

fun <T> List<T>.customFilter3(cond: (T) -> Boolean): List<T> =
this.fold(mutableListOf()) { acc, it ->
acc
}

// Custom Map Solutions
fun <T, U> List<T>.customMap2(func: (T) -> U): List<U> {
val retList = mutableListOf<U>()
return retList
}

fun <T, U> List<T>.customMap3(func: (T) -> U): List<U> =
this.fold(mutableListOf()) { acc, it ->
acc
}

// Custom Fold Left Solutions
fun <T, U> List<T>.customFoldLeft2(acc: U, func: (U, T) -> U): U {
var ret = acc
this.forEach { ret = func(ret, it) }
return ret
}

fun <T, U> List<T>.customFoldLeft3(acc: U, func: (U, T) -> U): U =
this.fold(acc) { acc, it -> func(acc, it) }     // using "shadowed" acc

// Custom Fold Right Solutions
fun <T, U> List<T>.customFoldRight2(acc: U, func: (T, U) -> U): U {
var ret = acc
this.reversed().forEach { ret = func(it, ret) }
return ret
}

fun <T, U> List<T>.customFoldRight3(acc: U, func: (T, U) -> U): U =
this.reversed().fold(acc) { acc, it -> func(it, acc) }  // using "shadowed" acc

// Custom Reverse Solutions
fun <T> List<T>.customReverse2(): List<T> {
val retList = mutableListOf<T>()
return retList
}

fun <T> List<T>.customReverse3(): List<T> =
this.reversed().fold(mutableListOf()) { acc, it ->
acc
}``````

The master of folds!

Note, however, that Collection.isEmpty() and Collection.plus() are used, for what it's worth.

(edited over 1 year ago)
Solution Author
commented over 1 year ago

True. The instructions didn't specify what we should & shouldn't use (the joys of Exercism in Independent Mode). My assumption is that solutions like =flatmap are right out, the others are fuzzier -- ForEach is just a lambda'd For loop, Fold is just ForEach with an accumulator, etc.

(edited over 1 year ago)

Ric0chet's Reflection

All solutions based on customFoldLeft or customFoldRight. (Includes my earlier solutions, which demonstrate transforming simple loops into inline lambdas.)