Set类的位置在哪里？

Question

在Haskell中Data.Set实现了一个具体的集合类型.普通[]列表还实现了一组(in Data.List)的所有操作.但似乎没有Set他们都实现的预定义类型类.你可以自己实现一个:

{-# LANGUAGE MultiParamTypeClasses, FlexibleInstances, FunctionalDependencies #-}

module Set where

import qualified Data.List as ConcreteList
import qualified Data.Set as ConcreteSet

class Set set a | set -> a where
  empty :: set
  singleton :: a -> set
  insert :: a -> set -> set
  delete :: a -> set -> set
  union :: set -> set -> set
  intersection :: set -> set -> set
  member :: a -> set -> Bool
  filter :: (a -> Bool) -> set -> set

instance (Ord a) => Set (ConcreteSet.Set a) a where
  empty = ConcreteSet.empty
  singleton = ConcreteSet.singleton
  insert = ConcreteSet.insert
  delete = ConcreteSet.delete
  union = ConcreteSet.union
  intersection = ConcreteSet.intersection
  member = ConcreteSet.member
  filter = ConcreteSet.filter

instance (Eq a) => Set [a] a where
  empty = []
  singleton e = [e]
  insert = (:)
  delete = ConcreteList.delete
  union = ConcreteList.union
  intersection = ConcreteList.intersect
  member = ConcreteList.elem
  filter = ConcreteList.filter

但似乎如果这是可行的话,这已经完成了.所以我的问题是:Set类型类或Haskell社区提出的替代解决方案在哪里？

我的问题与Haskell为什么缺少"明显的"类型类而非常相似,但通过更具体(侧重于示例实现的具体示例),我希望得到一些更具体的答案.

Answer 1

无论出于何种原因,Haskell倾向于不使用深层次的类型类来表示所有可能的容器类型.

通常,不同种类的容器具有用于不同操作的性能属性.通常,您知道哪些操作对您很重要,并且您选择最合适的容器并明确使用它.没有太多要求能够编写对每种可能类型的容器进行操作的真正通用代码.

请注意,已经存在一些用于处理容器的类型类 - 它们不是您可能期望的类型.例如:

• Functor允许您将函数应用于容器的每个元素 - 任何容器 - 并将结果收集到相同类型的新容器中.

• Applicative和/或Monad允许您将函数应用于每个元素并生成多个元素.(这可能不是很明显,但您可以使用它来执行"过滤"甚至"删除",尽管它可能效率不高.)

• Monoid提供你的empty和union方法(但命名mempty和mappend).

• Alternative,Foldable并且Traversable让你做进一步的有趣的魔法.

Answer 2

您可以尝试Data.Containers从mono-traversable

一般来说,Haskell代码往往倾向于泛化这样的数据类型而不是Java,这就是为什么这些抽象不在containers或者unordered-containers.

Answer 3

我会稍微注释一下这个类:

-- The functional dependency here ties in to the issues with 
-- restricted type class instances, for which there is no one
-- globally adopted solution.
class Set set a | set -> a where
  -- This is a `Monoid`- or `Alternative`-like constant
  empty :: set

  -- This is an `Applicative`-like operation
  singleton :: a -> set

  -- If you have `singleton` and `union` you have `insert`.
  -- Which means that `insert` might fall out of the 
  -- `Alternative` class.
  insert :: a -> set -> set

  -- This looks like a variant of `filter` below.
  delete :: a -> set -> set

  -- These two are `Semigroup` operations
  union :: set -> set -> set
  intersection :: set -> set -> set

  -- Can't think of anything for this one.
  member :: a -> set -> Bool

  -- This is very `Monad`-like operation.  You can write this
  -- in terms of a bind/`unionMap` operation + your `singleton`
  -- and `empty`.
  filter :: (a -> Bool) -> set -> set

所以基本上,社区更喜欢比这个Set类更可重用的许多小类.

这是另一个可能有用的观点.你似乎在心理上将类绑定到类型,作为类似的类型的心理分类,因为它们"代表集合".但是Haskell社区更经常将类与操作联系起来.您可以在上面的注释中看到这一点,我希望 - 您提出的大多数操作都会让我想起一些已经存在的类.黑色标记是这样的事实,大多数类不适Set用于具有元素类型约束的类型...