Test if all elements of a Foldable are the same The Ask Question Wizard is Live! ...

Was there ever a LEGO store in Miami International Airport?

How to keep bees out of canned beverages?

What do you call an IPA symbol that lacks a name (e.g. ɲ)?

Is Bran literally the world's memory?

Does using the Inspiration rules for character defects encourage My Guy Syndrome?

When does Bran Stark remember Jamie pushing him?

Are there existing rules/lore for MTG planeswalkers?

Putting Ant-Man on house arrest

Will I be more secure with my own router behind my ISP's router?

How would it unbalance gameplay to rule that Weapon Master allows for picking a fighting style?

Eigenvalues of the Laplacian of the directed De Bruijn graph

How to translate "red flag" into Spanish?

Has a Nobel Peace laureate ever been accused of war crimes?

How was Lagrange appointed professor of mathematics so early?

Are these square matrices always diagonalisable?

Where to find documentation for `whois` command options?

SQL Server placement of master database files vs resource database files

What is ls Largest Number Formed by only moving two sticks in 508?

Determinant of a matrix with 2 equal rows

Is it OK if I do not take the receipt in Germany?

Why did Europeans not widely domesticate foxes?

Coin Game with infinite paradox

What's parked in Mil Moscow helicopter plant?

Bright yellow or light yellow?



Test if all elements of a Foldable are the same



The Ask Question Wizard is Live!
Data science time! April 2019 and salary with experienceAn example of a Foldable which is not a Functor (or not Traversable)?Fragile and verbose code using xml-conduitError in function in do notationList processing in HaskellHaskell - Comparing different items with one another within a listComparing a List of tuples in haskellHow to define a parameterized similarity class (an ==-like operator with 3rd param) in Haskell?Foldable, Monoid and MonadExplanation of foldr implementation in FoldableDoes concat return a Foldable?





.everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty,.everyoneloves__bot-mid-leaderboard:empty{ height:90px;width:728px;box-sizing:border-box;
}







7















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








share


















  • 1





    Of course, you can always do allElementsEqualF = allElementsEqualL . toList.

    – Alexey Romanov
    6 hours ago













  • @AlexeyRomanov I recently thought of this solution, but I thought it could be very expensive from the point of view of conversion between types. If instead everything happened in a "lazy" way, maybe it would be the most convenient and fastest solution. Is it correct?

    – Alberto Capitani
    5 hours ago











  • @AlexeyRomanov 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).

    – Alberto Capitani
    5 hours ago











  • I decided it was worth a separate answer after all :)

    – Alexey Romanov
    4 hours ago


















7















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








share


















  • 1





    Of course, you can always do allElementsEqualF = allElementsEqualL . toList.

    – Alexey Romanov
    6 hours ago













  • @AlexeyRomanov I recently thought of this solution, but I thought it could be very expensive from the point of view of conversion between types. If instead everything happened in a "lazy" way, maybe it would be the most convenient and fastest solution. Is it correct?

    – Alberto Capitani
    5 hours ago











  • @AlexeyRomanov 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).

    – Alberto Capitani
    5 hours ago











  • I decided it was worth a separate answer after all :)

    – Alexey Romanov
    4 hours ago














7












7








7


1






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








share














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






haskell





share












share










share



share










asked 7 hours ago









Alberto CapitaniAlberto Capitani

539823




539823








  • 1





    Of course, you can always do allElementsEqualF = allElementsEqualL . toList.

    – Alexey Romanov
    6 hours ago













  • @AlexeyRomanov I recently thought of this solution, but I thought it could be very expensive from the point of view of conversion between types. If instead everything happened in a "lazy" way, maybe it would be the most convenient and fastest solution. Is it correct?

    – Alberto Capitani
    5 hours ago











  • @AlexeyRomanov 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).

    – Alberto Capitani
    5 hours ago











  • I decided it was worth a separate answer after all :)

    – Alexey Romanov
    4 hours ago














  • 1





    Of course, you can always do allElementsEqualF = allElementsEqualL . toList.

    – Alexey Romanov
    6 hours ago













  • @AlexeyRomanov I recently thought of this solution, but I thought it could be very expensive from the point of view of conversion between types. If instead everything happened in a "lazy" way, maybe it would be the most convenient and fastest solution. Is it correct?

    – Alberto Capitani
    5 hours ago











  • @AlexeyRomanov 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).

    – Alberto Capitani
    5 hours ago











  • I decided it was worth a separate answer after all :)

    – Alexey Romanov
    4 hours ago








