如何避免不必要的计算？

Question

如果测试在列表中超过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 ])

谢谢.

Answer 1

您可以使用filter检查失败元素的内容,然后take 4查看您拥有的元素数量length.

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

要避免的重要一点是"计算未通过测试的元素",或"过滤然后得到结果的长度",或类似的东西.首先不使用take或类似的东西,这样做会强制检查整个列表.这是null通常给初学者的"使用或模式匹配以检查空列表" 的更通用版本.但看起来你已经避免了这个错误!

Answer 2

对于像3这样的低数字,您可以使用模式匹配.

case filter isItemOk xs of
   x1 : x2 : x3 : _ -> ...
   _                -> ...

Answer 3

我想借此机会大肆宣传懒惰的自然数.使用这个库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