Haskellで "findM"を実装していますか？

Question

基本的にはmapMのような機能を探しています。リストのすべての値をパラメータとして一連のモナドアクションを実行し、各モナド関数はm (Maybe b)を返します。しかし、最初のパラメータの後で、関数がJustの値を返し、その後はそれ以上実行せず、その値を返すようにするために、この関数を停止したい。

まあ、おそらくちょうど型シグネチャを表示することが容易になります：

bは最初の Just値である

findM :: (Monad m) => (a -> m (Maybe b)) -> [a] -> m (Maybe b) 

。結果のMaybeは、find ing（空のリストの場合など）からのものであり、Monadic関数によって返されたMaybeとは関係ありません。

ライブラリ関数の簡単なアプリケーションでこれを実装することはできません。私は仕事であろう

findM f xs = fmap (fmap fromJust . find isJust) $ mapM f xs 

を使用することができますが、私はこれをテストし、モナド行動の全てがfindを呼び出す前に実行されているので、私はここに怠惰に頼ることができないようです。

ghci> findM (\x -> print x >> return (Just x)) [1,2,3] 
1 
2 
3 
-- returning IO (Just 1) 

この関数を実装する最良の方法は、最初の「返却」後にモナドのアクションを実行しないものですか？どうなる何か：

ghci> findM (\x -> print x >> return (Just x)) [1,2,3] 
1 
-- returning IO (Just 1) 

かさえ、理想的に、

ghci> findM (\x -> print x >> return (Just x)) [1..] 
1 
-- returning IO (Just 1) 

がうまくいけば、そこに明示的な再帰を使用していない答えは、可能な場合はライブラリ関数の組成物ですか？あるいはポイントフリーのでも？

Answer 1

単純なポイントフリーの解決策の1つは、MaybeT変圧器を使用しています。 m (Maybe a)が表示されたら、すぐにMaybeTにラップして、すぐにMonadPlusの機能をすべて取得できます。 MaybeTためmplusはまさに我々が必要ないので - msum我々が必要とまさにありません - それは最初のものはNothingが生じた場合にのみ、第二与えられたアクションが実行されます。

import Control.Monad 
import Control.Monad.Trans.Maybe 

findM :: (Monad m) => (a -> m (Maybe b)) -> [a] -> m (Maybe b) 
findM f = runMaybeT . msum . map (MaybeT . f) 

---

アップデート：この場合、私たちを私たちが必要とするセマンティクを持っているモナド変圧器（MaybeT）が存在することは幸運でした。しかし、一般的なケースでは、そのような変圧器を構築することは不可能である可能性がある。 MonadPlusには、他のモナド操作に関して満足しなければならないいくつかの法律があります。しかし、実際にはMonadPlusは必要ないので、すべてが失われるわけではありません。必要なのは、monoidで折り畳むだけです。

だから私たちはMaybeTを持っていない（できない）ふりをしましょう。ある一連の操作の第1の値を計算することは、Firstモノイドによって記述される。

newtype FirstM m a = FirstM { getFirstM :: m (Maybe a) } 
instance (Monad m) => Monoid (FirstM m a) where 
    mempty = FirstM $ return Nothing 
    mappend (FirstM x) (FirstM y) = FirstM $ x >>= maybe y (return . Just) 

このモノイドはまさにリストや他の構造体への参照せずにプロセスを説明しています。私たちは、ちょうど左の部分が値を持っている場合は、右側の部分を実行しませんモナドの変異体を作成する必要があります。今、私たちはちょうどこのモノイドを使用して、リストの上に折る：

findM' :: (Monad m) => (a -> m (Maybe b)) -> [a] -> m (Maybe b) 
findM' f = getFirstM . mconcat . map (FirstM . f) 

また、それは私たちがData.Foldableを使用して、より一般的な（そしてより短い）関数を作成することができます：

findM'' :: (Monad m, Foldable f) 
     => (a -> m (Maybe b)) -> f a -> m (Maybe b) 
findM'' f = getFirstM . foldMap (FirstM . f) 

Answer 2

これはそれを行う必要があります。

findM _ [] = return Nothing 
findM filter (x:xs) = 
    do 
     match <- filter x 
     case match of 
      Nothing -> findM filter xs 
      _ -> return match 

あなたは本当にそれが自由指し行う（編集として追加）したい場合は

Alternative数子を使用して、リスト内の何かを見つけるだろう、以下、 jozefgの答えのように折り目を使用すると、

findA :: (Alternative f) => (a -> f b) -> [a] -> f b 
findA = flip foldr empty . ((<|>) .) 

私の事、私たちは(Monad m) => m . Maybeのインスタンスを作ることができませんAlternativeが、我々は、既存の機能がありますふりができます：あなたは再帰を気にしないならば、私はCirdecの答えが好きその後、我々はfindA

findM :: (Monad m) => (a -> m (Maybe b)) -> [a] -> m (Maybe b) 
findM = flip foldr (return Nothing) . ((<||>) .) 

Answer 3

と同じ静脈にfindMを定義することができ

-- Left biased choice 
(<||>) :: (Monad m) => m (Maybe a) -> m (Maybe a) -> m (Maybe a) 
(<||>) left right = left >>= fromMaybe right . fmap (return . Just) 
-- Or its hideous points-free version 
(<||>) = flip ((.) . (>>=)) (flip ((.) . ($) . fromMaybe) (fmap (return . Just))) 

が、私同等の折り畳みベースの答えはかなりきれいだと思います。

findM f = foldr test (return Nothing) 
    where test x m = do 
       curr <- f x 
       case curr of 
        Just _ -> return curr 
        Nothing -> m 

折り目をどれだけうまく理解しているかをテストします。

Answer 4

これはかなりうまく表現することができますMaybeTモナドトランス、Data.Foldableです。

import Data.Foldable (msum) 
import Control.Monad.Trans.Maybe (MaybeT(..)) 

findM :: Monad m => (a -> m (Maybe b)) -> [a] -> m (Maybe b) 
findM f = runMaybeT . msum . map (MaybeT . f) 

そして、あなたはMaybeTスタックを生成するために、検索機能を変更した場合、それも立派になっ：

findM' :: Monad m => (a -> MaybeT m b) -> [a] -> MaybeT m b 
findM' f = msum . map f 

またはポイント・フリーで：

findM' = (.) msum . map 

オリジナルバージョンをすることができ完全にポイントフリーになっていますが、かなり読めなくなります。

findM = (.) runMaybeT . (.) msum . map . (.) MaybeT