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
I think Solution 0 is not very efficient, at least in terms of memory, because
map
will construct another list before applyingand
to its elements. Am I right?Solution 1 is still not very efficient, at least in terms of memory, because
takeWhile
will again build an additional list. Am I right?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?Solution 3 should be the best one, because it complexity should be O(log n)
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?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!
See Question&Answers more detail:os