2015-08-31 9 views
12

В this answer на "Может ли монада быть комонадой?" мы видим, чтоКаждая свободная монада над ??? функтор дает comonad?

Каждый CofreeComonad над Alternative functor дает монаду.

Что было бы двойным в этом вопросе? Есть ли класс функторов, который автоматически делает свободную монаду над ними комонадой?

+0

Догадка: 'empty ::() -> fa',' (<|>) :: (fa, fa) -> fa' - обращая стрелки, мы получаем 'fa ->()', 'fa - > (fa, fa) ', что не самое полезное в ** Hask **, хотя в системах линейного типа оно имеет смысл. – luqui

+0

@luqui Последнее замечание о системах линейного типа интересно, не могли бы вы рассказать об этом? –

+3

Контравариантная версия Альтернативы [Разрешимая] (http://hackage.haskell.org/package/contravariant-1.3.2/docs/Data-Functor-Contravariant-Divisible.html#t:Decidable). Не уверен, как это сделать. – danidiaz

ответ

4

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

Построение, на которое вы ссылаетесь, на самом деле нуждается в довольно небольшом количестве, поэтому давайте откажемся от багажа Хаска и работаем в следующей общности. Пусть

  • (C, ⊗, 1) моноидальная категория

  • F: C -> C моноид-значного функтор, то есть, есть карты 1 -> FX и FX ⊗ FX -> FX, которые являются естественными в X и являются унитарными и ассоциативными

Определить TX = X ⊗ F (TX). Предположим, что это рекурсивное определение имеет смысл как-то и мы можем сделать рекурсивные определения на Т. Тогда мы можем сделать T в монады со следующими картами структуры:

  • единицы заданной

    X = X ⊗ 1 
        -> X ⊗ F(TX)   [unit map of F] 
         = TX 
    
  • присоединиться данный от

    T(TX) = TX ⊗ F(TTX) 
         = X ⊗ F(TX) ⊗ F(TTX) 
        -> X ⊗ F(TX) ⊗ F(TX) [join recursively under F] 
        -> X ⊗ F(TX)   [multiplication of F] 
         = TX 
    

Когда ⊗ есть декартово произведение, эта конструкция является м onad на свободном comonad на альтернативном функторе, на который вы ссылаетесь. Фактически, Применительная часть Альтернативной структуры не имеет значения. Нужны только классные методы Альтернативы (плюс Functor): моноиднозначный функтор. Поэлементно, шаги, которые составляют присоединиться, как описано выше, дается

(x :< xs) :< xss -> (x :< xs, xss) 
        -> (x, xs, xss) 
        -> (x, xs, fmap join xss) 
        -> (x, xs <|> fmap join xss) 
        -> x :< (xs <|> fmap join xss) 

и это легко видеть (установив k = id) согласиться с

(a :< m) >>= k = case k a of 
        b :< n -> b :< (n <|> fmap (>>= k) m) 

Поскольку наша первоначальная структура была настолько мала, , он легко дуализирован. Так пусть (C, ⊗, 1) по-прежнему моноидальная категория, но теперь предположит

  • G: С -> С а comonoid многозначного функтор, то есть, есть карты GX -> 1 и GX -> GX ⊗ GX, которые являются естественными в X, и counital и coassociative

Тогда можно определить UX = X ⊗ G (UX) (опять же при условии, что это каким-то образом имеет смысл) и двумя конструкциями оснащать U со структурой комонад. Это в некотором смысле настоящий ответ здесь, но для решения вашего конкретного вопроса мы должны рассмотреть, что происходит для некоторых конкретных выборов ⊗.

Предположим сначала, что ⊗ снова является декартовым произведением. Тогда каждый функтор G кономиозначен однозначно (неотрицательность заставляет GX -> GX x GX быть диагональю). Итак, для любого функтора G мы получаем comonad UX = X x G (UX). На самом деле это оказывается просто обычной cofree comonad на конструкторе функтора (оправдывая часть «cofree comonad» вашего лозунга, а если F моноиднозначна, мы можем установить G = F, а G автоматически комонидозначна, а затем T и U имеют один и тот же базовый функтор).

Dally, если ⊗ - копроизведение ⨿, то любой G, который является кономиозначным для ⨿, также моноиднозначен для ⨿ единственным образом, поэтому UX = X ⨿ G (UX) также является свободной монадой на G как а также быть comonad.

Но в Hask единичный объект для ⨿ является пустым типом 0, а контингент G должен иметь тип GX -> 0, что возможно только тогда, когда GX = 0 для всех X (это верно в любом декартовой замкнутой категории). Итак, интересных примеров этой конструкции в Хаске нет. Это отсутствие симметрии является типичным явлением категорий, которые напоминают Set.