Устройство записи монад m и Любой e, категорически двойной?
Я заметил, что существует двойное отношение между Writer m и Either e монады. Если m является моноидом, то
unit :: () -> m
join :: (m,m) -> m
может использоваться для формирования монады:
return is composition: a -> ((),a) -> (m,a)
join is composition: (m,(m,a)) -> ((m,m),a) -> (m,a)
Двойной из () является Пустым (пустой тип), двойным из продукта является побочный продукт. Каждому типу e можно дать "comonoid" структуру:
unit :: Void -> e
join :: Either e e -> e
очевидным способом. Теперь,
return is composition: a -> Either Void a -> Either e a
join is composition: Either e (Either e a) -> Either (Either e e) a -> Either e a
и это Either e монада. Стрелки следуют точно за тем же шаблоном.
Вопрос: действительно ли возможно написать единственный общий код, который сможет выполнить обоих как Either e и как Writer m в зависимости от данного моноида?
3 ответа
Я бы не сказал, что эти монады категорически двойственны, а скорее, что они обе порождаются следующей конструкцией: дана моноидальная категория (C,, 1) и алгебра A в C, рассмотрим монаду, отправляющую X в A ⊗ X. В первом случае C - это Hask, ⊗ - это ×, а алгебра - моноид, а во втором случае C - это Hask, ⊗ - это (Either), а алгебра - это просто тип (каждый тип - это алгебра по-своему уникальным образом - это то, что вы называете «комоноидом», хотя обычно это означает что-то другое, см. ниже). Как обычно, я работаю в воображаемом мире, где ⊥ не существует, так что × на самом деле является продуктом и так далее. Вероятно, можно зафиксировать это общее обобщение с помощью подходящего класса типов для моноидальных категорий (я слишком устал, чтобы понять, какие дополнительные категории в данный момент пытается сделать в этом отношении) и тем самым одновременно определить Writer и Either как монады ( возможно по модулю новых типов).
Что касается категориального двойника Writer m - ну, это зависит от того, что вы хотите рассматривать как фиксированное, но наиболее вероятным кандидатом является структура комонад на (,) m без каких-либо условий на m:
instance Comonad ((,) m) where
coreturn (m, a) = a
cojoin (m, a) = (m, (m, a))
(обратите внимание, что здесь - это то место, где мы используем, что m является комоноидом, т. е. у нас есть отображения m → (), m → m × m).
Строго говоря, () и Пустота не двойственны - наличие ⊥ означает, что все типы населены, поэтому ⊥ является единственным обитателем Пустоты , что делает его конечным объектом. как и следовало ожидать. () содержит два значения, поэтому не имеет значения. Если вы махнете рукой ⊥, то () будет окончательным, а Пустота начальным, как и ожидалось.
Я тоже не думаю, что ваш пример является комоноидной структурой - я думаю, что сигнатура для комоноида должна быть примерно такой:
class Comonoid a
coempty :: a -> ()
coappend :: a -> (a, a)
Что, если вы рассматриваете, какими должны быть эквивалентные законы комоноидов, в итоге я думаю, что это бесполезно.
Вместо этого мне интересно, не связано ли то, что вы получаете, более тесно со стандартными моноидами сумма / произведение, чем с натуральными, применительно к алгебраическим типам данных? Пустота и Либо равны 0 / +, а () и (,) равны 1 / *.Но я не знаю, как оправдать остальное.
Вот код:
{-# LANGUAGE FlexibleInstances, EmptyDataDecls, MultiParamTypeClasses,
FunctionalDependencies, GeneralizedNewtypeDeriving, UndecidableInstances #-}
import Control.Arrow (first, second, left, right)
import Data.Monoid
data Void
data Iso a b = Iso { from :: a -> b, to :: b -> a}
-- monoidal category (Hask, m, unit)
class MonoidalCategory m unit | m -> unit where
iso1 :: Iso (m (m x y) z) (m x (m y z))
iso2 :: Iso x (m x unit)
iso3 :: Iso x (m unit x)
map1 :: (a -> b) -> (m a c -> m b c)
map2 :: (a -> b) -> (m c a -> m c b)
instance MonoidalCategory (,) () where
iso1 = Iso (\((x,y),z) -> (x,(y,z))) (\(x,(y,z)) -> ((x,y),z))
iso2 = Iso (\x -> (x,())) (\(x,()) -> x)
iso3 = Iso (\x -> ((),x)) (\((),x) -> x)
map1 = first
map2 = second
instance MonoidalCategory Either Void where
iso1 = Iso f g
where f (Left (Left x)) = Left x
f (Left (Right x)) = Right (Left x)
f (Right x) = Right (Right x)
g (Left x) = Left (Left x)
g (Right (Left x)) = Left (Right x)
g (Right (Right x)) = Right x
iso2 = Iso Left (\(Left x) -> x)
iso3 = Iso Right (\(Right x) -> x)
map1 = left
map2 = right
-- monoid in monoidal category (Hask, c, u)
class MonoidM m c u | m -> c u where
mult :: c m m -> m
unit :: u -> m
-- object of monoidal category (Hask, Either, Void)
newtype Eith a = Eith { getEith :: a } deriving (Show)
-- object of monoidal category (Hask, (,), ())
newtype Monoid m => Mult m = Mult { getMult :: m } deriving (Monoid, Show)
instance MonoidM (Eith a) Either Void where
mult (Left x) = x
mult (Right x) = x
unit _ = undefined
instance Monoid m => MonoidM (Mult m) (,) () where
mult = uncurry mappend
unit = const mempty
instance (MonoidalCategory c u, MonoidM m c u) => Monad (c m) where
return = map1 unit . from iso3
x >>= f = (map1 mult . to iso1) (map2 f x)
Использование:
a = (Mult "hello", 5) >>= (\x -> (Mult " world", x+1))
-- (Mult {getMult = "hello world"}, 6)
inv 0 = Left (Eith "error")
inv x = Right (1/x)
b = Right 5 >>= inv -- Right 0.2
c = Right 0 >>= inv -- Left (Eith {getEith="error"})
d = Left (Eith "a") >>= inv -- Left (Eith {getEith="a"})