Haskell является полностью функциональным и чрезвычайно лаконичным языком. Любой, кто когда-нибудь пробовал писать код на Haskell, замечает, насколько он получается более кратким и изящным, чем написать то же самое на императивном языке. Добиться такого же на Java, на мой взгляд, невозможно, но Kotlin позволяет продвинуться в этом направлении и примерить на себе полностью функциональный стиль. Мы можем вывести все сложные функции, которые нам могут понадобится из стартового базиса 3-х наиболее известных функций: map, filter, reduce. Кроме этого я создал репозиторий, который вы можете изучить и посмотреть тесты.

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

Базовые функции

Очень важную роль в языке играют списки, и для них реализовано много полезных функций. Рассмотрим некоторые из них и то, как их можно реализовать на Kotlin.

head (x:_) = x
head [] = badHead

Если в списке есть элементы, мы вернём первый, в противном случае вернём ошибку.
Писать такой код возможности у нас нету, но, в целом, если присмотреться, это очень похоже на when шаблон. Также воспользуемся extension функцией, чтобы позже иметь возможность использовать этот метод на списках и иметь чуть более лаконичный способ получения значения, без скобок в конце, как у вызова метода.

val <T> List<T>.head: T
   get() = when (this.isEmpty()) {
       true -> throw NoSuchElementException("List is empty.")
       false -> this[0]
   }

Для того, чтобы удобно использовать рекурсию, нам бы хотелось также разделять список на первый элемент + все остальные. Попробуем для этого реализовать функцию tail.

Вот как она выглядит на haskell:

tail (_:xs) =  xs
tail [] =  errorEmptyList "tail"

К сожалению, Kotlin не предоставляет такой уровень pattern matching, чтобы разработчики могли описать в таком же стиле, поэтому тут нам придётся написать немного когда.

val <T> List<T>.tail: List<T>
   get() = drop(1)

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

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

operator fun <T> List<T>.plus(x: T): List<T> = ArrayList(this).also { it.add(x) }

Теперь мы умеем прибавлять к элементу в конец список, и наша реализация функции map становится рабочей и готовой к использованию. К сожалению, снова нет возможности добавить к списку объект каким-либо более удобным способом, поэтому используем метод add.

У нас на данный момент есть почти, всё что нам нужно. Единственное, что нам теперь нужно — это иметь возможность описания граничного условия выхода из рекурсии. Для этого будем стандартный метод isEmpty(). Остановимся и посмотрим, что у нас есть на данный момент:

• isEmpty() — есть ли в списке элементы
• head — первый элемент списка
• tail — список без первого элемента
• list + element — можем конкатенировать список с объектом

На самом деле, это всё, что нам нужно, чтобы вывести все необходимые нам методы.
На мой вкус, было бы удобнее в when операторах использовать сравнение длины списка. Kotlin уже предоставляет нам size для того, чтобы получать эту длину списка. Однако, допустим, что мы хотим реализовать её самостоятельно. С нашим функционалом это будет совсем просто:

val <T> List<T>.size: Int
   get() = when (this.isEmpty()) {
       true -> 0
       false -> 1 + this.tail.size
   }

Применение базовых функций

Рассмотрим самый распространённый пример. Допустим, у нас есть список целых чисел, и мы хотим просуммировать их, забыв о существовании циклов. Всё, что у нас есть — это методы, которые мы вывели выше, и рекурсия. Для этого воспользуемся таким же подходом, как и при вычислении размера списка:

fun sum(xs: List<Int>): Int = when (xs.size) {
   0 -> 0
   else -> xs.head + sum(xs.tail)
}

Идея очень простая: если в списке нету элементов, то сумма равна 0; в противном случае, это сумма первого элемента и рекурсивный вызов суммы для хвоста.

