list - 在 Haskell 中，为什么没有一个 TypeClass 来表示可以像列表一样工作的东西呢？

Question

我正在阅读Learn You a Haskell我想知道为什么这么多东西都像一个列表，而 Prelude 中没有任何内容使用类型类的 native 工具来设置它:

"The bytestring version of : is called cons It takes a byte and a bytestring and puts the byte at the beginning. It's lazy though, so it will make a new chunk even if the first chunk in the bytestring isn't full. That's why it's better to use the strict version of cons, cons' if you're going to be inserting a lot of bytes at the beginning of a bytestring."

为什么没有一个 TypeClass listable 或提供 : 的东西统一功能Data.ByteString , Data.List , Data.ByteString.Lazy ， ETC？这是否有原因，或者这只是遗留 Haskell 的一个元素？使用:作为一个例子，有点轻描淡写，也来自 LYAH:

Otherwise, the bytestring modules have a load of functions that are analogous to those in Data.List, including, but not limited to, head, tail, init, null, length, map, reverse, foldl, foldr, concat, takeWhile, filter, etc.

Answer 1

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)

这里容器具有类型*->*。这不适用于字节串，因为它们不允许任意类型；他们有善良的*。它也不适用于 Data.Vector.Storable 向量，因为该类不包含上下文(Storable 约束)。

您可以通过将类定义更改为来解决此问题

class ListableMPTC container elem | container -> elem where

或

class ListableAT container where
  type Elem container :: *

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

instance ListableMPTC [a] a where

但你不再是 Haskell98。

这就是为什么即使是一个简单的 Listable 类型的接口(interface)也是不平凡的；当您需要考虑不同的集合语义(例如队列)时，它会变得有点困难。另一个真正巨大的挑战是可变数据与不可变数据。到目前为止，我见过的每一次尝试(除了一次)都通过创建一个可变接口(interface)和一个不可变接口(interface)来解决这个问题。我所知道的将两者统一起来的一个接口(interface)令人费解，调用了一堆扩展，并且性能相当差。

附录:字节串

这完全是我的猜测，但我认为我们一直坚持将字节串视为进化的产物。也就是说，它们是低性能 I/O 操作的第一个解决方案，并且使用 Ptr Word8 与 IO 系统调用进行交互是有意义的。对指针的操作需要 Storable，并且很可能当时还没有使多态性工作所需的扩展(如上所述)。现在很难克服他们的势头。具有多态性的类似容器当然是可能的，storablevector 包实现了这一点，但它还没有那么流行。

字节串可以是多态的，而不对元素有任何限制吗？我认为 Haskell 与此最接近的是数组类型。对于低级 IO，这几乎不如字节串，因为数据需要从指针解包到数组的内部格式中。此外，数据被装箱，这会增加大量的空间开销。如果您想要拆箱存储(更少的空间)和与 C 的高效接口(interface)，指针是最佳选择。一旦有了 Ptr，就需要 Storable，然后需要在类型类中包含元素类型，这样就需要扩展。

话虽这么说，我认为通过适当的扩展，这对于任何单个容器实现(模可变/不可变 API)来说本质上是一个已解决的问题。现在更困难的部分是提出一组合理的类，这些类可用于许多不同类型的结构(列表、数组、队列等)，并且足够灵活有用。我个人认为这相对简单，但我可能是错的。