21

我注意到流似乎很像列表，除了恒定时间附加。当然，向列表添加恒定时间追加并不是太复杂，而DList正是这样做的。

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

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

  1. 在某些情况下，列表比流更好并且
  2. 在某些情况下，流比列表更好。

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

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

附加信息：

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

  1. 列出清单或
  2. 使用两个整数创建一个对象：1 和 1000000，它们完全描述了列表。

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

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

4

3 回答 3

17

当您编写[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可能有最完整的解释。简短的版本是当您有很长的管道时：

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

于 2012-06-08T03:54:15.827 回答
8

流的优点是它们更强大。界面：

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 交换是一个糟糕的选择。目前的情况更好，如果需要，可以将它们引入其中，但初学者不会被它们的复杂性所困扰，熟练的用户也不必失去模式匹配。

编辑：关于[1..1000000]：

这等效于enumFromTo 1 1000000，它是惰性求值的，并且会进行融合（这使得它非常有效）。例如sum [1..1000000]，在优化开启的情况下不会生成任何列表（并使用常量内存）。所以情况（2）是正确的，由于惰性评估，这种情况对流来说不是优势。如上所述，流与列表相比还有其他优势。

于 2012-06-08T03:33:51.043 回答
7

简短的回答：列表和流在力量上是无与伦比的。流允许单子操作但不允许共享，而列表反之亦然。

更长的答案：

1) 请参阅@nanothief 了解无法用列表实现的反例 2) 下面是一个不能用流轻松实现的反例

问题是玩具列表示例通常不使用列表的共享功能。这是代码：

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

使用列表，您只需计算一次繁重的函数。baz在没有额外计算的情况下计算和quux 使用流的代码heavyFunction将难以维护。

于 2012-06-08T08:18:52.013 回答