recursion - 如何在 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 逻辑根据位置 j <= i 是否存在不满足谓词的项目(如果是，则包括)来决定是否将项目包含到结果中。这意味着您不能简单地维护结果项目:对于您已经处理的某些项目，您不知道它们是否应该实际包含在内。

例子:

(我们从右到左处理项目，所以前缀对我们来说是未知的)

... (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) 时间。