Блог

Главная - Вопросы по программированию - Как реализовать пользовательскую хвостовую рекурсивную карту для списков в Scala

Как реализовать пользовательскую хвостовую рекурсивную карту для списков в Scala

#scala

#scala

Вопрос:

Я хочу реализовать функцию с именем map, которая получает список и функцию и выдает результат применения функции к каждому элементу входного списка. Итак, у меня пока есть это:

 def map(list: List[Int], function: (Int) => Int): List[Int] = {
  def loop(list: List[Int], acc: List[Int]): List[Int] = {
    list match {
      case Nil => acc
      case head :: tail => loop(list.tail, function(head) :: acc)
    }
  }
  loop(list.reverse, Nil)
}

Этот код работает и дает мне ожидаемый результат, но я не могу отделаться от мысли, что есть более элегантный и эффективный способ, который не предполагает использования reverse или другого метода list, который не является head or tail .

Комментарии:

1. Нет, это не так. У вас было три варианта: 1) Два хвостовых рекурсивных обхода списка (что вы и сделали, однако чаще всего список переворачивается в конце) . 2) Пройдитесь по списку один раз с помощью не-хвостовой рекурсивной функции, которая может увеличить ваш стек. 3) Используйте мутацию и стандартный цикл while для достижения безопасности стека и только одного обхода (это то, что делает реализация стандартной библиотеки) . — Ну, вы также можете реализовать map в терминах других функций, таких как flatMap , foldLeft , foldRight . Но все они сходятся к предыдущим трем случаям.

Ответ №1:

Что касается развертывания вашей собственной реализации чисто функциональной map функции, без использования какого-либо изменяемого состояния или встроенных List функций более высокого порядка, вы проделали отличную работу! reverse Список кажется ненужным, но оно того стоит, потому что добавление к списку — очень эффективная операция.

Помимо других методов, предложенных в комментариях, вы могли бы создать acc a scala.collection.mutable.ListBuffer (который поддерживает эффективные операции добавления и дописывания), а затем преобразовать его в список, когда закончите. Однако процесс преобразования не является большим улучшением по сравнению с reverse .

В противном случае, есть несколько незначительных вещей, которые вы можете сделать, чтобы улучшить свою map функцию:

  • Используя аргументы curried, вы можете использовать map более элегантно.
  • Функции, которые должны быть хвостово-рекурсивными, всегда должны быть украшены scala.annotation.tailrec атрибутом. Затем компилятор Scala узнает о ваших намерениях и выдаст ошибку, если функция не может быть оптимизирована для использования хвостовой рекурсии.
  • Тривиально сделать эту функцию универсальной, что сделает ее гораздо более полезной.
  • Обычно более идиоматично выполнять reverse операцию над результатом. Это не имеет значения для операции map, но если бы вы написали, например, операцию filter, то было бы эффективнее отменить потенциально меньший набор отфильтрованных элементов.

Вот как это тогда выглядело бы: 

 import scala.annotation.tailrec

def map[A, B](list: List[A])(function: (A) => B): List[B] = {

  @tailrec
  def loop(rem: List[A], acc: List[B]): List[B] = rem match {
    case Nil => acc.reverse
    case head :: tail => loop(tail, function(head) :: acc)
  }
  loop(list, Nil)
}

Ответ №2:

Поскольку head :: tail это наиболее эффективный способ деконструкции и реконструкции List , то, что вы сделали, является довольно распространенным шаблоном. .reverse Неудачно, но обычно приводит к незначительному снижению производительности.

Как упоминалось в комментариях, map также может быть реализовано с помощью других стандартных библиотечных методов. Здесь это делается с помощью foldRight :

 def map(list :List[Int], function :Int => Int) :List[Int] = 
  list.foldRight(List.empty[Int])(function(_) :: _)