不使用序列实现 mapM

Question

我目前正在尝试解决 20 Intermediate Haskell Excercises 练习，但在不使用 sequence.

我只能通过简单地应用 fmap 生成 [m b]，但我不知道如何继续：

moppy :: [a] -> (a -> m b) -> m [b]
moppy la f = furry' f la -- how do I transform [m b] to m [b] without sequence

谁能告诉我应该看哪个方向？

Answer 1

好吧，我不知道如何在不剧透的情况下做到这一点——所以这里有一个非常基本的/递归的定义：

moppy :: Monad m => [a] -> (a -> m b) -> m [b]
moppy [] _ = return []
moppy (x:xs) f = do
  y  <- f x
  ys <- moppy xs f
  return (y:ys)

它应该是不言自明的——请注意您需要 Monad m 约束（我认为您无论如何都需要它，因为没有它就变得相当不可能；））

Answer 2

当您开始仅使用 >>= 和 return 实施 mapM 时，也许它会有所帮助。你最终会得到类似于：

mapM' :: Monad m => (a -> m b) -> [a] -> m [b]
mapM' _ []     = return []
mapM' f (x:xs) =        f x           >>=
                 \y  -> mapM' f xs    >>=
                 \ys -> return (y:ys)

这样就如上位发帖者所说给了你答案。您需要做的就是更改参数的顺序：

moppy :: (Misty m) => [a] -> (a -> m b) -> m [b]      
moppy []     _ = unicorn []
moppy (x:xs) f = banana (\y -> banana (\ys -> unicorn (y:ys)) (moppy xs f)) (f x)

或者：

moppy :: (Misty m) => [a] -> (a -> m b) -> m [b]      
moppy []     _ = unicorn []
moppy (x:xs) f = (\y  -> (\ys -> unicorn (y:ys)) `banana` moppy xs f) `banana` f x

或者：

moppy :: (Misty m) => [a] -> (a -> m b) -> m [b]      
moppy []     _ = unicorn []
moppy (x:xs) f = let g y = let h ys = unicorn (y : ys)
                            in h `banana` moppy xs f
                  in g `banana` f x

Answer 3

在现代，正如本杰明霍奇森所说，我们应该使用 Applicative 来达到这个特定目的：

myMapM :: Applicative f
       => (a -> f b) -> [a] -> f [b]

我们希望 myMapM f [] 为 pure []（我们无法获得任何 b！），所以

myMapM f [] = pure []

现在我们进入问题的核心，找出递归步骤。我们要myMapM f (x : xs)执行f x，执行myMapM f xs，合并结果。所以

myMapM f [] = pure []
myMapM f (x : xs) = (:) <$> f x <*> myMapM f xs

当用列表做一些好的和有规律的事情时，我们经常可以只用 foldr:

myMapM f = foldr go (pure []) where
  go x r = (:) <$> f x <*> r

Answer 4

采取这种实施方式：

moppy :: Monad m => (a -> m b) -> [a] -> m [b]
moppy f xs = foldr g n xs 
  where
    n = return []
    g x mys = do {
      y  <- f x ;
      ys <- mys ;
      return (y:ys) }

(mys :: m [b] 因为 foldr g n (x:xs) = g x (foldr g n xs).)

（改编自 C9 讲座：Ralf Lämmel - Going Bananas [8 分 06 秒 - youtube）。

不使用序列实现 mapM

Implement mapM without using sequence

monads

haskell