Count occurances in a list

Question

I would like to count occurrences of the element in a list in Haskell, but there is an error and I don't know why.

count:: Int -> [Int] -> Int
count n []= 0
count n (h:t) | (n `elem` (h:t)) =1+ count (n t) 
       | otherwise = count(n t)

Answer 1

There are two problems here: an error that has more to do with the proper syntax, and a semantical error.

Calling a function with "multiple" arguments

The error the compiler is probably complaining about has to do with the part in boldface:

count:: Int -> [Int] -> Int
count n []= 0
count n (h:t) | (n `elem` (h:t)) = 1+ count (n t)
              | otherwise = count (n t)

Something that is quite confusing for most programmers that first programmed in other languages is that one does not use brackets for function application. Indeed, in many programming languages if one writes foo(1), then in Haskell you can write foo 1.

As a result Haskell interprets the fact that you write count (n t) as the fact that the argument of count is (n t), and thus that we first performed function application with n the function, and t the argument. So in Python this would look like `count(n(t))``, which is not what you meant.

Then how do we pass multiple arguments to a function? Well in Haskell every function has exactly one argument. If you write count n you basically construct a new function. By applying the second argument to that new function, we thus "chained" function applications, like count n t, so we can solve the syntax error with:

count:: Int -> [Int] -> Int
count n [] = 0
count n (h:t) | (n `elem` (h:t)) = 1+ count n t
              | otherwise = count n t

Semantical error: elem instead of ==?

But now there is still a semantical error: what will n `elem` (h:t) do? Indeed it will check if n occurs in the list. Not per se in the head, so as a result, our function will - in some cases - count a value multiple times. For example count 3 [1, 2, 3, 4] will result in 3. Since 3 occurs [1, 2, 3, 4], [2, 3, 4] and [3, 4]. The idea of counting is that we only look at the head, and let the recursion look at the remaining elements, so the condition should be replaced with:

count:: Int -> [Int] -> Int
count n [] = 0
count n (h:t) | n == h = 1 + count n t
              | otherwise = count n t

Generalizing the type

Now we can make the function more generic: let the function work on lists with different type of objects. In fact there is only one thing that restricts these types: we need to be able to perform (==) :: Eq a => a -> a -> Bool on it, so we can generalize the type signature to:

count:: Eq a => a -> [a] -> Int
count n [] = 0
count n (h:t) | n == h = 1 + count n t
              | otherwise = count n t

Counting as a special foldr function

Instead of writing this recursion ourselves, we can use foldr for this, which is a catamorphism on the list. The foldr :: (a -> b -> b) -> b -> [a] -> b uses a function f :: a -> b -> b that takes the head of a list (an a), and the result of recursion on the list (a b), and thus constructs a new result of type b, that then is the result for the entire list. Furthermore the foldr function takes a value (of type b) that is the value that corresponds to the empty list, it can then perform this operation on a list ([a]), and returns the value for that list (a b).

Our count thus takes a look at the head element, in case it is equal to the element we search, we increment the "accumulator", otherwise we simply pass it, we can thus write count as:

count:: Eq a => a -> [a] -> Int
count n = foldr (\x -> if n == x then (+1) else id) 0