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

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' с бесконечным списком, чтобы создать таблицу с all значениями fib. Вуаля! Дешевое, легкое запоминание.

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

Answer 4

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

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

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

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, определенную в Prelude.

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

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

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

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

Answer 6

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

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

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