Является ли это свойство функтора более сильным, чем монада?

Ответ 1

Чтобы немного улучшить терминологию, я предлагаю называть эти функторы "жесткими", а не "связываемыми". Мотивация сказать "жесткая" будет объяснена ниже.

Определение

Функтор f называется жестким, если он имеет метод inject как показано. Обратите внимание, что у каждого функтора есть метод eject.

class (Functor f) => Rigid f where
  inject :: (a -> f b) -> f(a -> b)

  eject :: f(a -> b) -> a -> f b
  eject fab x = fmap (\ab -> ab x) fab

Закон "невырожденности" должен содержать:

eject . inject = id

свойства

Жесткий функтор всегда указан:

instance (Rigid f) => Pointed f where
  point :: t -> f t
  point x = fmap (const x) (inject id)

Если жесткий функтор аппликативный, то он автоматически монадический:

instance (Rigid f, Applicative f) => Monad f where
  bind :: f a -> (a -> f b) -> f b
  bind fa afb = (inject afb) <*> fa

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

Основными контрпримерами монадических функторов, которые не являются жесткими, являются Maybe и List. Это функторы, которые имеют более одного конструктора: такие функторы не могут быть жесткими.

Проблема с внедрением inject для Maybe заключается в том, что метод inject должен преобразовывать функцию типа a → Maybe b в Maybe(a → b) тогда как Maybe имеет два конструктора. Функция типа a → Maybe b может вернуть разные конструкторы для разных значений a. Тем не менее, мы должны построить значение типа Maybe(a → b). Если для некоторой a данная функция не выдаёт Nothing, у нас нет b поэтому мы не можем создать итоговую функцию a->b. Таким образом, мы не можем вернуть Just(a->b); мы вынуждены возвращать Nothing до тех пор, пока данная функция не выдаст Nothing даже для одного значения a. Но мы не можем проверить, что данная функция типа a → Maybe b производит Just(...) для всех значений a. Поэтому мы вынуждены Nothing возвращать во всех случаях. Это не удовлетворит закон невырожденности.

Таким образом, мы можем внедрить inject если ft является контейнером "фиксированной формы" (имеющим только один конструктор). Отсюда и название "жесткий".

Другое объяснение того, почему жесткость является более строгим, чем монадичность, заключается в рассмотрении естественно определенного выражения

(inject id) :: f(f a -> a) 

где id :: fa → fa. Это показывает, что у нас может быть f-алгебра fa → a для любого типа a, если она заключена в f. Это неправда, что любая монада имеет алгебру; например, различные "будущие" монады, а также монада IO описывают вычисления типа fa которые не позволяют нам извлекать значения типа a - у нас не должно быть метода типа fa → a даже если завернутый в f -container. Это показывает, что "будущие" монады и монада IO не являются жесткими.

Свойство, которое строго сильнее жесткости, это дистрибутивность одного из пакетов Э. Кметта. Функтор f является дистрибутивным, если мы можем поменять порядок как в p (ft) → f (pt) для любого функтора p. Жесткость - это то же самое, что возможность менять порядок только по отношению к функтору "читатель" rt = a → t. Итак, все дистрибутивные функторы жесткие.

Все дистрибутивные функторы обязательно представимы, что означает, что они эквивалентны функтору "читателя" c → t с некоторым фиксированным типом c. Однако не все жесткие функторы представимы. Примером является функтор g определенный как

type g t = (t -> r) -> t

Функтор g не эквивалентен c → t с фиксированным типом c.

Конструкции и примеры

Другими примерами жестких функторов, которые не представимы (т.е. Не являются "дистрибутивными"), являются функторы вида at → ft где a - любой контрактор, а f - жесткий функтор. Кроме того, декартово произведение и композиция двух жестких функторов снова жестки. Таким образом, мы можем привести множество примеров жестких функторов в классе экспоненциально-полиномиальных функторов.

Мой ответ на вопрос " Каков общий случай функции продвижения QuickCheck?" также перечислены конструкции жестких функторов:

