1

重複の可能性:
Haskellで文字列内の文字の頻度を見つける方法は?

入力文字列を指定して、各文字の出現回数を数えたいと思います。私には2つのアプローチがあります（インペリアル疑似コードで）：

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

Haskell でこれをかなり簡単に実装できると思います。私の 2 番目のアイデアは少しトリッキーです。

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

私は Haskell のデータ構造の経験がほとんどないので、この 2 番目の解決策は最初の解決策よりも少し威圧的です。ただし、独自のデータ構造を実装するか、組み込みライブラリから何かを使用して、もっと学びたいと思っています。

私がどのように進めるべきかについて、誰か提案はありますか？

4

4 に答える 4

4

Data.Map連想配列の標準です。それはcontainersパッケージに含まれており、かなりよく文書化されていると思います。この関数は、この問題にとって特に興味深いものです。新しいキーと値を挿入するだけでなく、値をマップに既に存在する値と組み合わせるinsertWith関数 ( を使用したい場合) を提供することもできます。+

于 2012-08-10T15:48:29.627 に答える
1

Haskell では、=記号は数学と同じように方程式を定義するために使用されます。慣用的な Haskell は、突然変異 (「カウンターをインクリメントする」など) を避け、代わりに純粋な関数を利用するソリューションを推奨します。ただし、を使用STすると、他の言語と同じように、突然変異を使用してアルゴリズムを作成できます。

1 つの文字が文字列に何回出現するかを判断するタスクを考えてみましょう。あなたの英語の説明によると

文字列をトラバースし、文字が見つかったときにカウンターをインクリメントします

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 に答える