1




1





Of course, you can always do allElementsEqualF = allElementsEqualL . toList.

– Alexey Romanov
6 hours ago







Of course, you can always do allElementsEqualF = allElementsEqualL . toList.

– Alexey Romanov
6 hours ago















@AlexeyRomanov I recently thought of this solution, but I thought it could be very expensive from the point of view of conversion between types. If instead everything happened in a "lazy" way, maybe it would be the most convenient and fastest solution. Is it correct?

– Alberto Capitani
5 hours ago





@AlexeyRomanov I recently thought of this solution, but I thought it could be very expensive from the point of view of conversion between types. If instead everything happened in a "lazy" way, maybe it would be the most convenient and fastest solution. Is it correct?

– Alberto Capitani
5 hours ago













@AlexeyRomanov 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).

– Alberto Capitani
5 hours ago





@AlexeyRomanov 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).

– Alberto Capitani
5 hours ago













I decided it was worth a separate answer after all :)

– Alexey Romanov
4 hours ago





I decided it was worth a separate answer after all :)

– Alexey Romanov
4 hours ago












4 Answers
4






active

oldest

votes


















11














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




share


























  • I think Same is isomorphic to Success a from the zero package.

    – Rein Henrichs
    7 hours ago






  • 1





    @ReinHenrichs I kind of doubt it. Same a has two extra constructors compared to a, whereas Success a has just one. Now it might be Success (Maybe a) or something... but at that point I would say having a custom type is more readable.

    – Daniel Wagner
    7 hours ago











  • It is, however, true that Zero (Same a) with zero = Fail.

    – HTNW
    7 hours ago











  • Same a has n + 2 elements. Success a is Maybe (Maybe a), which also has n + 2 elements. (Ignoring bottoms.)

    – Rein Henrichs
    7 hours ago











  • @ReinHenrichs Hm. When I follow your link, I see newtype Success a = Success { getSuccess :: Maybe a }, which has just one Maybe wrapper, not two.

    – Daniel Wagner
    7 hours ago





















5














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])





