Макар Кузьмичев
Назад

Как Макар начал clojure учить часть 2

История о том, как я начал учить clojure часть 2

В предыдущей серии:

  1. Часть 1

Особенность философии - программирование на абстракциях

  • Программируя на clojure, мы можем использовать map и reduce для любой структуры данных.
  • map и reduce не знают о типах данных, для них важно, чтобы были реализованы функции first, rest и cons - получение первого элемента, получение остальных элементов и добавление в начало соответственно.
  • В clojure работа идет с последовательностями, последовательность - абстракция. (последовательность действий, очередь и тд и тп, главное чтобы были реализованы first, rest и cons)
  • Всякий раз, когда ожидается работа с последовательностью (вызов map, reduce) - вызывается seq, чтобы понять, последовательность это или нет
(seq '(1 2 3))
; => (1 2 3)

(seq [1 2 3])
; => (1 2 3)

(seq #{1 2 3})
; => (1 2 3)

(seq {:name "Mak" :age 32})
; => ([:name "Mak"] [:age 32])
  • Если хочешь из seq вернуться в мапу - юзай into
(into {} (seq {:name "Mak" :age 32}))
; => {:name "Mak" :age 32}

Полезные функции, о которых стоит узнать в самом начале

Синтаксис у всех функций практически одинаковый:

(fnName fnPredicate args)

fnName -> название функции
fnPredicate -> функция-предикат, которая будет применяться к последовательности
args - последовательность и/или другие аргументы
  • map, reduce - универсальные функции, с помощью которых можно делать различные преобразования над последовательностями. map - проходится по всем элементам и преобразовывает их. reduce - проходит по всем элементам и собирает данные в новую структуру. С помощью reduce можно написать map, filter, some и тд, аналогично как и в javaScript.
  • take, drop - принимает два аргумента: число и последовательность:
(take 3 [1 2 3 4 5 6 7])
;;(1 2 3)
(drop 3 [1 2 3 4 5 6 7])
;;(4 5 6 7)
  • take-while, drop-while - то же самое, что и take, drop, только первый аргумент функция, с помощью которой можно определить, до какого момента брать/дропать элементы. ДО ПЕРВОГО ПОДХОДЯЩЕГО ПОД УСЛОВИЕ:
(drop-while even? [2 4 5 6 7])
;;(5 6 7)
(take-while odd? [1 3 4 5 6 7])
;;(1 3)
  • filter похож на take-while, но работает для всей последовательности
(filter even? [2 4 5 6 7])
;;(2 4 6)
  • some - проверяет, есть ли в последовательности элементБ удовлетворяющий условию
(some even? [2 4 5 6 7])
;;true
  • sort и sort-by - сортировка
  • concat - объединение последовательностей

Ленивые последовательности (Lazy Seqs)

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

Это дает следующие бонусы:

  • Эффективность: Если тебе нужен только первый элемент из миллиона, зачем вычислять остальные?
  • Бесконечные последовательности: Можно создавать последовательности без конца (например, бесконечный список чисел).

Если немного углубиться, то суть ленивых последовательностей (Lazy Seqs):

  1. Отложенные Вычисления (Deferred Computation): Это не просто "оптимизация". Это фундаментальный сдвиг парадигмы. Когда map, filter или аналоги возвращают lazy seq, они не вычисляют элементы сразу. Вместо этого они возвращают объект, хранящий:
    • "Рецепт" (Recipe): Функцию (или цепочку функций), описывающую как получить элементы, когда они понадобятся. В случае (map f coll) рецепт: "Чтобы получить n-ый элемент, примени f к n-ому элементу coll".
    • Кеш Реализованных Элементов (Realized Elements Cache): Пустой изначально. По мере доступа к элементам (реализации - realizing), они вычисляются по "рецепту" и кешируются для мгновенного доступа в будущем.
  2. Реализация (Realizing): Процесс вычисления элемента последовательности впервые. Происходит только тогда, когда код явно требует этот элемент (например, через first, nth, take, или при выводе на печать большего количества элементов, чем уже реализовано).
  3. Философское Преимущество:
    • Эффективность по Потребности (Efficiency on Demand): Избегаем вычислений для элементов, которые никогда не понадобятся.
    • Работа с Бесконечностью (Infinite Sequences): Последовательность может генерировать элементы вечно, так как элементы создаются только по запросу. "Рецепту" не нужен конец.
    • Композиция (Composition): Позволяет строить цепочки преобразований (map -> filter -> take) без промежуточных копий данных и без вычислений между этапами, пока не потребуется результат. Это мощь функционального программирования.

Пример с вампирами (из книги Clojure for the brave and true)

Задача:
Есть база данных из миллиона людей, среди которых один вампир. Нужно его найти.

Проблема без ленивости - проблема "Eager" (Нетерпеливого) подхода:

  • Если бы map работал "жадно" (eagerly), он бы сразу применил vampire-related-details ко всем 1 000 000 SSN.
  • filter затем обработал бы все 1 000 000 записей.
  • first взял бы первый результат filter.
  • Итог: Ожидание 1 000 000 секунд (≈12 дней) даже если вампир первый в списке. Катастрофа.

Решение с ленивостью:

  1. map применяет функцию к каждому элементу, но не сразу, а только когда элемент запрашивается.
  2. filter тоже ленивый - он проверяет элементы по одному, пока не найдёт подходящий.

Как это работает в коде:
Во-первых,

(def mapped-details (map vampire-related-details (range 0 1000000))) ; Мгновенно!

По пунктам:

  • (range 0 1000000) создает ленивую последовательность чисел [0, 1, 2, ..., 999999]. Она не хранит все числа в памяти, а знает как их генерить.
  • map применяет свой "рецепт": "Чтобы получить элемент n из mapped-details, возьми элемент n из последовательности (range 0 1000000) и примени к нему vampire-related-details".
  • Вычислений НЕТ! Создается только объект с "рецептом". Время ~0 мс!!!.

Во-вторых,

(defn identify-vampire
  [social-security-numbers]
  (first (filter vampire?
                 (map vampire-related-details social-security-numbers))))
  • map создаёт ленивую последовательность, но не вычисляет элементы.
  • filter начинает проверять элементы по одному.
  • first берёт первый подходящий — как только нашёл вампира, остальные не проверяются.

Первый Доступ и Чанкинг (Chunking):

(time (first mapped-details)) ; ≈32000 мс
  • first требует элемент 0. Пора реализовывать.
  • Ключевое Наблюдение: Clojure бьет на части (chunks) ленивые последовательности для оптимизации производительности.
  • Механика Чанкинга: Когда требуется реализовать один элемент, Clojure реализует сразу чанк (обычно 32 элемента). Он предполагает, что если нужен элемент n, то скоро понадобятся и n+1, n+2, и т.д. Доступ к последовательным элементам в памяти быстрее, чем повторные вызовы "рецепта" по одному элементу.
  • В Примере: Запрос (first mapped-details) приводит к:
    1. Реализации элементов 0-31 (32 элемента) последовательности mapped-details.
    2. Каждый элемент требует вызова vampire-related-details, который "спит" 1 секунду.
    3. Итог: ≈32 секунды (32 вызова * 1 сек) вместо ожидаемой 1 секунды.
  • Почему Чанкинг Хорош? Хотя в этом конкретном запросе (first) он выглядит избыточным, в подавляющем большинстве реальных сценариев (итерация по коллекции, take 10, take-while) он дает значительный прирост производительности за счет локальности данных и минимизации накладных расходов на организацию ленивости. Это компромисс.

Пример времени:

(time (identify-vampire (range 0 1000000)))
; => "Elapsed time: 32019.912 msecs" (≈32 секунды)

Почему не миллион секунд? Потому что map и filter ленивые, и first остановился после третьего элемента (вампира).

Повторный Доступ:

(time (first mapped-details)) ; ≈0 мс
  • Элемент 0 (и весь чанк 0-31) уже реализован и закеширован.
  • first просто берет значение из кеша. Никаких вызовов vampire-related-details.

Поиск Вампира (identify-vampire):

(time (identify-vampire (range 0 1000000))) ; ≈32000 мс
; => {:name "Damon Salvatore", ...}
  • (range ...) -> Ленивая последовательность SSN.
  • (map ...) -> Ленивая seq записей ("рецепт": SSN -> запись через vampire-related-details).
  • (filter vampire? ...) -> Ленивая seq, фильтрующая записи ("рецепт": брать записи из map, применять vampire?, пропускать false).
  • (first ...) -> Требует первый элемент от filter.
  • Процесс Реализации:
    1. first запрашивает элемент 0 у filter.
    2. filter запрашивает элементы у map, пока не найдет соответствующий критерию.
    3. filter запрашивает элемент 0 у map.
    4. map запрашивает элемент 0 у (range ...) -> 0.
    5. map применяет "рецепт": (vampire-related-details 0) -> реализует чанк (элементы 0-31 map), занимает ~32 сек. Возвращает запись 0.
    6. filter применяет vampire? к записи 0 -> false (не вампир).
    7. filter запрашивает элемент 1 у map (уже реализован в чанке! Берется из кеша мгновенно).
    8. filter применяет vampire? к записи 1 -> false.
    9. filter запрашивает элемент 2 у map (уже реализован).
    10. filter применяет vampire? к записи 2 -> true (найден вампир!).
    11. filter возвращает запись 2.
    12. first возвращает запись 2.
  • Итог: Найден 3-й элемент (Damon Salvatore). Время ~32 секунды (реализация первого чанка из 32 записей). Последующие записи в чанке проверялись мгновенно из кеша. Остальные 999968 записей никогда не были вычислены или проверены!

Бесконечные последовательности - сила "Рецепта":

Вот где ленивость раскрывается полностью. "Рецепту" не нужен конец.

  1. repeat:

    (take 8 (repeat "na")) ; => ("na" "na" ... "na") ; 8 раз
    • (repeat "na") создает ленивую seq с "рецептом": "Всегда возвращай "na"".
    • take 8 запрашивает первые 8 элементов у этой бесконечной seq.
    • "Рецепт" вызывается 8 раз, каждый раз возвращая "na".
    • Бесконечность безопасна, так как take знает, сколько элементов ему нужно.

  2. repeatedly:

    (take 3 (repeatedly #(rand-int 10))) ; => (7, 2, 4) ; Пример
    • (repeatedly #(rand-int 10)) создает ленивую seq с "рецептом": "При каждом запросе элемента вызывай (rand-int 10) и возвращай результат".
    • take 3 вызывает "рецепт" 3 раза. Каждый раз генерируется новое случайное число.

  3. Рекурсивное Построение (even-numbers): Тонкая Механика

    (defn even-numbers
  ([] (even-numbers 0))          ; Запуск с 0
  ([n] (cons n (lazy-seq (even-numbers (+ n 2)))))) ; Сердцевина
    • (cons n ...): Создает новую последовательность, где n - голова (первый элемент).
    • (lazy-seq ...): Критически важно! Это макрос, который:
      1. Откладывает вычисление: Не вычисляет свой аргумент (even-numbers (+ n 2)) в момент вызова cons.
      2. Создает "Рецепт": Возвращает объект ленивой последовательности, чей "рецепт" гласит: "Когда потребуется хвост последовательности, начни вычислять (even-numbers (+ n 2))".
    • Как это работает для (take 10 (even-numbers)):
      1. take 10 запрашивает первый элемент у (even-numbers 0).
      2. even-numbers возвращает (cons 0 <ленивый-хвост>).
      3. take видит голову 0. Он нужен, возвращаем 0. Теперь нужен rest последовательности.
      4. rest ленивой последовательности — это тот самый <ленивый-хвост>.
      5. При попытке получить первый элемент этого хвоста (т.е., второй элемент исходной seq) происходит реализация ленивого хвоста: вычисляется (even-numbers (+ 0 2)) => (even-numbers 2).
      6. (even-numbers 2) возвращает (cons 2 <ленивый-хвост>) (где "рецепт" хвоста — (lazy-seq (even-numbers 4))).
      7. take видит голову 2 (второй элемент). Возвращаем 2. Теперь нужен rest этого хвоста.
      8. При попытке получить первый элемент этого нового хвоста (т.е., третий элемент исходной seq) реализуется его "рецепт": (even-numbers 4) -> (cons 4 <ленивый-хвост>).
      9. ... Процесс повторяется, пока take не соберет 10 элементов (0, 2, 4, ..., 18).
    • Почему это не Stack Overflow? Рекурсивный вызов even-numbers происходит не в момент создания элемента n, а отложенно, в момент реализации следующего элемента (при обращении к хвосту). Вызовы even-numbers для генерации следующего элемента происходят последовательно, а не вглубь стека. Нет глубокой вложенности вызовов. Это рекурсия за счет ленивости, а не за счет стека вызовов. Каждый шаг вперед делается только по запросу.

По итогу:

Ленивые последовательности в Clojure - это не просто "оптимизация", а мощная абстракция для работы с последовательностями:

  1. Механизм: "Рецепт" + Кеш реализованных элементов + Чанкинг (для производительности).
  2. Преимущества:
    • Эффективность: Избегает ненужных вычислений.
    • Композируемость: Позволяет строить сложные цепочки преобразований без промежуточных коллекций и преждевременных вычислений.
    • Бесконечность: Позволяет работать с концептуально бесконечными потоками данных.
    • Экономия Памяти: Элементы вычисляются и хранятся только по мере необходимости (хотя чанкинг вносит компромисс).
  3. Ключевые Конструкторы: map, filter, remove, take, take-while, drop, drop-while, repeat, repeatedly, iterate, lazy-seq.
  4. Осторожность:
    • Побочные Эффекты: Функции внутри "рецепта" (как vampire-related-details или rand-int) выполняются в момент реализации, который может быть неочевидным. Управляй побочными эффектами осознанно.
    • Чанкинг: Может приводить к реализации большего числа элементов, чем кажется необходимым для одной операции (как в примере с first). Понимай эту особенность для анализа производительности.
    • Кеширование: Реализованный элемент хранится в памяти до сборки мусора. Это хорошо для повторного доступа, но может увеличить потребление памяти при работе с очень большими ленивыми seq, если удерживать ссылку на голову.

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

Больше всякого можно найти тут:Канал в telegram