与 Monad 的函数映射

Question

我有以下代码：

type Mapper a k v = a -> [(k,v)]
type Reducer k v = k -> [v] -> [v]


mapReduce :: Ord k => Mapper a k v -> Reducer k v -> [a] -> [(k,[v])]
mapReduce m r = reduce r . shuffleKeys . concatMap (map listifyVal . m)
  where listifyVal (k,v) = (k,[v])
        shuffleKeys = Map.fromListWith (++)
        reduce r = Map.toList . Map.mapWithKey r

我得到了 Monad 类型

   type MapperM m a k v = a -> m [(k,v)]
   type ReducerM m k v = k -> [v] -> m [v]

而且我需要转换现有代码才能使用 Monad

mapReduceM :: (Ord k, Monad m) => MapperM m a k v -> ReducerM m k v -> [a] -> m [(k,[v])]

我一直在转换表达式 concatMap (map listifyVal . m) 我写了这个辅助函数

listifyValM:: (Ord k, Monad m) => m(k,v) ->  m(k,[v])                        
listifyValM mkv = do
                    (k,v) <- mkv
                    return (k,[v])

并尝试了

 mapReduceM :: (Ord k, Monad m) => MapperM m a k v -> ReducerM m k v -> [a] -> m [(k,[v])]
 mapReduceM m r input =  do      
                            let step0 =  (map listifyValM )                                                  
                            return []

但我连这个（非常偏的）简单的东西都无法作为入门者使用。我得到：

  Could not deduce (Ord k0) arising from a use of `listifyValM'
  from the context: (Ord k, Monad m)
    bound by the type signature for:

我可能遗漏了一些关于 mapping 超过 Monads 的基本信息。

Answer 1

从头开始编写 mapReduceM 可能比尝试机械转换 mapReduce 更容易。你想要：

mapReduceM :: (Monad m, Ord k) => MapperM m a k v -> ReducerM m k v -> [a] -> m [(k,[v])]
mapReduceM m r as = ...

因此，让我们假设以下类型的参数并尝试构建函数：

m :: a -> m [(k,v)]
r :: k -> [v] -> m [v]
as :: [a]

创建一个使用具体类型的框架文件会很有帮助，它可以让我们在 GHCi 中键入检查表达式：

import Data.Map (Map)
import qualified Data.Map as Map

data A
data K = K deriving (Eq, Ord)
data V
data M a
instance Functor M
instance Applicative M
instance Monad M

m :: A -> M [(K,V)]
m = undefined
r :: K -> [V] -> M [V]
r = undefined
as :: [A]
as = undefined

显然，我们需要将 as 的元素传递给唯一可以接受它们的可用函数，即 m。将一元函数 a -> m b 应用于列表 [a] 的标准方法是使用 mapM 或 traverse 执行遍历。（在过去，前者是针对 monad 的，后者是针对 applicative 的，但是现在所有的 monad 都是 applicative，所以 traverse 是首选。）具体来说，加载了这个骨架后，我们可以在 GHCi 中键入检查这个表达式:

> :t traverse m as
traverse m as :: M [[(K, V)]]

要折叠列表的列表，我们要应用 concat "under" monad。幸运的是，monad 是函子，所以 fmap（或其同义词 (<$>)）可以做到：

> :t concat <$> traverse m as
concat <$> traverse m as :: M [(K, V)]

现在，我们想通过常用键将其加载到地图中。换句话说，我们要应用纯函数：

combineByKey :: [(K, V)] -> Map K [V]
combineByKey = Map.fromListWith (++) . map (\(k,v) -> (k,[v]))

在 monad 下：

> :t combineByKey . concat <$> traverse m as
combineByKey . concat <$> traverse m as :: M (Map K [V])

现在，我们要对地图应用缩减 r。这有点棘手。如果我们尝试以与 concat 和 combineByKey 相同的方式在 monad 下应用 mapWithKey，我们会得到一个额外的不需要的 monad 层：

> :t Map.mapWithKey r . combineByKey . concat <$> traverse m as
Map.mapWithKey r . combineByKey . concat <$> traverse m as
  :: M (Map K (M [V]))
     ^---------^---------- two monad layers

在这里，do符号可以帮助我们完成这个过程：

do mymap <- combineByKey . concat <$> traverse m as
   ...

在这里，mymap 被从 monad 中拉出来，所以有类型：

mymap :: Map K [V]
mymap = undefined

如果我们使用mapWithKey来应用减速器：

> Map.mapWithKey r mymap
Map.mapWithKey r mymap :: Map K (M [V])

我们有一个单元素结构。因为 Map 是可遍历的，所以我们可以用 sequence:

将 monad 拉到外面

> sequence $ Map.mapWithKey r mymap
sequence $ Map.mapWithKey r mymap :: M (Map K [V])

这几乎我们想要从 mapReduceM 得到的 return 值。我们只需要将map改成monad下的list即可：

> Map.toList <$> (sequence $ Map.mapWithKey r mymap)
Map.toList <$> (sequence $ Map.mapWithKey r mymap) :: M [(K, [V])]

最后，我们定义的mapReduceM就是完成的do-block：

mapReduceM :: (Monad m, Ord k) => MapperM m a k v -> ReducerM m k v -> [a] -> m [(k,[v])]
mapReduceM m r as = do
  mymap <- combineByKey . concat <$> traverse m as
  Map.toList <$> (sequence $ Map.mapWithKey r mymap)
  where combineByKey :: (Ord k) => [(k, v)] -> Map k [v]
        combineByKey = Map.fromListWith (++) . map (\(k,v) -> (k,[v]))

这可以转换为无点形式，如下所示：

import Control.Monad

mapReduceM :: (Monad m, Ord k) => MapperM m a k v -> ReducerM m k v -> [a] -> m [(k,[v])]
mapReduceM m r =
  traverse m >=>                       -- apply the mapper
  pure . combineByKey . concat >=>     -- combine keys
  sequence . Map.mapWithKey r >=>      -- reduce
  pure . Map.toList                    -- convert to list

  where combineByKey :: (Ord k) => [(k, v)] -> Map k [v]
        combineByKey = Map.fromListWith (++) . map (\(k,v) -> (k,[v]))

与 Monad 的函数映射

Function mapping with Monads

monads

haskell