Test if all elements of a Foldable are the same(New?) Modal Operators for FoldableAn 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?

Realistic Necromancy?

How could Tony Stark make this in Endgame?

If a warlock with the Repelling Blast invocation casts Eldritch Blast and hits, must the targets always be pushed back?

Does the sign matter for proportionality?

What do the phrase "Reeyan's seacrest" and the word "fraggle" mean in a sketch?

Shrinkwrap tetris shapes without scaling or diagonal shapes

Examples of subgroups where it's nontrivial to show closure under multiplication?

Pulling the rope with one hand is as heavy as with two hands?

How to type a section sign (§) into the Minecraft client

Why do Computer Science majors learn Calculus?

Does this extra sentence in the description of the warlock's Eyes of the Rune Keeper eldritch invocation appear in any official reference?

What does KSP mean?

With a Canadian student visa, can I spend a night at Vancouver before continuing to Toronto?

Phrase for the opposite of "foolproof"

Pass By Reference VS Pass by Value

A Strange Latex Symbol

How to have a sharp product image?

Was there a Viking Exchange as well as a Columbian one?

How did Captain America manage to do this?

French for 'It must be my imagination'?

How to solve constants out of the internal energy equation?

What makes accurate emulation of old systems a difficult task?

How do I deal with a coworker that keeps asking to make small superficial changes to a report, and it is seriously triggering my anxiety?

How to get a plain text file version of a CP/M .BAS (M-BASIC) program?



Test if all elements of a Foldable are the same


(New?) Modal Operators for FoldableAn 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|improve this question

















  • 1





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

    – Alexey Romanov
    Apr 23 at 17:35












  • @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
    Apr 23 at 18:32











  • @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
    Apr 23 at 18:38











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

    – Alexey Romanov
    Apr 23 at 20:15

















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|improve this question

















  • 1





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

    – Alexey Romanov
    Apr 23 at 17:35












  • @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
    Apr 23 at 18:32











  • @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
    Apr 23 at 18:38











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

    – Alexey Romanov
    Apr 23 at 20:15













7












7








7


2






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|improve this 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






haskell






share|improve this question













share|improve this question











share|improve this question




share|improve this question










asked Apr 23 at 16:37









Alberto CapitaniAlberto Capitani

551823




551823







  • 1





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

    – Alexey Romanov
    Apr 23 at 17:35












  • @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
    Apr 23 at 18:32











  • @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
    Apr 23 at 18:38











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

    – Alexey Romanov
    Apr 23 at 20:15












  • 1





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

    – Alexey Romanov
    Apr 23 at 17:35












  • @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
    Apr 23 at 18:32











  • @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
    Apr 23 at 18:38











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

    – Alexey Romanov
    Apr 23 at 20:15







1




1





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

– Alexey Romanov
Apr 23 at 17:35






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

– Alexey Romanov
Apr 23 at 17:35














@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
Apr 23 at 18:32





@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
Apr 23 at 18:32













@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
Apr 23 at 18:38





@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
Apr 23 at 18:38













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

– Alexey Romanov
Apr 23 at 20:15





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

– Alexey Romanov
Apr 23 at 20:15












4 Answers
4






active

oldest

votes


















