Как реализовать dropWhile рекурсивно с помощью foldRight в Котлине

Я реализую функции более высокого порядка рекурсивно с помощью .foldRight() как и 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() }) 

Во-первых, давайте набросаем идею решения.

С 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 должны быть включены в результат: это потому, что они имеют 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 этого кода с большим количеством тестов .


Примечание: копирование списка только для чтения с помощью uncertain + item или certain + uncertain + item на каждой итерации дает O(n^2) наихудшую временную сложность, что нецелесообразно. Использование изменяемых структур данных дает O(n) время.