CODEWITHSUNDEEP
kotlinfilterfunctional-programming
Steytz
Steytz

Reputation: 394

Kotlin - functional programming recursive implementation of the list filter function

The task is about functional programming in Kotlin, a sealed list class is given and our task is to implement map, fold, replaceif, filter, and any recursively. So far i have implemented every single function except filter, but i am very close, i am just missing something.

Given List class:

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

My implementation of map and 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))
}

Lastly filter which is not entirely correct:

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

I basically want to recursively test if p is true for each element if it is, it should filter out that element else let it through to the new List. So i need to change my if/else 'something' so it works.

Upvotes: 1

Views: 813

Answers (1)

Cililing
Cililing

Reputation: 4753

Okey, so, what would be the algorithm to filter a list?

  1. If Nil then Nil
  2. If Node AND predicate(head) then return the same list with a filtered tail.
  3. If Node AND !predicate(head) then return a filtered tail only

So, implementation would be:

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 put those function in class scope, so instead of passing a list into a function I use this pointer. This allows to chaining calls, for example filter, map and foreach:

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

Upvotes: 1

Related Questions