On Fri, Sep 25, 2015 at 05:38:02PM +0200, 'Klaus Aehlig' via ganeti-devel wrote:
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
Just nitpicking, (maybe (Just x) Just) might be slightly shortened as (Just
. fromMaybe x) or (`mplus` Just x). If you like any of these ideas, no need
to resend, if not, also OK.
In any case, LGTM, thanks.
+ 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