Несмотря на то, что мы не заботимся в этом коде о скорости выполнения и оптимизациях, нельзя не вспомнить про возможности языка по использованию хвостовой рекурсии. Хвостовая рекурсия — частный случай рекурсии, при которой рекурсивный вызов является последней операцией перед возвратом из функции. Подобный вид рекурсии примечателен тем, что гарантированно позволяет перестроить код на итерацию. Как вам известно, основная проблема рекурсии в том, что на протяжении выполнения функции необходимо хранить стек вызовов, чтобы при достижении граничного условия можно было вернуться назад и пересчитать итоговый результат.

Может показаться, что функция суммы, которую мы описали, является как раз такой, ведь последний вызов — это sum(xs.tail). Однако, это не верно. Если описать код немного по-другому, то это станет очевидно:

fun sum(xs: List<Int>): Int = when (xs.size) {
   0 -> 0
   else -> {
       val head = xs.head
       val tailSum = sum(xs.tail)
       head + tailSum
   }
}

Теперь видно, что фактически последним вызовом является сумма первого элемента и оставшейся части хвоста.

Хорошая новость в том, что, если добавить модификатор tailrec к функции, IDE подскажет, что функция не является таковой. Однако исправить это довольно несложно. Распространённым приёмом, с помощью которого исправляют функцию, является использование вспомогательной переменной для хранения результатов. Выглядит это следующим образом:

tailrec fun sum(xs: List<Int>, acum: Int): Int = when (xs.size) {
   0 -> acum
   else -> sum(xs.tail, xs.head + acum)
}

Для того, чтобы вычислить сумму элементов, достаточно в качестве 2-го параметра передать 0. И, чтобы сделать это совсем идиоматическим, ещё немного переделаем функцию, спрятав основные вычисления во внутреннюю функцию без того, чтобы внешний мир имел доступ к параметру, который ему не нужен.

fun sum(xs: List<Int>):Int {

   tailrec fun sumInner(xs: List<Int>, acum: Int): Int = when (xs.size) {
       0 -> acum
       else -> sumInner(xs.tail, xs.head + acum)
   }

   return sumInner(xs, 0)
}

Имея эти знания, можно заметить, что функция size, которую мы реализовали выше, не удовлетворяет необходимым условиям для хвостовой рекурсии.

Теперь мы готовы реализовывать map, filter, reduce c помощью Kotlin. Позже мы увидим, что достаточно было реализовать лишь только последнюю, а остальные, вообще говоря, являются производными от неё. Но обо всём по порядку.

Основные функции

MAP

Итеративная реализация данной функции предполагает последовательное движение по списку, применяя функцию преобразования и добавляя все полученные элементы в новую коллекцию. Мы будем использовать рекурсивные вызовы, где граничным условием является пустой список. Тогда реализация будет выглядеть следующим образом:

fun <T, R> List<T>.map(f: (T) -> R): List<R> = when (this.size) {
   0 -> listOf()
   else -> f(head) + tail.map(f)
}

Если в исходном списке нету элементов, то возвращаем пустой список, иначе — применяем трансформацию к первому элементу и добавляем в конец рекурсивный вызов для оставшейся части списка.

Однако у нас ещё нету функции для конкатенации элемента и списка. Но мы уже можем её реализовать. Для начала, выведем более общий случай по конкатенации пары списков и после этого воспользуемся им для добавления к элементу другого списка.

operator fun <T> List<T>.plus(xs: List<T>): List<T> = when (xs.size) {
   0 -> ArrayList(this)
   else -> (this + xs.head) + xs.tail
}

operator fun <T> T.plus(xs: List<T>): List<T> = listOf(this) + xs

FILTER

Реализация будет очень похожа на map. Только единственное отличие в том, что следует понять, нужно ли добавлять текущий элемент к результату. Для этого мы будет вызывать лямбду, которую получили в качестве параметра. Реализация будет выглядеть следующим образом:

fun <T> List<T>.filter(f: (T) -> Boolean): List<T> = when (this.size) {
   0 -> listOf()
   else -> if (f(head)) head + tail.filter(f) else tail.filter(f)
}

