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

我一直在使用.foldRight()递归地实现高阶函数，就像实践一样，但是却一直难以实现。 _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() })

首先，我们概述解决方案的概念。

使用foldRight ，您只能从右到左逐个处理项目，保持累加器。

问题是，对于位置i处的项目， dropWhile逻辑基于在位置j <= i处是否存在不满足谓词的项目来决定是否将项目包括到结果中（如果是，则包括）。 这意味着你不能简单地维护结果项目：对于你已经处理的一些项目，你不知道它们是否应该包括在内。

例：

（我们正在处理的项目从右到左，所以前缀是我们不知道的） 

 ... (some unknown items) ... ... ... ... abcd <--- (right-to-left) predicate satisfied: TTFT

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

  • 我们找到了序列的开始，没有给出谓词F项目： 

      (the sequence start) yzabcd <--- (right-to-left) predicate satisfied: TTTTFT ------- drop

    在这种情况下，应该删除前缀yzab 。

  • 我们发现一个不满足谓词的项目： 

     ... (some unknown items) ... wzabcd <--- (right-to-left) predicate satisfied: FTTTFT ------- include

    只有在这一点上，我们肯定知道我们需要包含wzab项目，我们不能这样做，因为可能有序列的开始，而不是项目w ，然后我们应该丢弃zab 。

但是请注意，在这两种情况下，我们都确定项目cd将被包含到结果中：这是因为它们在前面具有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演示与更多的测试 。

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

Interesting Posts