- A+

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.

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 `String`

s), 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 `String`

s, 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.