A Vicinity performs lookups of a commutative monoid over a key range in optimal time. Consider a collection of books in print that share a common set of properties:

>>> data Book = Book { title :: String, author :: String, year :: Int, cost :: Int }
>>> let b1 = Book "The Wings of Vanessa" "Diana Alexander" 1974 7
>>> let b2 = Book "Dweller and a Card" "Diana Alexander" 1977 4
>>> let b3 = Book "The Weeping Blight" "Diana Alexander" 1980 8
>>> let b4 = Book "The Northern Dog" "Thomas Brown" 1982 2
>>> let b5 = Book "Bridge and Blade" "Thomas Brown" 1988 3
>>> let b6 = Book "The Manor" "Bernice McNeilly" 1983 11
>>> let b7 = Book "Southern Pirate" "Donna Arnold" 1985 23
>>> let b8 = Book "Without the Mesa" "Donna Arnold" 1991 25
>>> let b9 = Book "The Hollywood Sky" "Preston Richey" 1975 10
>>> let books = [b1,b2,b3,b4,b5,b6,b7,b8,b9]

We would like to find the cheapest books published within various time ranges. So, we must also define a price metric that has a commutative semigroup instance:

>>> data Price = Price { ptitle :: String, pcost :: Int } deriving (Show)
>>> appendPrice (Price t1 c1) (Price t2 c2) = case compare c1 c2 of {LT -> Price t1 c1; EQ -> Price (min t1 t2) c1; GT -> Price t2 c2}
>>> instance Semigroup Price where { (<>) = appendPrice }

What does the append operator do here? It chooses the information for the value with the lower price. In the event of a tie (handled by the EQ case), it choose the lexographically lower title. Breaking the tie this way ensures that append is commutative. However, we're still missing a Monoid instance. Notice that Price cannot be made into a Monoid, since there is no sensible and law-abiding mempty. We will need to lift Price to get a Monoid. We can do this with Data.Semigroup.Option. Let's write a function to turn our collection of books into Option Price:

>>> import Data.Semigroup (Option(..))
>>> toPrice (Book t _ _ c) = Option (Just (Price t c))
>>> :t toPrice
toPrice :: Book -> Option Price

Now, we can fold over the collection of books to build our index of the cheapest book in each time range:

>>> let ixc = foldMap (\b -> singleton (year b) (toPrice b)) books
>>> :t ixc
ixc :: Vicinity Int (Option Price)
>>> query (Just 1977) (Just 1986) ixc
Option {getOption = Just (Price {ptitle = "The Northern Dog", pcost = 2})}

Cool. We could pick other commutative monoidal metrics as wells. We could handle things like the set of authors that published during the time range or the total number of books published during the time range. Or we could just do them all at once using the monoid instance of a three-tuple:

>>> import Data.Set (Set)
>>> import qualified Data.Set as S
>>> type Metrics = (Option Price, Set String, Sum Int)
>>> printMetrics (a,b,c) = print a >> print b >> print c
>>> toMetrics b = (toPrice b, S.singleton (author b), Sum (1 :: Int))
>>> :t toMetrics
toMetrics :: Book -> (Option Price, Set String, Sum Int)
>>> let ixa = foldMap (\b -> singleton (year b) (toMetrics b)) books
>>> printMetrics (query (Just 1974) (Just 1989) ixa)
Option {getOption = Just (Price {ptitle = "The Northern Dog", pcost = 2})}
fromList ["Bernice McNeilly","Diana Alexander","Donna Arnold","Preston Richey","Thomas Brown"]
Sum {getSum = 8}
>>> printMetrics (query (Just 1982) (Just 1985) ixa)
Option {getOption = Just (Price {ptitle = "The Northern Dog", pcost = 2})}
fromList ["Bernice McNeilly","Donna Arnold","Thomas Brown"]
Sum {getSum = 3}