Если текущий элемент удовлетворяет условию фильтра — добавляем его рекурсивно к хвосту списка, иначе — продолжаем работу только с хвостом списка.

REDUCE

Самая сложная для понимания и, в то же время, самая мощная функция (в функциональном мире известна как fold). Чаще всего она используется для того, чтобы свернуть список к одному элементу. У вас есть некое стартовое значение s0, а также есть список элементов a[] и функция f, которая для стартового значения и следующего элемента списка возвращает новый. f(s0, a[0]) = s1. И, таким образом, мы последовательно проходим по всему списку элементов, на выходе получая некое единое значение. Довольно распространённый пример — суммирование элементов массива. В таком случае стартовым значением является 0, а функция возвращает сумму двух элементов: f(s, a[i]) = s + a[i]. Рассмотрим, как мы можем рекурсивно реализовать эту функцию.

fun <T, R> reduce(s: T, xs: List<R>, f: (T, R) -> T): T = when (xs.size) {
   0 -> s
   else -> reduce(f(s, xs.head), xs.tail, f)
}

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

Заметим, что мы также можем создавать модификации этой функции. Например, не передавать стартовое значение, а использовать для этого первый элемент списка. Чтобы понять, что на этом возможности reduce не заканчиваются, представим, что мы в качестве стартового значения используем другой список. В этом случае, мы каждый раз на итерации будем хранить не одно значение, а список, благодаря чему наши возможности сильно возрастают. Например, попробуем применить функцию reducе таким образом, чтобы на выходе получить исходный список:

fun <T> reduceSame(xs: List<T>) = reduce(listOf<T>(), xs) { ys, s -> ys + s }

Теперь, думаю, вы догадываетесь, что мы могли использовать reduce, для альтернативной реализации map, filter. Так как мы научились возвращать с помощью reduce точно такой же список, нужно внести совсем немного изменений, чтобы получить возможность преобразовывать каждый элемент. Для filter всё очень похоже.

fun <T, R> List<T>.map2(f: (T) -> R): List<R> = reduce(mutableListOf(), this) 
  { xs, s -> (xs + f(s)).toMutableList() }

fun <T> List<T>.filter2(f: (T) -> Boolean): List<T> =  reduce(mutableListOf(), this)
  { ys, s ->
     if (f(s))
         return@reduce (ys + s).toMutableList()
     else
         ys
  }

Кроме этого, часто забывают о том, что мы можем также применять reduce не с начала списка, а с конца. Несомненно, мы можем просто развернуть список, и уже после этого применить reduce, но это не интересно. Попробуем написать и понять, как работает reduce для свёртывания списка в обратном порядке.

fun <T, R> reduceRight(s: T, xs: List<R>, f: (T, R) -> T): T = when (xs.size) {
   0 -> s
   else -> f(reduceRight(s, xs.tail, f), xs.head)
}

Если список не пустой, то мы применим функцию f к результату свёртывания хвоста списка и головы списка. Таким образом, последним будет обработан первый элемент; предпоследним — 2-й и тд. Для этого варианта тоже можно дописать модификации, которые в качестве стартового значения будут использовать последний элемент списка и т.д.

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

Давайте ещё реализуем функцию zip, которая позволит нам комбинировать 2 списка.
На вход получаем 2 списка. И мы хотим вернуть список пар, длина которого равняется минимальной из исходных списков.

Как обычно, нужно подумать о выходе из рекурсии и написать функцию.

fun <T, R> zip(xs: List<T>, ys: List<R>): List<Pair<T, R>> {
   return when (xs.isEmpty() || ys.isEmpty()) {
       true -> listOf()
       false -> Pair(xs.head, ys.head) + zip(xs.tail, ys.tail)
   }
}