1. f = Identity
2. если f и g оба жесткие, то произведение функтора ht = (ft, gt) также жесткое
3. если f и g оба жесткие, то композиция ht = f (gt) также жесткая
4. если f жесткая и g любой контравариантный функтор, то функтор ht = gt → ft жесткий

Еще одним свойством жестких функторов является то, что тип r() эквивалентен (), т.е. Существует только одно отдельное значение типа r(). Это значение point(), где point определена выше для любого жесткого функтора r. (У меня есть доказательство, но я не буду его здесь писать, потому что я не смог найти легкого однострочного доказательства.) Как следствие, жесткий функтор должен иметь только один конструктор. Это сразу показывает, что Maybe, Either, List и т.д. Не могут быть жесткими.

Связь с монадами

Если f - это монада, имеющая монадный преобразователь типа "составлено снаружи", tma = f (ma), то f - жесткий функтор.

"Жесткие монады", возможно, являются подмножеством жестких функторов, поскольку конструкция 4 дает жесткую монаду, только если f также является жесткой монадой, а не произвольным жестким функтором (но контравариантный функтор g все еще может быть произвольным). Однако у меня нет примеров жесткого функтора, который также не является монадой.

Простейшим примером жесткой монады является type ra = (a → p) → a, "поисковая монада". (Здесь p - фиксированный тип.)

Чтобы доказать, что у монады f с "составным внешним" трансформатором tma = f (ma) также есть метод inject, мы рассматриваем трансформатор tma с внешней монадой m выбранной в качестве монады читателя, ma = r → a. Тогда функция inject с правильной сигнатурой типа определяется как

 inject = join @t . return @r . (fmap @m (fmap @f return @m))

с соответствующим выбором параметров типа.

Закон невырожденности вытекает из монадической естественности t: монадический морфизм m → Identity (подставляя в читателя значение типа r) возводится в монадический морфизм tma → t Id a. Я опускаю детали этого доказательства.

Случаи применения

Наконец, я нашел два варианта использования жестких функторов.

Первый вариант использования был исходной мотивацией для рассмотрения жестких функторов: мы хотели бы вернуть несколько монадических результатов одновременно. Если m является монадой и мы хотим иметь fbind как показано в вопросе, нам нужно, чтобы f был жестким. Тогда мы можем реализовать fbind как

fbind :: m a -> (a -> f (m b)) -> f (m b)
fbind ma afmb = fmap (bind ma) (inject afmb)

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

Второй вариант использования вытекает из следующего рассмотрения. Предположим, у нас есть программа p :: a которая внутренне использует функцию f :: b → c. Теперь мы заметили, что функция f очень медленная, и мы хотели бы провести рефакторинг программы, заменив f на монадическое "будущее" или "задание", или, как правило, на стрелку Клейсли f' :: b → mc для некоторых монада m. Мы, конечно, ожидаем, что программа p также станет монадической: p' :: ma. Наша задача состоит в том, чтобы реорганизовать p в p'.

Рефакторинг выполняется в два этапа: во-первых, мы проводим рефакторинг программы p таким образом, чтобы функция f была явно аргументом p. Предположим, что это было сделано, так что теперь мы имеем p = qf где

q :: (b -> c) -> a

Во-вторых, мы заменим f на f'. Теперь предположим, что q и f' заданы. Мы хотели бы построить новую программу q' типа

q' :: (b -> m c) -> m a

так что p' = q' f'. Вопрос в том, можем ли мы определить общий комбинатор, который будет рефакторировать q в q',

refactor :: ((b -> c) -> a) -> (b -> m c) -> m a

Оказывается, что refactor можно построить, только если m - жесткий функтор. Пытаясь реализовать refactor, мы обнаруживаем, по существу, ту же проблему, что и при попытке внедрить inject для Maybe: нам предоставляется функция f' :: b → mc которая может возвращать разные монадические эффекты mc для разных b, но мы обязаны построить ma, который должен представлять один и тот же монадический эффект для всех b. Это не может работать, например, если m является монадой с более чем одним конструктором.

Если m жесткое (и нам не нужно требовать, чтобы m было монадой), мы можем реализовать refactor:

