首页 文章

在Haskell中，为什么没有TypeClass用于可以像列表一样的东西？

提问于
浏览 次
38

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

“bytestring version：被称为cons它需要一个字节和一个bytestring并将字节放在开头 . 虽然很懒，但即使字节串中的第一个块未满，它也会产生一个新的块 . 这是为什么最好使用缺点的严格版本，如果你要在字节串的开头插入大量字节，那就更好 . “

为什么没有TypeClass可列表或者提供 : 函数来统一 Data.ByteString ， Data.List ， Data.ByteString.Lazy 等？这有什么原因，或者这只是传统Haskell的一个元素？使用 : 作为一个例子是一种轻描淡写，也来自LYAH：

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

list haskell typeclass

6 回答

  • 17

    有两个类型叫做 Foldable 和 Traversable ，它们旨在抽象列表和其他顺序数据结构的一些common1行为 . 并非所有的数据结构都有这些实例，我不知道它们是否对编译器足够透明，以至于它仍然可以对它们进行优化（有人知道吗？）

    资料来源：Foldable and Traversable
    另见Why is Haskell missing “obvious” Typeclasses的答案

    回复于
  • 28

    在Haskell中为类似列表的数据创建类型类没有太多 Value . 为什么？ Because of laziness. 您可以编写一个将数据转换为列表的函数，然后使用该列表 . 该列表将仅在其子列表和元素被要求时被构造，并且只要没有对前缀的引用，它们的存储器就有资格收集 .

    类型类的值有一个提供通用的 toList 函数 - 但是，它已存在于Data.Foldable中 .

    基本上，解决方案是实现 Data.Foldable 并使用其 toList 函数 .

    回复于
  • 14

    ListLike包似乎提供了你从未理解为什么它不受欢迎的原因 .

    ListLike除了，Prelude中没有实现的一个原因是因为如果不调用某些语言扩展（多参数类型类和fundeps或相关类型），它就不可能这样做 . 有三种容器需要考虑：

    • 根本不关心其元素的容器（例如[]）

    • 仅针对特定元素（例如，字节串）实现的容器

    • 容器，它们对元素具有多态性但需要上下文（例如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 有点 *->* . 这赢得了't work for bytestrings because they don' t允许任意类型;他们有点 * . 它还赢得了包含上下文（Storable约束）的内容 .

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

    class ListableMPTC container elem | container -> elem where

    要么

    class ListableAT container where
  type Elem container :: *

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

    instance ListableMPTC [a] a where

    但你不再是Haskell98了 .

    这就是为什么即使是一个简单的Listable类型接口也是不平凡的;当你考虑不同的集合语义（例如队列）时，它会变得有点困难 . 另一个非常大的挑战是可变数据与不可变数据 . 到目前为止，我所看到的每个尝试（除了一个）都通过创建一个可变接口和一个不可变接口来解决这个问题 . 我所知道的一个界面确实统一了这两个界面是令人费解的，引用了一堆扩展，并且性能相当差 .

    附录：bytestrings

    完全猜测我，但我认为我们坚持使用字节串作为进化的产物 . 也就是说，它们是低性能I / O操作的第一个解决方案，使用 Ptr Word8 来与IO系统调用进行接口是有意义的 . 对指针的操作需要可存储，并且很可能必要的扩展（如上所述）使多态性工作不能克服它们的动力 . 具有多态性的类似容器当然是可能的，storablevector包实现了这一点，但它并不是那么受欢迎 .

    字节串可以是多态的，对元素没有任何限制吗？我认为最接近的Haskell就是Array类型 . 这不如低级IO的字节串好，因为数据需要从指针解包到数组的内部格式 . 此外，数据被加框，这增加了大量的空间开销 . 如果你想要无箱的存储（更少的空间）和与C的高效接口，那么指针就是你的选择 . 一旦你有了Ptr，你需要Storable，然后你需要在类型类中包含元素类型，这样你就需要扩展了 .

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

    回复于
  • 0

    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
    回复于
  • -1

    这类课程的主要问题是，即使它存在，它也只会提供肤浅的相似性 .

    使用不同结构构建的相同算法的渐近性会有很大差异 .

    在严格的字节串的情况下，使用cons构建它们是 terrible ，因为每次添加另一个Char时都会复制整个字符串 . 列表上的此O（1）操作将其转换为Bytestring上的O（n）操作 .

    这会导致O（n ^ 2）行为，当您实现可能会想到的第一个算法，map，而构建列表或具有cons的Data.Sequence.Seq是线性时间并且它可以在O（n）中实现对于字节串或向量以及一点思考 .

    事实证明，鉴于这一点，这种类的效用比实际更为肤浅 .

    我并不是说找不到好的设计，但是这样的设计难以使用并且要优化，并且设计的可用版本可能不会成为Haskell 98 .

    我已经在我的密钥包中设计了这个设计空间的一部分，它提供了许多用于索引到容器等的功能，但是我故意避免提供类似列表的API a . ）因为它之前已经完成了由于上面的渐近关注，很少有成功和b . ）

    tl;dr 当底层操作的渐近性发生变化时，您通常希望以非常不同的方式实现算法 .

    回复于
  • -1

    提供：函数来统一Data.ByteString，Data.List，Data.ByteString.Lazy等？

    已经尝试提出一个好的a）序列接口，和b）容器接口，然而，统一不同种类的数据类型，具有不同的类型约束，通常使得结果非标准化，很难想象把它们放在基础库中 . 类似地，对于数组，尽管Vector包现在具有相当通用的接口（基于关联的数据类型） .

    有几个项目可以通过单一界面统一这些不同的半相关数据类型，所以我希望我们很快就能看到结果 . 同样适用于容器类型 . 结果不会是微不足道的 .

    回复于

相关问题