6
\$\begingroup\$

Over on Stack Overflow, someone asked a simple Haskell question: how to test whether there is exactly one distinct vowel in a given string. To clarify, there can be any number of non-vowel characters, and the vowel may be repeated any number of times (at least once!), but no other vowels may occur.

I proposed the below solution, and am feeling fairly proud of it: it seems clean, short, general, and readable. I have a hard time imagining an improvement to it, but I know there is still plenty of room for me to get better at Haskell, so there is probably something cool I'm missing. Would someone please look over this, and tell me what could be better, or confirm that it truly has reached Nirvana?

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")
\$\endgroup\$
4
\$\begingroup\$
exactlyOne pred l = case filter pred l of
  [] -> False
  (x:xs) -> all (==x) xs

or equivalently

exactlyOne pred = (== (1 :: Natural)) . genericLength . nub . filter pred

since nub is lazy and takes O(optimal) time for this problem: If its input list has exactly one distinct member, the list is traversed once; if it has at least two, the list is traversed up to the second member and then (== (1 :: Natural)) knows to shortcut to False.

(I also like the operator .: and keep using it everywhere:)

infixr 8 .:
(f .: g) x = f . g x
exactlyOne = (== (1 :: Natural)) . genericLength . nub .: filter
\$\endgroup\$
2
\$\begingroup\$

Your solution is pretty good in terms of efficiency and simplicity. The only criticism might be that it loses style points for using explicit recursion.

Here is another approach to consider, which doesn't use explicit recursion. It uses dropWhile to skip to the first vowel. The string can be disqualified for having no vowels (xs' is null) or for having a different vowel (any $ (/= head xs') <&&> pred).

The <||> and <&&> operators are stolen from the predicate-combinators package, and help to apply all the tests to xs' without mentioning xs' everywhere.

As with your solution, it efficiently short-circuits (demonstrated by the fact that exactlyOne even [2,4..] does terminate).

import Control.Applicative (liftA2)

exactlyOne :: Eq a => (a -> Bool) -> [a] -> Bool
exactlyOne pred xs = not $ (null <||> (any $ (/= head xs') <&&> pred)) xs'
  where
    xs' = dropWhile (not.pred) xs
    (<||>) = liftA2 (||)
    (<&&>) = liftA2 (&&)

isVowel :: Char -> Bool
isVowel = (`elem` "AEIOUaeiou")
\$\endgroup\$
0
\$\begingroup\$

There's a little-known function from Data.List called nub. It's particularly good for code golfing.

import Data.List
exactlyOneVowel :: String -> Bool
exactlyOneVowel = (== 1) . length . nub . filter (`elem` "aeiouyAEIOUY")

I believe this satisfies all the constraints of the problem, and is unfortunately O(#characters ^ 2).

\$\endgroup\$
  • \$\begingroup\$ The sort call accomplishes nothing but wasting CPU cycles, and nub is needlessly inefficient. I'm looking for a good implementation, or critiques to my posted solution, not an unrelated point-free solution. \$\endgroup\$ – amalloy Mar 25 '16 at 6:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.