higher order function haskell

Question

I'm new to Haskell, I've to do a function that counts the number of vowels in a string using the higher order function foldr

I've tried to create this function

vowels [] = 0
vowels (x:xs)= if elem x "aeiou" then 1 + vowels xs else vowels xs

But it doesn't work and I'm not able to do it using foldr, any suggestion?

Answer 1

Well a foldr :: (a -> b -> b) -> b -> [a] -> b is a function where the first parameter is a function f :: a -> b -> b. You can here see the a parameter as the "head" of the list, the second parameter b as the result of the recursion with foldr, and you thus want to produce a result in terms of these two for the entire function. This logic is basically encapsulated in the second clause of your function.

Indeed:

vowels (x:xs) = if elem x "aeiou" then 1 + vowels xs else vowels xs

can be rewritten as:

vowels (x:xs) = if elem x "aeiou" then 1 + rec else rec
    where rec = vowels xs

and rec is thus the outcome of the recursive call, the second parameter of the "fold"-function. x on the other hand is the first parameter of the "fold"-function. We thus need to write this function, only in terms of x and rec, and this is simply:

\x rec -> if elem x "aeiou" then 1 + rec else rec

Furthermore we need to handle the case of an empty list, this is the first clause of your function. In that case the result is 0, this is the second paramter of the foldr, so we got:

vowels = foldr (\x rec -> if elem x "aeiou" then 1 + rec else rec) 0

Or a more clean syntax:

vowels = foldr f 0
    where f x rec | elem x "aeiou" = 1 + rec
                  | otherwise = rec

We can further clean it up, by abstracting away rec:

vowels = foldr f 0
    where f x | elem x "aeiou" = (1+)
              | otherwise = id

Answer 2

You need to take a look at foldr's signature.

foldr :: Foldable t => (a -> b -> b) -> b -> t a -> b

Never mind the Foldable part and focus on the first function it takes. (a -> b -> b) b is the same type that you are supposed to return, so directly translating the signature into a lambda gives you \x acc -> acc, but you want to do more than just ignore every element.

Take a look at your function if elem x "aeiou" then 1 + vowels xs else vowels xs. You need to return b, not recurse adding one to it.

if elem x "aeiou" this part is fine. then 1 + acc <- see what I'm doing here? I'm adding one to the accumulator, not recursing manually, that is done by foldr, as for the else case: acc. That's it. You don't need to even touch x.

Putting it all together: vowels = foldr (\x acc -> if elem x "aeiou" then 1 + acc else acc) 0 The 0 is what the acc will start as.

If you want to know more about folds, I suggest you reimplement them yourself.