Что такое Stream Fusion на Haskell?

Question

Что такое Stream Fusion на Haskell и как его использовать?

Answer 1

Бумага, на которую указывает Логан, великолепна, но немного сложна. (Просто спросите моих учеников.) Также много говорится о том, «как работает слияние потоков», и лишь малая часть о том, что такое слияние потоков и как вы можете его использовать.

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

nodenames = map ("n"++) $ map show [1..]

Наивный код выделит бесконечный список целых чисел [1, 2, 3, ...], бесконечный список строк ["1", "2", "3", ...] и, в конечном итоге, бесконечный список имен ["n1", "n2", "n3", ...]. Это слишком много.

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

Чтобы использовать потоковое объединение, вам нужно написать нерекурсивные функции списка , которые используют функции из библиотеки потокового объединения, описанные в GHC ticket 915 (map, foldr и т. Д.) Вместо явной рекурсии. Эта библиотека содержит новые версии всех функций Prelude, которые были переписаны для использования объединения потоков. По-видимому, этот материал планируется включить в следующую версию GHC (6.12), но его нет в текущей стабильной версии (6.10). Если вы хотите использовать библиотеку, у Porges есть хорошее простое объяснение в его ответе.

Если вы действительно хотите объяснить, как работает потоковое слияние, напишите другой вопрос - но это намного сложнее.

Answer 2

Насколько я знаю, и вопреки сказанному Норманом, слияние потоков не в настоящее время реализовано в базе GHC (т. Е. Вы не можете просто использовать функции Prelude). Для получения дополнительной информации см. билет GHC 915 .

Чтобы использовать потоковое объединение, вам необходимо установить библиотеку потокового объединения, импортировать Data.List.Stream (вы также можете импортировать Control.Monad.Stream) и использовать только функции из этого модуля, а не функции Prelude. Это означает, что импорт Prelude скрывает все функции списка по умолчанию, а не использует конструкции [x..y] или понимание списка.

Answer 3

Не правильно ли, что когда GHC в 6.12 по умолчанию использует эти новые функции, они также будут реализовывать [x..y] и перечислять понимания таким нерекурсивным способом? Потому что единственная причина, по которой они не являются правильными строками, состоит в том, что они внутренние и на самом деле написаны не на Хаскеле, а скорее как ключевые слова, ради скорости и / или потому, что вы не сможете переопределить это синтаксис.