Haskell - Count occurrences from multiple elements and return tuple

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

We can make use of functions like first :: Arrow a => a b c -> a (b, d) (c, d) and second :: Arrow a => a b c -> a (d, b) (d, c) to construct a tuple where we apply a function to one of the two items of the 2-tuple. For example:

Prelude Control.Arrow> first (1+) (1,4)
(2,4)
Prelude Control.Arrow> second (1+) (1,4)
(1,5)

We thus can use this to update the tuple with:

import Control.Arrow(first, second)
import Data.List(foldl')

occurrences :: (Eq a, Integral i, Integral j, Foldable f) => a -> a -> f a -> (i, j)
occurrences a b = foldl' (flip f) (0, 0)
    where f c | a == c = first (1+)
              | b == c = second (1+)
              | otherwise = id

For the sample input, this produces:

Prelude Control.Arrow Data.List> occurrences 3 7 [-1,3,-4,3,4,3,-8,7,7,3]
(4,2)

We can easily extent this behavior, by making use of lenses to update one of the elements of tuple.

@emg184 gave a good way to solve this problem, but there could be cleaner, easier to read ways to go about doing this. For example:

occurrences x y xs = (count x xs, count y xs)
    where count = (length .) . filter . (==)

count could also be written in a more readable:

count x = (length . filter (== x))

You could approach this problem a lot of different way's here is an example of doing it with a fold.

occurrences :: (Eq a) => a -> a -> [a] -> (Int, Int)
occurrences a b list = foldr (\y (a', b') -> ((isEqual y a a'), (isEqual y b b'))) (0, 0) list
  where isEqual listEle tupEle count = if (listEle == tupEle) then (count + 1) else count

One of the problem's is you have a type mismatch. you want a type of:

(Int, Int)

Yet you are returning a type of int here once you have an empty list:

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

You need some type of an accumulator you could do this by where binding a local function that takes your starting tuple of (0, 0) or you could pass it to occurrences like this:

occurrences :: Int -> Int -> [Int] -> (Int, Int) -> (Int, Int)

I would suggest using a local function since you'll always want to start with (0, 0) in this approach.

occurrences' :: (Eq a) => a -> a -> [a] -> (Int, Int)
occurrences' a b list = go list (0,0)
  where go x (e1, e2) = if (x == []) then (e1, e2) else (go (tail x) ((isEqual a (head x) e1), (isEqual b (head x) e2)))
        isEqual v v' accum = if (v == v') then (accum + 1) else (accum)

This isnt the most idiomatic way to do it but it shows the point. You should try to use types to help with this.,