在Haskell中实现"findM"？

Question

我正在寻找一个基本上就像mapM在列表上的函数- 它执行一系列monadic动作,将列表中的每个值作为参数 - 并且每个monadic函数返回m (Maybe b).但是,我希望它在导致函数返回Just值的第一个参数之后停止,之后不再执行,并返回该值.

好吧,只显示类型签名可能更容易:

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

其中b是第一个Just值.将Maybe在结果是从findING(在一个空列表等的情况下),并没有任何跟Maybe在一元函数返回.

我似乎无法通过直接应用库函数来实现它.我可以用

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

这将是有效的,但我测试了这一点似乎所有的monadic动作都是在调用之前执行的find,所以我不能在这里依赖懒惰.

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

实现此函数的最佳方法是什么,在第一次"正常"返回后不会执行monadic操作？可以做的事情:

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

一个简单的无点解决方案是使用MaybeT变压器.每当我们看到m (Maybe a)我们可以将其包装进去MaybeT并MonadPlus立即获得所有功能.由于mplus对MaybeT不正是我们所需要的-它运行仅当第一个导致第二个给定的动作Nothing- msum不正是我们所需要的:

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)

更新:在这种情况下,我们很幸运,存在一个monad transformer(MaybeT),mplus它只有我们需要的语义.但在一般情况下,可能无法构建这样的变压器.MonadPlus有一些法律必须满足其他monadic操作.然而,一切都没有丢失,因为我们实际上并不需要a MonadPlus,我们所需要的只是一个合适的幺半群.

所以我们假装我们不会(不能)拥有MaybeT.计算一些操作序列的第一个值由Firstmonoid 描述.如果左边的部分有一个值,我们只需要制作一个不会执行正确部分的monadic变体:

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)

这个幺半群确切地描述了该过程,而没有引用列表或其他结构.现在我们只使用这个monoid折叠列表:

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

如果你不介意递归,我喜欢Cirdec的答案,但我认为基于折叠的等效答案非常漂亮.

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

如何理解折叠的一个很好的小测试.

Answer 3

这应该这样做:

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,但我们可以假装有一个现有的功能:

-- 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用同样的方式定义findA

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

Answer 4

这可以用MaybeTmonad变换器很好地表达出来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