Переупаковка монад - какой-нибудь общий способ?

Question

Учитывая две монады, Monad m и Monad n, я хотел бы преобразовать m (n a) в n (m a).Но, похоже, нет общего способа, потому что и (>>=), и return имеют дело только с одним типом монад, и хотя (>>=) позволяет извлекать контент из монады, вы должны упаковать его обратно в тот же тип монады, чтобы он мог бытьзначение результата.

Однако, если мы установим для m фиксированный тип, задание станет простым.Возьмем Maybe в качестве примера:

reorder :: (Monad n) => Maybe (n a) -> n (Maybe a)
reorder Nothing = return Nothing
reorder (Just x) = do
    x' <- x
    return $ Just x'

Или список:

reorder :: (Monad n) => [n a] -> n [a]
reorder [] = return []
reorder (x:xs) = do
    x'  <- x
    xs' <- reorder xs
    return (x':xs')

Нетрудно увидеть, у нас здесь есть образец.Чтобы быть более очевидным, напишите это Applicative способом, и это не более чем применение конструктора данных к каждому элементу:

reorder (Just x) = Just <$> x
reorder (x:xs) = (:) <$> x <*> (reorder xs)

Мой вопрос: существует ли класс типов haskell для описания таких операций?или я должен сам изобрести колесо?

Я провел краткий поиск в документации GHC и не нашел ничего полезного для этой темы.

Answer 1

Data.Traversable обеспечивает то, что вы ищете:

sequenceA :: (Traversable t, Applicative f) => t (f a) -> f (t a)

GHC даже обеспечивает поддержку автоматического получения экземпляров:

{-# LANGUAGE DeriveFunctor, DeriveFoldable, DeriveTraversable #-}
import Data.Foldable
import Data.Traversable

data List a = Nil | Cons a (List a) 
  deriving(Functor, Foldable, Traversable)

Answer 2

Быстрый поиск в Google для (Monad m, Monad n) => m (n a) -> n (m a) показал мне, что есть несколько функций, которые (примерно) соответствуют подписи, которую вы ищете:

1. Data.Traversable.sequence :: (Traversable t, Monad m) => t (m a) -> m (t a);
2. Data.Traversable.sequenceA :: Applicative f => t (f a) -> f (t a);
3. Contro.Monad.sequence :: Monad m => [ma] -> m [a] (также экспортируется с помощью Prelude).

И [a], и Maybe a являются экземплярами для прохождения, так что ваши функции переупорядочения являются просто приложениями Data.Traversable.sequence.Например, можно написать:

ghci> (Data.Traversable.sequence $ Just (return 1)) :: IO (Maybe Int)
Just 1
it :: Maybe Int

ghci> (Data.Traversable.sequence $ Just ([1])) :: [Maybe Int]
[Just 1]
it :: [Maybe Int]

ghci> (Data.Traversable.sequence $ [Just 1]) :: Maybe [Int]
Just [1]
it :: Maybe [Int]

Обратите внимание, что объявление определенного класса равно class (Functor t, Foldable t) => Traversable t, и если вы посмотрите также на типы двух других функций, это не похоже на то, что выпоиск может быть выполнен в общем виде для всех монад m и n без ограничений / предварительных условий.

Answer 3

Это невозможно сделать в общем: хорошим примером монады, которая не может этого сделать, является монада читателя (или функции). Это потребовало бы определения следующей функции:

impossible :: (r -> IO a) -> IO (r -> a)

Непросто доказать, что функция не может быть реализована. Но интуитивно, проблема в том, что все, что IO должно быть сделано в возвращаемом значении, должно быть сделано , прежде чем мы узнаем, что параметр r равен . Так что impossible readFile должен был бы привести к чистой функции FilePath -> String, прежде чем он знал, какие файлы открывать. Ясно, что, по крайней мере, impossible не может делать то, что вы хотите.

Answer 4

Не все монады могут коммутировать таким образом. Дистрибутив Эдварда Кметта предоставляет класс типов Distributive для конструкторов типов, аналогичный тому, что вы хотите (упрощенно):

class Functor g => Distributive g where
  distribute  :: Functor f => f (g a) -> g (f a)
  collect     :: Functor f => (a -> g b) -> f a -> g (f b)

Определения по умолчанию предоставляются для distribute и collect, написанных в терминах друг друга. Я нашел этот пакет в поисках hayoo для нужной сигнатуры типа .