Haskell"集合"语言设计

Question

为什么Haskell实现如此专注于链表？

例如,我知道Data.Sequence对于大多数列表操作(操作除外cons)更有效,并且使用了很多; 但从语法上讲,它"几乎不受支持".Haskell在函数抽象方面投入了大量精力,例如Functor和Foldable类,但它们的语法与默认列表的语法不兼容.

如果在一个项目中我想用序列优化和替换我的列表 - 或者如果我突然想要支持无限集合,并用列表替换我的序列 - 结果代码更改是令人憎恶的.

所以我想我的疑惑可以在以下问题中具体化:

1. 为什么不map等于(Functor f) => (a -> b) -> f a -> f b？
2. 为什么不能将[]和(:)函数用于,例如,Data.Sequence中的类型？

我真的希望有一些解释,不包括"向后兼容性"或"它只是那种方式",但如果你认为没有,请告诉我.我们也欢迎任何相关的语言扩展.

Answer 1

在进入原因之前,这里是问题的摘要以及您可以采取的措施.构造函数[]和(:)保留用于列表,不能重新定义.如果计划对多个数据类型使用相同的代码,则定义或选择表示要支持的接口的类型类,并使用该类中的方法.以下是一些适用于列表和序列的通用函数.我不知道有什么概括(:),但你可以写自己的.

• fmap 代替 map
• mempty 代替 []
• mappend 代替 (++)

如果您打算进行一次性数据类型替换,那么您可以为事物定义自己的名称,并在以后重新定义它们.

-- For now, use lists
type List a = [a]
nil = []
cons x xs = x : xs

{- Switch to Seq in the future
-- type List a = Seq a
-- nil = empty
-- cons x xs = x <| xs
-}

请注意,[]并(:)有构造函数:您还可以将它们用于模式匹配.模式匹配特定于一种类型的构造函数,因此您无法在不重写模式匹配代码的情况下扩展模式以处理新数据类型.

为什么在Haskell中有如此多的特定于列表的东西

列表通常用于表示顺序计算,而不是数据.在命令式语言中,您可以构建一个带有循环的Set,该循环创建元素并将它们逐个插入到集合中.在Haskell中,您通过创建列表然后将列表传递给您来执行相同的操作Set.fromList.由于列表与这种计算抽象紧密匹配,因此它们不可能被另一个数据结构所取代.

事实仍然是,某些功能在列表特定时可能是通用的.一些常见的功能map是特定于列表的,因此新用户可以学习的东西较少.特别是,它们提供了更简单且(已确定)更易理解的错误消息.由于可以使用泛型函数,因此问题实际上只是语法上的不便.值得注意的是,Haskell语言实现具有非常少的列表特定代码,因此新的数据结构和方法可以与"内置"代码一样高效.

有几个类是列表的有用推广:

• Functor供应fmap,概括map.
• Monoid提供了对具有类似列表结构的集合有用的方法.空列表通过以下[]方式推广到其他容器mempty,并将列表连接(++)推广到其他容器mappend.
• Applicative和Monad提供的方法,用于将集合解释为计算.
• Traversable和Foldable提供了用于在集合上运行计算的有用方法.

其中只有Functor和Monad属于有影响力的Haskell 98规范,因此其他人在不同程度上被图书馆作家所忽视,这取决于图书馆的编写时间以及维护的积极程度.核心库很好地支持新接口.

Answer 2

我记得map在默认情况下阅读某个列表的地方,因为如果Haskell的新人犯了错误并且看到了一些他们不知道的"Functors"的复杂错误,他们会被推迟.因此,他们有两个map和fmap,而不仅仅是map.

编辑:"某处"是Monad Reader第13期,第20页,脚注3:

3你可能会问为什么我们需要一个单独的地图功能.为什么不放弃当前仅列表映射函数,并将fmap重命名为map？嗯,这是一个很好的问题.通常的论点是,有人在学习Haskell时,如果错误地使用地图,则更倾向于看到关于列表的错误,而不是关于Functors.

因为(:),这个(<|)功能似乎是一个替代品.我不知道[].

Answer 3

对于"列表操作"来说,一个挑剔的Data.Sequence效率不高,它对序列操作更有效.也就是说,Data.List中的很多函数都是序列操作.Data.Sequence中的手指树必须为cons(<|)等效于list(:)做更多的工作,并且它的内存表示也比列表大一些,因为它是由两种数据类型构成的一个FingerTree和深刻的.

列表的额外语法很好,它在哪些列表擅长的方面达到了最佳点 - cons(:)和左边的模式匹配.序列是否应该具有额外的语法是进一步的争论,但是因为你可以用列表获得很长的路径,并且列表本质上很简单,所以必须具有良好的语法.

List不是字符串的理想表示 - 内存布局效率低,因为每个Char都用构造函数包装.这就是ByteStrings推出的原因.虽然它们是作为数组布局的,但ByteStrings必须做一些管理工作 - 如果你使用短字符串,[Char]仍然可以具有竞争力.在GHC中,有一些语言扩展可以为ByteStrings提供更多类似String的语法.

另一个主要的懒惰函数Clean总是将字符串表示为字节数组,但它的类型系统使这更实用 - 我相信ByteString库使用了unsafePerfomIO.