exxo blog

В прошлый раз я начал делиться своим опытом изучения основ функционального программирования по книжке 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)
      }
    }

Еще раз повторюсь, что здесь мы сравниваем целые числа.

см. Лирическое отступление

Продолжение следует…