share































    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




    share





















    • 1





      I think this is the same as my answer?

      – HTNW
      7 hours ago











    • @HTNW Yep! Seems we overlapped in answering.

      – Daniel Wagner
      7 hours ago











    • It doesn't necessarily do two traversals. For structures where foldr can implement guarded recursion, it may only look at the top-most constructor the first time.

      – Rein Henrichs
      7 hours ago











    • @ReinHenrichs Good point. I'll amend my answer appropriately.

      – Daniel Wagner
      7 hours ago



















    2














    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).





    share

































      4 Answers
      4






      active

      oldest

      votes








      4 Answers
      4






      active

      oldest

      votes









      active

      oldest

      votes






      active

      oldest

      votes









      11














      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




      share


























      • I think Same is isomorphic to Success a from the zero package.

        – Rein Henrichs
        7 hours ago






      • 1





        @ReinHenrichs I kind of doubt it. Same a has two extra constructors compared to a, whereas Success a has just one. Now it might be Success (Maybe a) or something... but at that point I would say having a custom type is more readable.

        – Daniel Wagner
        7 hours ago











      • It is, however, true that Zero (Same a) with zero = Fail.

        – HTNW
        7 hours ago











      • Same a has n + 2 elements. Success a is Maybe (Maybe a), which also has n + 2 elements. (Ignoring bottoms.)

        – Rein Henrichs
        7 hours ago











      • @ReinHenrichs Hm. When I follow your link, I see newtype Success a = Success { getSuccess :: Maybe a }, which has just one Maybe wrapper, not two.

        – Daniel Wagner
        7 hours ago


















      11














      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




      share


























      • I think Same is isomorphic to Success a from the zero package.

        – Rein Henrichs
        7 hours ago






      • 1





        @ReinHenrichs I kind of doubt it. Same a has two extra constructors compared to a, whereas Success a has just one. Now it might be Success (Maybe a) or something... but at that point I would say having a custom type is more readable.

        – Daniel Wagner
        7 hours ago











      • It is, however, true that Zero (Same a) with zero = Fail.

        – HTNW
        7 hours ago











      • Same a has n + 2 elements. Success a is Maybe (Maybe a), which also has n + 2 elements. (Ignoring bottoms.)

        – Rein Henrichs
        7 hours ago











      • @ReinHenrichs Hm. When I follow your link, I see newtype Success a = Success { getSuccess :: Maybe a }, which has just one Maybe wrapper, not two.

        – Daniel Wagner
        7 hours ago
















      11












      11








      11







      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




      share















      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





      share













      share


      share








      edited 1 hour ago









      Joseph Sible

      7,52031337




      7,52031337










      answered 7 hours ago









      HTNWHTNW

      10.5k1833




      10.5k1833













      • I think Same is isomorphic to Success a from the zero package.

        – Rein Henrichs
        7 hours ago






      • 1





        @ReinHenrichs I kind of doubt it. Same a has two extra constructors compared to a, whereas Success a has just one. Now it might be Success (Maybe a) or something... but at that point I would say having a custom type is more readable.

        – Daniel Wagner
        7 hours ago











      • It is, however, true that Zero (Same a) with zero = Fail.

        – HTNW
        7 hours ago











      • Same a has n + 2 elements. Success a is Maybe (Maybe a), which also has n + 2 elements. (Ignoring bottoms.)

        – Rein Henrichs
        7 hours ago











      • @ReinHenrichs Hm. When I follow your link, I see newtype Success a = Success { getSuccess :: Maybe a }, which has just one Maybe wrapper, not two.

        – Daniel Wagner
        7 hours ago





















      • I think Same is isomorphic to Success a from the zero package.

        – Rein Henrichs
        7 hours ago






      • 1





        @ReinHenrichs I kind of doubt it. Same a has two extra constructors compared to a, whereas Success a has just one. Now it might be Success (Maybe a) or something... but at that point I would say having a custom type is more readable.

        – Daniel Wagner
        7 hours ago











      • It is, however, true that Zero (Same a) with zero = Fail.

        – HTNW
        7 hours ago











      • Same a has n + 2 elements. Success a is Maybe (Maybe a), which also has n + 2 elements. (Ignoring bottoms.)

        – Rein Henrichs
        7 hours ago











      • @ReinHenrichs Hm. When I follow your link, I see newtype Success a = Success { getSuccess :: Maybe a }, which has just one Maybe wrapper, not two.

        – Daniel Wagner
        7 hours ago



















      I think Same is isomorphic to Success a from the zero package.

      – Rein Henrichs
      7 hours ago





      I think Same is isomorphic to Success a from the zero package.

      – Rein Henrichs
      7 hours ago




      1




      1





      @ReinHenrichs I kind of doubt it. Same a has two extra constructors compared to a, whereas Success a has just one. Now it might be Success (Maybe a) or something... but at that point I would say having a custom type is more readable.

      – Daniel Wagner
      7 hours ago





      @ReinHenrichs I kind of doubt it. Same a has two extra constructors compared to a, whereas Success a has just one. Now it might be Success (Maybe a) or something... but at that point I would say having a custom type is more readable.

      – Daniel Wagner
      7 hours ago













      It is, however, true that Zero (Same a) with zero = Fail.

      – HTNW
      7 hours ago





      It is, however, true that Zero (Same a) with zero = Fail.

      – HTNW
      7 hours ago













      Same a has n + 2 elements. Success a is Maybe (Maybe a), which also has n + 2 elements. (Ignoring bottoms.)

      – Rein Henrichs
      7 hours ago





      Same a has n + 2 elements. Success a is Maybe (Maybe a), which also has n + 2 elements. (Ignoring bottoms.)

      – Rein Henrichs
      7 hours ago













      @ReinHenrichs Hm. When I follow your link, I see newtype Success a = Success { getSuccess :: Maybe a }, which has just one Maybe wrapper, not two.

      – Daniel Wagner
      7 hours ago







      @ReinHenrichs Hm. When I follow your link, I see newtype Success a = Success { getSuccess :: Maybe a }, which has just one Maybe wrapper, not two.

      – Daniel Wagner
      7 hours ago















      5














      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])





      share




























        5














        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])





        share


























          5












          5








          5







          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])





          share













          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])






          share











          share


          share










          answered 7 hours ago









          Silvio MayoloSilvio Mayolo

          14.9k22654




          14.9k22654























              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




              share





















              • 1





                I think this is the same as my answer?

                – HTNW
                7 hours ago











              • @HTNW Yep! Seems we overlapped in answering.

                – Daniel Wagner
                7 hours ago











              • It doesn't necessarily do two traversals. For structures where foldr can implement guarded recursion, it may only look at the top-most constructor the first time.

                – Rein Henrichs
                7 hours ago











              • @ReinHenrichs Good point. I'll amend my answer appropriately.

                – Daniel Wagner
                7 hours ago
















              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




              share





















              • 1





                I think this is the same as my answer?

                – HTNW
                7 hours ago











              • @HTNW Yep! Seems we overlapped in answering.

                – Daniel Wagner
                7 hours ago











              • It doesn't necessarily do two traversals. For structures where foldr can implement guarded recursion, it may only look at the top-most constructor the first time.

                – Rein Henrichs
                7 hours ago











              • @ReinHenrichs Good point. I'll amend my answer appropriately.

                – Daniel Wagner
                7 hours ago














              3












              3








              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




              share















              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





              share













              share


              share








              edited 7 hours ago

























              answered 7 hours ago









              Daniel WagnerDaniel Wagner

              104k7163288




              104k7163288








              • 1





                I think this is the same as my answer?

                – HTNW
                7 hours ago











              • @HTNW Yep! Seems we overlapped in answering.

                – Daniel Wagner
                7 hours ago











              • It doesn't necessarily do two traversals. For structures where foldr can implement guarded recursion, it may only look at the top-most constructor the first time.

                – Rein Henrichs
                7 hours ago











              • @ReinHenrichs Good point. I'll amend my answer appropriately.

                – Daniel Wagner
                7 hours ago














              • 1





                I think this is the same as my answer?

                – HTNW
                7 hours ago











              • @HTNW Yep! Seems we overlapped in answering.

                – Daniel Wagner
                7 hours ago











              • It doesn't necessarily do two traversals. For structures where foldr can implement guarded recursion, it may only look at the top-most constructor the first time.

                – Rein Henrichs
                7 hours ago











              • @ReinHenrichs Good point. I'll amend my answer appropriately.

                – Daniel Wagner
                7 hours ago








              1




              1





              I think this is the same as my answer?

              – HTNW
              7 hours ago





              I think this is the same as my answer?

              – HTNW
              7 hours ago













              @HTNW Yep! Seems we overlapped in answering.

              – Daniel Wagner
              7 hours ago





              @HTNW Yep! Seems we overlapped in answering.

              – Daniel Wagner
              7 hours ago













              It doesn't necessarily do two traversals. For structures where foldr can implement guarded recursion, it may only look at the top-most constructor the first time.

              – Rein Henrichs
              7 hours ago





              It doesn't necessarily do two traversals. For structures where foldr can implement guarded recursion, it may only look at the top-most constructor the first time.

              – Rein Henrichs
              7 hours ago













              @ReinHenrichs Good point. I'll amend my answer appropriately.

              – Daniel Wagner
              7 hours ago





              @ReinHenrichs Good point. I'll amend my answer appropriately.

              – Daniel Wagner
              7 hours ago











              2














              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).





              share






























                2














                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).





                share




























                  2












                  2








                  2







                  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).





                  share















                  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).






                  share













                  share


                  share








                  edited 3 hours ago

























                  answered 4 hours ago









                  Alexey RomanovAlexey Romanov

                  112k26217360




                  112k26217360















                      Popular posts from this blog

                      “%fieldName is a required field.”, in Magento2 REST API Call for GET Method Type The Next...

                      How to change City field to a dropdown in Checkout step Magento 2Magento 2 : How to change UI field(s)...

                      變成蝙蝠會怎樣? 參考資料 外部連結 导航菜单Thomas Nagel, "What is it like to be a...