Полезны ли бесконечные списки для любых реальных приложений?

Question

Я уже давно пользуюсь haskell, и я прочитал большую часть Real World Haskell и Learn You a Haskell. Я хочу знать, есть ли смысл в языке, использующем ленивую оценку, в частности «преимущество» наличия бесконечных списков, есть ли задача, которую бесконечные списки делают очень легкой, или даже задача, которая возможна только с бесконечной списки?

Answer 1

Вот совершенно тривиальный, но на самом деле полезный пример того, где бесконечные списки особенно пригодятся: когда у вас есть список элементов, которые вы хотите использовать для инициализации некоторой структуры данных типа ключ-значение, начиная с последовательные ключи. Итак, скажем, у вас есть список строк, и вы хотите поместить их в IntMap, считая от 0. Без ленивых бесконечных списков вы бы сделали что-то вроде обхода списка ввода, сохраняя запущенный счетчик «следующий индекс» и наращивание IntMap по ходу дела.

С бесконечными ленивыми списками, сам список играет роль счетчика хода; просто используйте zip [0..] со своим списком элементов, чтобы назначить индексы, затем IntMap.fromList, чтобы построить окончательный результат.

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

Answer 2

Очевидный пример - цепочка обработки данных от ввода до всего, что вы хотите с ним сделать. Например, чтение потока символов в ленивый список, который обрабатывается лексером, а также создает ленивый список токенов, которые разбираются в ленивую структуру AST, затем компилируются и выполняются. Это похоже на использование Unix-каналов.

Answer 3

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

take 10 mySequence
takeWhile (<100) mySequence

вместо того, чтобы иметь множество похожих, но не совсем одинаковых функций, которые генерируют подмножество

first10ofMySequence
elementsUnder100ofMySequence

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

Answer 4

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

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

Answer 5

По сути, ленивые списки позволяют откладывать вычисления до тех пор, пока они вам не понадобятся.Это может оказаться полезным, если вы заранее не знаете, когда остановиться и что делать заранее.

Стандартным примером является u_n последовательность числовых вычислений, сходящихся к некоторому пределу.Вы можете попросить первый член так, чтобы | u_n - u_ {n-1} |

Теперь у вас есть две такие последовательности u_n и v_n, и вы хотите узнать сумму пределов точности эпсилона.Алгоритм:

• вычислить u_n до точности epsilon / 2
• вычислить v_n до точности epsilon / 2
• return u_n + v_n

Все делается лениво, вычисляются только необходимые u_n и v_n.Вы можете хотеть менее простые примеры, например.вычисление f (u_n), где вы знаете (т.е. знаете, как вычислить) модуль непрерывности f.

Answer 6

Один из моих прагматических фаворитов - cycle. cycle [False, True] генерирует бесконечный список [False, True, False, True, False ...]. В частности, xs ! 0 = False, xs ! 1 = True, так что это просто говорит, является ли индекс элемента нечетным или нет. Где это появляется? Множество мест, но вот тот, который должен знать любой веб-разработчик: создание таблиц, чередующихся затенение от строки к строке.

Общий шаблон, который мы видим здесь, заключается в том, что если мы хотим выполнить какую-то операцию с конечным списком, а не создавать конкретный конечный список, который будет «делать то, что мы хотим», мы можем использовать бесконечный список, который будет работать для всех размеров списков. ответ camcann в том же духе.

Answer 7

Синтез звука - см. Эту статью Ежи Карчмарчука:

http://users.info.unicaen.fr/~karczma/arpap/cleasyn.pdf

У Ежи Карчмаркука есть ряд других работ, использующих бесконечные списки для моделирования математических объектов, таких как степенные ряды ипроизводные.

Я перевел основной код синтеза звука на Haskell - достаточно для генератора синусоидальных сигналов и ввода-вывода WAV-файла.Производительность была почти достаточной для работы с GHCi на 1,5 ГГц Athalon - поскольку я просто хотел протестировать концепцию, я так и не смог ее оптимизировать.

Answer 8

Бесконечные / ленивые структуры допускают идиому «завязывание узла»: http://www.haskell.org/haskellwiki/Tying_the_Knot

Канонически простым примером этого является последовательность Фибоначчи, определенная непосредственно как рекуррентное отношение. (Да, да, проведите обсуждение жалоб / алгоритмов эффективности - речь идет о идиоме .): fibs = 1:1:zipwith (+) fibs (tail fibs)

Вот другая история. У меня был некоторый код, который работал только с конечными потоками - он делал некоторые вещи, чтобы создать их до некоторой точки, а затем сделал целую кучу бессмыслицы, которая включала в себя воздействие на различные биты потока, зависящие от всего потока до этой точки, объединение его с информацией из другого потока и т. д. Это было довольно мило, но я понял, что у него есть целая куча ошибок, необходимых для работы с граничными условиями, и, в основном, что делать, когда в одном потоке кончается всякое. Затем я понял, что концептуально не было причины, по которой он не мог бы работать на бесконечных потоках. Поэтому я переключился на тип данных без нуля, то есть на подлинный поток, а не на список, и все бесполезно исчезло. Несмотря на то, что я знаю, что мне никогда не понадобятся данные после определенного момента, возможность полагаться на них, находясь там, позволила мне безопасно удалить много глупой логики и позволить математической / алгоритмической части моего кода выделяться более четко.