如何实现递归使用foldRight dropWhile在科特林

问题描述：

我已经实现高阶函数递归与.foldRight()像any，all，并takeWhile的做法，但dropWhile一直难以捉摸。 _Collections.kt具有必要的方式，但我无法将其转换为递归结构。如何实现递归使用foldRight dropWhile在科特林

以供参考，这是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) ... ... ... ... 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)时间。

如何实现递归使用foldRight dropWhile在科特林

相关推荐