4

今後の試験に向けて過去の試験を復習していて、いくつかの問題を解いた後、解けない問題に出くわしました。

String (または [Char]) を取り、String に含まれる英単語の数の Int を返す関数が必要です。isWord は、文字列を受け取り、単語が true か false かに応じて Boolean を返す架空の関数であると書かれています。単語は左から右に一列に並んでいる必要があります。与えられた例は「カタログ」でした。したがって、「cat」、「at」、「catalog」、「ogre」、および「log」の場合、関数は 5 を返す必要があります。

wordsInString :: [Char] -> Int
wordsInString [] = 0
wordsInString x
    | isWord (take 1 x)
    | isWord (take 2 x)

バンパーは私が考えていたことを示しているだけで、明らかに機能しません。

これが私が始めた方法であり、take関数を使用して一度に各文字をインクリメントし、開始文字を まで下に移動できると考えていました[]が、その再帰を正しく実装する方法がわかりませんでした。誰かがアイデアを持っているか、私に方法を示すことができれば、それは素晴らしいことです.

4

5 に答える 5

7

単語と非単語を区別する方法を知っている場合は、使用initsして、tails考えられるすべての候補のリストを取得できます。

> :m +Data.List
> concatMap inits $ tails "catalogre"
["","c","ca","cat","cata","catal","catalo","catalog","catalogr","catalogre","","a","at","ata","atal","atalo","atalog","atalogr","atalogre","","t","ta","tal","talo","talog","talogr","talogre","","a","al","alo","alog","alogr","alogre","","l","lo","log","logr","logre","","o","og","ogr","ogre","","g","gr","gre","","r","re","","e",""]
于 2012-04-19T08:37:05.233 に答える
4

その問題文は少しあいまいです。明示的に述べられていないいくつかの仮定を立てます - 単語は別の単語の接頭辞である可能性があり、重複する単語は毎回カウントされます。

次に、このような問題を解決するために、問題をいくつかの部分に分解します。あなたはすでにこれを少し行っていますが、そのコードをフォローアップしていないようです。Haskell の強力な機能は、多くの場合、コード構造が思考の構造に従っていることです。

したがって、テストする適切な部分文字列をすべて生成し、結果をカウントすることを明確に決定しました。それをコードに入れることから始めましょう。

wordCount :: String -> Int
wordCount = length . findWords

findWords :: String -> [String]
findWords = filter isWord . makeSubstrings

makeSubstrings :: String -> [String]
makeSubstrings xs = undefined -- hmm, this isn't clear yet

Ok。それが出発点です。問題の核心に迫ります。テストするすべての候補部分文字列をどのように考え出すのですか?

さて、あなたの質問はすでに必要なアイデアを示しています。それらをどのように行うかを見ることができるほど小さい断片に分解するだけです. 文字列のすべての開始位置から何かをしたいとおっしゃいました。では、各位置から始まり、最後まで文字列を返す関数を作成するのはどうでしょうか? それは論理的な最初のステップのように思えます。

-- for the input "foo", this should return the list ["foo", "oo", "o", ""]
tails :: String -> [String]
tails = undefined -- I'll leave this one up to you

その名前の選択は恣意的ではありません。まさにこれを行う関数がData.Listすでにありますが、それがどのように行われるかを確認するためだけに、自分で実装する必要があります。

しかし、それらのすべてのプレフィックスを調べる必要があることも明確にわかりました。したがって、文字列のすべてのプレフィックスを生成する別の関数を作成します。これはData.Listasinitsにもありますが、やはり自分で書いてみてください。

-- for the input "foo", this should return the list ["", "f", "fo", "foo"]
inits :: String -> [String]
inits = undefined - again, this is up to you

そして、 と を使用するmapと、他の回答が示すようconcatに、これらを実装する必要がある部分になります。makeSubstrings必要な手順について推論する方法と、それらの手順を使用してコードを構築する方法について、実際に感覚を伝えることができれば幸いです。

于 2012-04-19T08:59:19.700 に答える
2

subsequencesData.List から関数を探しています。

GHC に付属しているライブラリ、特に baseを一読することをお勧めします。試験でこれらの関数の使用が許可されていない場合でも、ソース コードを読むことは有用であり、時には啓発にもなります (タイプ シグネチャの右側にある「ソース」リンクをたどってください)。

編集：コメントは正しいので、Matveyの答えもそうです。私の回答を受け入れず、代わりに Matvey の回答を受け入れることができます。

于 2012-04-19T08:32:03.613 に答える
1 
allWordsInString :: [Char] -> [[Char]]
allWordsInString = filter isWord . concat . map tails . inits
--                                 ^^^^^^^^^^^^^^^^^^ or, concatMap tails

wordsInString :: [Char] -> Int
wordsInString = length . allWordsInString

与えられた文字列にどの英単語が含まれているかを知ることも興味深いかもしれないので、このようなものをお勧めします。

(.)関数合成です。concat :: [[a]] -> [a]リストを平坦化しますconcat [[1,2], [], [3] == [1,2,3]。inits指定されたリストのすべての可能な最初の接頭辞を返しtailsます。接尾辞も同様です。filter :: (a -> Bool) -> [a] -> [a]最終的に述語、リストを取り、述語を満たす要素のみを含むリストを返します。

于 2012-04-19T08:50:51.610 に答える
0

これは、リストの連結、リストの長さの計算、リストの末尾の取得、および再帰以外の派手な Haskell 機能を使用しない別のソリューションです。

アイデアは次のとおりです。

  1. candidatesWithLength :: Int -> String -> [String]最初に、アイテムの長さと何らかの文字列が与えられ、次にその長さのすべてのアイテムを含むリストを生成する関数を作成して、次のように動作させます。

    > candidatesWithLength 3 "Foo"
["Foo"]
> candidatesWithLength 2 "Foo"
["Fo", "oo"]
> candidatesWithLength 1 "Foo"
["F", "o", "o"]

  2. 次に、上記の関数を使用して、指定された文字列のすべての「候補」(潜在的な単語) を生成candidatesWithLengthする関数を作成します。candidates :: String -> [String]この関数は、長さ 1 のすべての候補と長さ 2 の候補、および長さ 3 の候補などを含む長いリストを単純に作成します。次のように動作します。

    > candidates "Foo"
["Foo", "Fo", "oo", "F, "o", "o"]

  3. これがある場合は、返されたリストで既存の関数を使用して、次のように、指定された関数が false を返すfilterすべてのものをスキップできます。isWord

    > filter isWord (candidates "catalogre")
["catalog", "ogre", "cat", "log", "at"]

以下は、2 つのメソッドの実装であり、派手な機能をあまり使用していませんcandidatesWithLength。candidates

candidatesWithLength :: Int -> String -> [String]
candidatesWithLength len s
    | len > (length s) = []
    | otherwise        = go s (length s - len + 1)
    where go _ 0 = []
          go s' movesLeft = take len s' : go (tail s') (movesLeft - 1)

candidates :: String -> [String]
candidates s = go (length s)
    where go 0 = []
          go itemLength = candidatesWithLength itemLength s ++ go (itemLength - 1)
于 2012-04-19T09:09:52.723 に答える