haskell – How can I change the code I made to a recursion


This was the initial code I made:

count :: Char → String → Int
count x xs = length [x’ | x’← xs, x == x’] 

Switch to recursion:

count = length x' | x' <- xs
    | x == x'

What am I doing wrong? Or is it even possible to switch the initial code to recursion?


Recursion, as you may already know, is a way of defining functions, in which the function is invoked within its own definition. This is a widely used concept, for example, when mathematical definitions are presented.

One of the most common examples is the definition of the set of natural numbers N (in this case we consider that 0 is part of the set):

1) 0  pertence a N
2) Se n pertence a N, então n+1 pertence também a N

The previous definition, like most recursive definitions, is divided into two cases: the base case (or stopping case) and the recursive step, where we define rules to formulate more complex cases in terms of simpler cases.

Important to note that without the stop case(s), the function normally enters an infinite loop/loop.

Applying the formula presented above to your problem, the number of occurrences of a given character ( c ) in an arbitrary list (where x represents the head and xs the tail) is:

1) 0 (zero) se a lista estiver vazia (caso base ou caso de paragem) 
2) Caso a lista não estiver vazia o resultado depende da comparação de `c` com o primeiro elemento da lista:
   - Se c é igual a x então o resultado é 1 + "número total de ocorrências de c na restante lista"
   - Se c é diferente de x, o resultado corresponde apenas ao "número total de ocorrências de c na restante lista".

You can try now, apply the formula above and try to define its function. Here's also an example, if you want to compare your solution:

count :: Char -> String -> Int
count _ [] = 0   -- Caso de paragem/base
count c (x:xs) 
  | c == x    = 1 + count c xs
  | otherwise = count c xs 
Scroll to Top