Как вернуть новый список из функции в scala?

Question

В образовательных целях я хочу реализовать функцию фильтра, которая принимает фильтр типа (_> 4) и список в качестве параметров. Должен вернуть отфильтрованный список. По сути, он должен делать то же самое, что и уже доступная функция list.filter, но я хочу реализовать это сам. Вопрос в том, как создать новый список из функции. Я не хочу изменять список из параметра, и поэтому я думаю, что это единственный способ сделать это.

Answer 1

Вот очень простой пример. Это не оптимально, вы все равно можете его улучшить.

val list1 =  List(1,2,3,4,5,6,7,8,9)

def filter(list:List[Int], predicate:Int => Boolean):List[Int] = list match {
  case Nil => Nil
  case head :: rest => 
    val frest = filter(rest, predicate)
    if (predicate(head)) head :: frest else frest 
}

println(filter(list1, _ > 2)) //List(3, 4, 5, 6, 7, 8, 9)
println(filter(list1, _ %2 == 0)) //List(2, 4, 6, 8)

https://scalafiddle.io/sf/yvLEnYL/7

Чтобы понять это, вы должны прочитать о рекурсии и сопоставлении с образцом в scala , Уловка здесь - это case head :: rest => часть, которая заботится о разбивке списка на первый элемент и остальном (rest может быть пустым списком Nil). Есть много материалов о том, например, есть хороший курс в Coursera, который охватывает такие темы (https://www.coursera.org/learn/progfun1).

Answer 2

Расширяя ответ @ Scalway, следующим логическим шагом может быть оптимизация рекурсивной функции до хвостовой рекурсии . Рекурсивная функция может быстро создавать кадры стека, которые приводят к StackOverflowError, но компилятор Scala может оптимизировать хвостовую рекурсивную функцию для использования только одного кадра стека.

def filter(list: List[Int], cond: Int => Boolean): List[Int] = {
  @scala.annotation.tailrec
  def loop(pending: List[Int], cumulated: List[Int]): List[Int] = pending match {
    case Nil =>
      cumulated
    case head :: tail =>
      loop(tail, if (cond(head)) head :: cumulated else cumulated)
  }
  loop(list, Nil).reverse
}

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

Поскольку filtering это обычное преобразование, применимое почти ко всем коллекциям, и для того, чтобы функция взяла список generi c type , я включаю также обобщенный фрагмент:

def filter[T](list: List[T], cond: T => Boolean): List[T] = {
  @scala.annotation.tailrec
  def loop(pending: List[T], cumulated: List[T]): List[T] = pending match {
    case Nil =>
      cumulated
    case head :: tail =>
      loop(tail, if (cond(head)) head :: cumulated else cumulated)
  }
  loop(list, Nil).reverse
}

Тестирование:

filter[Int](List(1, 2, 3, 4, 5), _ != 3)
// res1: List[Int] = List(1, 2, 4, 5)

filter[String](List("apple", "pear", "orange"), _ contains "r")
// res2: List[String] = List("pear", "orange")