没有`Ord`的类集合数据结构？

Question

给定以下类型：

import Data.Set as Set

-- http://json.org/

type Key = String

data Json = JObject Key (Set JValue)
            | JArray JArr
            deriving Show

data JObj = JObj Key JValue
            deriving Show

data JArr = Arr [JValue] deriving Show

data Null = Null deriving Show

data JValue = Num Double
              | S String
              | B Bool
              | J JObj
              | Array JArr
              | N Null
               deriving Show

我用一个元素创建了一个 JObject Key (Set Value)：

ghci> JObject "foo" (Set.singleton (B True))
JObject "foo" (fromList [B True])

但是，当我尝试创建一个 2 元素集时，出现编译时错误：

ghci> JObject "foo" (Set.insert (Num 5.5) $ Set.singleton (B True))

<interactive>:159:16:
    No instance for (Ord JValue) arising from a use of ‘insert’
    In the expression: insert (Num 5.5)
    In the second argument of ‘JObject’, namely
      ‘(insert (Num 5.5) $ singleton (B True))’
    In the expression:
      JObject "foo" (insert (Num 5.5) $ singleton (B True))

所以我问，"Why is it necessary for JValue to implement the Ord typeclass?"

Data.Set 上的文档回答了这个问题。

The implementation of Set is based on size balanced binary trees (or trees of bounded balance)

但是，有没有我可以使用的不需要 Ord 实现的类似集合（即无序）的数据结构？

Answer 1

你几乎总是需要至少 Eq 来实现一个集合（或者至少能力来编写一个 Eq 实例，无论是一个都不存在）。只有 Eq 会让你的效率低得可怕。您可以使用 Ord 或 Hashable.

进行改进

你可能想在这里做的一件事是使用 trie，它可以让你利用嵌套结构而不是不断地对抗它。

你可以先看看generic-trie。这似乎没有为您的 Array 件提供任何东西，因此您可能需要添加一些东西。

为什么 `Eq` 不够好

实现集合的最简单方法是使用列表：

type Set a = [a]

member a [] = False
member (x:xs) | a == x = True
              | otherwise = member a xs

insert a xs | member a xs = xs
            | otherwise = a:xs

这不好（除非元素很少），因为您可能必须遍历整个列表以查看是否有成员。

为了改善问题，我们需要使用某种树：

data Set a = Node a (Set a) (Set a) | Tip

我们可以制作很多不同种类的树，但为了使用它们，我们必须能够在每个节点处决定采用哪些分支。如果我们只有Eq，就没有办法选出合适的。如果我们有Ord（或Hashable），那就给了我们一个选择的方法。

trie 方法根据数据的结构构建树。当您的类型嵌套很深时（列表记录的数组列表...），散列或比较都可能非常昂贵，因此 trie 可能会更好。

`Ord`

旁注

虽然我认为您不应该在这里使用 Ord 方法，但它通常是正确的方法。在某些情况下，您的特定类型可能没有自然排序，但是有一些有效的方式来排序它的元素。在这种情况下，您可以使用 newtype:

玩个把戏

newtype WrappedThing = Wrap Thing

instance Ord WrappedThing where
  ....

newtype ThingSet = ThingSet (Set WrappedThing)
insertThing thing (ThingSet s) = ThingSet (insert (Wrap thing) s)
memberThing thing (ThingSet s) = member (WrapThing) s
...

在某些情况下，另一种方法是定义一个“基本类型”，它是一个 Ord 实例，但只导出一个 newtype 包装器；您可以将基本类型用于所有内部函数，但导出类型是完全抽象的（而不是 Ord 实例）。

没有`Ord`的类集合数据结构？

Set-like Data Structure without `Ord`?

haskell

set

为什么 `Eq` 不够好

`Ord`

没有`Ord`的类集合数据结构？

Set-like Data Structure without `Ord`?

haskell

set

为什么 Eq 不够好

Ord

为什么 `Eq` 不够好

`Ord`