测试可折叠元素的所有元素是否相同

Question

我构建了一个函数来验证可折叠结构的所有元素是否相等。

与清单上的类似功能相比，在我看来，更通用的功能非常复杂，但是我无法对其进行简化。

你有什么建议吗？

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

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

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

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

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

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

Answer 1

我不知道复杂程度如何，但是我认为这是最“干净”的方法。“干净”是指使用一个特殊的遍历结构Monoid。

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

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

Answer 2

关于您的第一个功能的便利之处是您没有第二个功能，这是我们有一种便捷的方式来获取列表的“头”。幸运的是，我们可以对进行相同的操作Foldable。让我们编写一个head'适用于任何对象的Foldable（为了类型安全，我们将head'返回a Maybe）

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

现在，我们可以编写与一般情况下的列表例基本相同的代码。

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

从语法上看，它看起来有所不同，但这与您在列表情况下所做的完全相同：检查结构是否为空，如果不是，则检查每个元素是否等于第一个元素。

请注意，从技术上讲，这与您发布的代码并不完全等效，因为它会将第一个元素与其自身进行比较。因此，如果您的==操作员由于某种原因而不是自反的，则会得到不同的结果（尝试运行我的代码，然后在列表中运行您的代码[read "NaN" :: Double]）

Answer 3

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

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

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

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

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

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

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

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