list - 有效地检查(大)列表的所有元素是否相同

Question

问题

假设我们有一个列表 xs (可能是一个非常大的)，我们要检查它的所有元素是否相同。

我想出了各种想法:

解决方案 0

检查 tail xs 中的所有元素等于 head xs :

allTheSame :: (Eq a) => [a] -> Bool
allTheSame xs = and $ map (== head xs) (tail xs)

解决方案 1

检查 length xs等于通过从 xs 中获取元素获得的列表的长度而它们等于 head xs

allTheSame' :: (Eq a) => [a] -> Bool
allTheSame' xs = (length xs) == (length $ takeWhile (== head xs) xs)

解决方案 2

递归解:allTheSame返回 True如果 xs 的前两个元素相等且 allTheSame返回 True剩下的xs

allTheSame'' :: (Eq a) => [a] -> Bool
allTheSame'' xs
  | n == 0 = False
  | n == 1 = True
  | n == 2 = xs !! 0 == xs !! 1
  | otherwise = (xs !! 0 == xs !! 1) && (allTheSame'' $ snd $ splitAt 2 xs)
    where  n = length xs

解决方案 3

分而治之:

allTheSame''' :: (Eq a) => [a] -> Bool
allTheSame''' xs
  | n == 0 = False
  | n == 1 = True
  | n == 2 = xs !! 0 == xs !! 1
  | n == 3 = xs !! 0 == xs !! 1 && xs !! 1 == xs !! 2
  | otherwise = allTheSame''' (fst split) && allTheSame''' (snd split)
    where n = length xs
          split = splitAt (n `div` 2) xs

解决方案 4

我只是在写这个问题时想到了这个:

allTheSame'''' :: (Eq a) => [a] -> Bool
allTheSame'''' xs = all (== head xs) (tail xs)

问题

我认为解决方案 0 的效率不是很高，至少在内存方面，因为 map将在应用 and 之前构建另一个列表到它的元素。我对吗？

解决方案 1 仍然不是很有效，至少在内存方面，因为 takeWhile将再次建立一个额外的列表。我对吗？

解决方案 2 是尾递归的(对吗？)，它应该非常有效，因为它会返回 False尽快(xs !! 0 == xs !! 1)是假的。我对吗？

解决方案 3 应该是最好的，因为它的复杂度应该是 O(log n)

解决方案 4 在我看来很像 Haskellish(是吗？)，但它可能与解决方案 0 相同，因为 all p = and . map p (来自 Prelude.hs)。我对吗？

有没有其他更好的写法allTheSame ?现在，我希望有人会回答这个问题，告诉我有一个内置函数可以做到这一点:我用 hoogle 搜索过，但没有找到。无论如何，由于我正在学习 Haskell，我相信这对我来说是一个很好的练习 :)

欢迎任何其他评论。谢谢!

Answer 1

gatoatigrado 的回答为衡量各种解决方案的性能提供了一些很好的建议。这是一个更具象征意义的答案。

我认为解决方案 0(或完全等价的解决方案 4)将是最快的。记住 Haskell 是懒惰的，所以 map不必在 and 之前构建整个列表被申请;被应用。建立对此的直觉的一个好方法是玩无穷大。例如:

ghci> and $ map (< 1000) [1..]
False

这询问是否所有数字都小于 1,000。如果 map在 and 之前构建了整个列表被应用了，那么这个问题永远无法回答。即使您给列表一个非常大的右端点，该表达式仍然会快速回答(也就是说，Haskell 不会根据列表是否为无限做任何“魔术”)。

要开始我的示例，让我们使用以下定义:

and [] = True
and (x:xs) = x && and xs

map f [] = []
map f (x:xs) = f x : map f xs

True && x = x
False && x = False

这是 allTheSame [7,7,7,7,8,7,7,7] 的评估顺序.会有额外的分享，写起来太痛苦了。我还将评估 head为了简洁起见，表达式比它更早(无论如何它都会被评估，所以它几乎没有什么不同)。

allTheSame [7,7,7,7,8,7,7,7]
allTheSame (7:7:7:7:8:7:7:7:[])
and $ map (== head (7:7:7:7:8:7:7:7:[])) (tail (7:7:7:7:8:7:7:7:[]))
and $ map (== 7)  (tail (7:7:7:7:8:7:7:7:[]))
and $ map (== 7)          (7:7:7:8:7:7:7:[])
and $ (== 7) 7 : map (== 7) (7:7:8:7:7:7:[])
(== 7) 7 && and (map (== 7) (7:7:8:7:7:7:[]))
True     && and (map (== 7) (7:7:8:7:7:7:[]))
            and (map (== 7) (7:7:8:7:7:7:[]))
(== 7) 7 && and (map (== 7)   (7:8:7:7:7:[]))
True     && and (map (== 7)   (7:8:7:7:7:[]))
            and (map (== 7)   (7:8:7:7:7:[]))
(== 7) 7 && and (map (== 7)     (8:7:7:7:[]))
True     && and (map (== 7)     (8:7:7:7:[]))
            and (map (== 7)     (8:7:7:7:[]))
(== 7) 8 && and (map (== 7)       (7:7:7:[]))
False    && and (map (== 7)       (7:7:7:[]))
False

看看我们如何甚至不必检查最后的 3 个 7？这是一种惰性求值，使列表更像一个循环。您的所有其他解决方案都使用昂贵的功能，例如 length (必须一直走到列表的末尾才能给出答案)，所以它们的效率会降低，而且它们也不会在无限列表上工作。在 Haskell 中，处理无限列表和高效通常是相辅相成的。