Отображение функций с помощью монад - PullRequest
Новая
       9

Отображение функций с помощью монад

1 голос
/ 29 февраля 2020

У меня есть следующий код: 

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:

Я, вероятно, что-то упускаю из базовых c относительно mapping более Monads.

1 Ответ

0 голосов
/ 02 марта 2020

Запись 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. Стандартный способ применения функции monadi c a -> m b к списку [a] - это выполнить обход, используя mapM или traverse. (В прежние времена первый был для монад, а второй - для аппликативных, но теперь, когда все монады являются аппликативными, предпочтительным является traverse.) В частности, с этим загруженным скелетом мы можем проверить это выражение в GHCi: 1019 * 

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

Чтобы свернуть списки списков, мы хотим применить concat «под» монадой. К счастью, монады являются функторами, поэтому 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]))

под монадой: 

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

Теперь мы хотим применить сокращение r к карте. Это немного сложно. Если мы попытаемся применить mapWithKey под монадой так же, как мы это сделали с concat и combineByKey, мы получим дополнительный нежелательный слой монады: 

> :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 извлекается из монады и имеет тип: 

mymap :: Map K [V]
mymap = undefined

Если мы использовали mapWithKey для применения редуктора : 

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

мы имеем структуру элементов monadi c. Поскольку Map является проходимым, мы можем вытянуть монаду наружу с помощью sequence: 

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

Это почти возвращаемое значение, которое мы хотели получить от mapReduceM. Нам просто нужно изменить карту на список под монадой: 

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

В конце, наше определение mapReduceM - это завершенный блок do: 

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

This можно преобразовать в форму без точек, например: 

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