Test if all elements of a Foldable are the same

Question

I built a function that verifies that all elements of a foldable structure are equal.

Compared to a similar function on the lists, it seems to me that the more general function is disproportionately complex, but I have not been able to simplify it.

Do you have any suggestions?

import Data.Monoid
import Data.Sequence as SQ
import Data.Matrix as MT

allElementsEqualL :: Eq a => [a] -> Bool
allElementsEqualL [] = True
allElementsEqualL (x:ns) = all (== x) ns
-- allElementsEqualL [1,1,1] -> True

allElementsEqualF :: (Foldable t, Eq a) => t a -> Bool
allElementsEqualF xs = case (getFirst . foldMap (First . Just) $ xs) of
                        Nothing -> True
                        Just x  -> all (== x) xs

-- allElementsEqualF [1,1,1] -> True

-- allElementsEqualF $ SQ.fromList [1,1,1] -> True

-- allElementsEqualF $ MT.fromLists [[1,1],[1,1]] -> True

Answer 1

I don't know about less complicated, but I think this is the "cleanest" way to do it. By "clean," I mean it's one traversal over the structure using a single, special Monoid.

data Same a = Vacuous | Fail | Same a
instance Eq a => Semigroup (Same a) where
    Vacuous    <> x       = x
    Fail       <> _       = Fail
    s@(Same l) <> Same r  = if l == r then s else Fail
    x          <> Vacuous = x
    _          <> Fail    = Fail
instance Eq a => Monoid (Same a) where
    mempty = Vacuous

allEq :: (Foldable f, Eq a) => f a -> Bool
allEq xs = case foldMap Same xs of
                Fail -> False
                _    -> True

Answer 2

The convenient thing about your first function that doesn't exist in your second is that we have a convenient way of getting the "head" of a list. Fortunately, we can do the same for a Foldable. Let's write a head' that works on any Foldable (and for the sake of type safety we'll have our head' return a Maybe)

head' :: (Foldable t, Eq a) => t a -> Maybe a
head' = foldr (\a _ -> Just a) Nothing

Now we can write basically the same code as the list case for the general one.

allElementsEqualF :: (Foldable t, Eq a) => t a -> Bool
allElementsEqualF f = case head' f of
                        Nothing -> True
                        Just a -> all (== a) f

Syntactically, it looks different, but it's the exact same thing you did in your list case: check if the structure is empty and, if it's not, then see if every element is equal to the first.

Note that, technically, this is not quite equivalent to the code you posted, as it compares the first element against itself. So if your == operator is for some reason not reflexive, you'll get different results (try running my code and yours on the list [read "NaN" :: Double])

Answer 3

Silvio's answer is syntactically small and easy to understand; however, it may do extra work associated with doing two folds if the Foldable instance can't compute head' cheaply. In this answer I will discuss how to perform the calculation in just one pass whether the underlying Foldable can compute head' cheaply or not.

The basic idea is this: instead of tracking just "are all the elements equal so far", we'll also track what they're all equal to. So:

data AreTheyEqual a
    = Empty
    | Equal a
    | Inequal
    deriving Eq

This is a Monoid, with Empty as the unit and Inequal as an absorbing element.

instance Eq a => Semigroup (AreTheyEqual a) where
    Empty <> x = x
    x <> Empty = x
    Equal a <> Equal b | a == b = Equal a
    _ <> _ = Inequal

instance Eq a => Monoid (AreTheyEqual a) where
    mempty = Empty

Now we can use foldMap to summarize an entire Foldable, like so:

allElementsEqual :: (Eq a, Foldable f) => f a -> Bool
allElementsEqual = (Inequal /=) . foldMap Equal

Answer 4

A rather trivial option, and I would generally prefer one of the other answers, is reusing allElementsEqualL:

allElementsEqualF = allElementsEqualL . toList

or after inlining

allElementsEqualF xs = case toList xs of
                         [] -> True
                         x:xs' -> all (== x) xs'

It's laziness which makes it reasonable. The all call doesn't demand the entire xs', but only until it finds the first one different from x. So toList will also not demand the entire xs. And at the same time, already examined elements don't need to be kept in memory.

You could write a Foldable instance for which toList is less lazy than necessary, but except for those cases I think it should do exactly as much work as Daniel Wagner's and HTNW's answer (with slight overhead not depending on input size).

I thought also a mixed solution:

allElementsEqualF2 xs | F.null xs = True 
                      | otherwise = all (== x) xs 
    where x = head $ F.toList xs 

so if goList is lazy, the test is carried out upon the original type (with all).

This does slightly more work in the non-empty case than Silvio's answer, because F.null duplicates exactly as much of F.toList's work as head' does. So Silvio's code has to get to the first element 2 times (one for head' and another inside all), and yours does it 3 times (null, head $ toList xs and all again).