You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
16 lines
554 B
16 lines
554 B
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)))
|
|
|