TL; DR One Line Решение:
val list = List(1,2,2,2,2,3,4,5)
list.zipWithIndex.filter(_._1 == 2).map(_._2) // List(1, 2, 3, 4)
Или назовите свои переменные с помощью регистра:
list.zipWithIndex.filter { case(value,index) => value == 2 } map { case(value,index) => index }
Или используйте метод сбора для объединения фильтраи карта:
list.zipWithIndex.collect { case (value,index) if value == 2 => index }
Рекурсия
Если вам действительно нужно использовать рекурсию, есть простой и сложный способ сделать это, и похоже, что выПытаюсь сделать это трудным путем.Трудный путь имеет смысл в этом случае, но сначала я сделаю его простым, чтобы помочь вам показать, что я делаю и почему.
Итак, учитывая список
val list = List(1,2,2,2,2,3,4,5) // named list instead of l because l looks like 1.
Нам нужна функция findIndices такая, что findIndices(list,2) возвращает List(1,2,3,4)
Я собираюсь начать с определения findIndices следующим образом:
def findIndices(list: List[Any], element: Any): List[Any] = ???
Теперь есть паравещи, которые я хочу изменить прямо сейчас.Во-первых, ваш пример использует список вещей с одним типом, так что это выглядит как отличная возможность использовать параметризованный тип.
def findIndices[T](list: List[T], element: T): List[Any] = ???
Во-вторых, независимо от того, что находится внутри списка, получаемый результатсписок индексов будет целым числом, потому что индексы являются целыми числами.
def findIndices[T](list: List[T], element: T): List[Int] = ???
Так что теперь я готов работать над телом метода.Я знаю, что это должно быть рекурсивно, и общая форма рекурсивной функции:
- проверка на завершение регистра.
- обработка не завершающих регистра.
Итак, моя функция будет выглядеть примерно так:
def findIndices[T](list: List[T], element: T): List[Int] = {
// if (terminating case) return termination
// else if (check for next index of element) return index plus recursive call
// else return recursive call
}
Заполнение пробелов дает нам что-то вроде этого:
def findIndices[T](list: List[T], element: T): List[Int] = {
if (list.isEmpty) List.empty[Int]
else if (list.head == element) 0 :: findIndices(list.tail, element)
else findIndices(list.tail, element)
}
К сожалению, в этом коде есть ошибка.Мы рассчитываем индексы на основе постоянно сокращающегося списка, а не исходного списка.Мы можем исправить это, отслеживая смещение индексов, так как мы используем более короткие и короткие версии списка:
def findIndices[T](list: List[T], element: T, offset: Int = 0): List[Int] = {
if (list.isEmpty) List.empty[Int]
else if (list.head == element) offset :: findIndices(list.tail, element, offset + 1)
else findIndices(list.tail, element, offset + 1)
}
Этот метод работает, как предполагалось ... только для небольших списков.Для очень больших списков мы получим переполнение стека.Способ исправить это состоит в том, чтобы сделать метод хвостовым рекурсивным, так что программе не нужно отслеживать стек, поскольку он выполняет каждый вызов.Это то, что вы пытаетесь сделать в своем вопросе.Я назвал это сложным способом, но как только у вас есть не хвостовая рекурсивная функция, преобразование ее в хвостовую рекурсивную функцию на самом деле довольно простое и механическое.
def findIndices[T](list: List[T], element: T, offset: Int = 0): List[Int] = ???
Внутри первой функции мы определяем новую функцию.Эта новая функция будет иметь те же параметры, что и старая, плюс аккумулятор.Этот аккумулятор позволит нам передавать промежуточные результаты алгоритма по стеку для следующего рекурсивного вызова функции, поэтому программе не нужно будет поддерживать стек вызовов для отслеживания каждого промежуточного результата.
единственное, что сделает наша внешняя функция, это вызовет внутреннюю функцию с начальными параметрами.
def findIndices[T](list: List[T], element: T, offset: Int = 0): List[Int] = {
def findIndicesAcc(list: List[T], element: T, acc: List[Int], offset: Int = 0): List[Int] = {
// do logic here
}
findIndicesAcc(list, element, List.empty[Int])
}
Логика внутри функции накопителя будет очень похожа на исходную функцию.Он просто воспользуется параметром аккумулятора вместо того, чтобы оставлять промежуточный результат в стеке.
def findIndices[T](list: List[T], element: T, offset: Int = 0): List[Int] = {
def findIndicesAcc(list: List[T], element: T, acc: List[Int], offset: Int = 0): List[Int] = {
if (list.isEmpty) acc
else if (list.head == element) findIndicesAcc(list.tail, element, offset + 1, offset :: acc)
else findIndicesAcc(list.tail, element, offset + 1, acc)
}
findIndicesAcc(list, element, List.empty[Int])
}
Эта функция работает, как и предполагалось, но есть пара заключительных элементов учета и очистки, которые мы можем сделать.Во-первых, мы можем избавиться от самого внешнего параметра смещения и убрать значение по умолчанию для внутреннего параметра смещения.Во-вторых, мы можем добавить аннотацию @tailrec к внутренней функции, чтобы убедиться, что мы решили проблему переполнения стека.В-третьих, если важен порядок индексов в возвращаемом списке, мы можем вызвать реверс на выходе аккумулятора.
import scala.annotation.tailrec
def findIndices[T](list: List[T], element: T): List[Int] = {
@tailrec
def findIndicesAcc(list: List[T], element: T, offset: Int, acc: List[Int]): List[Int] = {
if (list.isEmpty) acc
else if (list.head == element) findIndicesAcc(list.tail, element, offset + 1, offset :: acc)
else findIndicesAcc(list.tail, element, offset + 1, acc)
}
findIndicesAcc(list, element, 0, List.empty[Int]).reverse
}
Подробнее о рекурсии Tail
Хвостовая рекурсия относится к рекурсивной функции, где рекурсивный вызов - это последнее, что происходит в функции.Иногда вам нужно присмотреться, чтобы увидеть, является ли что-то хвостовым или нет.Например, фрагмент кода
else if (list.head == element) offset :: findIndices(list.tail, element, offset + 1)
не является хвостовой рекурсией, потому что offset должен быть добавлен перед результатами findIndices после его возвращения.Это может стать более понятным, если мы разбиваем каждую операцию фрагмента кода на отдельные строки:
else if (list.head == element) {
val tail = list.tail
val newOffset = offset + 1
val recursiveResult = findIndices(tail, element, newOffset)
return offset :: recursiveResult
}
Когда код разбит таким образом, мы можем видеть, что послеfindIndices recursive * call return.
С другой стороны, фрагмент кода
else if (list.head == element) findIndicesAcc(list.tail, element, offset + 1, offset :: acc)
является хвостово-рекурсивным.Когда мы разбиваем операции на отдельные строки, мы получаем
else if (list.head == element) {
val tail = list.tail
val newOffset = offset + 1
val combinedList = offset :: acc
return findIndicesAcc(tail, element, newOffset, combinedList)
}
и ясно видим, что вызов findIndicesAcc - это последнее, что происходит.
В первом случаеПрограмма вынуждена поддерживать весь стек вызовов, потому что она должна помнить, какое значение offset было в каждой предыдущей итерации функции.На машинах Linux у нас обычно есть 8 МБ стека.Для очень длинных списков мы используем все 8 МБ стека, что приводит к исключению переполнения стека.
Во втором случае все соответствующие данные передаются на следующую итерацию рекурсивной функции.,В предыдущем вызове функции нет ничего, что необходимо отслеживать программе.Компилятор может обнаружить это и оптимизировать код в основном цикл.В этом случае нет стека вызовов, который нужно поддерживать, и, следовательно, нет риска исключения переполнения стека.
Последнее предупреждение: я проверял этот код как можно ближе, но у меня не было доступа ккомпилятор scala, когда я написал это, поэтому я прошу прощения за любые опечатки.