在Haskell中，为什么没有TypeClass可以像列表一样工作？ [英] In Haskell, why isn't there a TypeClass for things that can act like lists?
问题描述
我正在阅读学习你是一个Haskell ，我想知道为什么很多事情都像一个列表，并且Prelude中没有任何内容使用类型类的本地工具来设置它：
字符串版本：被称为cons它需要一个字节和一个字节字符串，并将字节放在开始位置，虽然很懒，所以即使字节串中的第一个块不满，也会产生新的块，这就是为什么使用严格版本的缺点，'cons'如果你要在字节串的开头插入很多字节。
为什么不是有一个TypeClass listable 或者提供：函数来统一 Data.ByteString 的东西， Data.List ， Data.ByteString.Lazy ，等等？是否有这个原因，还是仅仅是遗留Haskell的元素？使用：作为示例，这也是LYAH的轻描淡写：否则，字节串模块具有类似于Data.List中的函数的负载，包括但不限于头，尾，初始值，空值，长度，映射，反向，foldl，foldr，concat，takeWhile，过滤器等等。 ListLike 软件包似乎提供了您要查找的内容。我从来没有理解过为什么它不会更受欢迎。
ListLike不管，Prelude没有实现的一个原因是因为它不可能做得很好而无需调用某些语言扩展（多参数类型类和fundeps或关联类型）。有三种容器需要考虑：
- 完全不关心它们元素的容器（例如[]）
- 仅针对特定元素（例如字节串）实现的容器
- 元素为多态但需要上下文的容器
（例如Data.Vector .Storable，其中
包含任何类型的可存储
实例）。
这里有一个非常基本的ListLike -b
$ b
class可以列表的容器，其中
head :: container a - >
实例Listable []其中
head（x：xs）= x
实例可列出的ByteString其中--compiler错误，错误类型
instance Listable SV.Vector其中
head v = SV.head - 编译器错误，无法推断上下文（可存储a）
这里容器有类型 * - > * 。这对于字节串不起作用，因为它们不允许任意类型;他们有种 * 。它也不适用于Data.Vector.Storable向量，因为该类不包含上下文（Storable约束）。
您可以修复此问题通过改变你的类定义为
class ListableMPTC container elem |容器 - > elem其中
或
class ListableAT容器其中
类型Elem container :: *
现在容器有种类 * ;它是一个完全应用的类型构造函数。也就是说，你的实例看起来像
实例ListableMPTC [a] a其中
但你不再是Haskell98。
这就是为什么即使是简单的Listable类型接口非平凡;当你有不同的集合语义来解释时（例如队列），它会变得更难一些。另一个非常大的挑战是可变数据与不可变数据。到目前为止，我所见过的每一次尝试（除了一次）都会通过创建一个可变接口和一个不可变接口来解决这个问题。我所知道的将这两者统一起来的界面是大脑弯曲，引发了一堆扩展，并且性能相当差。
附录：bytestrings
我完全猜测，但我认为我们坚持将字节串作为进化的产物。也就是说，它们是低性能I / O操作的第一个解决方案，并且使用 Ptr Word8 来连接IO系统调用是有意义的。对指针的操作需要可存储，并且最有可能的必要扩展（如上所述）使多态性工作不可用。现在很难克服它们的势头。一个具有多态性的类似容器当然是可能的，storablevector包实现了这一点，但它并没有受到任何限制。
字节串是否可以是多态的，对元素没有任何限制？我认为最接近Haskell的是这个数组类型。这不如低级IO的字节串好，因为数据需要从指针解压缩到数组的内部格式。数据也被装箱，这增加了显着的空间开销。如果你想要无箱的存储空间（更小的空间）和高效的C接口，指针是最好的选择。一旦你有了一个Ptr，你需要Storable，然后你需要在类型类中包含元素类型，所以你只需要扩展。
据说，我认为，通过适当的扩展可用，这对于任何单个容器实现（modulo mutable / immutable API）来说基本上是一个解决的问题。现在比较困难的部分是提出一组可用于许多不同类型结构（列表，数组，队列等）的灵活类，并且足够灵活以实用。我个人会认为这是相对直接的，但我可能是错的。
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:
"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."
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:
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.
The ListLike package seems to provide what you're looking for. I've never understood why it isn't more popular.
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:
- Containers that don't care about their elements at all (e.g. [])
- Containers which are only implemented for specific elements (e.g. bytestrings)
- Containers which are polymorphic over elements but require a context (e.g. Data.Vector.Storable, which will hold any type with a storable instance).
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)
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
or
class ListableAT container where
type Elem container :: *
Now container has kind *; it's a fully-applied type constructor. That is, your instances look like
instance ListableMPTC [a] a where
but you're no longer Haskell98.
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.
Addendum: bytestrings
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.
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.
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屋！