refactor bca bmc = fmap bca (inject bmc)

Если m не является жестким, мы не можем рефакторировать произвольные программы. До сих пор мы видели, что монада продолжения жесткая, но "будущие" монады -like и монада IO не являются жесткими. Это еще раз показывает, что жесткость, в некотором смысле, более сильное свойство, чем монадичность.

Ответ 2

В последнее время я проводил некоторые эксперименты, чтобы лучше понять Distributive. К счастью, мои результаты тесно связаны с вашими жесткими функторами, что разъясняет их обоих.

Для начала, вот одна из возможных презентаций жестких функторов. Я взял на себя смелость немного покататься на твоих именах, по причинам, которые я скоро доберусь до:

flap :: Functor f => f (a -> b) -> a -> f b
flap u a = ($ a) <$> u 

class Functor g => Rigid g where
    fflip :: (a -> g b) -> g (a -> b)
    fflip f = (. f) <$> extractors

    extractors :: g (g a -> a)
    extractors = fflip id

-- "Left inverse"/non-degeneracy law: flap . fflip = id

instance Rigid ((->) r) where
    fflip = flip

Несколько замечаний по поводу моей фразы:

• Я изменил названия inject и eject на fflip и flap, главным образом потому, что, на мой взгляд, flap больше похож на инъекцию из-за таких вещей:

  sweep :: Functor f => f a -> b -> f (a, b)
  sweep u b = flap ((,) <$> u) b
  

• Я взял имя flap у протолуда. Это игра на flip, которая подходит, потому что это один из двух симметричных способов ее обобщения. (Мы можем вытащить функцию за пределы произвольного Functor, как в flap, или вытянуть функтор Rigid за пределы функции, как в fflip.)

• Сначала я осознал значение extractors во время игры с Distributive, но мне не пришло в голову, что он может иметь смысл как часть другого класса. extractors и fflip взаимозаменяемы, что позволяет, например, написать этот довольно аккуратный экземпляр для монады поиска/выбора:

  newtype Sel r a = Sel { runSel :: (a -> r) -> a }
      deriving (Functor, Applicative, Monad) via SelectT r Identity
  
  instance Rigid (Sel r) where
      -- Sel r (Sel r a -> a) ~ ((Sel r a -> a) -> r) -> Sel r a -> a
      extractors = Sel $ \k m -> m 'runSel' \a -> k (const a)
  

Каждый дистрибутивный функтор жесток:

fflipDistrib :: Distributive g => (a -> g b) -> g (a -> b)
fflipDistrib = distribute @_ @((->) _)
-- From this point on, I will pretend Rigid is a superclass of Distributive.
-- There would be some tough questions about interface ergonomics if we were
-- writing this into a library. We don't have to worry about that right now,
-- though.

С другой стороны, мы можем написать функцию, которая имитирует подпись distribute, используя Rigid:

infuse :: (Rigid g, Functor f) => f (g a) -> g (f a)
infuse u = (<$> u) <$> extractors

infuse, однако, не является distribute. Как вы заметили, существуют жесткие функторы, которые не являются дистрибутивными, такие как Sel. Поэтому мы должны сделать вывод, что infuse в общем случае не следует распределительным законам.

(Помимо: то, что infuse не является законным distribute в случае Sel, может быть установлено с помощью аргумента мощности. Если infuse следует распределительным законам, мы бы имели infuse . infuse = id для любых двух жестких функторов Однако что-то вроде infuse @((->) Bool) @(Sel r) приводит к типу результата с меньшим количеством жителей, чем к типу аргумента, поэтому нет никакого способа, которым он может иметь обратный слева.)

Место в созвездии

На этом этапе было бы уместно уточнить нашу картину того, что именно отличает Distributive от Rigid. Учитывая, что ваш жесткий закон равен flap . fflip = id, интуиция предполагает, что другая половина изоморфизма, fflip . flap = id, может иметь место в случае Distributive. Проверка этой гипотезы требует обхода через Distributive.

