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

Question

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 map will construct another list before applying and to its elements. Am I right?

2. Solution 1 is still not very efficient, at least in terms of memory, because takeWhile will again build an additional list. Am I right?

3. Solution 2 is tail recursive (right?), and it should be pretty efficient, because it will return False as soon as (xs !! 0 == xs !! 1) is False. Am I right?

4. Solution 3 should be the best one, because it complexity should be O(log n)

5. Solution 4 looks quite Haskellish to me (is it?), but it's probably the same as Solution 0, because all p = and . map p (from Prelude.hs). Am I right?

6. Are there other better ways of writing allTheSame? Now, I expect someone will answer this question telling me that there's a build-in function that does this: I've searched with hoogle and I haven't found it. Anyway, since I'm learning Haskell, I believe that this was a good exercise for me :)

Any other comment is welcome. Thank you!

Answer 1

gatoatigrado's answer gives some nice advice for measuring the performance of various solutions. Here is a more symbolic answer.

I think solution 0 (or, exactly equivalently, solution 4) will be the fastest. Remember that Haskell is lazy, so map will not have to construct the whole list before and is applied. A good way to build intuition about this is to play with infinity. So for example:

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

This asks whether all numbers are less than 1,000. If map constructed the entire list before and were applied, then this question could never be answered. The expression will still answer quickly even if you give the list a very large right endpoint (that is, Haskell is not doing any "magic" depending on whether a list is infinite).

To start my example, let's use these definitions:

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

Here is the evaluation order for allTheSame [7,7,7,7,8,7,7,7]. There will be extra sharing that is too much of a pain to write down. I will also evaluate the head expression earlier than it would be for conciseness (it would have been evaluated anyway, so it's hardly different).

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

See how we didn't even have to check the last 3 7's? This is lazy evaluation making a list work more like a loop. All your other solutions use expensive functions like length (which have to walk all the way to the end of the list to give an answer), so they will be less efficient and also they will not work on infinite lists. Working on infinite lists and being efficient often go together in Haskell.