wdrażanie "findM" w Haskell?

Question

Szukam funkcji, która zasadniczo jest podobna do mapM na liście - wykonuje serię monadycznych akcji, przyjmując każdą wartość na liście jako parametr - a każda funkcja monadyczna zwraca m (Maybe b). Chcę jednak, aby zatrzymał się po pierwszym parametrze, który powoduje, że funkcja zwraca wartość Just, a nie wykonuje więcej po tym i zwraca tę wartość.

Cóż, to chyba łatwiej będzie po prostu pokazać podpis typu:

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

gdzie b jest pierwszą wartość Just. Maybe w wyniku pochodzi z find (w przypadku pustej listy itp.) I nie ma nic wspólnego z Maybe zwróconym przez funkcję Monadic.

Nie mogę tego wdrożyć z prostym zastosowaniem funkcji bibliotecznych. Mógłbym użyć

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

która będzie działać, ale ja testowałem to i wydaje się, że wszystko z monadycznych czynności wykonywane są przed wywołaniem find, więc nie mogę polegać na lenistwo tutaj.

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

Jaki jest najlepszy sposób realizacji tej funkcji, która nie będzie wykonywać monadycznych działań po pierwszym "sprawiedliwym" zwrocie? Coś, co zrobić:

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

lub nawet najlepiej,

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

Mam nadzieję, że jest to odpowiedź, która nie korzysta z wyraźną rekurencji i są kompozycje funkcji bibliotecznych jeśli to możliwe? A może nawet bez punktu? jeden?

Answer 1

Jednym prostym, pozbawionym punktu rozwiązaniem jest zastosowanie transformatora MaybeT. Ilekroć widzimy m (Maybe a) możemy zawinąć go do MaybeT i otrzymujemy natychmiast wszystkie funkcje MonadPlus. Od mplus dla MaybeT robi dokładnie musimy - uruchamia drugą daną akcję tylko wtedy, gdy pierwszy z nich spowodowało Nothing - msum robi dokładnie to, czego potrzebujemy:

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) 

---

Aktualizacja: W tym przypadku mieli szczęście, że istnieje transformator monady (MaybeT), którego mplus ma właśnie taką semantyczną, jakiej potrzebujemy. Ale w ogólnym przypadku może się okazać, że nie będzie możliwe zbudowanie takiego transformatora. MonadPlus ma pewne prawa, które muszą być spełnione w odniesieniu do innych operacji monadycznych. Jednak wszystko nie jest stracone, ponieważ właściwie nie potrzebujemy MonadPlus, wszystko czego potrzebujemy to właściwe monoid spasować.

Więc udawaj, że nie mamy (nie może) mieć MaybeT. Obliczanie pierwszej wartości niektórych sekwencji operacji opisano w monoidzie First. Musimy tylko zrobić jednowartościowy wariant, który nie wykona odpowiednią część, jeśli lewa część ma wartość:

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) 

Ten monoid dokładnie opisuje proces bez jakiegokolwiek odniesienia do list lub innych struktur. Teraz tylko zagiąć listę za pomocą tego monoid:

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

Ponadto, pozwala nam stworzyć funkcję bardziej ogólny (a nawet krótszy) używając Data.Foldable:

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

Answer 2

ten powinien zrobić:

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

Jeśli naprawdę chcesz zrobić to wskazuje free (dodawany jako Edit)

Poniżej znajdzie coś na liście za pomocą Alternative funktor, stosując jako krotnie w odpowiedzi jozefg za

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

I nie rzecz, którą można zrobić (Monad m) => m . Maybe instancję Alternative, ale możemy udawać, nie istniejąca funkcja:

-- 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))) 

Wtedy możemy zdefiniować findM w tym samym duchu jak findA

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

Answer 3

Lubię odpowiedź Cirdec, jeśli nie masz nic rekursji, ale uważam, że równoważna, oparta na fałdach odpowiedź jest całkiem ładna.

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

Niezły test, jak dobrze rozumiesz fałdy.

Answer 4

ta może być wyrażona całkiem ładnie z transformatorem monadowym MaybeT i 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) 

A jeśli zmienisz funkcję wyszukiwania do wyprodukowania MaybeT stos, staje się jeszcze ładniejszy:

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

lub w punkcie wolne:

findM' = (.) msum . map 

Oryginalna wersja może być w pełni bez punktu, ale staje się całkiem nieczytelny:

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