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

Ответ 1

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

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

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

zip [1..] items

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

Ответ 2

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

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

Ответ 3

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

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

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

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

Ответ 4

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

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

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, наверняка будут кричать "но мне не нужна лень, я могу просто", и они верны. Если ваш язык завершен, он может быть выполнен. Но лень может быть настолько элегантным.

Ответ 5

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

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

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

Ответ 6

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

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

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