Ответ 1
Это самая минимальная рекурсивная реализация max, которую я когда-либо мог придумать:
def max(xs: List[Int]): Option[Int] = xs match {
case Nil => None
case List(x: Int) => Some(x)
case x :: y :: rest => max( (if (x > y) x else y) :: rest )
}
Он работает, сравнивая первые два элемента в списке, отбрасывая меньший (или первый, если оба равны), а затем вызывает себя в оставшемся списке. В конце концов, это уменьшит список до одного элемента, который должен быть самым большим.
Я возвращаю Опцию, чтобы иметь дело с тем, чтобы получить пустой список без исключения исключения, что заставляет вызывающий код распознавать возможность и обрабатывать его (вплоть до вызывающего, если они хотят выбросить исключение).
Если вы хотите, чтобы он был более общим, он должен быть написан следующим образом:
def max[A <% Ordered[A]](xs: List[A]): Option[A] = xs match {
case Nil => None
case x :: Nil => Some(x)
case x :: y :: rest => max( (if (x > y) x else y) :: rest )
}
который будет работать с любым типом, который либо расширяет черту Ordered, либо имеет неявное преобразование от A до Ordered[A] в области видимости. Поэтому по умолчанию он работает для Int, BigInt, Char, String и т.д., Потому что scala.Predef определяет для них конверсии.
Мы можем стать еще более типичными:
def max[A <% Ordered[A]](xs: Seq[A]): Option[A] = xs match {
case s if s.isEmpty || !s.hasDefiniteSize => None
case s if s.size == 1 => Some(s(0))
case s if s(0) <= s(1) => max(s drop 1)
case s => max((s drop 1).updated(0, s(0)))
}
который будет работать не только со списками, но и с векторами и любой другой коллекцией, которая расширяет черту Seq. Обратите внимание, что мне пришлось добавить чек, чтобы увидеть, действительно ли последовательность имеет определенный размер - это может быть бесконечный поток, поэтому мы отступаем, если это может быть так. Если вы уверены, что ваш поток будет иметь определенный размер, вы всегда можете заставить его вызывать эту функцию - она все равно будет работать через весь поток. См. Примечания в конце, почему я действительно не хотел бы возвращать None для неопределенного потока. Я делаю это здесь исключительно для простоты.
Но это не работает для множеств и карт. Что делать? Следующий общий супертип Iterable, но это не поддерживает updated или что-либо эквивалентное. Все, что мы построим, может быть очень плохо выполнено для фактического типа. Таким образом, моя чистая не-вспомогательная функция рекурсии ломается. Мы могли бы перейти на использование вспомогательной функции, но в других ответах есть много примеров, и я собираюсь придерживаться подхода с одной простой функцией. Итак, в этот момент мы можем перейти на reduceLeft (и пока мы на нем, отпустим для "Traversable" и обслуживаем все коллекции):
def max[A <% Ordered[A]](xs: Traversable[A]): Option[A] = {
if (xs.hasDefiniteSize)
xs reduceLeftOption({(b, a) => if (a >= b) a else b})
else None
}
но если вы не учитываете редукцию reduceLeft, мы можем это сделать:
def max[A <% Ordered[A]](xs: Traversable[A]): Option[A] = xs match {
case i if i.isEmpty => None
case i if i.size == 1 => Some(i.head)
case i if (i collect { case x if x > i.head => x }).isEmpty => Some(i.head)
case _ => max(xs collect { case x if x > xs.head => x })
}
Он использует комбинатор collect, чтобы избежать некоторого неуклюжего способа выведения нового Итератора из xs.head и xs drop 2.
Любой из них будет работать безопасно почти с любой коллекцией всего, что имеет порядок. Примеры:
scala> max(Map(1 -> "two", 3 -> "Nine", 8 -> "carrot"))
res1: Option[(Int, String)] = Some((8,carrot))
scala> max("Supercalifragilisticexpialidocious")
res2: Option[Char] = Some(x)
Обычно я не рассматриваю этих других как примеры, потому что для этого требуется более экспертное знание scala.
Кроме того, помните, что базовый признак Traversable предоставляет метод max, так что все это просто для практики;)
Примечание. Я надеюсь, что все мои примеры показывают, насколько тщательный выбор последовательности выражений case может сделать каждое индивидуальное выражение как можно более простым.
Важное примечание: О, также, когда я очень комфортно возвращаю None для ввода Nil, на практике я бы сильно склонялся к исключению для hasDefiniteSize == false. Во-первых, конечный поток может иметь определенный или неопределенный размер, зависящий исключительно от последовательности оценки, и эта функция будет эффективно случайным образом возвращать Option в этих случаях, что может занять много времени для отслеживания. Во-вторых, я хотел бы, чтобы люди могли различать пройденный Nil и прошедший поистине ввод риска (т.е. Бесконечный поток). Я только вернул Option в эти демонстрации, чтобы код был как можно более простым.