Существует альтернативное представление Distributive (и Rigid), в котором distribute (или fflip) учитывается через функтор функций. Более конкретно, любое функторное значение типа g a может быть преобразовано в CPS-суспензию, для которой требуется экстрактор forall x. g x -> x:

-- The existential wrapper is needed to prevent undue specialisation by GHC.
-- With pen and paper, we can leave it implicit.
-- Note this isn't necessarily the best implementation available; see also
-- https://stackoverflow.com/q/56826733/2751851
data Ev g a where
    Ev :: ((g x -> x) -> a) -> Ev g a

-- Existential aside, this is ultimately just a function type.
deriving instance Functor (Ev g)

-- Morally, evert = flip id
evert :: g a -> Ev g a
evert u = Ev $ \e -> e u

Если g равен Rigid, мы можем пойти в другом направлении и восстановить значение функториала из приостановки:

-- Morally, revert = flip fmap extractors
revert :: Rigid g => Ev g a -> g a
revert (Ev s) = s <$> extractors

Ev g сам по себе является Distributive, независимо от того, что g - в конце концов, это просто функция:

-- We need unsafeCoerce (yikes!) because GHC can't be persuaded that we aren't
-- doing anything untoward with the existential.
-- Note that flip = fflip @((->) _)
instance Rigid (Ev g) where
    fflip = Ev . flip . fmap (\(Ev s) -> unsafeCoerce s)

-- Analogously, flap = distribute @((->) _)
instance Distributive (Ev g) where
    distribute = Ev . flap . fmap (\(Ev s) -> unsafeCoerce s) 

Далее, fflip и distribute для произвольных функторов Rigid/Distributive могут быть направлены через evert и revert:

-- fflip @(Ev g) ~ flip = distribute @((->) _) @((->) _)
fflipEv :: Rigid g => (a -> g b) -> g (a -> b)
fflipEv = revert . fflip . fmap evert

-- distribute @(Ev g) ~ flap = distribute @((->) _) _
distributeEv :: (Rigid g, Functor f) => f (g a) -> g (f a) 
distributeEv = revert . distribute . fmap evert

revert, на самом деле, будет достаточно для реализации Distributive. В таких терминах законы распределения требуют, чтобы evert и revert были обратными:

revert . evert = id  -- "home" roundtrip, right inverse law
evert . revert = id  -- "away" roundtrip, left inverse law

Два обхода соответствуют, соответственно, двум несвободным законам распределения:

fmap runIdentity . distribute = runIdentity                               -- identity
fmap getCompose . distribute = distribute . fmap distribute . getCompose  -- composition

(Требование distribute . distribute = id, указанное в документах Data.Distributive, в конечном итоге соответствует этим двум законам плюс естественность.)

Ранее я размышлял об изоморфизме с участием fflip:

flap . fflip = id  -- "home" roundtrip, left inverse Rigid law  
fflip . flap = id  -- "away" roundtrip, would-be right inverse law

Можно непосредственно проверить, что жесткий закон, flap . fflip = id, эквивалентен другому "домашнему" циклу, revert . evert = id. Другое направление сложнее. Предполагаемые изоморфизмы могут быть связаны следующим образом:

                        g (a -> b)        
    {fflip => <= flap}              {evert => <= revert}
a -> g b                                                   Ev g (a -> b)
    {fmap evert => <= fmap revert} {distribute => <= distribute}
                             a -> Ev g b

Давайте предположим, что строгий закон выполняется. Мы хотим доказать, что fflip . flap = id тогда и только тогда, когда evert . revert = id, поэтому мы должны обрабатывать оба направления:

• Во-первых, давайте предположим evert . revert = id. Способ обхода квадрата против часовой стрелки от a -> g b до g (a -> b) составляет fflip (см. определение fflipEv выше). Поскольку путь против часовой стрелки состоит из трех изоморфизмов, отсюда следует, что fflip имеет обратное. Поскольку flap является его левой обратной (по жесткому закону), он также должен быть обратной. Поэтому fflip . flap = id.

