Что такое Haskell Stream Fusion

Ответ 1

Бумага, на которую указывает Логан, велика, но это немного сложно. (Просто спросите моих учеников.) Это также много говорит о том, "как работает слияние потоков" и только о фракции "что такое слияние потоков и как вы можете его использовать".

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

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 имеет приятное простое объяснение в своем ответе.

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

Ответ 2

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

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

Ответ 3

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