[Haskell-cafe] Search monad
Edsko de Vries
devriese at cs.tcd.ie
Mon Mar 19 13:11:19 EDT 2007
Hey,
I have a structure containing Xs in various places, like so
data X
data Structure = Structure .. [X] .. [X] ..
And I defined mapStructure
mapStructure :: (X -> X) -> (Structure -> Structure)
I then wanted to use mapStructure to define queries as well as
transformations on structures. I generalized mapStructure to
mapStructureM:
mapStructure :: Monad m => (X -> m X) -> (Structure -> m Structure)
and then defined the following search monad:
> data Search f a b = Found (f a) b
>
> class Monad (m a) => SearchMonad m a where
> found :: a -> m a a
>
> fromSearch :: Search f a b -> f a
> fromSearch (Found a _) = a
>
> search :: (SearchMonad m a) => (a -> Bool) -> a -> m a a
> search f a
> | f a = found a
> | otherwise = return a
Instances of the monad for finding one and for finding all elements:
> instance SearchMonad (Search Maybe) a where
> found a = Found (Just a) a
>
> instance SearchMonad (Search []) a where
> found a = Found [a] a
>
> instance Monad (Search Maybe a) where
> return b = Found Nothing b
> Found (Just a) a' >>= f = case f a' of
> Found _ b -> Found (Just a) b
> Found Nothing a' >>= f = f a'
>
> instance Monad (Search [] a) where
> return b = Found [] b
> Found as a' >>= f = case f a' of
> Found as' b -> Found (as ++ as') b
Here is a simple sample session with ghci
*Util> fromSearch $ mapM (search even) [1,3,5] :: Maybe Int
Nothing
*Util> fromSearch $ mapM (search even) [1,2,3,4,5] :: Maybe Int
Just 2
*Util> fromSearch $ mapM (search even) [1,2,3,4,5] :: [Int]
[2,4]
What I'm wondering about is if this monad is an instance of a more general monad(if so, which one?), and generally if people have any comments about these definitions.
Thanks!
Edsko
More information about the Haskell-Cafe
mailing list