6

我正在寻找一个基本上类似于mapM列表的函数——它执行一系列单子操作，将列表中的每个值作为参数——并且每个单子函数都返回m (Maybe b)。但是，我希望它在导致函数返回Just值的第一个参数之后停止，之后不再执行，并返回该值。

好吧，只显示类型签名可能会更容易：

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

其中 b 是第一个Just值。结果Maybe中的 in 来自ing（如果是空列表等），与Monadic 函数find的返回无关。Maybe

我似乎无法通过直接应用库函数来实现这一点。我可以使用

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

这会起作用，但我对此进行了测试，似乎所有的单子动作都是在 call 之前执行的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)

希望有一个不使用显式递归的答案，如果可能的话，是库函数的组合吗？或者甚至是免费的？

4

4 回答 4

17

一种简单的无点解决方案是使用MaybeT变压器。每当我们看到m (Maybe a)我们可以把它包装进去MaybeT，我们立即得到所有MonadPlus的功能。因为mplusforMaybeT正是我们需要的——它只在第一个导致的情况下运行第二个给定的动作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 转换器 ( MaybeT)，它mplus具有我们需要的语义。但在一般情况下，可能无法构建这样的变压器。MonadPlus对于其他一元运算，有一些必须满足的规律。然而，一切都没有丢失，因为我们实际上不需要 a MonadPlus，我们只需要一个适当的幺半群来弃牌。

所以让我们假装我们没有（不能）拥有MaybeT. 计算某些操作序列的第一个值由Firstmonoid 描述。如果左边部分有值，我们只需要创建一个不会执行右边部分的一元变体：

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)
于 2013-09-01T08:12:21.327 回答
9

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

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

一个很好的小测试，测试你对折叠的理解程度。

于 2013-09-01T03:38:25.317 回答
6

这应该这样做：

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) . ((<||>) .)
于 2013-09-01T03:07:25.823 回答
5

这可以用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
于 2013-09-01T08:21:48.190 回答