haskell - tipos - tag del trap

¿Por qué Data.Set requiere que los elementos sean una instancia de Ord?

Question

Esto no funciona

data Cutlery = Knife | Fork deriving (Show,Eq)
let x = [Knife,Fork]
let set1 = Set.fromList x

mientras se define

data Cutlery = Knife | Fork deriving (Show,Ord,Eq)

Resuelve el problema pero no tiene sentido. ¿Es Data.Set diferente a la definición matemática de un conjunto?

Answer 1

¿Es Data.Set diferente a la definición matemática de un conjunto?

Obviamente, los conjuntos matemáticos pueden ser infinitos, no podrás representar eso en general con una computadora, o incluso una máquina de Turing.

Pero la respuesta que está buscando es la siguiente: Data.Set es un tipo de datos basado en árboles binarios, y necesita un orden lineal total en los elementos para saber si colocar y luego encontrar algo en el subárbol izquierdo o derecho de un nodo. Entonces, si bien sería posible implementar un tipo de datos establecido sin una restricción Ord , esta implementación en particular, más eficiente, no lo haría.

Answer 2

Data.HashSet si desea un conjunto desordenado:

https://hackage.haskell.org/package/unordered-containers-0.1.4.6/docs/Data-HashSet.html

Answer 3

Es para la eficiencia. Data.Set se implementa como un árbol de búsqueda binario (también conocido como árboles binarios ordenados u ordenados ). El uso de esta estructura de datos significa que podemos escribir una función de búsqueda, member , que toma tiempo logarítmico , tiempo O (logn), en lugar de lo que sería tiempo lineal , O (n). Al ordenar los elementos, podemos realizar comparaciones exponencialmente menos al realizar búsquedas.

De Wikipedia :

Los árboles de búsqueda binarios mantienen sus claves ordenadas , de modo que la búsqueda y otras operaciones puedan usar el principio de búsqueda binaria . ... cada búsqueda, inserción o eliminación lleva un tiempo proporcional al logaritmo del número de elementos almacenados en el árbol.

Si los elementos no fueran una instancia de Ord , no habría una manera de ordenar los elementos del árbol binario de búsqueda: solo podríamos formar un árbol binario, no un árbol binario de búsqueda. Como resultado, no podríamos obtener tiempos de búsqueda rápidos.

Answer 4

Un conjunto de Data.Set captura la abstracción matemática de un conjunto, pero no es idéntico. La principal diferencia es que un conjunto de Data.Set requiere que se Data.Set sus elementos, mientras que un conjunto matemático solo requiere que sus elementos sean comparables para la igualdad.

La razón para requerir Ord es la eficiencia. Sería perfectamente posible construir una abstracción de conjunto definiendo

data Set a = Set [a]

es decir, debajo del capó es solo una lista, y nos aseguramos de que nunca insertemos elementos duplicados. Las operaciones elem y de insert serían

elem a (Set as) = any (a ==) as

insert a (Set as) | a `elem` as = Set as
                  | otherwise   = Set (a:as)

Sin embargo, esto significa que tanto elem como el insert son operaciones O ( n ). Si queremos hacer algo mejor que esto, los enfoques estándar son

1. Almacena los elementos en un árbol binario equilibrado (que requiere una instancia de Ord )
2. Hash los elementos y almacenarlos en una matriz (que requiere una instancia de Hashable ).

TreeSet

La implementación elegida por los autores de Data.Set fue utilizar un árbol binario, que se puede ver yendo a la source . La implementación es más o menos

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

Ahora puedes escribir la función elem como

elem :: Ord a => a -> Set a -> Bool
elem = go
  where
    go _  Tip = False
    go x (Bin y l r) = case compare x y of
      LT -> go x l
      GT -> go x r
      EQ -> True

que es una operación O (log n ), en lugar de O ( n ). Las inserciones son más complicadas (ya que es necesario mantener el árbol equilibrado) pero similares.

HashSet

En un conjunto hash, no se comparan directamente los elementos cuando se insertan y eliminan. En lugar de ello, cada elemento se convierte en un entero y se almacena en una ubicación basada en ese entero.

En teoría, esto no requiere una instancia de Ord . En la práctica, necesita algún método para realizar un seguimiento de varios elementos que tienen el mismo valor, y el método elegido por los desarrolladores de Data.HashSet es almacenar múltiples elementos en un Data.Set regular, por lo que resulta que sí lo necesita. La instancia de Ord después de todo!

data HashSet a = HashSet (Data.IntMap.IntMap (Data.Set.Set a))

Podría haber sido escrito en su lugar como

data HashSet a = HashSet (Data.IntMap.IntMap [a])

en cambio, lo que elimina el requisito de Ord a costa de alguna ineficiencia si hay muchos elementos que tienen el mismo valor.