title: efficiently checking that all the elements of a (big) list are the same
body: <h2>Problem</h2>
  
  <p>Let us suppose that we have a list <code>xs</code> (possibly a very big one), and we want to check that all its elements are the same.</p>
  
  <p>I came up with various ideas:</p>
  
  <h2>Solution 0</h2>
  
  <p>checking that all elements in <code>tail xs</code> are equal to <code>head xs</code>:</p>
  
  <pre><code>allTheSame :: (Eq a) =&gt; [a] -&gt; Bool
  allTheSame xs = and $ map (== head xs) (tail xs)
  </code></pre>
  
  <h2>Solution 1</h2>
  
  <p>checking that <code>length xs</code> is equal to the length of the list obtained by taking elements from <code>xs</code> while they're equal to <code>head xs</code></p>
  
  <pre><code>allTheSame' :: (Eq a) =&gt; [a] -&gt; Bool
  allTheSame' xs = (length xs) == (length $ takeWhile (== head xs) xs)
  </code></pre>
  
  <h2>Solution 2</h2>
  
  <p>recursive solution: <code>allTheSame</code> returns <code>True</code> if the first two elements of <code>xs</code> are equal and <code>allTheSame</code> returns <code>True</code> on the rest of <code>xs</code></p>
  
  <pre><code>allTheSame'' :: (Eq a) =&gt; [a] -&gt; Bool
  allTheSame'' xs
    | n == 0 = False
    | n == 1 = True
    | n == 2 = xs !! 0 == xs !! 1
    | otherwise = (xs !! 0 == xs !! 1) &amp;&amp; (allTheSame'' $ snd $ splitAt 2 xs)
      where  n = length xs
  </code></pre>
  
  <h2>Solution 3</h2>
  
  <p>divide and conquer:</p>
  
  <pre><code>allTheSame''' :: (Eq a) =&gt; [a] -&gt; Bool
  allTheSame''' xs
    | n == 0 = False
    | n == 1 = True
    | n == 2 = xs !! 0 == xs !! 1
    | n == 3 = xs !! 0 == xs !! 1 &amp;&amp; xs !! 1 == xs !! 2
    | otherwise = allTheSame''' (fst split) &amp;&amp; allTheSame''' (snd split)
      where n = length xs
            split = splitAt (n `div` 2) xs
  </code></pre>
  
  <h2>Solution 4</h2>
  
  <p>I just thought about this while writing this question:</p>
  
  <pre><code>allTheSame'''' :: (Eq a) =&gt; [a] -&gt; Bool
  allTheSame'''' xs = all (== head xs) (tail xs)
  </code></pre>
  
  <h2>Questions</h2>
  
  <ol>
  <li><p>I think Solution 0 is not very efficient, at least in terms of memory, because <code>map</code> will construct another list before applying <code>and</code> to its elements. Am I right?</p></li>
  <li><p>Solution 1 is still not very efficient, at least in terms of memory, because <code>takeWhile</code> will again build an additional list. Am I right?</p></li>
  <li><p>Solution 2 is tail recursive (right?), and it should be pretty efficient, because it will return <code>False</code> as soon as <code>(xs !! 0 == xs !! 1)</code> is False. Am I right?</p></li>
  <li><p>Solution 3 should be the best one, because it complexity should be O(log n)</p></li>
  <li><p>Solution 4 looks quite Haskellish to me (is it?), but it's probably the same as Solution 0, because <code>all p =  and . map p</code> (from Prelude.hs). Am I right?</p></li>
  <li><p>Are there other better ways of writing <code>allTheSame</code>? 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 :)</p></li>
  </ol>
  
  <p>Any other comment is welcome. Thank you!</p>