Roman Ponomarev
Jul 11, 2017 · 3 min read

Перевод статьи Boris Cherny: Introducing: Lazy Arrays in JavaScript. Опубликовано с разрешения автора.

Сегодня я представляю lazy-arr, привносящую ленивые массивы в JavaScript.

Что такое ленивый массив и почему он полезен?

Давайте вспомним свое первое собеседование по разработке программного обеспечения: напишем функцию Фибоначчи. Мы определяем базовые случаи 0 и 1, а затем рекурсивно генерируем остальные:

let fib = n => {
switch (n) {
case 0: return 0
case 1: return 1
default: return fib(n - 1) + fib(n - 2)
}
}

Проще некуда.

В чем проблема этого решения? Ну, это действительно неэффективно. Чтобы вычислить n-е число Фибоначчи, мы вызовем fib 2 в степени n-1 раз! Ясно, что это отстой, и мы должны делать лучше.

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

let memoize = fn => {
let cache = new Map
return _ => {
if (!cache.has(_)) {
cache.set(_, fn(_))
}
return cache.get(_)
}
}
let fib = memoize(n => {
switch (n) {
case 0: return 0
case 1: return 1
default: return fib(n - 1) + fib(n - 2)
}
})

Ах, уже лучше! Теперь мы вызываем fib только n - 1 раз для ввода размера n. Как еще мы можем сделать это?

Ленивые последовательности

В Scala вы можете сделать это так (авторство Philipp Gabler):

def fib(n: Int): Stream[Int] = {
lazy val stream: Stream[Int] = 0 #:: stream.scan(1)(_ + _)
stream.take(n)
}

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

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

fibs :: [Integer]
fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

И та же идея, но в Clojure:

(defn fib []
((fn rfib [a b]
(cons a (lazy-seq (rfib b (+ a b)))))
0 1))

Ну, вы поняли.

Итак, как вы это можете сделать в JavaScript?

Ленивые последовательности в JavaScript

С lazy-arr вы можете это сделать так:

let fibs = lazy([0, 1])(_ => fibs[_ - 1] + fibs[_ - 2])

И это всё! Затем вы можете обращаться к элементам в массиве по мере необходимости, и они будут вычисляться по требованию:

fibs[10] // 55
fibs[7] // 13

В первой строке вычисляется десятый номер Фибоначчи, и поскольку мы определили, что вычисление рекурсивно (в терминах предыдущих чисел Фибоначчи), нам нужно вычислить первые девять чисел Фибоначчи, чтобы вычислить десятую. Поэтому, когда мы вычисляем седьмой номер Фибоначчи во второй строке, результат возвращается мгновенно, потому что мы уже вычислили его!

Хорошая новость для обеспокоенного пользователя. Массив fibs не делает ничего лениво или с состоянием, или рекурсивно, или что угодно в этом роде. Это всего лишь массив. Всё зашито lazy-arr, а генератор - одна строка.

Аккуратно, да?


Слушайте наш подкаст в iTunes и SoundCloud, читайте нас на Medium, контрибьютьте на GitHub, общайтесь в группе Telegram, следите в Twitter и канале Telegram, рекомендуйте в VK и Facebook.

Статья на GitHub

devSchacht

Подкаст. Переводы. Веб-разработка.

Roman Ponomarev

Written by

arrival.com developer, youknow.st activist, medium.com/maria-machine author; github.com/maksugr

devSchacht

Подкаст. Переводы. Веб-разработка.

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade