2012-04-21 25 views
6

Estaba escribiendo un código y pensé que sería capaz de crear un mapa infinito a partir de una lista infinita de tuplas. Algo similar a lo siguiente: Map.fromList [(i,i+1)|i<-[1..]]Mapas infinitos en Haskell

Por supuesto, descubrí inmediatamente que Data.Map y Data.Set no admiten mapas y conjuntos infinitos, respectivamente. Observé una pregunta similar sobre la implementación codiciosa de Data.Set de fromList y, después de leer las respuestas here, está claro que las implementaciones perezosas y codiciosas son posibles para Set, solo que las codiciosas funcionan mejor. Realmente no entiendo, sin embargo, por qué una implementación perezosa de Map.fromList no funcionaría. ¿Algo que ver con la forma en que se almacenan las claves?

+8

¿Cómo sabría qué elemento de la lista sería el nodo raíz del árbol final sin conocer toda la lista? – sepp2k

Respuesta

13

Data.Map se implementa como un árbol equilibrado (aproximadamente binario, creo); ¡es difícil crear y equilibrar infinitamente árboles binarios sin ningún tipo de conocimiento previo sobre la entrada! Sin embargo, es posible que le guste algo como el paquete MemoTrie, que usa, en su lugar, intentos infinitos (de bits).

> let x = trie (\x -> x+1) 
> untrie x 72 
73 
> untrie x 37 
38