Conduit, замена спискам?

Я думал о списках в Haskell, и я думал, что в других языках списки не используются для всего. Конечно, вы можете захотеть сохранить список, если вам потребуются значения позже, но если это всего лишь один случай, скажем, итерация от [1..n], зачем использовать список, где все, что действительно нужно, — это увеличиваемая переменная?

Я также читал о «слиянии списков» и заметил, что, хотя компиляторы Haskell пытаются реализовать эту оптимизацию для устранения промежуточных списков, они часто безуспешны, в результате чего сборщику мусора приходится очищать списки, которые используются только один раз.

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

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

Затем я наткнулся на conduit, в котором говорится, что это:

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

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

Например, могу ли я сделать следующее:

fold f3 $ take 10 $ map f2 $ unfold f1 init_value

И с несколькими правильно размещенными аннотациями типов использовать каналы для всего процесса вместо списков?

Я надеялся, что, возможно, classy-prelude позволит использовать такой код, но я не уверен. Если возможно, может ли кто-нибудь привести пример, например, как указано выше?


list haskell conduit
person Clinton    schedule 15.01.2013    source источник
comment
я думаю, что ваша интуиция о списках неверна, и вы также можете забыть о ленивом вычислении, когда говорите о хранении списка. В любом случае проблема, которую решает conduit, связана с ленивым вводом-выводом. также посмотрите на пакет vector.   -  person jberryman    schedule 15.01.2013

Ответы (2)


arrow_upward
8
arrow_downward

Список потоков вычислений в постоянной памяти в тех же обстоятельствах, что и для conduit. Наличие или отсутствие промежуточных структур данных не влияет на то, работает ли он в постоянной памяти. Все, что он меняет, — это эффективность и размер постоянной памяти, в которой он обитает.

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

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

person Gabriel Gonzalez    schedule 15.01.2013
comment
Значит, проводник недостаточно умен, чтобы объединить map f $ map g в map (f . g)? - person Clinton; 15.01.2013
comment
@Clinton В принципе, вы можете добавить правило перезаписи, которое преобразует левую часть в правую, но я пробовал что-то подобное для своей собственной библиотеки pipes, и оно не срабатывает надежно. Тем не менее, версия слияния потока, на которую я ссылался, фактически автоматически оптимизировала бы левую часть правой стороны без каких-либо подсказок, но это имеет свои собственные проблемы. Суть проблемы в том, что ghc на самом деле не очень хорошо справляется с сокращением циклов, поэтому люди придумали слияние потоков в первую очередь для преобразования рекурсивного кода в нерекурсивный код. - person Gabriel Gonzalez; 15.01.2013

arrow_upward
4
arrow_downward

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

Если вы соедините это с classy-prelude-conduit, вы можете получить относительно простой код. И мы, безусловно, могли бы добавить больше экспорта в classy-prelude-conduit, чтобы лучше оптимизировать его для этого варианта использования. А пока вот пример, следующий основной сути того, что вы изложили выше:

{-# LANGUAGE NoImplicitPrelude #-}
{-# LANGUAGE OverloadedStrings #-}
import ClassyPrelude.Conduit
import Data.Conduit.List (unfold, isolate)
import Data.Functor.Identity (runIdentity)

main = putStrLn
     $ runIdentity
     $ unfold f1 init_value
    $$ map f2
    =$ isolate 10
    =$ fold f3 ""

f1 :: (Int, Int) -> Maybe (Int, (Int, Int))
f1 (x, y) = Just (x, (y, x + y))

init_value = (1, 1)

f2 :: Int -> Text
f2 = show

f3 :: Text -> Text -> Text
f3 x y = x ++ y ++ "\n"
person Michael Snoyman    schedule 15.01.2013