{-# LANGUAGE ScopedTypeVariables #-}
module Data.Find.Linear
 ( search, searchM
 ) where

import           Data.Functor.Identity

search :: forall a
        . (Ord a)
       => (Integer -> a) -- ^ Read a value at
       -> (Integer, Integer) -- ^ (min, max)
       -> a -- ^ The value we're looking for
       -> Maybe Integer
search r rng t = runIdentity $ searchM (pure . r) rng t

searchM :: forall m a
         . (Monad m, Ord a)
        => (Integer -> m a) -- ^ Read a value at
        -> (Integer, Integer) -- ^ (min, max)
        -> a -- ^ The value we're looking for
        -> m (Maybe Integer)
searchM r (rmin, rmax) t =
    go rmin rmax
  where
    go :: Integer -> Integer -> m (Maybe Integer)
    go l h | l >  h = pure Nothing
    go l h | l <= h = do
      vl <- r l
      if vl == t
      then pure $ Just l
      else go (l+1) h