CODEWITHSUNDEEP
haskellrecursion
Ricardo DM
Ricardo DM

Reputation: 33

Count the instances of Char in a String in a recursive function

I am trying to count the number of characters in a string coupled with a recursive function but it does not seem to be working.

{- characterCounts s
   PRE:  True
POST: a table that maps each character that occurs in s to the number of
     times the character occurs in s
EXAMPLES:
 -}
characterCounts :: String -> Table Char Int
characterCounts [] = Table.empty
characterCounts s = characterCountsAux s Table.empty

characterCountsAux:: String -> Table Char Int -> Table Char Int
characterCountsAux [] table = table
characterCountsAux (x:xs) table = characterCountsAux xs (Table.insert (table) x (count x (x:xs) ))


count:: Char -> String -> Int
count c s = length $ filter (==c) s

so in case I do: characterCounts "atraa" I should get T [('a',3),('t',1),('r',1)] but instead I get T [('a',1),('t',1),('r',1)].

Suggestions will be appreciated.

Upvotes: 1

Views: 694

Answers (3)

shortmanikos
shortmanikos

Reputation: 201

When you call characterCountsAux xs _ you are giving your function the remainder of the list. That means that on the 4th iteration you are calling

characterCountsAux "aa" T [('a',3),('t',1),('r',1)]

which changes the table to T [('a',2),('t',1),('r',1)] and on the next iteration we have

characterCountsAux "a" T [('a',2),('t',1),('r',1)]

which gives you the final T[('a',1),('t',1),('r',1)].

A naive solution would be removing all occurrences of x from xs i.e.

characterCountsAux (x:xs) table = characterCountsAux (filter (/= x) xs) (Table.insert (table) x (count x (x:xs) ))

Of course it doesn't look very efficient...

Upvotes: 1

fjarino
fjarino

Reputation: 191

Your Table looks a lot like a Map. So, if you can use Maps you could try the following:

import qualified Data.Map as M

characterCounts :: [Char] -> M.Map Char Int
characterCounts = foldr ((flip $ M.insertWith (+)) 1) M.empty

Now, characterCounts "atraa" returns fromList [('a',3),('r',1),('t',1)], i.e. a Map Char Int similar to the Table Char Int you are asking for. It should be easy to implement a conversion, if needed.

Upvotes: 1

Tomas By
Tomas By

Reputation: 1394

I don't seem to have a "Table" module (in GHC).

Your code looks odd: you seem to loop over the all the chars and then try to loop again when counting (but only over the tail of the list).

There is a "count" function in the Table module linked in the other comment.

You should probably do something like

Table.insert table x ((count table x) + 1)

and remove your "count" function.

Addition: you also need to handle the first occurrence of a char in the table.

Upvotes: 1

Related Questions