4

我正在复习过去的考试，为即将到来的考试做准备，在完成了几个问题后，我遇到了一个我无法解决的问题。

它需要一个函数，该函数将接受一个字符串（或 [Char]）并返回字符串中英语单词数量的 Int。它说 isWord 是一个假设函数，它接受一个字符串并根据单词是真还是假返回一个布尔值。单词必须排成一行，从左到右。给出的例子是“目录”。所以“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

好的。这是一个起点。它触及问题的核心。您将如何提出所有候选子字符串进行测试？

好吧，您的问题已经表明了必要的想法。只需将它们分解成足够小的碎片，您就可以看到如何制作它们。你提到想要从字符串中的每个起始位置做一些事情。那么如何编写一个从每个位置开始返回字符串并一直到结尾的函数呢？这似乎是合乎逻辑的第一步。

-- 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.Listas 中inits，但再次尝试自己编写。

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

并且，使用mapand concat，这些加起来就是您需要实施的部分makeSubstrings，正如其他答案所示。希望我能够真正传达一种感觉，即如何推理必要的步骤，以及如何使用这些步骤来构建代码。

于 2012-04-19T08:59:19.700 回答
2

subsequences您正在从 Data.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]finally 接受一个谓词，一个列表，并返回一个仅包含满足谓词的元素的列表。

于 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. 如果你有这个，你可以使用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)
于 2012-04-19T09:09:52.723 回答