efficiently checking that all the elements of a (big) list are the same

Problem

Let us suppose that we have a list xs (possibly a very big one), and we want to check that all its elements are the same.

I came up with various ideas:

Solution 0

checking that all elements in tail xs are equal to head xs:

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

Solution 1

checking that length xs is equal to the length of the list obtained by taking elements from xs while they're equal to head xs

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

Solution 2

recursive solution: allTheSame returns True if the first two elements of xs are equal and allTheSame returns True on the rest of 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

Solution 3

divide and conquer:

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

Solution 4

I just thought about this while writing this question:

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

Questions

1. I think Solution 0 is not very efficient, at least in terms of memory, because ma