MonadPlus：返す値の型をリスト、Maybeから選択できる関数

あどけない話 / QAで学ぶMonadの最後に MonadPlus を使って、返す型を指定することにより、検索結果をリストで返すか、Maybe で返すか指定できる関数が紹介されています。

• MonadPlus の定義

class Monad m => MonadPlus m where
   -- | the identity of 'mplus'.  It should also satisfy the equations
   --
   -- > mzero >>= f  =  mzero
   -- > v >> mzero   =  mzero
   --
   mzero :: m a 
   -- | an associative operation
   mplus :: m a -> m a -> m a

-- リストとMaybe に mzero と mplus が定義されています。
instance MonadPlus [] where
   mzero = []
   mplus = (++)

instance MonadPlus Maybe where
   mzero = Nothing

   Nothing `mplus` ys  = ys
   xs      `mplus` _ys = xs

• ツリーをなぞって条件に一致した値を返す。

import Control.Monad

data Tree = Empty | Tree Int Tree Tree
              deriving (Show)

-- ツリーをなぞって条件に一致した値をリストで返す。
search :: (Int -> Bool) -> Tree -> [Int]
search _ Empty = []
search p (Tree c l r)
  | p c       = search p l ++ [c] ++ search p r
  | otherwise = search p l ++  search p r

> search odd   (Tree 3 (Tree 2 Empty Empty) (Tree 1 Empty Empty))    -- => [3,1]
> search even  (Tree 3 (Tree 2 Empty Empty) (Tree 1 Empty Empty))    -- => [2]
> search (>0)  (Tree 3 (Tree 2 Empty Empty) (Tree 1 Empty Empty))    -- => [2,3,1]

-- mzero、mplus を使うと返す型の指定で検索結果をリストで返すか、Maybe で返すか指定できる。
msearch :: MonadPlus m => (Int -> Bool) -> Tree -> m Int
msearch _ Empty = mzero
msearch p (Tree c l r)
  | p c       = msearch p l `mplus` return c `mplus` msearch p r
  | otherwise = msearch p l `mplus` msearch p r

> msearch odd (Tree 3 (Tree 2 Empty Empty) (Tree 1 Empty Empty)) :: [Int]      -- => [3,1]
> msearch odd (Tree 3 (Tree 2 Empty Empty) (Tree 1 Empty Empty)) :: Maybe Int  -- => Just 3

-- リストをなぞって条件に一致した値をMonadPlusで返す。
mLsearch :: MonadPlus m => (Int -> Bool) -> [Int] -> m Int
mLsearch _ [] = mzero
mLsearch isCond (x:xs)
  | isCond x  = return x `mplus` mLsearch isCond xs
  | otherwise = mLsearch isCond xs

指定された型で値が返される。

-- リストで返す。
> mLsearch (==10) [0..20]  :: [Int]       -- => [10]
> mLsearch (>10)  [0..20]  :: [Int]       -- => [11,12,13,14,15,16,17,18,19,20]
> mLsearch (==99) [0..20]  :: [Int]       -- => []

-- Maybeで返す。
>  mLsearch (==10)  [0..20]  :: Maybe Int  -- => Just 10
>  mLsearch (==100) [0..20]  :: Maybe Int  -- => Nothing
>  mLsearch (>100)  [0..20]  :: Maybe Int  -- => Nothing