list - Haskell:列表与流

Question

我注意到 streams似乎很像列表，除了固定时间追加。当然，将常量时间追加到列表中并不太复杂，DList正是这样做的。

在接下来的讨论中，让我们假设列表具有恒定的时间附加，或者我们根本对它不感兴趣。

我的想法是 Haskell 列表应该简单地实现为流。如果不是这种情况，我假设需要满足以下条件:

在某些情况下，列表优于流 和

在某些情况下，流比列表更好。

我的问题是:以上两种情况的例子是什么？

注意:出于这个问题的目的，请忽略我讨论过的特定实现中容易修复的遗漏。我在这里寻找更多的核心结构差异。

附加信息:

我想我在这里得到的部分内容是说如果我们写 [1..1000000] ，Haskell 编译器(比如 GHC)会做:

列个 list 或

使用两个整数创建一个对象:1 和 1000000，它们完全描述了列表。

如果是情况(1)，为什么要这样做，因为创建中间列表似乎是不必要的性能损失？

或者如果是情况(2)，那么我们为什么需要流？

Answer 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 ""

和评估将完成。

我们需要流的原因有点微妙。原论文， Stream fusion: From lists to streams to nothing at all ，可能有最完整的解释。简短的版本是当您有很长的管道时:

concatMap foo . map bar . filter pred . break isSpecial

...如何让编译器编译掉所有中间列表并不是那么明显。您可能会注意到，我们可以将列表视为一种正在迭代的“状态”，并且这些函数中的每一个，而不是遍历列表，只是改变了每次迭代时修改状态的方式。 Stream type 试图明确这一点，结果是流融合。下面是它的外观:我们首先将所有这些函数转换为流版本:

(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显式构建一个迭代器，而不是通过内部构建然后立即消除实际列表来隐式构建它。