Haskell: списки против потоков

Ответ 1

Когда вы пишете [1..1000000], что GHC действительно делает, это создать объект, содержащий 1 и 1000000, который описывает, как создать список интересов; этот объект называется "thunk". Список создается только по мере необходимости, чтобы удовлетворять требованиям к делу; например, вы можете написать:

printList [] = putStrLn ""
printList (x:xs) = putStrLn (show x) >> printList xs

main = printList [1..1000000]

Что оценивается следующим образом:

main
= { definition of main }
printList [1..1000000]
= { list syntax sugar }
printList (enumFromTo 1 1000000)
= { definition of printList }
case enumFromTo 1 1000000 of
    [] -> putStrLn ""
    x:xs -> putStrLn (show x) >> printList xs
= { we have a case, so must start evaluating enumFromTo;
    I'm going to skip a few steps here involving unfolding
    the definition of enumFromTo and doing some pattern
    matching }
case 1 : enumFromTo 2 1000000 of
    [] -> putStrLn ""
    x:xs -> putStrLn (show x) >> printList xs
= { now we know which pattern to choose }
putStrLn (show 1) >> printList (enumFromTo 2 1000000)

Тогда вы обнаружите, что 1 был напечатан на консоли, и мы начнем с вершины с enumFromTo 2 1000000 вместо enumFromTo 1 1000000. В конце концов, вы получите все напечатанные номера, и пришло время оценить

printList (enumFromTo 1000000 1000000)
= { definition of printList }
case enumFromTo 1000000 1000000 of
    [] -> putStrLn ""
    x:xs -> putStrLn (show x) >> printList xs
= { skipping steps again to evaluate enumFromTo }
case [] of
    [] -> putStrLn ""
    x:xs -> putStrLn (show x) >> printList xs
= { now we know which pattern to pick }
putStrLn ""

и оценка будет завершена.

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

concatMap foo . map bar . filter pred . break isSpecial

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

(toList . S.concatMap foo . fromList) .
(toList . S.map bar . fromList) .
(toList . S.filter pred . fromList) .
(toList . S.break isSpecial . fromList)

то заметим, что мы всегда можем аннулировать fromList . toList:

toList . S.concatMap foo . S.map bar . S.filter pred . S.break . fromList

... и затем происходит волшебство, потому что цепочка S.concatMap foo . S.map bar . S.filter pred . S.break явно вырабатывает итератор, а не строит его неявно путем внутреннего построения, а затем немедленно уничтожает фактические списки.

Ответ 2

Преимущество потоков - они более мощные. Интерфейс:

data Stream m a = forall s . Stream (s -> m (Step s a)) s Size   

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

• Отслеживать размер (например, Unknown, Max 34, Exact 12)
• Выполняйте монадические действия, чтобы получить следующий элемент. Списки могут частично делать это с ленивым IO, но эта техника оказалась склонной к ошибкам и обычно используется только новичками или для простых небольших скриптов.

Однако они имеют большой недостаток по сравнению со списками - сложность! Для начинающего программиста, чтобы понимать потоки, вы должны быть на вершине экзистенциальных типов и монадических действий. Было бы очень сложно изучить haskell, если использовать основной тип списка, который вам нужно было изучить у этих двух сложных предметов.

Сравните это с списками, которые имеют интерфейс:

data [] a = a : [a] | []

Это очень просто, и что-то, чему можно легко научить новому программисту.

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

getTwo (a : b : _) = Just (a,b)
getTwo _ = Nothing

Это полезно для опытных программистов (я по-прежнему использую сопоставление шаблонов списков во многих методах) и для начинающих программистов, которые еще не изучили стандартные функции более высокого порядка, которые можно использовать для управления списками.

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

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

EDIT: около [1..1000000]:

Это эквивалентно enumFromTo 1 1000000, который оценивается лениво и подвержен слиянию (что делает его очень эффективным). Например, sum [1..1000000] не будет генерировать списки (и использовать постоянную память) с включенной оптимизацией. Итак, случай (2) верен, эта ситуация не является преимуществом для потоков из-за ленивой оценки. Однако, как отмечено выше, потоки имеют другие преимущества перед списками.

Ответ 3

Короткий ответ: списки и потоки несравнимы по мощности. Потоки допускают монолитные действия, но запрещают совместное использование, в то время как списки - наоборот.

Более длинный ответ:

1) См. @nanothief для контрпримера, который не может быть реализован со списками 2) Ниже приведен контрпример, который не может быть легко реализован с потоками.

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

foo = map heavyFunction bar
baz = take 5 foo
quux = product foo

В списках вы вычисляете тяжелую функцию только один раз. Код для вычисления baz и quux с потоками без дополнительных вычислений heavyFunction будет трудно поддерживать.