Вы можете добавить свои модификации, которые позволят вам, вместо того чтобы возвращать пару элементов, применить некую функцию к двум элементам. В Haskell такая функция имеет название zipWith. И реализуется она с тем функционалом, который мы успели написать очень просто:

fun <T, R, C> zipWith(xs: List<T>, ys: List<R>, f: (T, R) -> C): List<C> =
       zip(xs, ys).map { f(it.first, it.second) }

Очень часто при использовании функционального подхода возникают проблемы, когда нужно производить манипуляции, основываясь не на объектах в списках, а на основании индексов. Например, нам нужно просуммировать все чётные элементы списка. Можно попробовать добиться этого с помощью reduce, поддерживая в качестве текущего значения Pair<Int, Boolean> и добавляя значение в том случае, если flag == true, и каждый раз для следующего шага брать отрицание flag. Однако это выглядит как-то не слишком красиво, и читающему код придётся разбираться в том, что же вы хотели этим кодом выразить. В Kotlin есть бесконечные последовательности, и они замечательно подойдут для решения этой задачи. Если проанализировать то, что мы хотим сделать получится, что мы хотим отфильтровать все элементы с нечётными индексами, а оставшиеся — просуммировать. А для того, чтобы иметь возможность получения индексов, достаточно вызвать zip для списка и sequence [0,1,2..]

fun sumWithEvenIndexes(xs: List<Int>) =
       zip(xs, generateSequence(0) { it + 1 }.take(xs.size).toList())
           .filter { it.second % 2 == 0 }
           .map { it.first }
           .sum()

В стандартной библиотеке Kotlin вы можете найти функцию zip для пары sequence.

А теперь давайте рассмотрим простую задачку, которая вдохновила меня на написание этого гайда, и то, как её реализация выглядит на императивном языке на Kotlin и в самом конце на Haskell.

Необходимо вычислить максимальную сумму среди пар рядом стоящих чисел в массиве целых чисел. Длина массива больше 1, и можно не заботится о переполнении при суммировании элементов.

Императивный подход на Java:

public Integer maxSum(List<Integer> array) {
   Integer max = array.get(0) + array.get(1);
   for (int i = 2; i < array.size(); i++)
       if (array.get(i) + array.get(i-1) > max)
           max = array.get(i) + array.get(i-1);
   return max;
}

Функциональный подход на Kotlin с использованием написанных функций (функцию max предлагаю в качестве тренировки реализовать самостоятельно):

fun maxSum(xs: List<Int>) = zipWith(xs, xs.tail, {a, b -> a + b}).max()

Реализация на Haskell:

maxSum xs = maximum $ zipWith (+) xs (tail xs)

Как мы видим, то, что мы реализовали на Kotlin (между прочим, мы могли использовать reduce для решения этой задачи), очень похоже на то, что можно написать на Haskell.

Заключение

Несомненно, это не стоит использовать в разработке, потому что всё было реализовано неоптимально лишь для того, чтобы продемонстрировать функциональный подход. Также почти всё, что было написано, есть в стандартной библиотеке Kotlin, поэтому, возможно, в будущем, вместо того, чтобы написать очередной цикл for, вы воспользуетесь функциональным стилем, который предоставляет нам Kotlin.

Наверное, самым сложным в функциональном стиле является то, что задачу можно решать разными способами. Самые очевидные могут быть громоздкими и сложными для понимания в будущем, а для написания самых понятных может потребоваться время и серьезные мыслительные усилия. Единственное, что может помочь в освоении — это постоянная практика и тренировки.

P.S.: Как было указано выше, вы можете посмотреть репозиторий со всеми примерами, которые есть в статье. Запустите тесты и посмотрите как это работает!

P.P.S: Вы также можете посмотреть альтернативный подход, который реализует похожую функциональность.

А обязательно посмотреть позже https://arrow-kt.io/. На мой взгляд, сразу смотреть туда не стоит, потому что выглядит всё довольно страшно, но позже, когда вас не будут пугать функторы и монады, обязательно изучите.