CODEWITHSUNDEEP
recursioncollectionskotlinhigher-order-functionsfold
ersin-ertan
ersin-ertan

Reputation: 2301

How to implement dropWhile recursively using foldRight in Kotlin

I've been implementing higher order functions recursively with .foldRight() like any, all, and takeWhile as practice, but dropWhile has been elusive. _Collections.kt has the imperative way but I couldn't convert it to a recursive structure.

For reference, this is takeWhile

fun takeWhile(list:List<Int>, func:(Int) -> Boolean):List<Int> = list.foldRight(emptyList(),
    { next:Int, acc:List<Int> -> if (func(next)) acc.plus(next) else emptyList() })

Upvotes: 2

Views: 1176

Answers (1)

hotkey
hotkey

Reputation: 148119

First, let's outline the idea of the solution.

With foldRight, you can only process the items one by one from right to left, maintaining an accumulator.

The problem is, for an item at position i, the dropWhile logic makes a decision whether to include the item into the result or not based on whether there is an item at position j <= i that does not satisfy the predicate (include if yes). This means you cannot simply maintain the result items: for some items you already processed, you don't know if they should actually be included.

Example:

(we're processing the items right-to-left, so the prefix is unknown to us)

... (some unknown items) ... ... ... ... a b c d <--- (right-to-left)
                   predicate satisfied:  T T F T

As we discover more items on the left, there are two possibilities:

  • We found the beginning of the sequence, and there were no items that gave F on the predicate:

              (the sequence start) y z a b c d <--- (right-to-left)
         predicate satisfied:  T T T T F T
                               -------
                                 drop

    In this case, the prefix y z a b should be dropped.

  • We found an item that does not satisfy the predicate:

    ... (some unknown items)  ...  w z a b c d <--- (right-to-left)
         predicate satisfied:  F T T T F T
                               -------
                               include

    Only at this point we know for sure that we need to include the items w z a b, we could not do that earlier because there could be the beginning of the sequence instead of item w, and then we should have dropped z a b.

But note that in both cases we are certain that the items c d are to be included into the result: that's because they have c with F predicate in front of them.

Given this, it becomes clear that, when processing the items right-to-left, you can maintain a separate list of items that are not certain to be included into the result and are either to be dropped or to be included when a false predicate result is encountered, together with the item that gave such false result.

My implementation:

I used a pair of two lists for the accumulator, where the first list is for the items that are certain to be included, and the second one for those which are not.

fun <T> List<T>.myDropWhile(predicate: (T) -> Boolean) =
    foldRight(Pair(emptyList<T>(), emptyList<T>())) { item, (certain, uncertain) ->
        if (predicate(item))
            Pair(certain, uncertain + item) else
            Pair(certain + uncertain + item, emptyList())
    }.first.reversed()

Example:

val ints = listOf(0, 0, 0, 1, 0, 2, 3, 0, 0, 4)
println(ints.myDropWhile { it == 0 }) // [1, 0, 2, 3, 0, 0, 4]

See: runnable demo of this code with more tests.

Note: copying a read-only list by doing uncertain + item or certain + uncertain + item in each iteration gives O(n^2) worst-case time complexity, which is impractical. Using mutable data structures gives O(n) time.

Upvotes: 3

Related Questions