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

Question

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.

I remember Table from a previous homework problem posted. I think it's just an association list, maybe a previous homework assignment to implement it. — jberryman
– jberryman, Commented Feb 7, 2017 at 18:50

Tomas By · Accepted Answer · 2017-02-07 17:41:23Z

1

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.

answered Feb 7, 2017 at 17:41

Tomas By

1,3941 gold badge12 silver badges23 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

fjarino · Accepted Answer · 2017-02-07 19:05:33Z

1

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.

answered Feb 7, 2017 at 19:05

fjarino

1914 bronze badges

Comments

shortmanikos · Accepted Answer · 2017-02-07 23:27:28Z

1

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

answered Feb 7, 2017 at 23:27

shortmanikos

2111 silver badge5 bronze badges

1 Comment

Ricardo DM Over a year ago

Bingo! I was thinking of recursion backwardsly!

Collectives™ on Stack Overflow

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

3 Answers 3

Comments

Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related