Блог

Главная - Вопросы по программированию - Рекурсивный поиск n-го элемента списка в scala с сопоставлением с образцом

Рекурсивный поиск n-го элемента списка в scala с сопоставлением с образцом

#list #scala #recursion #pattern-matching

#Список #scala #рекурсия #сопоставление с образцом

Вопрос:

У меня здесь проблема из 99 проблем scala (http://aperiodic.net/phil/scala/s-99/p03.scala ), что я пытаюсь понять, как это работает. Я довольно новичок в Scala. Я смог выполнить эту задачу с помощью аналогичного решения, используя сопоставление с образцом и рекурсию, однако мой не рассматривал список в сопоставлении. Мой код приведен ниже:

 def nth[A](k: Int, l: List[A]): A = k match {
  case 0 => l.head
  case _ => nth(k-1, l.drop(1))
}

и это, казалось, сделало свое дело. Однако нет проверки ошибок, если список равен нулю. Решение 99 проблем scala обеспечивает:

 def nthRecursive[A](n: Int, ls: List[A]): A = (n, ls) match {
  case (0, h :: _   ) => h
  case (n, _ :: tail) => nthRecursive(n - 1, tail)
  case (_, Nil      ) => throw new NoSuchElementException
}

Чего я не понимаю, так это 

 case(0, h:: _ )

и 

 case(n, _ :: tail)

Что здесь делает автор? Я понимаю :: добавляет все, что находится слева, к началу того, что справа, но я точно не уверен, что происходит. Кто-нибудь может меня просветить?

Спасибо!

Ответ №1:

Оператор :: используется для извлечения заголовка и остальной части списка (хвоста).

Здесь:

 case(0, h :: _ )

только заголовок имеет значение, поэтому хвост не получает ссылку.

И здесь:

 case(n, _ :: tail)

имеет значение только хвост, поэтому заголовок не получает ссылку.

Вы также можете использовать:

 case(0, head :: tail)
case(n, head :: tail)

(т. е. Предоставление ссылки на обе части) и получение точно такого же результата.

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

1. Итак, в основном, поскольку _ является шаблоном (соответствует чему-либо), но на самом деле не хранит что-то, совпадение будет хранить только head и игнорировать tail? Это интересно. Интересно, почему этот синтаксис не описан в документации по списку на веб-сайте Scala.

Ответ №2:

По сути, это выражение сопоставления с образцом. Вот почему сопоставление шаблонов Scala настолько мощно, поэтому мы можем отбросить некоторые тяжелые шаблоны посетителей, такие как Java (из этой темы).

Простой пример:

 case class User(name: String, age: Int)

def doStuff(user: User) = user match {
  case User(_, age) if age > 100 => println("Impossible!")
  case User(name, _) => println("hello "   name)
}

В этом случае _ :: tail просто означает, что я хочу получить ссылку на хвост.