Может ли монада быть комонадой?
Я знаю, что такое монада. Я думаю, что правильно обдумал, что такое комонада. (Или, скорее, то, что кажется достаточно простым; сложная часть состоит в том, чтобы понять, что в этом полезно...)
Мой вопрос: может ли что-то быть монадой и комонадой?
Я предвижу два возможных ответа:
- Да, это распространено и широко полезно.
- Нет, они выполняют такие разные работы, что не было бы никакой причины хотеть, чтобы что-то было и тем и другим.
Итак, что это?
5 ответов
Да. Превращение некоторых комментариев в ответ:
newtype Identity a = Identity {runIdenity :: a} deriving Functor
instance Monad Identity where
return = Identity
join = runIdentity
instance CoMonad Identity where
coreturn = runIdentity
cojoin = Identity
Reader и Writer - точные двойники, как показано
class CoMonoid m where
comempty :: (m,a) -> a
comappend :: m -> (m,m)
--every haskell type is a CoMonoid
--that is because CCCs are boring!
instance Monoid a => Monad ((,) a) where
return x = (mempty,x)
join (a,(b,x)) = (a <> b, x)
instance CoMonoid a => CoMonad ((,) a) where
coreturn = comempty
cojoin = associate . first comappend
instance CoMonoid a => Monad ((->) a) where
return = flip (curry comempty)
join f = uncurry f . comappend
instance Monoid a => CoMonad ((->) a) where
coreturn f = f mempty
cojoin f a b = f (a <> b)
Cofree Comonad дает некоторые структуры данных, которые могут быть полезны как Монады, так и Комонады:
data Cofree f a = a :< f (Cofree f a)
Каждый Cofree Comonad над функтором Alternative дает монаду - посмотрите пример здесь:
http://hackage.haskell.org/packages/archive/free/3.4.1/doc/html/Control-Comonad-Cofree.html
instance Alternative f => Monad (Cofree f) where
return x = x :< empty
(a :< m) >>= k = case k a of
b :< n -> b :< (n <|> fmap (>>= k) m)
Это дает нам, например, непустые списки в виде монад и комонад (вместе с непустыми f-ветвящимися деревьями и т. Д.).
Identity не альтернатива, но Cofree Identity дает бесконечный поток, и мы можем фактически дать другой экземпляр монады этому потоку:
http://hackage.haskell.org/packages/archive/streams/3.1/doc/html/Data-Stream-Infinite.html
data Stream a = a :> Stream a
instance Comonad Stream where
duplicate = tails
extend f w = f w :> extend f (tail w)
extract = head
instance Monad Stream where
return = repeat
m >>= f = unfold (\(bs :> bss) -> (head bs, tail <$> bss)) (fmap f m)
(обратите внимание, что приведенные выше функции не указаны в списках, а определены в streams пакет).
Точно так же стрелка читателя не является альтернативой, но Cofree ((->) r) дает машину Мура, а машины Мура также являются монадами и комонадами:
http://hackage.haskell.org/packages/archive/machines/0.2.3.1/doc/html/Data-Machine-Moore.html
data Moore a b = Moore b (a -> Moore a b)
instance Monad (Moore a) where
return a = r where r = Moore a (const r)
Moore a k >>= f = case f a of
Moore b _ -> Moore b (k >=> f)
_ >> m = m
instance Comonad (Moore a) where
extract (Moore b _) = b
extend f w@(Moore _ g) = Moore (f w) (extend f . g)
Какова же интуиция за всеми этими примерами? Ну, мы получаем комонадические операции бесплатно. Монадические операции, которые мы получаем, представляют собой все формы диагонализации. С альтернативой мы можем <|> вещи вместе, чтобы "смять" структуру, и волшебство "пустых" вещей, когда мы исчерпали структуру, чтобы смять. Это позволяет нам работать в конечных случаях. В отсутствие альтернативы нам нужно иметь неопределенное количество структуры, так что независимо от того, сколько операций "соединения" (которые мы можем рассматривать как сплайсинг или замену), которые мы выполняем, всегда есть больше места для размещения склеенных элементов (как в Отель Hilbert: http://www.encyclopediaofmath.org/index.php/Hilbert_infinite_hotel).
Соответственно, каждый Comonad порождает связанную монаду (хотя я считаю это более любопытным):
http://hackage.haskell.org/packages/archive/kan-extensions/3.1.1/doc/html/Control-Monad-Co.html
Есть много интересных структур, которые являются Monad и Comonad,
Identity Функтор был указан здесь несколькими другими людьми, но есть нетривиальные примеры.
WriterMonad играет Readerроль как Comonad,
instance Monoid e => Monad ((,) e)
instance Comonad ((,) e)
ReaderMonad играет Writerроль как Comonad,
instance Monad ((->) e)
instance Monoid e => Comonad ((->)e)
Непустые списки также образуют как монаду, так и комонаду и фактически являются частным случаем более крупной конструкции, включающей бесплатные комонады. Identity Случай также может рассматриваться как частный случай этого.
Есть также различные Yoneda а также Codensity-подобные конструкции, основанные на расширениях Кан, которые работают для преобразования монад и комонад, хотя они предпочитают одну или другую с точки зрения операционной эффективности.
У меня также есть адаптер, который преобразует произвольную комонаду в монадный преобразователь. К сожалению, в Хаскеле обратное преобразование невозможно.
В линейной алгебре есть понятие биалгебры. В идеале, если у нас есть что-то, что формирует Monad и Comonad и мы хотим использовать эти операции вместе без рассуждений на индивидуальной основе, хотелось бы, чтобы return а также join являются Comonad Coalgebras и, следовательно, что extract а также duplicate являются Monad алгебры. Если эти условия выполняются, вы можете рассуждать о коде, который имеет Monad f а также Comonad f ограничивает и смешивает комбинаторы от каждого без индивидуального подхода.
Это зависит от того, что вы считаете "монадой". Если вы спросите "возможно ли, чтобы тип был экземпляром обоих Monad а также Comonad сразу?"тогда да. Вот тривиальный пример.
newtype Id a = Id a
instance Monad Identity where
return = Id
(Id a) >>= f = f a
instance Comonad Identity where
extract (Id a) = a
extend f ida = Id (f ida)
Если вы имеете в виду математически, то монада - это тройка (X, return, bind) где X это тип и return а также bind следуйте типам и законам, которые вы ожидаете. Точно так же (X, extend, extract), Я только что продемонстрировал, что Xs может быть одинаковым, но так как типы extend а также return или же extract а также bind разные, они не могут быть одинаковыми функциями. Так что математическая монада никогда не может быть комонадой.
Разобравшись с предложением Хаммера, кажется, что достаточно просто написать функцию [x] -> [[x]], Например,
map (\ x -> [x])
будет работать просто отлично. Так что, похоже, списки могут образовывать комонаду. Ах, но подожди. Это обрабатывает cojoin, но что насчет coreturn :: [x] -> x? По- видимому, именно поэтому только непустые списки образуют комонаду.
Это дает нам функцию cobind с типом ([x] -> x) -> [x] -> [x], Интересно, что Google не знает о такой функции. И все же у нас уже есть concatMap :: (x -> [x]) -> [x] -> [x], Я не вижу непосредственного использования функции cobind, но могу представить, что она существует.
Я все еще пытаюсь сосредоточиться на комонаде и на чем она может быть полезна. Ответы до сих пор дали мне кое-что подумать...