Я знаю, что такое монада. Кажется, я правильно обдумал, что такое comonad. (Или, вернее, то, что кажется простым, сложная часть понимает, что полезно об этом...)
Мой вопрос: может ли быть монада и комонада?
Я предвижу два возможных ответа:
Итак, что это?
Да. Превращение некоторых комментариев в ответ:
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 дает некоторые структуры данных, которые полезны как Monads и Comonads:
data Cofree f a = a :< f (Cofree f a)
Каждый Cofree Comonad над альтернативным функтором дает Monad - см. пример здесь:
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)
Это дает нам, например. непустые списки как Monads и Comonads (вместе с непустыми 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 [email protected](Moore _ g) = Moore (f w) (extend f . g)
Итак, что такое интуиция за всеми этими примерами? Ну, мы бесплатно получаем comonadic операции. Монадические операции, которые мы получаем, - все формы диагонализации. С альтернативой мы можем <|> объединять вещи, чтобы "смазать" структуру, и магия "пустых" вещей, когда у нас кончается структура, чтобы смять. Это позволяет нам работать на конечных случаях. Не имея альтернативы, нам нужно иметь неопределенный объем структуры, так что независимо от того, сколько операций "присоединяться" (которые мы можем рассматривать как сплайсинг или замену), которые мы делаем, всегда больше места для размещения сплайсированных элементов (например, на Hilbert Hotel: 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 был отмечен здесь несколькими другими людьми, но есть нетривиальные примеры.
Writer Monad играет роль Reader как a Comonad.
instance Monoid e => Monad ((,) e)
instance Comonad ((,) e)
Reader Monad играет a Writer -подобную роль как Comonad.
instance Monad ((->) e)
instance Monoid e => Comonad ((->)e)
Непустые списки также образуют как монаду, так и комонаду и на самом деле являются частным случаем более крупной конструкции, включающей cofree comonads. Случай Identity также может рассматриваться как частный случай.
Существуют также различные конструкторы Yoneda и Codensity, основанные на расширениях Kan, которые работают для преобразования монад и comonads, хотя они предпочитают то или другое с точки зрения операционной эффективности.
У меня также есть адаптер, который преобразует произвольный comonad в монадный трансформатор. К сожалению, противоположная конверсия невозможна в Haskell.
В линейной алгебре существует понятие bialgebra. В идеале, если у нас есть что-то, что образует как Monad, так и Comonad, и мы хотим использовать эти операции вместе, не рассуждая в каждом конкретном случае, хотелось бы, чтобы return и join были Комонад-коалгебр и расширением, что 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 соответствуют типам и законам, которые вы ожидаете. Аналогично, comonad (X, extend, extract). Я только что продемонстрировал, что X может быть одинаковым, но поскольку типы extend и return или extract и bind различны, для них невозможно быть одинаковыми функциями. Поэтому математическая монада никогда не может быть комонадой.
Расширяясь по предложению Хаммера, кажется достаточно простым написать функцию [x] -> [[x]]. Например,
map (\ x -> [x])
будет работать нормально. Таким образом, похоже, что списки могут образовывать comonad. Ах, но подождите. Это обрабатывает cojoin, но как насчет coreturn :: [x] -> x? Это, по-видимому, является причиной того, что только непустые списки образуют comonad.
Это дает нам функцию cobind с типом ([x] -> x) -> [x] -> [x]. Интересно, что Hoogle не знает такой функции. И все же у нас уже есть concatMap :: (x -> [x]) -> [x] -> [x]. Я не вижу немедленного использования функции cobind, но я могу представить один существующий.
Я все еще пытаюсь обдумать вокруг comonad и что это может быть полезно для. Ответы до сих пор давали мне кое-что о чем подумать...