Estoy trabajando en un lenguaje Haskell-meets-SQL para manipulaciones de bases de datos, y en una biblioteca de clases de tipos común para ir con él, desde Hackage donde sea que tenga sentido.Data.Foldable para contenedores desordenados
Dado que un objetivo importante de un optimizador de consultas de base de datos es eliminar la ordenación innecesaria, es importante conservar una representación estática de dónde es realmente necesaria la ordenación. Lo que nos lleva a definir una clase de tipos para pliegues.
de Haskell Data.Foldable tiene: (elidiendo definiciones predeterminadas que no son relevantes para el punto que estoy haciendo)
class Foldable t where
-- | Combine the elements of a structure using a monoid.
fold :: Monoid m => t m -> m
-- | Map each element of the structure to a monoid,
-- and combine the results.
foldMap :: Monoid m => (a -> m) -> t a -> m
-- | Right-associative fold of a structure.
foldr :: (a -> b -> b) -> b -> t a -> b
-- | Left-associative fold of a structure.
foldl :: (a -> b -> a) -> a -> t b -> a
-- | A variant of 'foldr' that has no base case,
-- and thus may only be applied to non-empty structures.
foldr1 :: (a -> a -> a) -> t a -> a
-- | A variant of 'foldl' that has no base case,
-- and thus may only be applied to non-empty structures.
foldl1 :: (a -> a -> a) -> t a -> a
Me parece que esta clase hace caso omiso de una distinción que es, a efectos prácticos, no tan importante para la mayoría de las aplicaciones Haskell pero de mucho más interés en la configuración de una base de datos. A saber: todas las instancias Data.Foldable vienen con un pedido.
¿Cuál es el nombre para la generalización de este concepto que se aplica a los tipos de contenedores que no imponen un orden en sus elementos?
Para Haskell Data.Set s funciona bien, porque hay un contexto Ord requerido por la implementación. Sin embargo, el requisito de pedido es un artefacto de implementación, y para muchos tipos útiles, el orden que se utiliza puede no tener ningún significado de nivel de dominio.
Para los conjuntos de forma más general, la definición de fold :: Monoid m => t m -> m en sí misma es en su mayoría correcta (así es foldMap). Digo principalmente porque su tipo incluye la ley de asociatividad (a través de la definición de Monoid) pero no la ley de conmutatividad requerida. Las otras variantes ni siquiera existen.
No quiero introducir géneros donde no los necesiten. Tampoco quiero introducir no determinismo donde no se puede rastrear. Estoy interesado en la construcción de un lenguaje y una biblioteca que no tiene una función toList :: Set a -> [a] por ahí en cualquier lugar, ya que introduce una dicotomía entre:
- Permitir que la gente observe los detalles de implementación acerca de cómo se almacena un conjunto físicamente/relación
- perder de vista no determinismo como un efecto
Obviamente tanto sortBy :: (a -> a -> Ordering) -> Set a -> [a] y shuffle :: Set a -> Data.Random.RVar [a] son útiles, inobjetable, y se incluirán. De hecho, sortBy tiene un tipo aún más general como sortBy :: (TheUnorderedFoldableClassIAmTryingToName f) => (a -> a -> Ordering) -> f a -> [a].
¿Cómo se llama esta idea? Si estoy fuera de la base, ¿dónde dejé el camino de la base?