"I think that I shall never see..."

I'm rummaging around Stack Overflow and Hoogle. Data.Set and Data.Map are implemented underneath as balanced trees, but for my purposes I need the tree nature exposed so I can do something like

countInRange Empty m n = 0
countInRange (Node value (Tree lhs) (Tree rhs)) m n
    | value < m = countInRange rhs m n
    | value > n = countInRange lhs m n
    | otherwise = 1 + (countInRange lhs m n)
                    + (countInRange rhs m n)

The set fold doesn't guarantee ordering, so I don't see a way to let it quit early or otherwise skip portions that can't contribute to the count.

Maybe I will have to roll my own.

UPDATE:  Twar van Laarhoven's "Search trees without sorting" looks promising for my purpose. Dank U wel.