5

如果列表中超过 3 个元素的测试失败，我需要返回 false。有什么我可以优化的吗？

isItemOk :: Integer -> Boolean 
isItemOk = ( some costly opernation )

这是我要优化的功能，

isListOk :: [Integer] -> Boolean 
isListOk = 3 >= sum ( [ 1 | x <- [1.1000], isItemOk x ])

我的优化尝试，假设如果找到 4 个元素就不会寻找更多。

isListOk :: [Integer] -> Boolean 
isListOk = 3 >= sum ( take 4 [ 1 | x <- [1.1000], isItemOk x ])

谢谢。

4

4 回答 4

8

您可以只使用filter检查失败元素的东西，然后take 4查看您有多少元素length。

懒惰的评估意味着找到这四个后它不会检查任何东西，所以你完成了。当然，如果测试在三个或更少的元素上失败，它会检查整个列表，但你无能为力。

要避免的重要事情是“计算未通过测试的元素”，或“过滤然后得到结果的长度”，或类似的东西。如果不先使用take或类似的东西，这样做将强制检查整个列表。null这是经常给初学者的“使用或模式匹配检查空列表”建议的更通用版本。但看起来你已经在避免这个错误了！

于 2012-09-19T23:44:18.180 回答
6

对于像 3 这样的小数字，您可以只使用模式匹配。

case filter isItemOk xs of
   x1 : x2 : x3 : _ -> ...
   _                -> ...
于 2012-09-19T23:42:42.800 回答
5

我想借此机会炒作一下惰性自然数。使用这个库genericLength，我们可以写

import Data.Number.Natural
import Data.List
isListOk = (3 :: Natural) >= genericLength (filter isItemOk [1..1000])

它不会做更多的工作：这个函数在返回之前最多会找到四个正常的项目。例如：

> (3 :: Natural) >= genericLength (filter even (2:4:6:8:undefined))
False
于 2012-09-20T06:11:01.287 回答
4

让我先重写一下你的函数，如

isListOk :: Bool 
isListOk = length (filter isItemOk [1 .. 1000]) <= 3

可以说比你的版本更惯用。（请注意，我还更改了类型签名，因为您的签名不正确。此外，您应该写1 .. 1000而不是1.1000.）

惰性求值是你最好的朋友，因为它通常会确保不会执行不必​​要的计算。

不幸的是，您使用length（或将列表中的每个元素映射到 1，然后像您一样对结果列表求和）在这里遇到了阻碍。也就是说，length在列表的脊椎中是严格的：它只能在将列表评估到最后时才产生列表的长度，在这种情况下，这意味着您的程序将不得不运行您的检查一千次。

一种解决方案是将长度的计算（即，遍历列表的脊椎）和计算的长度是否不超过给定阈值的测试组合成一个函数，该函数实际上在其脊椎中是惰性的参数列表：

isNotLongerThan :: [a] -> Integer -> Bool
isNotLongerThan []       n = n >= 0
isNotLongerThan (_ : xs) n = n >= 1 && isNotLongerThan xs (n - 1)

然后写

isListOk :: Bool 
isListOk = filter isItemOk [1 .. 1000] `isNotLongerThan` 3

对于可重用的解决方案，您当然可以对谓词和阈值进行抽象：

forNoMoreThan :: (a -> Bool) -> Integer -> [a] -> Bool
forNoMoreThan p n = (`isNotLongerThan` n) . filter p

isListOk :: Bool
isListOk = (isItemOk `forNoMoreThan` 3) [1 .. 1000]

最后，正如 hammar 所指出的，如果您的阈值足够小且固定，您可以简单地使用模式匹配来确定列表是否足够短。

于 2012-09-20T00:52:08.200 回答