• Во-вторых, допустим fflip . flap = id. Опять же, путь против часовой стрелки от a -> g b до g (a -> b) - это fflip, но теперь мы знаем, что он имеет обратную сторону, а именно flap. Отсюда следует, что каждая из функций, составленных для составления пути против часовой стрелки, должна иметь обратную. В частности, у revert должно быть обратное. Поскольку evert является его обратным справа (по жесткому закону), оно также должно быть обратным. Поэтому evert . revert = id.

Приведенные выше результаты позволяют нам точно определить, где Rigid находится по отношению к Distributive. Жесткий функтор является потенциальным дистрибутивом, за исключением того, что он следует только тождественному закону дистрибутива, а не составному. Превращение fflip в изоморфизм с обратным flap равносильно обновлению Rigid до Distributive.

Разные замечания

• Рассматривая fflip и flap с монадической точки зрения, мы могли бы сказать, что жесткие монады снабжены инъективным преобразованием из стрел клейсли в статические стрелки. С помощью распределительных монад преобразование преобразуется в изоморфизм, который является обобщением того, как Applicative и Monad эквивалентны для Reader.

• extractors конденсирует большую часть того, о чем Distributive. Для любого распределительного функтора g существует значение g (g a -> a), в котором каждая позиция заполнена соответствующей функцией экстрактора g a -> a. Кажется точным сказать, что при переходе от Distributive к Rigid мы теряем эту гарантию того, что положение и экстрактор будут совпадать, а вместе с этим и способность восстанавливать адекватную функторную форму из ничего. В этом контексте стоит еще раз взглянуть на реализацию extractors для Sel в начале этого ответа. Любая функция a -> r соответствует экстрактору Sel r a -> a, что означает, что обычно будет множество экстракторов, которые мы не можем перечислить, поэтому нам нужно довольствоваться неизоморфными fflip и infuse (задним числом, const, который появляется в реализации extractors, уже выдает игру). Это похоже на отсутствие экземпляра Traversable для функций. (В этом случае, тем не менее, существует способ обмана, если тип домена функции перечислим, стиль Data.Universe. Я не уверен, существует ли такой обходной путь, каким бы непрактичным он ни был, для Sel.)

• Я получил результаты об изоморфизме revert для Distributive в значительной степени, отразив, как работает декомпозиция формы и содержания из Traversable, двойственного класса. (Очень удобочитаемая статья, в которой рассматривается тема формы и содержания, - Понимание идиоматических обходов назад и вперед, автор Bird et al.). Хотя более подробное описание этого вопроса, вероятно, лучше оставить для отдельного поста, здесь стоит задать хотя бы один вопрос: имеет ли смысл понятие, аналогичное Rigid, для Traversable? Я верю, что это так, хотя мне кажется, что это звучит менее полезно, чем Rigid. Одним из примеров "жесткой" псевдопереходимости может быть структура данных, снабженная обходом, который дублирует эффекты, но затем отбрасывает соответствующие дубликаты элементов после перестройки структуры под аппликативным уровнем, так что следует закону идентичности - но не композиционный.

• Говоря о revert, конструкция Ev сама по себе довольно значима: это кодировка свободного дистрибутивного функтора. В частности, evert и revert сравнимы с liftF и retract для свободных монад, а также с аналогичными функциями для других свободных конструкций. (В таком контексте revert, являющийся полной противоположностью evert, намекает на то, насколько сильным является Distributive. В некоторых случаях для отвода является более привычным отбрасывать информацию, как это происходит в общем случае Rigid. ].)

• Наконец, но не в последнюю очередь, есть еще один способ понять Ev: это означает, что тип полиморфного экстрактора представляет дистрибутивный функтор в смысле Representable, где evert соответствует index и от revert до tabulate. К сожалению, из-за количественного определения очень неудобно выражать это в Haskell с реальным интерфейсом Representable. (Симптоматично, что мне пришлось дотянуться до unsafeCoerce, чтобы дать Ev свои естественные экземпляры Rigid и Distributive.) Если это служит утешением, это все равно не будет ужасно практичным представлением: если бы я уже у меня в руках есть полиморфный экстрактор, мне на самом деле не нужен index для извлечения значений.