Partitioning consecutive elements of a list based on a predicate in functional style

user_223365 0
Viewed 266

I need to implement a function in Kotlin:

fun <T> partitionConsecutiveWithPredicate(input : List<T>, pred : (T, T) -> Boolean) : List<List<T>>

The function partitions the input list into a list of lists when every sub-list in the resulting list is a group of consecutive elements from the original list which conform to the provided predicate.

Example #1 - invoking the method on the Int list of [2, 2, 2, 2, 5, 5, 8, 2, 2, 3]
with the predicate { t1 : Int, t2 : Int -> t1 == t2}
should result in [[2, 2, 2, 2], [5, 5], [8], [2, 2], [3]]

Example #2 - invoking the method on the Int list of [1, 2, 3, 4, 3, 2, 1, 2]
with the predicate { t1 : Int, t2 : Int -> t2 == t1 + 1}
should result in [[1, 2, 3, 4], [3], [2], [1, 2]]

Naturally, I can achieve that with a traditional while-loop and list manipulation library functions, but I want to do it in a purely functional style, i.e. only using lambdas/sequences (no explicit for/while loops allowed). I tried using runningReduce and runningFold, but it creates a resulting list in every step, which isn't desirable in this case (you should create a sub-list only when the predicate stops being satisfied).

EDIT: It's been brought to my attention that a similar question exists, but said question doesn't emphasize the need for a functional solution, therefore I'm leaving this one as is.

kotlin lambda functional-programming
1 Answers

There might be better ways of doing it, one way is using a loop:

fun <T> partitionConsecutiveWithPredicate2(input: List<T>, pred: (T, T) -> Boolean): List<List<T>> {
    val result = mutableListOf<List<T>>()
    var currentList = mutableListOf<T>()
    input.forEachIndexed { i, el ->
        currentList.add(el)
        if (i + 1 >= input.size || !pred(el, input[i + 1])) {
            result.add(currentList.toList())
            currentList = mutableListOf()
        }
    }
    return result
}

The idea here is to accumulate the values in the currentList until all the elements have been processed (i + 1 >= input.size) or the predicate is not fulfilled in which case the currentList is added to the result and emptied.

Executable code in kotlin playground: https://pl.kotl.in/rv_Yq8WdG with functional and iterative versions.

Or use fold:

fun <T> partitionConsecutiveWithPredicate(input: List<T>, pred: (T, T) -> Boolean)
    = input
        .fold(mutableListOf()) { acc: MutableList<MutableList<T>>, elem ->
            when {
                acc.lastOrNull() == null -> acc.add(mutableListOf(elem))
                acc.lastOrNull() != null -> acc.last().apply {
                    if (pred(last(), elem)) {
                        add(elem)
                    } else {
                        acc.add(mutableListOf(elem))
                    }
                }
            }
            acc
        }

Executable code in kotlin playground: https://pl.kotl.in/z_ccIgX5C

user_15408540
Related