哈斯克爾的字數計劃

Question

我正在爲我即將開始的考試而過去考試，在完成了一些問題之後，我發現了一個我無法解決的問題。

它想要一個函數，該函數將接受一個String（或[Char]）並返回一個Int字符串中的英文單詞的數量。它說，isWord是一個假設函數，它接受一個字符串並返回一個布爾值，取決於該字是真還是假。 單詞必須從左到右連續排列。給出的例子是「catalogre」。因此，「貓」，「AT」，「產品目錄」，「怪物」和「日誌」，函數應該返回5.

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

保險槓只是展示我在想什麼，很顯然它不會工作。

這就是我開始的方式，我在想我可以使用take函數並每次遞增一個字母，然後將起始字母向下移動到[]，但我不確定如何實現該遞歸正確。如果任何人有任何想法或可以給我一個方法，這將是偉大的。

Answer 1

您正在尋找Data.List中的subsequences函數。

這是一個好主意，通過the libraries that come with GHC，尤其是基地閱讀。即使您不允許在考試中使用這些功能，它仍然很有用，有時還可以閱讀源代碼（請按照類型簽名右側的「源」鏈接）。

---

編輯：評論是正確的，Matvey的答案也是如此。你可以不接受我的回答，而是接受Matvey的。

Answer 2

如果你知道如何區分非字字可以使用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",""] 

Answer 3

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]最終接受一個謂詞，一個列表，並返回一個只包含滿足謂詞的元素的列表。

Answer 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 

好的。這是一個起點。它陷入了問題的核心。你打算如何提出所有候選子串來測試？

那麼，你的問題已經顯示了必要的想法。只要將它們分解成足夠小的碎片，就可以看到如何去做。你提到想要從字符串中的每個起始位置做些事情。那麼如何編寫一個函數來返回從每個位置開始的字符串，並且到最後？這似乎是合乎邏輯的第一步。

-- 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.List爲inits，但是再次嘗試自己寫。

-- 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件，作爲其他的答案顯示。希望我能夠真正傳達如何推理必要的步驟，以及如何使用這些步驟來構建代碼。

Answer 5

這是另一種解決方案，除了連接列表之外，不使用任何花哨的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. 如果你有這個，你coud使用現有filter函數返回的列表上，讓你跳過所有的這些你給isWord功能產生錯誤的，這樣的事情：

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

這裏有兩種方法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)