The search tree corresponding to @fromList (map Max [1..5])@. Circles are @Leaf@s and squares are @Branch@es.

So indeed, @satisfy q a || satisfy q b ==> satisfy q (meet a b)@.
And this bound is in fact tight, so also the other way around @satisfy q (meet a b) ==> satisfy q a || satisfy q b@. This will become important later.
Now here are some example queries:
]> λ> findFirst (Ge 3) (fromList $ map Max [1,2,3,4,5])
]> Just (Max 3)
]> λ> findFirst (Ge 3) (fromList $ map Max [2,4,6])
]> Just (Max 4)
]> λ> findFirst (Ge 3) (fromList $ map Max [6,4,2])
]> Just (Max 6)
]> λ> findFirst (Ge 7) (fromList $ map Max [2,4,6])
]> Nothing
Semilattices and queries can easily be combined into tuples. For a tree of pairs, and queries of pairs, you could use.
> -- IGNORE
> -- Note: this instance requires UndecidableInstances when we use a FunDep for Satisfy
> instance (Semilattice a, Semilattice b) => Semilattice (a,b) where
> meet (a,b) (c,d) = (meet a c, meet b d)
> instance (Satisfy a b, Satisfy c d) => Satisfy (a,c) (b,d) where
> satisfy (a,c) (b,d) = satisfy a b && satisfy c d
Now we can not only questions like "What is the first/last/smallest element that is greater than some given query?". But also "What is the first/last/smallest element greater than a given query that also satisfies some other property?".
-- When is it efficient? --
It's nice that we now have a search tree that always gives correct answers.
But is it also efficient?
As hinted in the introduction, that is not always the case.
First of all, @meet@ could give a really bad bound. For example, if @meet a b = Bottom@ for all @a /= b@, and Bottom satisfies everything, then we really can do no better than a brute force search.
On the other hand, suppose that @meet@ gives 'perfect' information, like the @Ge@ example above,
]> --BLOCK: haskell-equational-reasoning
]> satisfy q (meet a b) ==> satisfy q a || satisfy q b
That is equivalent to saying that
]> --BLOCK: haskell-equational-reasoning
]> not (satisfy q a) && not (satisfy q b) ==> not (satisfy q (meet a b))
Then for any Branch, we only have to search either the left or the right subtree.
Because, if a subtree doesn't contain the value, we know can see so from the bound.
For a balanced tree, that means the search takes $O(log n)$ time.
Another efficient case is when the items are sorted.
By that I mean that, if an item satisfies the query, then all items after it also satisfy that query.
We actually need something slightly more restrictive: namely that if a query is satisfied for the meet of some items, then all items after them also satisfy the query.
In terms of code:
]> --BLOCK: haskell-equational-reasoning
]> let st = fromList (xs__1 ++ xs__2 ++ xs__3)
]> satisfy q (meet xs__2) ==> all (satisfy q) xs__3
Now suppose that we are searching a tree of the form @st = mkBranch a b@ with @findFirst q@. Then there are three cases: