Haskell:Lists vs Streams

Question

我注意到溪流看起来很像列表,除了不断添加时间.当然,添加常量时间附加到列表并不太复杂,DList就是这么做的.

让我们假设在剩下的讨论中,任何一个列表都有不变的时间附加,或者我们根本就不感兴趣.

我的想法是Haskell列表应该简单地实现为流.对于这种情况并非如此,我认为以下内容需要保留:

1. 在某些情况下,列表优于流AND
2. 有些情况下流比列表更好.

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

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

附加信息:

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

1. 列表或
2. 创建一个具有两个整数的对象: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:从列表到流到什么都没有,可能有最完整的解释.简短的版本是当你有一个长管道时:

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

Answer 2

流的优势在于它们更强大.界面:

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

让你做许多普通列表不能做的事情.例如:

• 跟踪大小(例如Unknown,Max 34,Exact 12)
• 执行monadic动作以获取下一个元素.列表可以通过惰性IO部分地执行此操作,但该技术已证明容易出错,通常仅供初学者使用,或者用于简单的小脚本.

然而,与列表相比,它们有很大的缺点 - 复杂性!对于初学者程序员来说,要理解流,你必须在存在类型和monadic动作之上.如果要使用基本列表类型来学习这两个复杂的主题,那么学习haskell会非常困难.

将其与具有接口的列表进行比较:

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

这非常简单,可以轻松地向新程序员讲授.

列表的另一个优点是您可以简单地匹配它们.例如:

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

这对有经验的程序员(我仍然在许多方法中使用列表模式匹配)以及尚未学习可用于操作列表的标准高阶函数的初学者程序员都很有用.

效率也是列表的另一个潜在优势,因为ghc花费了大量时间进行列表融合.在很多代码中,从不生成中间列表.使用流进行优化可能要困难得多.

所以我认为用Streams交换列表是一个糟糕的选择.目前的情况更好,如果你需要它们你可以把它们带进去,但是初学者不会被它们的复杂性所困扰,熟练的用户也不必失去模式匹配.

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

这等同于enumFromTo 1 1000000懒惰评估,并且融合(这使得它非常有效).例如,sum [1..1000000]在打开优化时不会生成任何列表(并使用常量内存).因此情况(2)是正确的,由于惰性评估,这种情况对于流不是优势.如上所述,流比列表具有其他优势.

Answer 3

简短的回答:列表和流是无与伦比的力量.Streams允许monadic操作但不允许共享,而列表则相反.

更长的答案:

1)请参阅@nanothief以获取无法用列表实现的反例2)以下是一个反例,使用流不能轻易实现

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

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

使用列表,您只需计算一次重函数.计算baz和quux 使用流而无需额外计算的代码heavyFunction将难以维护.