module Search where

import Control.Monad.Instances
import Coalgebra

-- from http://math.andrej.com/2008/11/21/a-haskell-monad-for-infinite-search-in-finite-time/
-- Here we search for elements x such that p x = True
-- If there is none, it may lie
newtype Searchable a = S {find :: (a -> Bool) -> a}

search :: Searchable a -> (a -> Bool) -> Maybe a
search xs p = let x = find xs p in if p x then Just x else Nothing

forsome, forevery :: Searchable a -> (a -> Bool) -> Bool
forsome xs p = p(find xs p)
forevery xs p = not(forsome xs (\x -> not(p x)))