An established data structure without `Ord`?

Question

Given the following types:

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

I created JObject Key (Set Value)with one element:

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

But when I tried to create a set of 2 elements, I got a compile-time error:

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))

So, I asked: "Why do I need to JValueimplement Ordtypeclass?"

The docs on Data.Set answer this question.

The implementation of Set is based on size-balanced binary trees (or trees with limited balance)

But is there a non-standard data structure that does not require an implementation Ordthat I can use?

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

, , , node , . 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).