Списки В Котлине. Хаскелл-Подход

Haskell — полнофункциональный и чрезвычайно лаконичный язык.

Любой, кто когда-либо пробовал писать код на Haskell, заметит, насколько это более лаконично и элегантно, чем писать то же самое на императивном языке.

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

Мы можем получить все сложные функции, которые могут нам понадобиться, на основе трех самых известных функций: Map, Filter, Reduc. Кроме того, я создал репозиторий , который вы можете изучить и посмотреть тесты.

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

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

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

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

Давайте рассмотрим некоторые из них и то, как их можно реализовать в Котлине.

   

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

   

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

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"

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

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) }

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

К сожалению, более удобным способом добавить объект в список опять же нет возможности, поэтому воспользуемся методом добавлять .

На данный момент у нас есть почти все, что нам нужно.

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

Для этого воспользуемся стандартным методом пусто() .

Давайте остановимся и посмотрим, что у нас есть на данный момент:

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

На мой вкус было бы удобнее когда операторы используют сравнение длины списка.

Котлин уже предоставляет нам размер чтобы получить эту длину списка.

Однако предположим, что мы хотим реализовать это сами.

С нашим функционалом это будет довольно просто:

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.хвост) .

Однако это неправда.

Если описать код немного по-другому, то станет очевидно:

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

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

Хорошей новостью является то, что если вы добавите модификатор хвострек функции, IDE сообщит вам, что функция не является функцией.

Однако исправить это довольно легко.

Распространенный метод исправления функции — использование вспомогательной переменной для хранения результатов.

Это выглядит так:

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

Чтобы вычислить сумму элементов, достаточно передать 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) }

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

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

Но обо всем по порядку.

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

КАРТА

Мы будем использовать рекурсивные вызовы, где граничным условием является пустой список.

Тогда реализация будет выглядеть так:

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

ФИЛЬТР

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

Реализация будет выглядеть так:

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) }

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

УМЕНЬШАТЬ

Чаще всего он используется для свертывания списка в один элемент. У вас есть начальная стоимость с0 а также есть список элементов а[] и функция ж , который для начального значения и следующего элемента списка возвращает new. 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) }

В принципе реализация абсолютно такая же, как мы обсуждали выше.

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

Обратите внимание, что мы также можем создавать модификации этой функции.

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

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

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

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

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

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

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 }

Кроме того, часто забывают, что мы также можем применить сокращение не с начала списка, а с конца.

Конечно, мы могли бы просто расширить список, а затем применить сокращение, но это неинтересно.

Давайте попробуем написать и понять, как работает сокращение, чтобы свернуть список в обратном порядке.

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-х функций, чтобы получить интересующий вас результат. Давайте реализуем функцию еще раз молния , что позволит нам объединить 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) }

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

Например, нам нужно просуммировать все четные элементы списка.

Вы можете попытаться добиться этого, используя сокращение, сохраняя Pair в качестве текущего значения и добавления значения if flag == true, и каждый раз принимая отрицание flag для следующего шага.

Однако выглядит это не очень красиво, и читателю кода придется разбираться, что вы хотели выразить этим кодом.

В Котлине есть бесконечные последовательности, и они отлично подходят для решения этой проблемы.

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

И чтобы иметь возможность получать индексы, достаточно вызвать молния для списка и последовательность [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 для пары последовательностей.

Теперь давайте посмотрим на простую проблему, которая вдохновила меня на написание этого руководства, и на то, как выглядит ее реализация на императивном языке в 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; }

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

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

max()

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

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

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

Заключение

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

Самые очевидные из них могут оказаться громоздкими и трудными для понимания в будущем, а написание наиболее понятных может потребовать времени и серьезных умственных усилий.

Единственное, что может помочь вам овладеть им, — это постоянная практика и тренировки.

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

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

Обязательно посмотрите позже https://arrow-kt.io/ .

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

Теги: #Kotlin #Функциональное программирование #функциональное программирование #абстракция

• Максимальные Меры Безопасности

  19 Oct, 24

• Сбербанк Проведет Конкурсы В Области Анализа Данных С Призами На 1,4 Млн Рублей

  19 Oct, 24

• Clickhouse Рядом С Zabbix Или Как Собирать Логи С Мониторингом

  19 Oct, 24

• В 2015 Году Каждая Пятая Машина Будет Продаваться Через Интернет?

  19 Oct, 24

• Разработан Новый Мгновенный Анализ Крови Для Выявления Повреждений Головного Мозга

  19 Oct, 24

• Nixie Часы На Одном Порту - Atmega8

  19 Oct, 24

• Письмо Из Прошлого Или «Обещанное Ждали Три Года»…

  19 Oct, 24

• Солнечного Всем Привет!

  19 Oct, 24

• Технология Передачи Данных В Системе Экстренного Реагирования Эра-Глонасс

  19 Oct, 24

• Десять Попали В Блог

  19 Oct, 24