12














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|improve this answer

























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

    – Rein Henrichs
    Apr 23 at 17:07






  • 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
    Apr 23 at 17:08











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

    – HTNW
    Apr 23 at 17:11











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

    – Rein Henrichs
    Apr 23 at 17:12











  • @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
    Apr 23 at 17:13



















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|improve this answer






























    4














    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|improve this answer




















    • 1





      I think this is the same as my answer?

      – HTNW
      Apr 23 at 17:06











    • @HTNW Yep! Seems we overlapped in answering.

      – Daniel Wagner
      Apr 23 at 17:06











    • 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
      Apr 23 at 17:08











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

      – Daniel Wagner
      Apr 23 at 17:09


















    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|improve this answer

























      Your Answer






      StackExchange.ifUsing("editor", function ()
      StackExchange.using("externalEditor", function ()
      StackExchange.using("snippets", function ()
      StackExchange.snippets.init();
      );
      );
      , "code-snippets");

      StackExchange.ready(function()
      var channelOptions =
      tags: "".split(" "),
      id: "1"
      ;
      initTagRenderer("".split(" "), "".split(" "), channelOptions);

      StackExchange.using("externalEditor", function()
      // Have to fire editor after snippets, if snippets enabled
      if (StackExchange.settings.snippets.snippetsEnabled)
      StackExchange.using("snippets", function()
      createEditor();
      );

      else
      createEditor();

      );

      function createEditor()
      StackExchange.prepareEditor(
      heartbeatType: 'answer',
      autoActivateHeartbeat: false,
      convertImagesToLinks: true,
      noModals: true,
      showLowRepImageUploadWarning: true,
      reputationToPostImages: 10,
      bindNavPrevention: true,
      postfix: "",
      imageUploader:
      brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
      contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
      allowUrls: true
      ,
      onDemand: true,
      discardSelector: ".discard-answer"
      ,immediatelyShowMarkdownHelp:true
      );



      );













      draft saved

      draft discarded


















      StackExchange.ready(
      function ()
      StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f55815807%2ftest-if-all-elements-of-a-foldable-are-the-same%23new-answer', 'question_page');

      );

      Post as a guest















      Required, but never shown

























      4 Answers
      4






      active

      oldest

      votes








      4 Answers
      4






      active

      oldest

      votes









      active

      oldest

      votes






      active

      oldest

      votes









      12














      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|improve this answer

























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

        – Rein Henrichs
        Apr 23 at 17:07






      • 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
        Apr 23 at 17:08











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

        – HTNW
        Apr 23 at 17:11











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

        – Rein Henrichs
        Apr 23 at 17:12











      • @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
        Apr 23 at 17:13
















      12














      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|improve this answer

























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

        – Rein Henrichs
        Apr 23 at 17:07






      • 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
        Apr 23 at 17:08











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

        – HTNW
        Apr 23 at 17:11











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

        – Rein Henrichs
        Apr 23 at 17:12











      • @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
        Apr 23 at 17:13














      12












      12








      12







      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|improve this answer















      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|improve this answer














      share|improve this answer



      share|improve this answer








      edited Apr 23 at 22:47









      Joseph Sible

      7,54031337




      7,54031337










      answered Apr 23 at 17:03









      HTNWHTNW

      10.7k1933




      10.7k1933












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

        – Rein Henrichs
        Apr 23 at 17:07






      • 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
        Apr 23 at 17:08











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

        – HTNW
        Apr 23 at 17:11











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

        – Rein Henrichs
        Apr 23 at 17:12











      • @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
        Apr 23 at 17:13


















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

        – Rein Henrichs
        Apr 23 at 17:07






      • 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
        Apr 23 at 17:08











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

        – HTNW
        Apr 23 at 17:11











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

        – Rein Henrichs
        Apr 23 at 17:12











      • @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
        Apr 23 at 17:13

















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

      – Rein Henrichs
      Apr 23 at 17:07





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

      – Rein Henrichs
      Apr 23 at 17:07




      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
      Apr 23 at 17:08





      @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
      Apr 23 at 17:08













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

      – HTNW
      Apr 23 at 17:11





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

      – HTNW
      Apr 23 at 17:11













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

      – Rein Henrichs
      Apr 23 at 17:12





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

      – Rein Henrichs
      Apr 23 at 17:12













      @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
      Apr 23 at 17:13






      @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
      Apr 23 at 17:13














      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|improve this answer



























        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|improve this answer

























          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|improve this answer













          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|improve this answer












          share|improve this answer



          share|improve this answer










          answered Apr 23 at 16:56









          Silvio MayoloSilvio Mayolo

          14.9k22654




          14.9k22654





















              4














              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|improve this answer




















              • 1





                I think this is the same as my answer?

                – HTNW
                Apr 23 at 17:06











              • @HTNW Yep! Seems we overlapped in answering.

                – Daniel Wagner
                Apr 23 at 17:06











              • 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
                Apr 23 at 17:08











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

                – Daniel Wagner
                Apr 23 at 17:09















              4














              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|improve this answer




















              • 1





                I think this is the same as my answer?

                – HTNW
                Apr 23 at 17:06











              • @HTNW Yep! Seems we overlapped in answering.

                – Daniel Wagner
                Apr 23 at 17:06











              • 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
                Apr 23 at 17:08











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

                – Daniel Wagner
                Apr 23 at 17:09













              4












              4








              4







              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|improve this answer















              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|improve this answer














              share|improve this answer



              share|improve this answer








              edited Apr 23 at 17:10

























              answered Apr 23 at 17:05









              Daniel WagnerDaniel Wagner

              105k7163289




              105k7163289







              • 1





                I think this is the same as my answer?

                – HTNW
                Apr 23 at 17:06











              • @HTNW Yep! Seems we overlapped in answering.

                – Daniel Wagner
                Apr 23 at 17:06











              • 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
                Apr 23 at 17:08











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

                – Daniel Wagner
                Apr 23 at 17:09












              • 1





                I think this is the same as my answer?

                – HTNW
                Apr 23 at 17:06











              • @HTNW Yep! Seems we overlapped in answering.

                – Daniel Wagner
                Apr 23 at 17:06











              • 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
                Apr 23 at 17:08











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

                – Daniel Wagner
                Apr 23 at 17:09







              1




              1





              I think this is the same as my answer?

              – HTNW
              Apr 23 at 17:06





              I think this is the same as my answer?

              – HTNW
              Apr 23 at 17:06













              @HTNW Yep! Seems we overlapped in answering.

              – Daniel Wagner
              Apr 23 at 17:06





              @HTNW Yep! Seems we overlapped in answering.

              – Daniel Wagner
              Apr 23 at 17:06













              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
              Apr 23 at 17:08





              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
              Apr 23 at 17:08













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

              – Daniel Wagner
              Apr 23 at 17:09





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

              – Daniel Wagner
              Apr 23 at 17:09











              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|improve this answer





























                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|improve this answer



























                  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|improve this answer















                  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|improve this answer














                  share|improve this answer



                  share|improve this answer








                  edited Apr 23 at 21:31

























                  answered Apr 23 at 20:14









                  Alexey RomanovAlexey Romanov

                  112k26217360




                  112k26217360



























                      draft saved

                      draft discarded
















































                      Thanks for contributing an answer to Stack Overflow!


                      • Please be sure to answer the question. Provide details and share your research!

                      But avoid


                      • Asking for help, clarification, or responding to other answers.

                      • Making statements based on opinion; back them up with references or personal experience.

                      To learn more, see our tips on writing great answers.




                      draft saved


                      draft discarded














                      StackExchange.ready(
                      function ()
                      StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f55815807%2ftest-if-all-elements-of-a-foldable-are-the-same%23new-answer', 'question_page');

                      );

                      Post as a guest















                      Required, but never shown





















































                      Required, but never shown














                      Required, but never shown












                      Required, but never shown







                      Required, but never shown

































                      Required, but never shown














                      Required, but never shown












                      Required, but never shown







                      Required, but never shown







                      Popular posts from this blog

                      Sum ergo cogito? 1 nng

                      三茅街道4182Guuntc Dn precexpngmageondP