没有`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上的文档回答了这个问题.

Set的实现基于大小平衡的二叉树(或有界平衡树)

但是,是否有一个类似Set的,即无序的数据结构,不需要Ord我可以使用的实现？

Answer 1

您几乎总是需要至少Eq实现一个集合(或者至少是编写实例的能力Eq,无论是否存在).有只 Eq会给你一个horrifyingly低效的.你可以用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方法基于数​​据结构构造树.当您的类型被深度嵌套(列表的记录数组列表......)时,散列或比较可能非常昂贵,因此特里可能会更好.

旁注 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实例).