How to avoid unnecessary computation?

Question

I need to return false if a test fails for more than 3 elements in a list. Is there anything I can to do optimize ?

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

This is the function I am trying to optimize,

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

My attempt at optimization , assuming take if it finds 4 elements will not look for more.

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

Thanks.

Answer 1

You can just use filter with something that checks for failing elements, then take 4 and see how many elements you have with length.

Lazy evaluation means it won't bother checking anything after finding those four, so you're done. Of course, if the test fails for three or fewer elements, it'll check the whole list, but there's nothing you can do about that.

The important thing to avoid is something like "count the elements that fail the test", or "filter and then get the length of the result", or anything like that. Without using take or something similar first, doing that will force checking the entire list. This is a more general version of the "use null or pattern matching to check for empty lists" advice often given to beginners. But it looks like you're already avoiding that mistake!

Answer 2

For a low number like 3, you can just use pattern matching.

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

Answer 3

I would like to take this opportunity to hype lazy natural numbers a bit. Using this library and genericLength, we can just write

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

and it will do no more work than it has to: this function will find at most four okay items before returning. For example:

> (3 :: Natural) >= genericLength (filter even (2:4:6:8:undefined))
False

Answer 4

Let me first rewrite your function a bit, as

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

is arguably more idiomatic than your version. (Note that I also changed the type signature as yours was incorrect. Furthermore, you should have written 1 .. 1000 rather than 1.1000.)

Lazy evaluation is your best friend here, as it will typically make sure that no unnecessary computations will be performed.

Unfortunately, your use of length (or mapping each element from a list to 1 and then summing the resulting list, as you do) is getting in the way here. That is, length is strict in the spine of the list: it can only produce the length of the list if it evaluates it to its very end, which, in this case, means that your program will have to run your check a thousand times.

A solution would be to combine the computation of the length (i.e., the traversal of the spine of the list) and the test whether the computed length does not exceed a given threshold into a single function that is in fact lazy in the spine of its argument list:

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

and then write

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

For a reusable solution, you can of course abstract over both the predicate and the threshold:

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

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

Finally, as hammar points out, if your threshold is small enough and fixed, you may simply use pattern matching to determine whether a list is short enough.