CODEWITHSUNDEEP
performancehaskelllazy-evaluation
Justin Harjanto
Justin Harjanto

Reputation: 23

Naive implementation of Haskell function is faster than 'smarter' solution?

So I'm a newbie to Haskell and I'm trying to figure out why my naive implementation is actually faster than what I thought was the smarter solution.

I'm trying to write a function that given a String will return a Bool that indicates whether or not the String uses one and exactly one vowel. The following is my naive implementation:

singleVowel :: Maybe String -> Bool
singleVowel Nothing = False
singleVowel (Just s) = singleVowel (Just s) = length (nub $ filter (`elem` "aeiouyAEIOUY") s) == 1

Notice that I filter out all of the elements that are not in the vowel set. I then make another pass using the nub function to remove the duplicates from the filtered list, and see if there is exactly 1 vowel in the list. It follows then in the worst case, this solution will use O(n) memory and time since it has to allocate memory for the filtered list.

Now for my other solution, I decided to use recursion and passed a character on each recursive call to keep track of the current vowel if there was one seen.

singleVowelFaster :: Maybe String -> Bool
singleVowelFaster Nothing = False
singleVowelFaster (Just s) = singleVowelHelper s Nothing

singleVowelHelper :: String -> Maybe Char -> Bool
singleVowelHelper [] Nothing = False
singleVowelHelper [] _ = True
singleVowelHelper (x:xs) Nothing = if x `elem` "aeiouyAEIOUY"
  then singleVowelHelper xs (Just x)
  else singleVowelHelper xs Nothing
singleVowelHelper (x:xs) (Just c) =
  (x `elem` "aeiouyAEIOUY" && c == x) && singleVowelHelper xs (Just c)

But for some odd reason the 'naive' implementation runs faster than the 'smarter' solution.

Could it be the fact that (xelem"aeiouyAEIOUY" && c == x) is not being evaluated since Haskell is lazy, so all of the thunks are evaluated once the base case is reached thus contributing to being slower than the 'naive' implementation?

If this is the case, then why is it the case then when I put (xelem"aeiouyAEIOUY" && c == x) into an if statement to force evaluation the performance of the function is similar?

Am I also right to say that the second function has O(1) space usage with O(n) time?

Upvotes: 0

Views: 205

Answers (1)

amalloy
amalloy

Reputation: 91962

The simplest fix is to reverse the order of your first && call, performing the cheap == check before the expensive elem check.

That will make your function run faster...but it will still be incorrect! You are basically asserting that, after the first vowel, all following characters are exactly the same vowel; what you intended to do instead is assert that all following vowels are the same vowel. I would write it like this:

(x == c || not (x `elem`vowels)) && singleVowelHelper xs (Just c)

Or, well, really I would write the whole function somewhat differently, but the above is the simplest change to make your implementation work. Here's the implementation I would write, starting with a more general predicate-based function, and then specializing to vowels:

exactlyOne :: Eq a => (a -> Bool) -> [a] -> Bool
exactlyOne pred [] = False
exactlyOne pred (x:xs)
  |    pred x = not . any pred . filter (/= x) $ xs
  | otherwise = exactlyOne pred xs

exactlyOneVowel :: String -> Bool
exactlyOneVowel = exactlyOne (`elem` "aeiouAEIOU")

Upvotes: 5

Related Questions