在给定字符串中计算字符的出现次数 - Haskell

Question

简单问题。

给定一个字符串，我想输入一个字母，并让我的函数计算出该字母在字符串中出现的次数。

countLetters :: String -> Char -> Int

怎么做到这一点呢？

- user2863323

Answer 1

随着

countLetters :: String -> Char -> Int
countLetters str c = length $ filter (== c) str

这将获取str中与c相等的字符，然后计算其长度。

- bheklilr

---

这会导致性能下降，因为需要遍历整个输入字符串进行过滤，然后再遍历结果以获取长度。 - user2407038

但是 length 和 filter 都是惰性函数，不是吗？我想 GHC 可以优化这样一个简单的情况，以产生一个单一的循环。 - bheklilr

Answer 2

这取决于您想为一个字符串执行多少次调用。简单的解决方案是读取字符串中的每个字符，如果匹配您要查找的字符，则增加计数器。如果您需要使用计数器映射某个内容，那么可以使用fold。

countLetters xs x = foldl (\count char -> if char == x then (count + 1) else count) 0 xs

然而，如果您想进行多个查询，构建查找表（即排序）就更有意义了。然后，您可以在O(1)的时间内获取任意字符的重复次数（整个算法仍然是O(n)）。

- Bartek Banachewicz

---

排序后您的操作不是更像O(m)吗，其中m是重复字符的数量？ - Wes

假设你正在使用固定范围和固定尺寸的表格，提取一个值的速度是 O(1)。可以想象原始内存访问和指针算术运算，例如。 - Bartek Banachewicz