1

可能重复：
如何在 Haskell 中查找字符串中字符的频率？

给定一个输入字符串，我希望计算每个字符的出现次数。我有两种方法（在帝国伪代码中）：

For each character in the "alphabet"
  traverse the string and increment a counter when the character is found

我相信我可以很容易地在 Haskell 中实现这一点。我的第二个想法有点棘手：

For each character in the string
  increment a counter and store it in a map (or similar data structure)

我对 Haskell 中的数据结构几乎没有经验，所以第二个解决方案比第一个更令人生畏。但是，我当然想通过实现我自己的数据结构或使用内置库中的某些东西来了解更多信息。

有人对我应该如何进行有任何建议吗？

4

4 回答 4

4

Data.Map是关联数组的标准。我认为它在containers包装中并且有很好的文档记录。该insertWith函数可能对这个问题特别感兴趣 - 它允许您插入一个新的键和值，但还提供一个函数（您可能想要使用+）将值与映射中已有的值（如果有）组合。

于 2012-08-10T15:48:29.627 回答
1

在 Haskell 中，=符号就像在数学中一样用于定义方程。惯用的 Haskell 避免突变（例如“增加一个计数器”），而是鼓励使用纯函数的解决方案。但是，ST您可以使用变异来编写算法，就像使用任何其他语言一样。

考虑确定单个字符在字符串中出现多少次的任务。根据你的英文描述

遍历字符串并在找到字符时增加一个计数器

Python实现将是

def count(c, s):
  i = 0
  for c0 in s:
    if c == c0:
      i += 1
  return i

使用 ST 我们可以编写完全相同的代码，尽管它稍微冗长一些，因为所有可变变量的创建、读取和写入都被显式命名：

import Control.Monad (when, forM_)
import Control.Monad.ST (runST)
import Data.STRef

count :: Char -> String -> Int
count c s = runST $ do     -- def count(c, s):
  i <- newSTRef 0          --   i = 0
  forM_ s $ \c' -> do      --   for c0 in s:
    when (c == c') $ do    --     if c == c0:
      modifySTRef i (+1)   --       i += 1
  readSTRef i              --   return i

正如我之前所说，这不是惯用的 Haskell，但是当您已经考虑到使用突变的命令式算法时，我认为没有理由避开 ST。由于突变是针对函数的，并且从外部无法观察到，我们可以使用它runST来隐藏实现细节并呈现一个纯接口Char -> String -> Int。

于 2012-08-10T18:36:56.543 回答
1

我建议：

  • 阅读折叠。折叠是处理列表的函数式编程中非常常见的模式。

  • 浏览一些Haskell 库（警告：它们很广泛，需要一段时间才能理解——但绝对值得付出努力）。像您这样的问题的解决方案通常可以通过将一些预定义的函数（例如，排序/分组/映射/长度）粘合在一起来找到。本练习让您更熟悉库、Haskell 语法和编码风格、FP 以及通过组合解决问题。

于 2012-08-10T15:51:33.217 回答
0

我认为 Haskell prelude 中可能有一个函数用于此（查找(Eq a, Integral i) => [a] -> a -> i），但这可以很容易地表示为折叠

count a = foldr (\x sum -> if x == a then sum+1 else sum) 0

http://hackage.haskell.org/packages/archive/base/latest/doc/html/Prelude.html#v:foldr

至于地图，请查看 Data.Map 模块。（也很容易编写一个简单的基于列表的地图）

于 2012-08-10T15:52:19.893 回答