quotientBy

q.hs

{-# OPTIONS_GHC -Wall #-}
import Data.List     (groupBy, sortBy)

-- | Construct the set of equivalence classes for a given list of items, given
-- an equivalence relation to partition the input set by. The partition of all
-- equivalence classes among the items in a set \(X\) is also known as the
-- __quotient set__ or __quotient space__ of \(X\), defined by an equivalence
-- relation \(R\), and written \(X/R\).
--
-- Technically the quotient /could/ be defined in terms of @'Eq'@, but here we
-- use @'Ordering'@, as it implies a much more efficient @'sort'@-based
-- implementation method for partitioning, and the underlying equivalence
-- relation can be derived from the ordering relation.
quotientBy
  :: (a -> a -> Ordering)
  -- ^ The equivalence relation \(R\).
  -> [a]
  -- ^ The input set \(X\), represented as a simple list.
  -> [[a]]
  -- ^ The resulting quotient set \(X/R\), defined as a list of lists, where
  -- every item in the resulting list is another set of items grouped by \(R\).
quotientBy k
  = groupBy (fmap (== EQ) . k)
  . sortBy k

-- | Construct the set of equivalence classes for a given list of items, using
-- @'(==)'@ as the equivalence relation.
--
-- This is equivalent to @'quotient' = 'quotientBy' 'compare'@.
quotient :: Ord a => [a] -> [[a]]
quotient = quotientBy compare