эффективная проверка того, что все элементы (большого) списка совпадают

Проблема

Предположим, что у нас есть список 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 возвращает Истина в остальной части 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)

Вопросы

1. Я думаю, что Решение 0 не очень эффективно, по крайней мере, с точки зрения памяти, потому что map построит другой список перед применением и к его элементам. Я прав?

2. Решение 1 все еще не очень эффективно, по крайней мере, с точки зрения памяти, потому что takeWhile снова построит дополнительный список. Я прав?

3. Решение 2 хвостовое рекурсивное (верно?), И оно должно быть довольно эффективным, потому что оно вернет False , как только (xs !! 0 == xs! ! 1) неверно. Я прав?

4. Решение 3 должно быть лучшим, потому что его сложность должна быть O (log n)

5. Решение 4 мне кажется довольно хаскелльским (не так ли?), Но, вероятно, оно такое же, как Решение 0, потому что все p = и. карта p (из Prelude.hs). Я прав?

6. Есть ли другие способы лучше написать allTheSame ? Теперь я ожидаю, что кто-то ответит на этот вопрос, сказав, что есть встроенная функция, которая делает это: я искал с помощью hoogle, но не нашел. В любом случае, поскольку я изучаю Haskell, я считаю, что это было для меня хорошим упражнением :)

Любые другие комментарии приветствуются. Спасибо!