Learn You Scala for Great Good! Часть 2
В прошлый раз я начал делиться своим опытом изучения основ функционального программирования по книжке Learn You a Haskell for Great Good! применительно к языку программирования Scala.
Сегодня я разберу пример из главы, посвященной рекурсии.
Нахождение максимального числа в списке
Здесь сразу хочу заметить, что пример на Haskell является более общим и находит наибольшее число от чего угодно, что може быть отсортировано (of things that can be ordered). Достаточно, чтобы члены списка были экземплярами тайпкласса Ord. В Scala, чтобы в полной мере использовать тайпклассы, нужно обратиться к таким библтотекам, как Scalaz или Cats. Я здесь не буду этого делать. Мой пример на Scala будет для List[Int]
Итак, Haskell:
maximum :: (Ord a) => [a] -> a
maximum [] = error "maximum of empty list"
maximum [x] = x
maximum (x:xs)
| x > maxTail = x
| otherwise = maxTail
where maxTail = maximum xs
Применение функции maximum к пустому списку выдаст ошибку.
Применение к списку из одного элемента вернет этот элемент.
В общем случае используется сравнение с образом (head:tail) и строится рекурсия:
Если head
(первый элемент списка) больше, чем наибольший элемент из tail
(остальной части списка), то приисходит выход из рекурсии. В противном случае функция вызывается снова с параметром tail
.
На Scala это выглядит так:
def maximum(l:List[Int]):Int = {
l match {
case Nil => throw new Exception("maximum of empty list")
case x::Nil => x
case x::xs if x > maximum(xs) => x
case x::xs => maximum(xs)
}
}
Еще раз повторюсь, что здесь мы сравниваем целые числа.
см. Лирическое отступление
Продолжение следует…