Standard module List defines:
-- group splits its list argument into a list of lists of equal, adjacent
-- elements. e.g.,
-- group "Mississippi" == ["M","i","ss","i","ss","i","pp","i"]
group :: (Eq a) => [a] -> [[a]]
group = groupBy (==)
groupBy :: (a -> a -> Bool) -> [a] -> [[a]]
groupBy eq [] = []
groupBy eq (x:xs) = (x:ys) : groupBy eq zs
where (ys,zs) = span (eq x) xs
In my programs, I often use the following function to compute
equivalence classes:
eqClasses :: Eq a => [a] -> [[a]]
eqClasses = eqClassesBy (==)
eqClassesBy :: (a -> a -> Bool) -> [a] -> [[a]]
eqClassesBy eq [] = []
eqClassesBy eq (x : xs) =
(x : p) : (eqClassesBy eq p')
where
(p, p') = partition (eq x) xs
There is a single difference: The use of span vs. partition, i.e.
grouping and computing equivalence classes are very similiar. Indeed,
if a set is represented by a sorted list, grouping can be used to
compute its equivalence classes efficiently.
Michael Marte
