Haskell - Count occurrences from multiple elements and return tuple

Question

Heyy, I'm Haskell beginner and I pretend to do the following function:

occurrences 3 7 [-1,3,-4,3,4,3,-8,7,7,3]

Output that I want: (4,2)

I made this try but doesn't worked so well, guess I having troubles to count the elements individually and to return the tuple

occurrences  a b [] = 0

occurrences  a b (x:xs) 
                       | x == a =  1 + occurrences  a b xs
                       | x == b =  1 + occurrences  a b xs
                       | otherwise = occurrences  a b xs

I appreciate any tip and help, thanks ;)

Answer 1

A good approach is to add a type signature, and use the error messages to guide you:

occurrences :: (Eq a) => a -> a -> [a] -> (Int, Int)
occurrences a b [] = 0
occurrences a b (x:xs)
  | x == a = 1 + occurrences a b xs
  | x == b = 1 + occurrences a b xs
  | otherwise = occurrences a b xs

The first error is “Could not deduce (Num (Int, Int)) arising from the literal 0 from the context Eq a”. This means that we can’t use 0 in the first equation because it’s not a tuple, or more precisely, there is no Num instance that allows us to convert from the literal 0 to a tuple via fromIntegral. In the base case, we should return a tuple containing 0 for both sums:

occurrences :: (Eq a) => a -> a -> [a] -> (Int, Int)
occurrences a b [] = (0, 0)
occurrences a b (x:xs)
  | x == a = 1 + occurrences a b xs
  | x == b = 1 + occurrences a b xs
  | otherwise = occurrences a b xs

The next error is “Could not deduce (Num (Int, Int)) arising from a use of + from the context Eq a. This means we’re trying to use + on the result of occurrences, but as with the previous error, it doesn’t have a Num instance to provide +, because it’s now a tuple. The fix here is to match on the result of occurrences and add to the first or second element of the tuple accordingly:

occurrences :: (Eq a) => a -> a -> [a] -> (Int, Int)
occurrences a b [] = (0, 0)
occurrences a b (x:xs)
  | x == a = let (m, n) = occurrences a b xs in (m + 1, n)
  | x == b = let (m, n) = occurrences a b xs in (m, n + 1)
  | otherwise = occurrences a b xs

Now this produces the expected result:

> occurrences 'a' 'b' "ababcb"
(2,3)

But we can improve this solution in a few ways. First, a and b remain the same throughout the computation, so we can do the recursion in a helper function instead of passing a and b around to every call.

occurrences :: (Eq a) => a -> a -> [a] -> (Int, Int)
occurrences a b = go
  where
    go [] = (0, 0)
    go (x:xs)
      | x == a = let (m, n) = go xs in (m + 1, n)
      | x == b = let (m, n) = go xs in (m, n + 1)
      | otherwise = go xs

The idiom here is to define f a b … = go where go = …, and replace calls to f a b … with go—because they’re defined as equal! This is a great example of equational reasoning, replacing one side of an equation with the other.

Finally, since every equation of go except the base case contains a tail call to go, it suggests we can express this pattern of recursion with a fold. Here, our accumulator is the pair of results, and the combining function can increment the results accordingly as we step through the list. Since our accumulator is just a pair of integers, it’s a good idea to use a strict fold (foldl').

import Data.List (foldl')

occurrences :: (Eq a) => a -> a -> [a] -> (Int, Int)
occurrences a b = foldl' go (0, 0)
  where
    go (m, n) x
      | x == a = (m + 1, n)
      | x == b = (m, n + 1)
      | otherwise = (m, n)

Finally, instead of keeping an accumulator and adding elements one by one, we can just map each element to a value (0 or 1) and reduce them by summation. This map/reduce pattern is captured by foldMap :: (Foldable t, Monoid m) => (a -> m) -> t a -> m, which maps each element of a container (t a) to a value (m) and combines the results using a Monoid instance. The monoid to use here is Sum from Data.Monoid, whose Monoid and Semigroup instances define mempty = Sum 0 and Sum a <> Sum b = Sum (a + b) respectively.

import Data.Coerce (coerce)
import Data.Foldable (foldMap)
import Data.Monoid (Sum(..))

occurrences :: (Eq a) => a -> a -> [a] -> (Int, Int)
occurrences a b = coerce . foldMap go
  where
    go x
      | x == a = (Sum (1 :: Int), mempty)
      | x == b = (mempty, Sum (1 :: Int))
      | otherwise = mempty