Алгоритм построения естественной карты

Question

дает конструктивное определение естественной карты, Этот пост на Reddit от Эдварда Кметтавзятой из бесплатной теоремы (которую я прочитал в еще одном сообщении Эдварда Кметта ):

Для данного f, g, h а также k, так что f . g = h . k: $map f . fmap g = fmap h . $map k, где $map естественная карта для данного конструктора.

Я не совсем понимаю алгоритм. Подойдем к этому постепенно:

Мы можем определить «естественное отображение» индукцией по любому конкретному выбору Fвы даете. В конечном итоге любой такой ADT состоит из сумм, произведений, 1с, 0s, 's, вызовы других функторов и т. д.

Рассмотреть возможность:

      data Smth a = A a a a | B a (Maybe a) | U | Z Void deriving ...

Стрелок нет. Давайте посмотрим, как (что я считаю естественным выбором для любого ADT без s в нем) будет работать здесь:

      instance Functor Smth where
  fmap xy (A x x1 x2)  = A (xy x) (xy x1) (xy x2)
  fmap xy (B x xPlus1) = B (xy x) (fmap xy xPlus1) 
  -- One can pattern-match 'xPlus1' as 'Just x1' and 'Nothing'.
  -- From my point of view, 'fmap' suits better here. Reasons below.
  fmap _xy U     = U 
  fmap _xy (Z z) = absurd z

Что кажется естественным . Говоря более формально, мы обращаемся к каждому x, применять fmap xy каждому T x, где a, мы оставляем без изменений каждую единицу и передаем каждую Void на absurd. Это работает и для рекурсивных определений!

      data Lst a = Unit | Prepend a (Lst a) deriving ...

instance Functor Lst where
    fmap xy Unit             = Unit
    fmap xy (Prepend x lstX) = Prepend (xy x) (fmap xy lstX)

И для неиндуктивных типов :_{(Подробное объяснение в этом ответе под связанным сообщением.)}

      Graph a = Node a [Graph a]

instance Functor Graph where
    fmap xy (Node x children) = Node (xy x) (fmap (fmap xy) children) 

Эта часть ясна.

Когда мы позволяем, у нас появляется первое, что смешивает дисперсию. Аргумент левого типа находится в контравариантном положении, правая часть находится в ковариантном положении. Таким образом, вам нужно отслеживать переменную последнего типа по всему ADT и видеть, находится ли она в положительной и / или отрицательной позиции.

Теперь мы включаем (->)с. Попробуем продолжить эту индукцию:

Мы каким-то образом вывели естественные карты для и. Таким образом, мы хотим рассмотреть следующее:

      data T2S a = T2S (T a -> S a)

instance ?Class? T2S where
    ?map? ?? (T2S tx2sx) = T2S $ \ ty -> ???

И я считаю, что именно здесь мы начинаем выбирать. У нас есть следующие возможности:

• встречается ни в T ни в S. в T2S является фантомом, поэтому мы можем реализовать как (Фантом) неconst phantom.
• (Ковариант) встречается и не встречается в. Таким образом, это что-то среди строк ReaderT с (которая на самом деле не зависит от) в качестве среды, которая заменяет ?Class? с участием Functor, с участием fmap, , с участием xy с участием:

          let tx = phantom ty 
      sx = tx2sx tx
      sy = fmap xy sx
  in sy
  

• (Контравариант) встречается и не встречается в. Я не вижу способа сделать это ковариантным функтором, поэтому мы реализуем Contravariant пример здесь, который заменяется на contramap, с участием yx, с участием:

          let tx = fmap yx ty 
      sx = tx2sx tx
      sy = phantom sx 
  in sy
  

• a происходит как в T a а также S a. Мы больше не можем использовать phantom, что оказалось весьма кстати. Есть модуль (Инвариант)Data.Functor.InvariantЭдвард Кметт. Он предоставляет следующий класс с картой:

          class Invariant f where
    invmap :: (a -> b) -> (b -> a) -> f a -> f b
    -- and some generic stuff...
  

  И все же я не вижу способа превратить это во что-то, что мы можем включить в бесплатную теорему для fmap - тип требует дополнительного аргумента функции, от которого мы не можем отмахнуться как idили что-то. Во всяком случае, ставим invmap вместо ?map?, xy yx вместо ??, и следующее вместо ???:

          let tx = fmap yx ty 
      sx = tx2sx tx
      sy = fmap xy sx
  in sy
  

