Haskell提前结束递归调用的一部分

Question

我正试图编写一个函数，返回可以从字符串(无重复(中提取的动物的可能列表

即给定

dict=["dog","cat","bat","cock","cow","pig","fox",
"ant","bird","lion","wolf","deer","bear","frog",
"hen","mole","duck","goat"]

应该给出

λ= fnd dict "gtcoaode"
[["dog","cat"],["goat"]]

我希望输出只是在每种情况下可以从字符串中提取的最大动物数量：

到目前为止，我的代码是：

contains :: String -> String -> Bool
contains x y = length (x \ y) == (length x - length y)
fnd :: [String] -> String -> [String]
fnd [] _ = [[]]
fnd (x:xs) y
| y `contain` x = (([x]++) <$> (fnd (x:xs) (y \ x))) ++ (fnd xs y)
| otherwise     = scp xs y

然而，这给出了：

λ= fnd names "gtcoaode"
[["dog","cat"],["dog"],["cat"],["goat"],[]]
(0.01 secs, 2,144,368 bytes)

处理代表的案件的最佳方法是什么

Answer 1

一种方法是将找到的每个元素插入到Data.List.Ordered或集合中，而不是将其附加到列表的末尾。这保证了独特性。您也可以将生成的集合作为累积参数传递，并使函数本身成为递归尾部或折叠。

更新

既然听起来你想自己解决这个特定的问题，这里有一个不是特别有效的解决方案来解决一个人为的问题：给定一个字符串，对每一对连续的字母进行排序，不重复。

main :: IO ()
main = (print . myNub . digraphs) "banana"
insertSet :: Ord a => a -> [a] -> [a]
{- Inserts an element into a set, represented as a sorted list in ascending
- order.  If an element in the set is already equal to x, x replaces the
- first such element.
-}
insertSet x [] = [x]
insertSet x (y:ys) | x == y    = x:ys
| x < y     = x:y:ys
| otherwise = y:(insertSet x ys)
myNub :: Ord a => [a] -> [a]
{- A naïve insertion sort of the input list that removes duplicates (and equiv-
- alents).
-}
myNub xs = go [] xs where
go acc [] = acc
go acc (y:ys) = go (insertSet y acc) ys
digraphs :: String -> [String]
{- Returns the list of all consecutive pairs of letters in the string.
-}
digraphs [] = []
digraphs [_] = []
digraphs (x1:x2:xs) = [x1,x2]:(digraphs (x2:xs))

你可以做一些基本的优化：按O(n log n(时间对列表进行排序，然后在O(n(时间扫描它是否重复；使CCD_ 3的CCD_ 2参数严格；使用CCD_ 4高阶函数；使用CCD_ 5中的函数。

不过，您最好使用不同的数据结构。在这种情况下，由于有少量可能的结果(["cat"]、["dog"]、["cat","dog"]等(可以通过计算字母的出现次数来包括或排除，因此您可以简单地计算每个字母在一次传递中出现的次数