Sto lavorando su un linguaggio Haskell-meets-SQL per le manipolazioni del database e su una libreria di classi di tipi comuni per utilizzarla, cribbing da Hackage ovunque abbia senso..Portabile per contenitori non ordinati
Poiché un obiettivo significativo di un ottimizzatore di query del database è di eliminare l'ordinamento non necessario, è importante conservare una rappresentazione statica di dove l'ordinamento è effettivamente necessario. Il che ci porta a definire un typeclass per le pieghe.
Haskell di Data.Foldable
ha: (elidendo definizioni predefinite che non sono rilevanti per il punto che sto facendo)
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
Mi sembra che questa classe ignora una distinzione che è, per scopi pratici, non così importante per la maggior parte delle applicazioni Haskell ma molto più interessante per le impostazioni del database. A proposito: tutte le istanze Data.Foldable
vengono fornite con un ordine.
Qual è il nome per la generalizzazione di questo concetto che si applica a tipi di contenitori che non impongono un ordinamento sui loro elementi?
Per Haskell Data.Set
s funziona correttamente, poiché esiste un contesto Ord
richiesto dall'implementazione. Tuttavia, il requisito di ordinazione è un artefatto di implementazione e, per molti tipi utili, l'ordinamento utilizzato potrebbe non avere alcun significato a livello di dominio.
Per gli insiemi in genere la definizione fold :: Monoid m => t m -> m
a parte è per la maggior ragione (quindi è foldMap
). Dico soprattutto perché il suo tipo include la legge di associatività (attraverso la definizione di Monoid
) ma non la necessaria commutatività. Le altre varianti non esistono nemmeno.
Non voglio introdurre tipi in cui non sono necessari. Inoltre, non desidero introdurre il non determinismo in cui non può essere monitorato. Sono interessato a costruire un linguaggio e una biblioteca che non ha una funzione toList :: Set a -> [a]
in giro da nessuna parte, perché introduce una dicotomia tra:
- Permettere alle persone di osservare i dettagli di implementazione su come un insieme/relazione è memorizzato fisicamente
- perdere di non determinismo come effetto
Ovviamente entrambi sortBy :: (a -> a -> Ordering) -> Set a -> [a]
e shuffle :: Set a -> Data.Random.RVar [a]
sono utili, ineccepibile, e saranno inclusi. Infatti, sortBy
ha un tipo ancora più generico come sortBy :: (TheUnorderedFoldableClassIAmTryingToName f) => (a -> a -> Ordering) -> f a -> [a]
.
Come si chiama questa idea? Se sono lontano dalla base, dove ho lasciato il percorso di base?