Итак, правильно ли я понимаю такой алгоритм? Если да, то как нам правильно обработать инвариантный случай?

Answer 1

Я считаю, что ваш алгоритм слишком сложен, потому что вы пытаетесь написать один алгоритм. Вместо этого написание двух алгоритмов значительно упрощает задачу. Один алгоритм построит естественную fmap, а другой построит естественную contramap. НО оба алгоритма должны быть недетерминированными в следующем смысле: будут типы, которые не могут быть успешными, и поэтому не возвращают реализацию; и будут типы, в которых есть несколько способов добиться успеха, но все они эквивалентны.

Для начала давайте внимательно определим, что значит быть параметризованным типом. Вот различные типы параметризованных типов, которые мы можем иметь:

      F ::= F + F'
    | F * F'
    | F -> F'
    | F . F'
    | Id
    | Const X

В Const X, то X распространяется на все конкретные непараметрические типы, например Int а также Boolи так далее. А вот их интерпретация, то есть конкретный тип, которому они изоморфны после того, как задан параметр:

      [[F + F']] a = Either ([[F]] a) ([[F']] a)
[[F * F']] a = ([[F]] a, [[F']] a)
[[F -> F']] a = [[F]] a -> [[F']] a
[[F . F']] a = [[F]] ([[F']] a)
[[Id]] a = a
[[Const X]] a = X

Теперь мы можем привести два наших алгоритма. Первый бит, который вы уже написали сами:

      fmap @(F + F') f (Left x) = Left (fmap @F f x)
fmap @(F + F') f (Right x) = Right (fmap @F' f x)
fmap @(F * F') f (x, y) = (fmap @F f x, fmap @F f y)
fmap @(Id) f x = f x
fmap @(Const X) f x = x

Они соответствуют положениям, которые вы дали в первом случае. Затем в вашем [Graph a] Например, вы дали предложение, соответствующее этому:

      fmap @(F . F') f x = fmap @F (fmap @F' f) x

Это нормально, но это также первый момент, когда мы получаем некоторый недетерминизм. Один из способов сделать это функтором действительно вложенный s; но другой способ - вложенный s.

      fmap @(F . F') f x = contramap @F (contramap @F' f) x

Если возможны оба предложения, то нет Ids в любом F или же F', поэтому оба экземпляра вернутся x без изменений.

Единственное, что осталось, это футляр для стрелы, о котором вы спрашиваете. Но оказывается, что в этом формализме это очень просто, есть только один выбор:

      fmap @(F -> F') f x = fmap @F' f . x . contramap @F f

Вот и весь алгоритм, подробно описывающий естественный fmap. ... кроме одной детали - алгоритма естественного contramap. Но, надеюсь, если вы выполните все вышеперечисленное, вы сможете воспроизвести этот алгоритм самостоятельно. Я рекомендую вам попробовать, а затем сравнить свои ответы с моими ниже.

      contramap @(F + F') f (Left x) = Left (contramap @F f x)
contramap @(F + F') f (Right x) = Right (contramap @F' f x)
contramap @(F * F') f (x, y) = (contramap @F f x, contramap @F' f y)
contramap @(F -> F') f x = contramap @F' f . x . fmap @F f

contramap @(F . F') f x = contramap @F (fmap @F' f) x
-- OR
contramap @(F . F') f x = fmap @F (contramap @F' f) x

-- contramap @(Id) fails
contramap @(Const X) f x = x

Лично меня интересует одна вещь: оказывается, что contramap @(Id)это единственный листовой случай, который терпит неудачу. Все дальнейшие отказы являются индуктивными отказами, в конечном итоге происходящими из этого - факт, о котором я никогда раньше не думал! (Двойственное утверждение состоит в том, что оказывается, что fmap @(Id) является единственным листовым случаем, который фактически использует свой первый аргумент функции.)