haskell - 没有 `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))

所以我问，“为什么 JValue 需要实现 Ord 类型类？”

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

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

但是，是否存在不需要 Ord 的类似 Set 的数据结构，即无序的数据结构？我可以使用的实现？

Answer 1

您几乎总是需要至少 Eq实现一个集合(或者至少能够编写一个 Eq 实例，无论是否存在)。只有Eq会给你一个非常低效的。您可以使用 Ord 改进这一点或与 Hashable .
在这里您可能想要做的一件事是使用特里树，它可以让您利用嵌套结构而不是不断地对抗它。
您可以先查看 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 方法根据数据的结构构造树。当您的类型是深度嵌套的(列表记录数组的列表...)时，散列或比较可能非常昂贵，因此特里可能会更好。
关于 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 实例)。