在 Haskell 中，为什么没有一个 TypeClass 来处理可以像列表一样的东西? [英] In Haskell, why isn't there a TypeClass for things that can act like lists?

问题描述

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

I'm reading Learn You a Haskell and I'm wondering why so many things are acting like a list, and nothing in the Prelude is using the native facility of type classes to set this up:

" : 的字节串版本被称为 cons 它接受一个字节和一个字节串并将字节放在开头.虽然它很懒惰，所以即使字节串中的第一个块没有满，它也会创建一个新块. 这就是为什么如果要在字节串的开头插入大量字节，最好使用 cons, cons' 的严格版本."

"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 等?这是否有原因，或者这只是遗留 Haskell 的一个元素?使用 : 作为例子有点轻描淡写，同样来自 LYAH:

Why isn't there a TypeClass listable or something that offers the : function to unify Data.ByteString, Data.List, Data.ByteString.Lazy, etc? Is there a reason for this, or is this just an element of legacy Haskell? Using : as an example is kind of an understatement, also from LYAH:

否则，bytestring 模块有很多类似于 Data.List 中的函数，包括但不限于 head、tail、init、null、length、map、reverse、foldl、foldr、concat、takeWhile、过滤器等

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.

推荐答案

ListLike 包似乎提供您正在寻找的内容.我一直不明白为什么它不那么受欢迎.

The ListLike package seems to provide what you're looking for. I've never understood why it isn't more popular.

List 和 List 一样，在 Prelude 中没有实现的一个原因是，如果不调用一些语言扩展(多参数类型类和 fundeps 或关联类型)，就不可能做得很好.需要考虑三种容器:

ListLike aside, one reason this isn't implemented in the Prelude is because it's not possible to do so well without invoking some language extensions (multi-param type classes and fundeps or associated types). There are three sorts of containers to consider:

1. 根本不关心其元素的容器(例如 [])
2. 仅针对特定元素(例如字节串)实现的容器
3. 多态于元素但需要上下文的容器(例如 Data.Vector.Storable，它将持有任何类型的可存储实例).

这是一个非常基本的 ListLike 风格的类，没有使用任何扩展:

Here's a very basic ListLike-style class without using any extensions:

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 约束).

Here container has kind *->*. This won't work for bytestrings because they don't allow an arbitrary type; they have kind *. It also won't work for a Data.Vector.Storable vector, because the class doesn't include the context (the Storable constraint).

您可以通过将类定义更改为

You can fix this problem by either changing your class definition to

class ListableMPTC container elem | container -> elem where

或

class ListableAT container where
  type Elem container :: *

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

Now container has kind *; it's a fully-applied type constructor. That is, your instances look like

instance ListableMPTC [a] a where

但你不再是 Haskell98.

but you're no longer Haskell98.

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

That's why even a simple Listable-type interface is non-trivial; it gets a bit harder when you have different collection semantics to account for (e.g. queues). The other really big challenge is mutable-vs.-immutable data. So far every attempt I've seen (except one) punts on that issue by creating a mutable interface and an immutable one. The one interface I know which did unify the two was mind-bending, invoked a bunch of extensions, and had quite poor performance.

附录:字节串

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

Totally conjecture on my part, but I think we're stuck with bytestrings as a product of evolution. That is, they were the first solution to low performance I/O operations, and it made sense to use Ptr Word8s for interfacing with IO system calls. Operations on pointers require Storable, and most likely the necessary extensions (as described above) to make polymorphism work weren't available then. Now it's difficult to overcome their momentum. A similar container with polymorphism is certainly possible, the storablevector package implements this, but it's not anywhere near as popular.

字节串可以是多态的，对元素没有任何限制吗?我认为最接近 Haskell 的是 Array 类型.这几乎不如低级 IO 的字节串好，因为数据需要从指针解包到数组的内部格式.此外，数据是装箱的，这增加了显着的空间开销.如果您想要未装箱的存储(更少的空间)和与 C 的高效接口，指针是要走的路.一旦你有了 Ptr，你就需要 Storable，然后你需要在类型类中包含元素类型，这样你就需要扩展了.

Could bytestrings be polymorphic without any restrictions on the elements? I think the closest Haskell has to this is the Array type. This isn't nearly as good as a bytestring for low-level IO because data needs to be unpacked from the pointer into the array's internal format. Also the data is boxed, which adds significant space overhead. If you want unboxed storage (less space) and efficient interfacing with C, pointers are the way to go. Once you have a Ptr, you need Storable, and then you need to include the element type in the type class, so then you're left with requiring extensions.

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

That being said, I think that with the appropriate extensions available this is essentially a solved problem for any single container implementation (modulo mutable/immutable APIs). The harder part now is coming up with a sensible set of classes that are usable for many different types of structures (lists, arrays, queues, etc.) and is flexible enough to be useful. I personally would expect this to be relatively straightforward, but I could be wrong.

这篇关于在 Haskell 中，为什么没有一个 TypeClass 来处理可以像列表一样的东西?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！