Haskell - Number of occurencies of a Char in a String-CodePudding

I am writing a function in Haskell to count the occurencies of a Char value in a String, but getting an error with the pattern matching. Is there any way I could change the pattern matching to check if the 'xs' String's first value is 'a'?

howMany :: Char -> String -> Int
howMany a [] = 0
howMany a (a : xs) = 1   howMany a xs
howMany a (x : xs) = 0   howMany a xs

CodePudding user response：

All patterns should be linear: that means you can not use the same variable twice in the head of a function. Haskell does pattern matching, not unification like in Prolog. This is specified in section 3.17.1 Patterns of the Haskell report:

All patterns must be linear — no variable may appear more than once. For example, this definition is illegal:
f (x,x) = x     -- ILLEGAL; x used twice in pattern 

You thus should check if x == a with the help of a guard:

howMany :: Char -> String -> Int
howMany a [] = 0
howMany a (x : xs)
  | x == a = 1   howMany a xs
  | otherwise = howMany a xs

CodePudding user response：

Think about it, how would your code translate into using explicit pattern matching with case?

howMany :: a -> [a] -> Int
howMany a b = case b of
    []       -> 0                   -- case 1
    (a : xs) -> 1   howMany a xs    -- case 2
    (x : xs) -> 0   howMany a xs    -- case 3

The a in -- case 2 is a completely new variable, fully independent of the outer a serving as a formal parameter to howMany. It could be named with any other name, like

howMany :: a -> [a] -> Int
howMany a b = case b of
    []       -> 0                   -- case 1
    (x : xs) -> 1   howMany a xs    -- case 2
    (x : xs) -> 0   howMany a xs    -- case 3

and now we see clearly what was true before as well -- that the cases 2 and 3 are one and the same.

But that is not what we intended. We wanted to differentiate between x==a case and its negation.

The solution is just to be explicit about our intentions:

howMany :: Eq a => a -> [a] -> Int
howMany a b = case b of
    []       -> 0                   -- case 1
    (x : xs) 
      | x==a -> 1   howMany a xs    -- case 2
    (x : xs) -> 0   howMany a xs    -- case 3

The above can be further translated with lambda notation as

howMany :: Eq a => a -> [a] -> Int
howMany = \a -> (\b -> case b of
    []       -> 0                   -- case 1
    (x : xs) 
      | x==a -> 1   howMany a xs    -- case 2
    (x : xs) -> 0   howMany a xs )  -- case 3

So this is why non-linear patterns are disallowed in Haskell -- because the arguments to a function are pattern matched one by one, and not in unison.

That's what "matched, not unified" technical remark in the other answer means. The inner lambda is a Haskell value in its own right, standing on its own. But if it were to differentiate on its argument variable name it would have to be made to act differently -- nay, to be different -- according to some other variable in some outer environment somewhere? That's just won't do.