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

Your definition can be tweaked into

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

which matches the pattern

foldr r z [] = z
foldr r z (x:xs) = r x (foldr r z xs)

if we have foldr r z = vowels and r = g, and also z = 0.

That "pattern" is in fact a valid definition of the foldr function.

Thus we indeed have

vowels xs = foldr g 0 xs
  where
  g x rec = if elem x "aeiou" then 1 + rec else rec

Answer 2

The easiest way to write something like that is to let the compiler guide you.

First, look only at the obvious parts of the foldr signature. ^{_{This is the traditional signature, specialised to lists. Nowedays, foldr can actually work on any other suitable container as well, but this isn't important here.}}

foldr :: (a -> b -> b)  -- ^ Not obvious
      -> b              -- ^ Not obvious
      -> [a]            -- ^ A list... that'll be the input string
      -> b              -- ^ Final result, so nothing to be done here.

So, your implementation will be of the form

vowels :: String -> Int
vowels s = foldr _ _ s

where we yet need to find out what to put in the _ gaps. The compiler will give you useful hints as to this:

$ ghc wtmpf-file6869.hs 
[1 of 1] Compiling Main             ( wtmpf-file6869.hs, wtmpf-file6869.o )

/tmp/wtmpf-file6869.hs:2:18: error:
    • Found hole: _ :: Char -> Int -> Int
    • In the first argument of ‘foldr’, namely ‘_’
      In the expression: foldr _ _ s
      In an equation for ‘Main.vowels’: Main.vowels s = foldr _ _ s
    • Relevant bindings include
        s :: String (bound at /tmp/wtmpf-file6869.hs:2:8)
        vowels :: String -> Int (bound at /tmp/wtmpf-file6869.hs:2:1)
  |
2 | vowels s = foldr _ _ s
  |                  ^

So, a function that merely takes a single character, and then modifies an integer. That was actually already part of your original implementation:

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

The bold part is essentially a function of a single character, that yields a number-modifier. So we can put that in the foldr implementation, using lambda syntax:

vowels s = foldr (\x -> if x`elem`"aeiou" then (1+) else _) _ s

I had to put the 1+ in parenthesis so it works without an explicit argument, as an operator section.

Ok, more gaps:

    • Found hole: _ :: Int -> Int
    • In the expression: _
      In the expression: if x `elem` "aeiou" then (1 +) else _
      In the first argument of ‘foldr’, namely
        ‘(\ x -> if x `elem` "aeiou" then (1 +) else _)’
    • Relevant bindings include
        x :: Char (bound at wtmpf-file6869.hs:2:20)
        s :: String (bound at wtmpf-file6869.hs:2:8)
        vowels :: String -> Int (bound at wtmpf-file6869.hs:2:1)
  |
2 | vowels s = foldr (\x -> if x`elem`"aeiou" then (1+) else _) _ s
  |                                                          ^

So that's the modifier that should take action when you've found a non-vowel. What do you want to modify in this case? Well, nothing actually: the count should stay as-is. That's accomplished by the id function.

vowels s = foldr (\x -> if x`elem`"aeiou" then (1+) else id) _ s

    • Found hole: _ :: Int
    • In the second argument of ‘foldr’, namely ‘_’
      In the expression:
        foldr (\ x -> if x `elem` "aeiou" then (1 +) else id) _ s
      In an equation for ‘vowels’:
          vowels s
            = foldr (\ x -> if x `elem` "aeiou" then (1 +) else id) _ s
    • Relevant bindings include
        s :: String (bound at wtmpf-file6869.hs:2:8)
        vowels :: String -> Int (bound at wtmpf-file6869.hs:2:1)
  |
2 | vowels s = foldr (\x -> if x`elem`"aeiou" then (1+) else id) _ s
  |                                                              ^

So that's an integer that's completely outside of the foldr. I.e. it can't depend on the string. In particular, it will also be used if the string is empty. Can only be 0!

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

No more gaps, so the compiler will just accept this. Test it:

$ ghci wtmpf-file6869
GHCi, version 8.2.1: http://www.haskell.org/ghc/  :? for help
Loaded GHCi configuration from /home/sagemuej/.ghc/ghci.conf
Loaded GHCi configuration from /home/sagemuej/.ghci
[1 of 1] Compiling Main             ( wtmpf-file6869.hs, interpreted )
Ok, 1 module loaded.
*Main> vowels "uwkaefdohinurheoi"
9

Answer 3

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.

Answer 4

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