Kotlin - функциональное программирование, рекурсивная реализация функции фильтра списка

Question

Задача о функциональном программировании в Kotlin, дан класс запечатанного списка, и наша задача - реализовать карту, сложить, заменить, отфильтровать и любой рекурсивно. До сих пор я реализовал каждую функцию, кроме фильтра, но я очень близок, я просто что-то упустил.

Данный класс List:

   sealed class List<T> {

    class Node<T>(val head: T, val tail: List<T>) : List<T>() {
        override fun toString() =
            "${head.toString()} , ${tail.toString()}"
    }

    object Nil : List<Nothing>() {
        override fun toString() = "NIL"
    }

    companion object {
        operator
        fun <T> invoke(vararg values: T): List<T> {
            val empty = Nil as List<T>
            val res = values.foldRight(empty, { v, l -> l.addFirst(v) })
            return res
        }
    }

    fun addFirst(head: T): List<T> = Node(head, this)

    fun removeFirst(): List<T> = when (this) {
        is Nil -> throw IllegalStateException()
        is Node<T> -> this.tail
    }
}

Моя реализация map и replaceif:

fun <T, R> map(list: List<T>, f: (T) -> R): List<R> = when (list) {
    is List.Nil -> List.Nil as List<R>
    is List.Node -> List.Node(f(list.head), map(list.tail, f))
}

fun <T> replaceIf (list : List<T> , f : (T)-> T , p : (T)-> Boolean ):List<T> = when (list) {
    is List.Nil -> List()
    is List.Node -> List.Node(if(p(list.head)) f(list.head) else list.head, replaceIf(list.tail, f, p))
}

Наконец, фильтр, который не совсем корректен:

fun <T> filter(list: List<T>, p: (T) -> Boolean): List<T> = when (list) {
    is List.Nil -> List()
    is List.Node -> {
        val it = if(p(list.head)) 'something' else 'something'
        List.Node(it,filter(list.tail, p))
    }
}

Я хочу рекурсивно проверить, является ли p истинным для каждого элемента, если он есть, он должен отфильтровать этот элемент, иначе это до нового списка. Так что мне нужно изменить свое if / else «что-то», чтобы оно работало.

Answer 1

Ладно, так какой же будет алгоритм фильтрации списка?

1. Если Nil, то Nil
2. Если предикат Node AND (head), вернуть тот же список с отфильтрованный хвост.
3. Если предикат Node AND! (head) возвращает только отфильтрованный хвост

Итак, реализация будет:

fun filter(predicate: (T) -> Boolean): FList<T> = when (this) {
    is Nil -> this
    is Node<T> -> if (predicate(head)) Node(head, tail.filter(predicate)) else tail.filter(predicate)
}

PS: I поместите эти функции в область действия class, поэтому вместо передачи списка в функцию я использую указатель this. Это позволяет объединять вызовы, например, filter, map и foreach:

FList(0, 1, 2, 3, 4, 5, 6, 7, 8)
    .filter { it % 3 == 0 }
    .map { it * 2 }
    .foreach { println(it) }