¿Por qué el Data.Set de Haskell no admite conjuntos infinitos?

Question

En el siguiente fragmento:

import qualified Data.Set as Set 

data Nat = Zero | Succ Nat deriving (Eq, Show, Ord) 

instance Enum Nat where 
    pred (Succ x)  = x 
    succ x   = Succ x 
    toEnum 0   = Zero 
    toEnum x   = Succ (toEnum (x-1)) 
    fromEnum Zero  = 0 
    fromEnum (Succ x) = 1 + (fromEnum x) 

nats :: [Nat] 
nats = [Zero ..] 

natSet :: Set.Set Nat 
natSet = Set.fromList nats 

¿Por qué:

• elem (toEnum 100) nats == True

pero

• Set.member (toEnum 100) natSet nunca termina?

Answer 1

Set.fromList no es flojo, por lo que no terminará si le pasa una lista infinita. Pero natSet no se construye hasta que se necesita, por lo que solo lo notará cuando ejecute Set.member en él.

Por ejemplo, incluso Set.null $ Set.fromList [0..] no finaliza.

Answer 2

No puede tener infinitos conjuntos. Esto no solo afecta a Set.member, siempre que haga algo que ocasione que natSet se evalúe incluso en un paso (incluso Set.null), entrará en un bucle infinito.

Answer 3

Las respuestas existentes son suficientes, pero quiero exponer un poco sobre el comportamiento de Set s.

Parece que está esperando un conjunto perezoso de todos Nat s; toma la lista infinita de todos Nat sy utiliza Set.toList en ella. Eso estaría bien; los matemáticos a menudo hablan en términos del "conjunto de todos los números naturales". El problema es que la implementación de Set no es tan complaciente con la pereza como lo son las listas.

La implementación de Set se basa en el tamaño de árboles equilibrados binarios (o árboles de equilibrio acotado)

The docs for Data.Set

Supongamos que desea construir perezosamente un árbol binario de una lista . Los elementos de la lista solo se insertarían en el árbol cuando fuera necesario un cruce más profundo del árbol. Entonces preguntas si 100 está en el árbol. Sería conveniente agregar los números del 1 al 99, uno por uno. Entonces finalmente agregaría 100 al árbol, y descubriría que 100 es de hecho un elemento en el árbol. Pero fíjate en lo que hicimos. ¡Acabamos de realizar un recorrido en orden de la lista perezosa! Así que la primera vez, nuestro imaginario LazyTree.contains tendría más o menos la misma complejidad que List.find (suponiendo un ammortized O (1) inserción, que es un supuesto mal para un simple árbol binario, lo que tendría O (log n) complejidad) Y sin equilibrar, nuestro árbol estaría muy desequilibrado (añadimos los números del 1 al 100 en orden, por lo que sería una gran lista vinculada al hijo correcto de cada rama). Pero con el balanceo de árboles durante la travesía, sería difícil saber por dónde comenzar el recorrido de nuevo; al menos ciertamente no sería inmediatamente intuitivo.

tl; dr: nadie (afaik) ha hecho un buen conjunto perezoso todavía. Por lo tanto, los Conjuntos infinitos se representan más fácilmente como listas infinitas, por ahora.

Answer 4

Vamos a ver lo que sucede cuando nos adaptamos GHC's Set code para dar cabida a los conjuntos infinitos:

module InfSet where 

data InfSet a = Bin a (InfSet a) (InfSet a) 

-- create an infinite set by unfolding a value 
ofUnfold :: (x -> (x, a, x)) -> x -> InfSet a 
ofUnfold f x = 
    let (lx,a,rx) = f x 
     l = ofUnfold f lx 
     r = ofUnfold f rx 
    in Bin a l r 

-- check for membership in the infinite set 
member :: Ord a => a -> InfSet a -> Bool 
member x (Bin y l r) = case compare x y of 
         LT -> member x l 
         GT -> member x r 
         EQ -> True  

-- construct an infinite set representing a range of numbers 
range :: Fractional a => (a, a) -> InfSet a 
range = ofUnfold $ \(lo,hi) -> 
      let mid = (hi+lo)/2 
      in ((lo, mid), mid, (mid, hi)) 

Nota cómo, en vez de construir el conjunto infinito de una lista infinita, Yo en cambio definir una función ofUnfold a desplegarse un solo valor en una lista infinita. Nos permite construir ambas ramas perezosamente en paralelo (no necesitamos terminar una rama antes de construir otra).

Vamos a darle un giro:

ghci> :l InfSet 
[1 of 1] Compiling InfSet   (InfSet.hs, interpreted) 
Ok, modules loaded: InfSet. 
ghci> let r = range (0,128) 
ghci> member 64 r 
True 
ghci> member 63 r 
True 
ghci> member 62 r 
True 
ghci> member (1/2) r 
True 
ghci> member (3/4) r 
True 

Bueno, que parece funcionar. ¿Qué pasa si probamos un valor fuera del conjunto?

ghci> member 129 r 
^CInterrupted. 

Eso solo se ejecutará y se ejecutará y nunca lo abandonará. No hay ramas de detención en el conjunto inifinite, , por lo que la búsqueda nunca se cierra. Podríamos comprobar el rango original de alguna manera, pero eso no es práctico para los conjuntos infinitos de elementos discretos:

ghci> let ex = ofUnfold (\f -> (f . (LT:), f [EQ], f . (GT:))) id 
ghci> :t ex 
ex :: InfSet [Ordering] 
ghci> member [EQ] ex 
True 
ghci> member [LT,EQ] ex 
True 
ghci> member [EQ,LT] ex 
^CInterrupted. 

conjuntos infinitos Así son posibles pero no estoy seguro de que son útiles .

Answer 5

Me sentí de la misma manera, así que agregué un conjunto que funciona con listas infinitas. Sin embargo, deben ordenarse, por lo que mi algoritmo sabe cuándo dejar de buscar más.

Prelude> import Data.Set.Lazy 
Prelude Data.Set.Lazy> natset = fromList [1..] 
Prelude Data.Set.Lazy> 100 `member` natset 
True 
Prelude Data.Set.Lazy> (-10) `member` natset 
False 

Its on hackage. http://hackage.haskell.org/package/lazyset-0.1.0.0/docs/Data-Set-Lazy.html