计算递归函数中字符串中 Char 的实例

Question

我正在尝试计算字符串中与递归函数耦合的字符数，但它似乎不起作用。

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

所以万一我这样做：characterCounts "atraa"我应该得到T [('a',3),('t',1),('r',1)]但我得到T [('a',1),('t',1),('r',1)].

建议将不胜感激。

Answer 1

我似乎没有"表格"模块(在 GHC 中(。

你的代码看起来很奇怪：你似乎遍历了所有的字符，然后在计数时尝试再次循环(但仅限于列表的尾部(。

在另一个注释中链接的表格模块中有一个"计数"函数。

你可能应该做类似的事情

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

并删除您的"计数"功能。

另外：您还需要处理表中第一次出现的字符。

Answer 2

您的表格看起来很像地图。因此，如果您可以使用地图，则可以尝试以下操作：

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

现在，characterCounts "atraa"返回fromList [('a',3),('r',1),('t',1)]，即类似于您请求Table Char Int的Map Char Int。如果需要，实现转换应该很容易。

Answer 3

当你调用characterCountsAux xs _时，你给你的函数提供了列表的其余部分。这意味着在第 4 次迭代中，您正在调用

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

将表更改为 T [('a'，2(，('t'，1(，('r'，1(] 在下一次迭代中我们有

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

它给你最终的 T[('a

'，1(，('t'，1(，('r'，1(]。

一个天真的解决方案是从 xs 中删除所有出现的 x，即

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

当然，它看起来效率不高...