title: Data.Foldable for unordered containers
body: <p>I'm working on a Haskell-meets-SQL language for database manipulations, and on a common type class library to go with it, cribbing from Hackage wherever it makes sense.</p>
  
  <p>Because a significant objective of a database query optimizer is to eliminate unnecessary sorting, it's important to preserve a static representation of where sorting is in fact necessary. Which brings us to defining a typeclass for folds.</p>
  
  <p>Haskell's <code>Data.Foldable</code> has: (eliding default definitions which aren't relevant to the point I'm making)</p>
  
  <pre><code>class Foldable t where
    -- | Combine the elements of a structure using a monoid.
    fold :: Monoid m =&gt; t m -&gt; m
  
    -- | Map each element of the structure to a monoid,
    -- and combine the results.
    foldMap :: Monoid m =&gt; (a -&gt; m) -&gt; t a -&gt; m
  
    -- | Right-associative fold of a structure.
    foldr :: (a -&gt; b -&gt; b) -&gt; b -&gt; t a -&gt; b
  
    -- | Left-associative fold of a structure.
    foldl :: (a -&gt; b -&gt; a) -&gt; a -&gt; t b -&gt; a
  
    -- | A variant of 'foldr' that has no base case,
    -- and thus may only be applied to non-empty structures.
    foldr1 :: (a -&gt; a -&gt; a) -&gt; t a -&gt; a
  
    -- | A variant of 'foldl' that has no base case,
    -- and thus may only be applied to non-empty structures.
    foldl1 :: (a -&gt; a -&gt; a) -&gt; t a -&gt; a
  </code></pre>
  
  <p>It seems to me that this class ignores a distinction which is, for practical purposes, not so important to most Haskell applications but of much more interest in a database setting. To wit: all <code>Data.Foldable</code> instances come with an ordering.</p>
  
  <p><strong>What is the name for the generalization of this concept that applies at container types which don't impose an ordering on their elements?</strong></p>
  
  <p>For Haskell <code>Data.Set</code>s it works out fine, because there is an <code>Ord</code> context required by the implementation. The ordering requirement is an implementation artifact though, and for many useful types the ordering being used may not have any domain-level meaning.</p>
  
  <p>For sets more generally the <code>fold :: Monoid m =&gt; t m -&gt; m</code> definition on its own is mostly right (so is <code>foldMap</code>). I say mostly because its type includes the associativity law (through the definition of <code>Monoid</code>) but not the required commutativity law. The other variants don't even exist.</p>
  
  <p>I don't want to introduce sorts where they aren't needed. I also don't want to introduce <strong>non-determinism</strong> where it can't be tracked. I'm interested in building a language and library that doesn't have a <code>toList :: Set a -&gt; [a]</code> function lying around anywhere, because it introduces a dichotomy between:</p>
  
  <ol>
  <li>Allowing people to observe implementation details about how a set/relation is physically stored</li>
  <li>Losing track of non-determinism as an effect</li>
  </ol>
  
  <p>Obviously both <code>sortBy :: (a -&gt; a -&gt; Ordering) -&gt; Set a -&gt; [a]</code> and <code>shuffle :: Set a -&gt; Data.Random.RVar [a]</code> are useful, unobjectionable, and will be included. In fact, <code>sortBy</code> has an even more general type as <code>sortBy :: (TheUnorderedFoldableClassIAmTryingToName f) =&gt; (a -&gt; a -&gt; Ordering) -&gt; f a -&gt; [a]</code>.</p>
  
  <p><strong>What is this idea called? If I'm way off base, where did I leave the base path?</strong></p>