Больше бесконечных списков в схеме

Это продолжение моего предыдущего рассказа, который можно найти здесь.

Объединение потоков

В прошлый раз мы сделали несколько интересных стримов с помощью stream-add. Теперь я хочу представить более универсальную функцию, которая позволит нам создавать более интересные потоки.

Эта функция почти точно такая же, как stream-add, за исключением того, что мы можем передать ей любую операцию, а не только +. stream-add и (stream-combine +) эквивалентны.

Новые силы

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

Как и в случае с натуральными числами, предположим, что поток степеней двойки powsOf2 существует. Это поток '(1 2 4 8 16 32 ...), когда мы объединяем потоки, умножая это на '(2 2 2 2 2 2 ...), получаем '(2 4 6 8 16 32 64 ...). Так что, как и раньше, ((stream-combine *) twos powsOf2)) является хвостом нашего списка, и нам просто нужно начать с 1.

Другой поток, который теперь легко построить, — это последовательность квадратов.

И факториалы

Снова обратите внимание, что факториалы: '(1 2 6 24 120 720 …), умноженные на натуральные числа: '(1 2 3 4 5 6), равны cdr факториалов: '(2 6 24 120 720 5040 …). Поскольку у нас уже есть cdr факториалов, нам просто нужно явно начать с первого и объединить два.

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

К простым числам

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

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

Простое использование

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

Сито Эратосфена

Решето Эратосфена — древний алгоритм нахождения простых чисел. По сути, вы берете список натуральных чисел, начинающихся с 2 (первое простое число). Любое число, кратное двум, по определению не простое, поэтому удалите их из списка. Теперь перейдите к следующему простому числу и удалите из списка все его кратные и так далее. Этот процесс удалит все числа с коэффициентами, отличными от единицы или самого себя. (дальнейшее чтение) Обычно для этого процесса требуется верхняя граница, но мы нашли способ поиграть с бесконечностью. И снова ленивое вычисление спасает положение, фильтруя только тогда, когда нам это нужно.

Праймы до бесконечности

Функция sieve просто реализует описанный выше алгоритм. Он принимает первый элемент потока как простое число, отфильтровывает все его факторы и повторяет процесс для следующего (простого) числа. Прохождение потока натуральных чисел, начиная с 2, дает простые числа.

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

Об авторе

Эрик Брейер — студент факультета компьютерных наук Университета Райса. Найти его можно на его сайте, а также на GitHub и LinkedIn.