在Haskell中，为什么没有TypeClass可以像列表一样工作？

Question

我读Learn You a Haskell，我不知道为什么有这么多的东西都表现得像一个列表，并没有什么前奏是使用类型类的本地设备进行此设置：

“的字节串版本of：被称为cons它需要一个字节和一个字节字符串，并将字节放在开始位置，虽然很懒，所以即使字符串中的第一个字节未满，它也会创建一个新的块，这就是为什么它最好使用严格版本的缺点，缺点'如果你要在字节串的开头插入大量的字节。“

为什么没有一个类型类可列或东西，它提供了:功能统一Data.ByteString，Data.List，Data.ByteString.Lazy等？是否有这个原因，还是仅仅是遗留Haskell的元素？使用:作为一个例子是一种一个保守的，也从LYAH：

否则，字节串模块具有的是类似于那些在Data.List模块，包括功能的负载，但不限于，头，尾时，init，NULL，长度，地图，反向，与foldl，foldr相似，concat，则takeWhile，过滤器等

Answer 1

，它提供了：功能来统一Data.ByteString，Data.List模块，Data.ByteString 。拉齐等？

已经有人试图想出一个好的a）序列接口，b）容器接口，但是统一不同类型的数据类型，不同类型的约束，通常会导致结果不够规范很难想象将它们放在基础库中。同样，对于数组，虽然Vector包中有一个相当一般的接口（基于关联的数据类型）。

有几个项目用统一的接口来统一这些不同的半相关数据类型，所以我希望我们很快会看到一个结果。类似的容器类型。结果虽然不是微不足道的。

Answer 2

ListLike包似乎提供你在找什么。我从来不明白为什么它不是更受欢迎。

ListLike除此之外，Prelude中没有实现的一个原因是因为如果不调用某些语言扩展（多参数类型类和fundeps或关联类型），就无法做得很好。有三类容器来考虑：不关心，在他们所有的元素

1. 容器（如[]）
2. 容器，只为特定元素实现（如字节串）
3. 集装箱它们是元素上的多态，但需要一个上下文 （例如Data.Vector.Storable，它将使用可存储的 实例保存任何类型的数据。

这里是一个非常基本的ListLike风格类，而无需使用任何扩展：

class Listable container where 
    head :: container a -> a 

instance Listable [] where 
    head (x:xs) = x 

instance Listable ByteString where --compiler error, wrong kind 

instance Listable SV.Vector where 
    head v = SV.head --compiler error, can't deduce context (Storable a) 

这里container有种*->*。这对于字节串不起作用，因为它们不允许任意类型;他们有种类*。它也不适用于Data.Vector.Storable向量，因为该类不包含上下文（Storable约束）。

你可以通过改变你的类定义要么解决这个问题

class ListableMPTC container elem | container -> elem where 

或

class ListableAT container where 
    type Elem container :: * 

现在container有种*;它是一个完全应用的类型构造函数。也就是说，你的实例看起来像

instance ListableMPTC [a] a where 

但你不再是Haskell98。

这就是为什么即使是一个简单的Listable类型接口也不重要的原因;当你有不同的集合语义来解释时（例如队列），它会变得更难一些。另一个非常大的挑战是可变数据与不可变数据。到目前为止，我所见过的每一次尝试（除了一次）都会通过创建一个可变接口和一个不可变接口来解决这个问题。我所了解的将这两者统一起来的界面之一是大脑弯曲，引发了一系列扩展，并且性能相当差。

附录：字节串

完全猜想我的一部分，但我认为我们坚持以字节串作为进化的产物。也就是说，它们是低性能I/O操作的第一个解决方案，使用Ptr Word8来连接IO系统调用是有意义的。对指针的操作需要可存储，并且最有可能的必要扩展（如上所述）使多态性工作不可用。现在很难克服它们的势头。具有多态性的类似容器当然是可能的，可存储的vec​​torvector包实现了这一点，但它并没有受到任何的欢迎。

字节串是否是多态的，对元素没有任何限制？我认为最接近Haskell的是这个数组类型。这不如低级IO的字节串好，因为数据需要从指针解压缩到数组的内部格式。数据也被装箱，这增加了显着的空间开销。如果你想要无箱的存储空间（更小的空间）和高效的C接口，指针是最好的选择。一旦你有了一个Ptr，你需要Storable，然后你需要在类型类中包含元素类型，所以你需要扩展。这就是说，我认为，通过适当的扩展可用，这对于任何单个容器实现（modulo mutable/immutable API）来说基本上是一个解决的问题。现在比较困难的部分是提出一组可用于许多不同类型结构（列表，数组，队列等）的灵活类，并且足够灵活以实用。我个人预计这会比较简单，但我可能是错的。

Answer 3

ByteString不是泛型类型。

在其他语言中，对于所有类似列表的数据结构，都有类似Sequence的东西。 我想这样的作品，以正确的扩展名：

class Seq a b | a -> b where 
    head :: a -> b 
    isTail :: a -> Bool 

# ([a]) is a sequence of a's 
instance Seq [a] a where 
    head (x:xs) = x 
    isTail = (== []) 

# ByteString is a sequence of chars 
instance Seq ByteString Char 

或者试试呢？

type BS a = ByteString 
instance List BS 

Answer 4

在Haskell中为类列表数据提供类型类没有什么价值。为什么？ 因为懒惰。您可以编写一个函数将数据转换为列表，然后使用该列表。该列表只会按照它的子列表和元素的要求进行构建，只要没有引用保留在前缀中，它们的内存就有资格收集。

提供通用toList函数的类型类的值有所不同 - 但是，该函数已存在于Data.Foldable中。

所以基本上，解决的办法是实现Data.Foldable并使用它的toList函数。

Answer 5

这样的类的主要问题是，即使它存在，它只会提供表面相似性。

使用不同结构构建的相同算法的渐近线会有很大的不同。

在严格字节串的情况下，使用cons来建立它们是糟糕的，因为每当你添加另一个字符时，你都会复制整个字符串。这个O（1）在列表上的操作将它变成对Bytestring操作的O（n）。

这导致O（n^2）行为，当你实现第一个算法可能会想到，地图，而建立一个列表或Data.Sequence.Seq与cons是线性时间，它可以是实现在O（n）字节串或向量以及一点点想法。

事实证明，这样的类的实用程序，因为这比实际更肤浅。

我不是说没有找到好的设计，但是这样的设计很难使用，并且优化设计的可用版本并且可能不会被认为是Haskell 98.

我已经在我的keys包中提供了这个设计空间的一部分，它提供了很多用于索引到容器等的函数，但是我故意避免提供一个类似列表的API a），因为它已经完成之前几乎没有成功，b。）因为上面的渐近关注。

tl; dr您通常想要在底层操作的渐近性发生变化时非常不同地实现算法。

Answer 6

有两种类型称为Foldable和Traversable，其目的是抽象列表和其他顺序数据结构的一些common1行为。并不是所有的数据结构都具有这些实例，但我不知道它们是否足够透明，以至于它仍然可以对它们进行优化（是否有人对此有所了解？）

来源：Foldable and Traversable
又见这个答案 Why is Haskell missing “obvious” Typeclasses