如何在 Kotlin 中使用 foldRight 递归地实现 dropWhile

Question

我一直在使用 .foldRight() 递归地实现高阶函数，例如 any、all 和 takeWhile 作为实践，但是 dropWhile难以捉摸。 _Collections.kt 有命令式的方式，但我无法将其转换为递归结构。

作为参考，这是 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() })

Answer 1

首先，让我们概述一下解决方案的思路。

使用foldRight，只能从右到左逐项处理，维护一个累加器。

问题是，对于位置i的项目，dropWhile逻辑根据位置[是否有项目来决定是否将项目包含在结果中=18=] 不满足谓词（如果是则包含）。这意味着您不能简单地维护结果项：对于您已经处理过的某些项，您不知道它们是否真的应该包括在内。

示例：

_{（我们从右到左处理项目，所以我们不知道前缀）}

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

当我们在左侧发现更多项目时，有两种可能性：

我们找到了序列的开头，并且没有在谓词上给出 F 的项目：

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

在这种情况下，应删除前缀 y z a b。

我们发现了一个不满足谓词的项目：
```
... (some unknown items)  ...  w z a b c d <--- (right-to-left)
         predicate satisfied:  F T T T F T
                               -------
                               include
```
只有在这一点上我们才能确定我们需要包括项目 w z a b，我们不能更早地这样做，因为可能是序列的开头而不是项目 w，然后我们应该删除 z a b.

但请注意，在这两种情况下，我们都确定项目 c d 将包含在结果中：那是因为它们前面有 c 和 F 谓词.

鉴于此，很明显，当从右到左处理项目时，您可以维护一个单独的项目列表，这些项目不一定包含在结果中，要么被删除，要么被删除。当遇到 false 谓词结果时包括在内，以及给出这种 false 结果的项目。

我的实现：

_{我为累加器使用了一对两个列表，其中第一个列表用于确定包含的项目，第二个列表用于不包含的项目。}

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

示例：

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]

参见：runnable demo of this code with more tests。

注意： 通过在每次迭代中执行 uncertain + item 或 certain + uncertain + item 来复制只读列表给出 O(n^2) 最坏情况时间复杂度，这是不切实际的。使用可变数据结构给了 O(n) 时间。

如何在 Kotlin 中使用 foldRight 递归地实现 dropWhile

How to implement dropWhile recursively using foldRight in Kotlin

collections

recursion

fold

higher-order-functions

kotlin