Функциональное программирование дает много преимуществ при создании распределенной системы. Вы будете иметь дело с меньшим количеством ошибок в параллельной среде, потому что все неизменяемо. Это также помогает нам локальное мышление и композиция - мы можем создавать приложения и программы, такие как строительные блоки лего, которые дадут предсказуемый результат. Имея предсказуемый результат, мы можем понять, что код масштабируется в зависимости от размера кодовой базы.
Однако есть и обратная сторона, если вы строго сделаете все чистым и неизменным. Например, в моих предыдущих статьях наличие функциональной структуры данных, такой как List, может быть дорогостоящим. Возьмем для примера следующее:
List(1,2,3,4).map(_ + 1).filter(_ % 2 == 0).map(_ * 2)
Каждая из этих операций, описанных выше, будет вводить данные и создавать новый промежуточный список на выходе. Выражение выше для функции map
представит новый List(2,3,4,5)
. Затем он переходит к filter
функции и отфильтровывает все нечетные числа, в результате чего создается новый список List(2,4)
, который получает переход к последней map
операции. Каждое преобразование создает короткий список, который используется в качестве входных данных для следующего преобразования и затем немедленно отбрасывается. Если мы вручную создадим трассировку для ее выходной оценки, она будет примерно такой:
List(1,2,3,4).map(_ + 1).filter(_ % 2 == 0).map(_ * 2)
List(2,3,4,5).filter(_ % 2 == 0).map(_ * 2)
List(2,4).map(_ * 2)
List(4, 8)
Вы, должно быть, сейчас думаете - синтаксис композиционный и лаконичный, но производительность и использование памяти ужасны. В идеале мы захотим объединить преобразование последовательности для каждого такого элемента за один раз. Мы не хотим ждать, пока весь List завершит преобразование первого элемента в его второе преобразование. Мы также не хотим создавать временный элемент списка в середине каждого изменения.
Как мы это делаем?
Мы можем изменить структуру на цикл while и for. Однако мы хотим сохранить композиционную структуру преобразования, а не писать монолитные схемы. Один из способов сделать это - сделать структуру данных нестрогой (ленивой).
Что такое нестрогие (ленивые)?
Прежде чем мы поговорим о том, что является нестрогим, я хочу объяснить, что является строгим.
Формальное определение строгости таково: «Если оценка выражения выполняется бесконечно или выдает ошибку вместо возврата определенного значения, мы говорим, что выражение не завершается или что оно оценивается как bottom. Функция f
является строгой, если выражение f(x)
вычисляется до дна для всех x этого значения до дна. '
Проще говоря, если функция строгая, это означает, что функция будет оценивать все свои аргументы. Возьмем пример:
def add[A](a:A, b:A): A = a + b
add(1,2)
Функция add
получит оцененные аргументы 1
и 2
. Если мы сделаем что-то вроде этого:
add(sys.error("something wrong"), sys.error("something wrong"))
Он вызывает аргументы сначала до того, как функция add
сможет оценить значение своих аргументов.
Строгость - это норма в языках программирования, и, действительно, большинство функций поддержки языка программирования ожидают, что его аргументы будут вычислены.
Нестрогость означает, что функция может выбрать не для оценки одного или нескольких своих аргументов первыми при вызове этой функции.
Нестрогость широко используется в языках программирования, и вы наверняка знакомы с этой концепцией. Одним из примеров является короткое замыкание в логической операции &&
и ||
. Хотя логическая операция является встроенным синтаксисом в языке, мы можем рассматривать ее как функцию, которая решает не оценивать следующую операцию в зависимости от результата первой оценки.
false && (1 + 1 == 2)
Следующее выражение не будет оцениваться, потому что первое выражение возвращает false
.
Если вы хотите создать операцию &&
в scala, это будет примерно так:
Аргумент, который мы передаем без вычисления, имеет () =>
синтаксис, обычно он называется преобразователем. () =>
означает, что вы передаете функцию без аргументов. Затем внутри функции a()
вызывает эту функцию.
Поскольку это широко используется в Scala, у нас есть более красивый синтаксис, : =>
, который обычно называется _pass по имени.
Следовательно, указанную выше функцию можно перевести так:
Обратите внимание, что эти оцененные функции не кэшируются. Поэтому, если вы вызовете их несколько раз, он будет вызван много раз. Чтобы запомнить оцениваемое значение, вы должны использовать lazy val
. Один раз он лениво оценил стоимость, а потом запомнил результат.
Ленивый список (поток)
Теперь вы знаете определение нестрогости и лени. Давайте решим первый пример, воссоздав наш список в «ленивых».
Интуиция
Сначала мы дадим определение ленивому списку. Затем мы создадим foldRight
функций, общую функцию преобразования значений, и foldRight
, чтобы создать map
и filter
для нашего ленивого списка. Наконец, я объясню, как работают программы и почему использование Lazy List намного эффективнее обычного неизменяемого List.
Определение ленивого списка
Определим ленивый список:
Вышеупомянутая реализация представляет собой простой пример ленивого списка. cons
и empty
- это умный конструктор для кэширования любого экземпляра объекта.
Это похоже на обычный список, за исключением того, что все является преобразователем. Таким образом, нам нужно заставить аргументы оценить определение функции.
Отдельное описание программы и оценка
Теперь, когда вы видите, что все не строго, мы можем разделить описание и его оценку. В моей предыдущей статье Как написать приложение для обработки данных в FS2 все значения внутри Stream являются описанием программы, пока не будет unsafeRunSync
.
Важная тема функционального программирования связана с проблемами разделения. Например, функции первого класса описывают некоторые вычисления в теле, но будут выполняться, если мы предоставим аргументы этим функциям. Мы использовали Option
, чтобы зафиксировать описание программы о том, что произошла какая-то ошибка. Однако решение о том, что делать с этими ошибками, остается отдельной задачей. С помощью Lazy List мы создаем вычисление последовательности элементов, не оценивая их, а запускаем эти элементы только тогда, когда они нам нужны.
Это имеет значительное преимущество: мы можем описать обильное выражение больше, чем нам нужно, и оценить только его часть. Вы увидите это на примере foldRight
ниже.
Реализовать foldRight
Давайте определим реализацию foldRight
:
Одно из основных отличий от обычного foldRight
в списке состоит в том, что B
является проходным именем. Это означает, что функция t().foldRight(z)(f)
будет оцениваться в зависимости от функции f
. В обычном списке это будет рекурсивный вызов t().foldRight(z)(f)
, пока не будет достигнут базовый вариант. Здесь это будет зависеть от того, как реализована функция f
.
Давайте рассмотрим пример определения функции exists
, которая будет проверять, существует ли значение в списке:
Эта функция будет перемещаться по списку, пока p(a)
не вернет истину. Как только p(a)
вернет истину, он не будет оценивать b
и короткое замыкание. Мы не можем сделать это со строгой функцией foldRight
, поскольку она будет вызывать t().foldRight(z)(f)
рекурсивно, пока функция не достигнет базового случая.
Внедрить карту и фильтр
Вернемся к первому примеру выше:
List(1,2,3,4).map(_ + 1).filter(_ % 2 == 0).map(_ * 2)
Давайте определим функции map
и filter
.
Реализуя общую рекурсивную функцию foldRight
, мы можем применять map
и filter
, используя foldRight
нестрогим образом.
Когда мы определили map
и filter
нестрогим образом, реализация не полностью генерирует ответ. Даже когда функция развернется, она просто сделает достаточно работы, чтобы сгенерировать запрошенные элементы.
Давайте проследим слой за слоем, как работает наш первый пример:
Поскольку мы используем LazyList
, нам нужно выполнить функцию toList
, которая принудительно выполнит оценку для последующего LazyList
.
Подражая приведенному выше примеру с LazyList
:
Отслеживание того, как работает эта программа:
Теперь преобразование filter
и map
чередуются - оно добавит единицу с map
к этому элементу и проверит с filter
, чтобы увидеть, делится ли этот элемент на 2, и умножит полученный результат на 2. Все аспекты внутри LazyList не являются делится на два; затем он будет продолжать вызывать следующий элемент, пока не создаст Cons(a, b)
. Функция toList
- заставить оценить следующий компонент, если это еще один Lazy List.
Примечание. Если вы запустите val lst = LazyList(2,2,2).map(_ + 1).filter(_ % 2 == 0)
. Затем print(lst)
он оценит весь список без необходимости навязывать оценку всем элементам в ленивом списке.
Инкрементальный характер преобразования Lazy List также имеет значительные последствия для использования памяти. Поскольку промежуточный список не создается, преобразование требует достаточно рабочей памяти только для хранения и преобразования текущих элементов. Таким образом, сборщик мусора может освободить пространство, выделенное для значений, выдаваемых картой, и, как только фильтр определит, в нем нет необходимости.
Забрать
- Оценивая структуру данных нестрогим образом, мы можем отделить описание от его оценки.
- Используя нестрогую функцию, мы можем оптимизировать преобразование и преобразовать только необходимые элементы в Списке.
Спасибо за внимание! Если вам понравился этот пост, не стесняйтесь подписаться на мою рассылку, чтобы получать уведомления об эссе о карьере в технологиях, интересных ссылках и контенте!
Вы можете подписаться на меня и подписаться на меня на Medium, чтобы увидеть больше подобных сообщений.
Первоначально опубликовано на https://edward-huang.com.