Каковы некоторые убедительные случаи использования бесконечных структур данных?

Question

Некоторые языки (Haskell, Clojure, Scheme и т. Д.) Имеют ленивую оценку. Одна из "точек продажи" ленивых вычислений - бесконечные структуры данных. Что в этом такого хорошего? Каковы некоторые примеры случаев, когда возможность иметь дело с бесконечными структурами данных явно выгодна?

Answer 1

Вот два примера, один большой и один маленький:

Почему "Функциональное программирование имеет значение " Джона Хьюза имеет хороший пример шахматной игры. Дерево ходов для игры в шахматы на самом деле не бесконечно, но достаточно велико, чтобы оно могло быть бесконечным (назовите его "почти бесконечным"). На строгом языке вы не можете рассматривать его как дерево, потому что не хватает места для хранения всего дерева. Но в ленивом языке вы просто определяете дерево, а затем определяете функцию "nextMove", чтобы пройти ее по мере необходимости. Ленивый механизм оценки заботится о деталях.

Небольшой пример просто связывает индексный номер с каждым элементом в списке, так что ["foo", "bar", "baz"] становится [(1,"foo"), (2,"bar"), (3,"БАЗ")]. В строгом языке вам нужен цикл, который отслеживает последний индекс и проверяет, если вы находитесь в конце. В Хаскеле вы просто говорите:

zip [1..] items

Первый аргумент zip - это бесконечный список. Вам не нужно думать, как долго это должно быть раньше времени.

Answer 2

Несколько преимуществ, которые я могу придумать:

• Более чистый код - интересно отметить, что код для генерации бесконечных последовательностей, если часто проще и чище, чем код, работающий с ограниченными данными. Это потому, что такой код часто ближе к основному математическому определению.
• Гибкость - вместо того, чтобы заранее решать, каким должен быть размер ваших данных, если вы пишете их, используя ленивую бесконечную структуру, вам просто не нужно беспокоиться. Это будет "просто работать"
• Производительность - если вы используете ленивость правильно, вы можете использовать ее для повышения производительности, вычисляя только значения данных, когда и когда они необходимы, и, возможно, вовсе нет. Таким образом, вы можете избежать большого количества ненужных вычислений.
• Абстракция бесконечных процессов - существует интересное использование бесконечных ленивых последовательностей в качестве абстракции для потоков событий, например, чтение входных данных из сетевого соединения во времени. Это может создать несколько очень элегантных и интересных способов создания кода для обработки потоков событий. например, смотрите библиотеку stream-utils в Clojure.
• Лучшие алгоритмы - есть некоторые алгоритмы, которые легче выразить с помощью бесконечных структур данных - идея заключается в том, что вы лениво "извлекаете" те части решения, которые вам нужны, оставляя остальную часть бесконечного алгоритма без оценки. Если использование этого подхода позволяет вам, чтобы уменьшить временную сложность вашего алгоритма (скажем, из O(n^2) в O(n log n)) тогда это может быть большой победой.

Answer 3

Существует каноническая стратегия чистого запоминания:

fib = (map fib' [0..] !!)
    where
    fib' 0 = 0
    fib' 1 = 1
    fib' n = fib (n-1) + fib (n-2)

Мы наносим на карту fib' функция над бесконечным списком, чтобы построить таблицу всех значений fib, Вуаля! Дешевое, легкое запоминание.

Конечно, это время поиска линейно в аргументе. Вы можете заменить его на бесконечное три, чтобы получить логарифмическое время поиска. ср data-inttrie.

Answer 4

Я собирался комментировать относительно схемы @knivil. Вместо этого я просто брошу это как другой ответ.

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

Knivil упоминается с использованием схемы iota, Посмотрите, как легко написать полный метод (со всеми тремя аргументами), полагаясь на лень:

iota count begin step = let xs = begin:map (+step) xs
                        in take count xs

-- or, alternately
iota count begin step = take count $ map ((+begin).(*step)) [0..]

Я мог бы также написать length для непустых списков, злоупотребляя ленью:

len = fst . last . zip [1..]

-- or even handling empty lists
len = fst . last . zip [0..] . (undefined:)

Рассмотрим мощный и элегантный iterate функция определена в прелюдии.

iterate f x = x : iterate f (f x)

Это создает бесконечный список [x, f x, f (f x), f (f (f x)), ...], Я мог бы написать iota с точки зрения iterate:

iota count begin step = take count $ iterate (+step) begin

Ленивый подход - элегантный способ программирования. Это не единственный способ, и люди, привыкшие к C или Java, наверняка будут кричать "но мне не нужна лень, я могу просто _", и они правы. Если ваш язык завершен по Тьюрингу, это можно сделать. Но лень может быть такой элегантной.

Answer 5

Ну, у меня был хороший пример использования в прошлом месяце. Мне нужен был генератор для уникальных имен при копировании объектов. Это означает, что генератор берет оригинальное имя Xи генерирует новое имя для копии. Это делается путем добавления текста вроде

X - copy
X - copy (2)
X - copy (3)
...

до тех пор, пока имя не используется в наборе объектов в той же группе. Использование "бесконечной структуры данных" (бесконечного массива строк) для этого вместо простого цикла имеет одно преимущество: вы можете полностью отделить часть, генерирующую имя, от теста, если имя уже используется. Таким образом, я мог бы повторно использовать функцию генератора для различных типов объектов, где используемый тест немного отличается для каждого типа объекта.

Answer 6

Бесконечные структуры данных обеспечивают элегантное представление (вычислимых) действительных чисел. Например, бесконечный список, как

[(0, 4), (1, 3.5), (3.1, 3.2), ...]

может представлять pi, Со встроенной ленью оперировать этим представлением становится легко.