Add a utility function, that, as long as `p` is monotone on `xs` is the same as `find p xs`, however evaluating the predicate `p` less often by using the monotonicity property. This is useful if evaluating the predicate is an expensive operation. To use further knowledge about the list to be searched through, the function is monotonic in the heuristics. Examples of heuristics include - taking `const 10` for constant-look-ahead guess and verify, and - taking `\ x -> length x / 2` for binary search.
Signed-off-by: Klaus Aehlig <[email protected]> --- src/Ganeti/Utils.hs | 20 ++++++++++++++++++++ 1 file changed, 20 insertions(+) diff --git a/src/Ganeti/Utils.hs b/src/Ganeti/Utils.hs index 895c9e4..f66e37d 100644 --- a/src/Ganeti/Utils.hs +++ b/src/Ganeti/Utils.hs @@ -99,6 +99,7 @@ module Ganeti.Utils , isSubsequenceOf , maxBy , threadDelaySeconds + , monotoneFind ) where import Prelude () @@ -849,3 +850,22 @@ isSubsequenceOf a@(x:a') (y:b) | x == y = isSubsequenceOf a' b -- arguments. maxBy :: (a -> a -> Ordering) -> a -> a -> a maxBy ord a b = maximumBy ord [a, b] + +-- | Given a predicate that is monotone on a list, find the +-- first list entry where it holds, if any. Use the monotonicity +-- property to evaluate the property at as few places as possible, +-- guided by the heuristics provided. +monotoneFind :: ([a] -> Int) -> (a -> Bool) -> [a] -> Maybe a +monotoneFind heuristics p xs = + let count = heuristics xs + in case () of + _ | x:xs' <- drop count xs + -> if p x + then maybe (Just x) Just . monotoneFind heuristics p + $ take count xs + else monotoneFind heuristics p xs' + _ | x:xs' <- xs + -> if p x + then Just x + else monotoneFind heuristics p xs' + _ -> Nothing -- 2.6.0.rc2.230.g3dd15c0
