Count elements on ordered list

Question

I want to do a Haskell function where the input (a list of Strings) is ordered (always. input is valid only if is ordered) and I want to get the number of occurrences of each different string.

Example:

ContaOcs["a", "a", "b", "c", "c", "c", "d"]

Should return:

[(2,"a"), (1,"b"), (3,"c"), (1,"d")]

Here is What I'm trying to do:

module Main where

contaOcs :: [String] -> [(Int, String)]
contaOcs [] = [_,_]
contaOcs [x] = [1,x]
contaOcs (i, x1:x2:xs)
 | x1 == x2 =  (i+1,(x2:xs))
 | otherwise = (0, (x2:xs))

But this code have some errors and I'm not so sure how I should do to accomplish this I'm new to functional programing and Haskell. Can anyone help me with some information?

Thanks for any help.

Answer 1

There are some syntactical problems as well as problems with the types. The first line looks like:

contaOcs [] = [_,_]

But an underscore (_) in the result does not makes any sense, you can only construct lists with values in it. When we count the number of occurences of an empty list, the result will be an empty list, so contaOcs [] = [].

As for the second:

   contaOcs [x] = [1,x]

Here you aim to return a list with two elements: a 1 and an x (which is a String). In Haskell the elements of a list all have the same type. What you can do is return a list of 2-tuples with the first item an Int, and the second a String, like the signature suggests, but then you need to wrap the values in a 2-tuple, like contaOcs [x] = [(1,x)].

In your last clause, you write:

contaOcs (i, x1:x2:xs) = ...

which does not make much sense: the input type is a list (here of Strings), not a 2-tuple with an Int, and a list of strings.

So the input will look like:

contaOcs (x1:x2:xs) = ...

The output, like (i+1,(x2:xs)) also is not in "harmony" with the proposed output type in the signature, this looks like a 2-tuple with an Int, and a list of Strings, so (Int, [String]), not [(Int, String)].

Based on the above comments, we have derived something like:

contaOcs :: [String] -> [(Int, String)]
contaOcs [] = []
contaOcs [x] = [(1,x)]
contaOcs (x1:x2:xs)
     | x1 == x2 =  -- ...
     | otherwise = -- ...

So now there are two parts to fill in. In case x1 and x2 are not equal, that means that we can first yield a tuple (1, x1) in the list, followed by the result of contaOcs on the rest of the list (x2 included), so:

(1, x1) : contaOcs (x2:xs)

In the latter case, it means that we first make a recursive call to contaOcs with (x2:xs), and then increment the counter of the first item of that list. We are sure such element exists, since we make a recursive call with a list containing at least one element, and by induction, that means the result contains at least one element as well, since the base case contains one element, and the recursive case either prepends elements to the result, or updates these.

So we can use a pattern guard, and maniplate the result, like:

contaOcs :: [String] -> [(Int, String)]
contaOcs [] = []
contaOcs [x] = [(1,x)]
contaOcs (x1:x2:xs)
     | x1 == x2, ((yi, yv):ys) <- contaOcs (x2:xs) = (yi+1, yv) : ys
     | otherwise = (1, x1) : contaOcs (x2:xs)

We can also use an "as-pattern": we only need a reference to the tail of the list starting with x2, not xs:

contaOcs :: [String] -> [(Int, String)]
contaOcs [] = []
contaOcs [x] = [(1,x)]
contaOcs (x1:xs@(x2:_))
     | x1 == x2, ((yi, yv):ys) <- contaOcs xs = (yi+1, yv) : ys
     | otherwise = (1, x1) : contaOcs xs

The above is however not very elegantly. It might be better to use an accumulator here, I leave this as an exercise.