Комонады Застежки-Молнии, Вообще

как childcatcher в Chitty-Chitty-Bang-Bang заманивая детей в плен со сладостями и игрушками, рекрутеры к физике бакалавриата любят дурачиться с мыльными пузырями и бумерангами, но когда дверь лязгает, это "право, дети, время, чтобы узнать о частичной дифференциации!". Я тоже. Не говори, что я тебя не предупреждал.

вот еще одно предупреждение: следующий код {-# LANGUAGE KitchenSink #-}, а точнее

{-# LANGUAGE TypeFamilies, FlexibleContexts, TupleSections, GADTs, DataKinds,
    TypeOperators, FlexibleInstances, RankNTypes, ScopedTypeVariables,
    StandaloneDeriving, UndecidableInstances #-}

в частности, нет порядок.

дифференцируемые функторы дают комонадные молнии

что такое дифференцируемый функтор, в любом случае?

class (Functor f, Functor (DF f)) => Diff1 f where
  type DF f :: * -> *
  upF      ::  ZF f x  ->  f x
  downF    ::  f x     ->  f (ZF f x)
  aroundF  ::  ZF f x  ->  ZF f (ZF f x)

data ZF f x = (:<-:) {cxF :: DF f x, elF :: x}

это функтор, который имеет производную, которая также является функтором. Производная представляет собой контекст с одним отверстием для элемент. Тип молнии ZF f x представляет пару контекста с одним отверстием и элемент в отверстии.

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

теперь, типа aroundF может напомнить некоторым из вас о

class Functor c => Comonad c where
  extract    :: c x -> x
  duplicate  :: c x -> c (c x)

и вы правы, что напомнили! У нас есть, с прыжком и скипом,

instance Diff1 f => Functor (ZF f) where
  fmap f (df :<-: x) = fmap f df :<-: f x

instance Diff1 f => Comonad (ZF f) where
  extract    = elF
  duplicate  = aroundF

и мы настаиваем на том, что

extract . duplicate == id
fmap extract . duplicate == id
duplicate . duplicate == fmap duplicate . duplicate

нам тоже это нужно

fmap extract (downF xs) == xs              -- downF decorates the element in position
fmap upF (downF xs) = fmap (const xs) xs   -- downF gives the correct context

полиномиальные функторы дифференцируемы

постоянный функторы являются дифференцируемыми.

data KF a x = KF a
instance Functor (KF a) where
  fmap f (KF a) = KF a

instance Diff1 (KF a) where
  type DF (KF a) = KF Void
  upF (KF w :<-: _) = absurd w
  downF (KF a) = KF a
  aroundF (KF w :<-: _) = absurd w

там негде поставить элемент, так невозможно сформировать контекст. Некуда идти upF или downF от, и мы легко находим все ни один из способов пойти downF.

The личность функтор является дифференцируемой.

data IF x = IF x
instance Functor IF where
  fmap f (IF x) = IF (f x)

instance Diff1 IF where
  type DF IF = KF ()
  upF (KF () :<-: x) = IF x
  downF (IF x) = IF (KF () :<-: x)
  aroundF z@(KF () :<-: x) = KF () :<-: z

есть один элемент в тривиальном контексте, downF находит его, upF перепаковывает его, и aroundF могу только оставаться на месте.

Sum сохраняет дифференцируемости.

data (f :+: g) x = LF (f x) | RF (g x)
instance (Functor f, Functor g) => Functor (f :+: g) where
  fmap h (LF f) = LF (fmap h f)
  fmap h (RF g) = RF (fmap h g)

instance (Diff1 f, Diff1 g) => Diff1 (f :+: g) where
  type DF (f :+: g) = DF f :+: DF g
  upF (LF f' :<-: x) = LF (upF (f' :<-: x))
  upF (RF g' :<-: x) = RF (upF (g' :<-: x))

другие биты и кусочки немного больше горсти. Идти downF, мы должны идти downF внутри помеченного компонента, затем исправьте полученные молнии, чтобы показать тег в контексте.

  downF (LF f) = LF (fmap (\ (f' :<-: x) -> LF f' :<-: x) (downF f))
  downF (RF g) = RF (fmap (\ (g' :<-: x) -> RF g' :<-: x) (downF g))

нужно aroundF, мы снимаем тег, выясняем, как обойти непомеченную вещь, а затем восстанавливаем тег во всех полученных молниях. Элемент в фокусе, x, заменяется вся его молния,z.

  aroundF z@(LF f' :<-: (x :: x)) =
    LF (fmap (\ (f' :<-: x) -> LF f' :<-: x) . cxF $ aroundF (f' :<-: x :: ZF f x))
    :<-: z
  aroundF z@(RF g' :<-: (x :: x)) =
    RF (fmap (\ (g' :<-: x) -> RF g' :<-: x) . cxF $ aroundF (g' :<-: x :: ZF g x))
    :<-: z

обратите внимание, что я должен использовать ScopedTypeVariables для устранения неоднозначности рекурсивные вызовы aroundF. Как функция типа,DF не является инъективным, так что тот факт, что f' :: D f x недостаточно, чтобы заставить f' :<-: x :: Z f x.

продукт сохраняет дифференцируемости.

data (f :*: g) x = f x :*: g x
instance (Functor f, Functor g) => Functor (f :*: g) where
  fmap h (f :*: g) = fmap h f :*: fmap h g

чтобы сосредоточиться на элементе в паре, вы либо фокусируетесь на левой стороне и оставляете правую в покое, либо наоборот. Известное правило продукта Лейбница соответствует простой пространственной интуиции!

instance (Diff1 f, Diff1 g) => Diff1 (f :*: g) where
  type DF (f :*: g) = (DF f :*: g) :+: (f :*: DF g)
  upF (LF (f' :*: g) :<-: x) = upF (f' :<-: x) :*: g
  upF (RF (f :*: g') :<-: x) = f :*: upF (g' :<-: x)

теперь downF работает аналогично как это было для сумм, за исключением того, что мы должны исправить контекст молнии не только с тегом (чтобы показать, в какую сторону мы пошли), но и с нетронутым другим компонентом.

  downF (f :*: g)
    =    fmap (\ (f' :<-: x) -> LF (f' :*: g) :<-: x) (downF f)
    :*:  fmap (\ (g' :<-: x) -> RF (f :*: g') :<-: x) (downF g)

но aroundF это огромный мешок смеха. Какую бы сторону мы сейчас ни посещали, у нас есть два варианта:

1. движение aroundF с той стороны.
2. движение upF вон с той стороны и downF в другую сторону.

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

  aroundF z@(LF (f' :*: g) :<-: (x :: x)) =
    LF (fmap (\ (f' :<-: x) -> LF (f' :*: g) :<-: x)
          (cxF $ aroundF (f' :<-: x :: ZF f x))
        :*: fmap (\ (g' :<-: x) -> RF (f :*: g') :<-: x) (downF g))
    :<-: z
    where f = upF (f' :<-: x)
  aroundF z@(RF (f :*: g') :<-: (x :: x)) =
    RF (fmap (\ (f' :<-: x) -> LF (f' :*: g) :<-: x) (downF f) :*:
        fmap (\ (g' :<-: x) -> RF (f :*: g') :<-: x)
          (cxF $ aroundF (g' :<-: x :: ZF g x)))
    :<-: z
    where g = upF (g' :<-: x)

Фух! Полиномы все дифференцируемы и, таким образом, дают нам комонады.

Мда. Это все немного абстрактно. Поэтому я добавил deriving Show везде, где я мог, и бросил в

deriving instance (Show (DF f x), Show x) => Show (ZF f x)

что позволило следующее взаимодействие (прибрано вручную)

> downF (IF 1 :*: IF 2)
IF (LF (KF () :*: IF 2) :<-: 1) :*: IF (RF (IF 1 :*: KF ()) :<-: 2)

> fmap aroundF it
IF  (LF (KF () :*: IF (RF (IF 1 :*: KF ()) :<-: 2)) :<-: (LF (KF () :*: IF 2) :<-: 1))
:*:
IF  (RF (IF (LF (KF () :*: IF 2) :<-: 1) :*: KF ()) :<-: (RF (IF 1 :*: KF ()) :<-: 2))

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

сладкий! Теперь мы можем идти домой? Конечно, нет. Мы не дифференцировали ни одного рекурсивные структур пока нет.

создание рекурсивных функторов из бифункторов

A Bifunctor, как объясняет существующая литература по типам данных generic programming (см. работу Патрика Янссона и Йохана Джуринга или отличные лекционные заметки Джереми Гиббонса), это конструктор типов с двумя параметры, соответствующие двум видам подструктуры. Мы должны быть в состоянии "карты" как.

class Bifunctor b where
  bimap :: (x -> x') -> (y -> y') -> b x y -> b x' y'

можно использовать Bifunctors, чтобы дать структуру узлов рекурсивных контейнеров. Каждый узел имеет подузлы и элементов. Это могут быть только два вида субструктуры.

data Mu b y = In (b (Mu b y) y)

посмотреть? Мы "завязываем рекурсивный узел" в bпервый аргумент, и сохранить параметр y во втором. Соответственно, мы получаем один раз все

instance Bifunctor b => Functor (Mu b) where
  fmap f (In b) = In (bimap (fmap f) f b)

чтобы использовать это, нам понадобится набор Bifunctor экземпляров.

Бифункциональный Комплект

константы являются бифункциональными.

newtype K a x y = K a

instance Bifunctor (K a) where
  bimap f g (K a) = K a

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

переменные являются бифункциональными.

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

data Var = X | Y

data V :: Var -> * -> * -> * where
  XX :: x -> V X x y
  YY :: y -> V Y x y

, что составляет V X x y копия x и V Y x y копия y. Соответственно

instance Bifunctor (V v) where
  bimap f g (XX x) = XX (f x)
  bimap f g (YY y) = YY (g y)

суммы и продукты из бифункторов являются бифункторами

data (:++:) f g x y = L (f x y) | R (g x y) deriving Show

instance (Bifunctor b, Bifunctor c) => Bifunctor (b :++: c) where
  bimap f g (L b) = L (bimap f g b)
  bimap f g (R b) = R (bimap f g b)

data (:**:) f g x y = f x y :**: g x y deriving Show

instance (Bifunctor b, Bifunctor c) => Bifunctor (b :**: c) where
  bimap f g (b :**: c) = bimap f g b :**: bimap f g c

до сих пор так шаблонно, но теперь мы можем определить такие вещи, как

List = Mu (K () :++: (V Y :**: V X))

Bin = Mu (V Y :**: (K () :++: (V X :**: V X)))

если вы хотите использовать эти типы для фактических данных и не пойти слепой в пуантилистской традиции Жоржа Сера, используйте шаблон синонимы.

а как же молнии? Как мы это покажем Mu b является дифференцируемой? Нам нужно будет показать это b дифференцируется в и переменные. Лязг! Пришло время узнать о частичной дифференциации.

частные производные бифункторов

потому что у нас есть две переменные, мы должны быть в состоянии говорить о них иногда коллективно и индивидуально в другое время. Нам понадобится семья синглтонов:

data Vary :: Var -> * where
  VX :: Vary X
  VY :: Vary Y

теперь мы можем сказать, что значит для Бифунктора иметь частные производные по каждой переменной, и дать соответствующее понятие молнии.

class (Bifunctor b, Bifunctor (D b X), Bifunctor (D b Y)) => Diff2 b where
  type D b (v :: Var) :: * -> * -> *
  up      :: Vary v -> Z b v x y -> b x y
  down    :: b x y -> b (Z b X x y) (Z b Y x y)
  around  :: Vary v -> Z b v x y -> Z b v (Z b X x y) (Z b Y x y)

data Z b v x y = (:<-) {cxZ :: D b v x y, elZ :: V v x y}

этой D операция должна знать, какую переменную выбрать. Соответствующая молния Z b v говорит нам, что переменная v должен быть в фокусе. Когда мы "украшаем контекстом" , мы должны украсить x-элементы с X-контексты и y-элементы с Y-контекстах. Но в остальном, это та же история.

у нас осталось две задачи: во-первых, показать, что наш набор бифункторов дифференцируем; во-вторых, показать, что Diff2 b позволяет установить Diff1 (Mu b).

дифференциация набора Бифункторов

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

константы как до.

instance Diff2 (K a) where
  type D (K a) v = K Void
  up _ (K q :<- _) = absurd q
  down (K a) = K a
  around _ (K q :<- _) = absurd q

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

instance Diff2 (V X) where
  type D (V X) X = K ()
  type D (V X) Y = K Void
  up VX (K () :<- XX x)  = XX x
  up VY (K q :<- _)      = absurd q
  down (XX x) = XX (K () :<- XX x)
  around VX z@(K () :<- XX x)  = K () :<- XX z
  around VY (K q :<- _)        = absurd q

instance Diff2 (V Y) where
  type D (V Y) X = K Void
  type D (V Y) Y = K ()
  up VX (K q :<- _)      = absurd q
  up VY (K () :<- YY y)  = YY y
  down (YY y) = YY (K () :<- YY y)
  around VX (K q :<- _)        = absurd q
  around VY z@(K () :<- YY y)  = K () :<- YY z

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

vV :: Vary v -> Z b v x y -> V v (Z b X x y) (Z b Y x y)
vV VX z = XX z
vV VY z = YY z

я создал гаджеты для облегчения своего рода "перейти" необходимо для down и around. (Конечно, я видел, какие гаджеты мне нужны, как я был рабочий.)

zimap :: (Bifunctor c) => (forall v. Vary v -> D b v x y -> D b' v x y) ->
         c (Z b X x y) (Z b Y x y) -> c (Z b' X x y) (Z b' Y x y)
zimap f = bimap
  (\ (d :<- XX x) -> f VX d :<- XX x)
  (\ (d :<- YY y) -> f VY d :<- YY y)

dzimap :: (Bifunctor (D c X), Bifunctor (D c Y)) =>
         (forall v. Vary v -> D b v x y -> D b' v x y) ->
         Vary v -> Z c v (Z b X x y) (Z b Y x y) -> D c v (Z b' X x y) (Z b' Y x y)
dzimap f VX (d :<- _) = bimap
  (\ (d :<- XX x) -> f VX d :<- XX x)
  (\ (d :<- YY y) -> f VY d :<- YY y)
  d
dzimap f VY (d :<- _) = bimap
  (\ (d :<- XX x) -> f VX d :<- XX x)
  (\ (d :<- YY y) -> f VY d :<- YY y)
  d

и с этой партией готовы идти, мы можем измельчить детали. С суммами все просто.

instance (Diff2 b, Diff2 c) => Diff2 (b :++: c) where
  type D (b :++: c) v = D b v :++: D c v
  up v (L b' :<- vv) = L (up v (b' :<- vv))
  down (L b) = L (zimap (const L) (down b))
  down (R c) = R (zimap (const R) (down c))
  around v z@(L b' :<- vv :: Z (b :++: c) v x y)
    = L (dzimap (const L) v ba) :<- vV v z
    where ba = around v (b' :<- vv :: Z b v x y)
  around v z@(R c' :<- vv :: Z (b :++: c) v x y)
    = R (dzimap (const R) v ca) :<- vV v z
    where ca = around v (c' :<- vv :: Z c v x y)

продукты тяжелая работа, поэтому я математик, а не инженер.

instance (Diff2 b, Diff2 c) => Diff2 (b :**: c) where
  type D (b :**: c) v = (D b v :**: c) :++: (b :**: D c v)
  up v (L (b' :**: c) :<- vv) = up v (b' :<- vv) :**: c
  up v (R (b :**: c') :<- vv) = b :**: up v (c' :<- vv)
  down (b :**: c) =
    zimap (const (L . (:**: c))) (down b) :**: zimap (const (R . (b :**:))) (down c)
  around v z@(L (b' :**: c) :<- vv :: Z (b :**: c) v x y)
    = L (dzimap (const (L . (:**: c))) v ba :**:
        zimap (const (R . (b :**:))) (down c))
      :<- vV v z where
      b = up v (b' :<- vv :: Z b v x y)
      ba = around v (b' :<- vv :: Z b v x y)
  around v z@(R (b :**: c') :<- vv :: Z (b :**: c) v x y)
    = R (zimap (const (L . (:**: c))) (down b):**:
        dzimap (const (R . (b :**:))) v ca)
      :<- vV v z where
      c = up v (c' :<- vv :: Z c v x y)
      ca = around v (c' :<- vv :: Z c v x y)

концептуально все так же, как и раньше, но с большей бюрократией. Я построил их с использованием технологии pre-type-hole, используя undefined как заглушка в местах, где я не был готов работать, и вводил преднамеренную ошибку типа в одном месте (в любом случае учитывая время), где я хотел получить полезную подсказку от typechecker. Вы тоже можете иметь проверку типа как опыт видеоигр, даже в Haskell.

молнии Подузлов для рекурсивных контейнеров

частичная производная от b с уважением X говорит нам, как найти подузел на один шаг внутри узла, поэтому мы получаем обычное понятие молнии.

data MuZpr b y = MuZpr
  {  aboveMu  :: [D b X (Mu b y) y]
  ,  hereMu   :: Mu b y
  }

мы можем увеличить весь путь до корня, повторяя подключение X должностное положение.

muUp :: Diff2 b => MuZpr b y -> Mu b y
muUp (MuZpr {aboveMu = [], hereMu = t}) = t
muUp (MuZpr {aboveMu = (dX : dXs), hereMu = t}) =
  muUp (MuZpr {aboveMu = dXs, hereMu = In (up VX (dX :<- XX t))})

а нужно элемент-молнии.

элемент-молнии для точек фиксации бифункторов

каждый элемент находится где-то внутри узла. Этот узел сидит под стеком X-производных. Но положение элемента в этом узле задается Y-производное. Мы получаем

data MuCx b y = MuCx
  {  aboveY  :: [D b X (Mu b y) y]
  ,  belowY  :: D b Y (Mu b y) y
  }

instance Diff2 b => Functor (MuCx b) where
  fmap f (MuCx { aboveY = dXs, belowY = dY }) = MuCx
    {  aboveY  = map (bimap (fmap f) f) dXs
    ,  belowY  = bimap (fmap f) f dY
    }

смело заявляю

instance Diff2 b => Diff1 (Mu b) where
  type DF (Mu b) = MuCx b

но прежде чем я разработаю операции, мне нужно какие-то мелочи.

я могу торговать данными между functor-zippers и bifunctor-zippers следующим образом:

zAboveY :: ZF (Mu b) y -> [D b X (Mu b y) y]  -- the stack of `X`-derivatives above me
zAboveY (d :<-: y) = aboveY d

zZipY :: ZF (Mu b) y -> Z b Y (Mu b y) y      -- the `Y`-zipper where I am
zZipY (d :<-: y) = belowY d :<- YY y

этого достаточно, чтобы я определил:

  upF z  = muUp (MuZpr {aboveMu = zAboveY z, hereMu = In (up VY (zZipY z))})

то есть, мы идем вверх, сначала собирая узел, где находится элемент, превращая элемент-молнию в подузел-молнию, а затем масштабируя весь путь, как указано выше.

далее, я говорю

  downF  = yOnDown []

идти вниз, начиная с пустого стека, и определить вспомогательная функция, которая идет down повторно снизу любого стека:

yOnDown :: Diff2 b => [D b X (Mu b y) y] -> Mu b y -> Mu b (ZF (Mu b) y)
yOnDown dXs (In b) = In (contextualize dXs (down b))

теперь down b только принимает нас внутри узла. Молнии, которые нам нужны, также должны нести контекст узла. Вот что contextualise тут:

contextualize :: (Bifunctor c, Diff2 b) =>
  [D b X (Mu b y) y] ->
  c (Z b X (Mu b y) y) (Z b Y (Mu b y) y) ->
  c (Mu b (ZF (Mu b) y)) (ZF (Mu b) y)
contextualize dXs = bimap
  (\ (dX :<- XX t) -> yOnDown (dX : dXs) t)
  (\ (dY :<- YY y) -> MuCx {aboveY = dXs, belowY = dY} :<-: y)

для каждого Y-позиция, мы должны дать элемент-молния, так что хорошо, что мы знаем весь контекст dXs вернуться к корню, а также dY который описывает, как элемент находится в своем узле. Для каждого X-позиция, есть еще поддерево для изучения, поэтому мы растем стек и продолжаем идти!

это оставляет только дело смещения фокуса. Мы могли бы остаться на месте, или спуститься с того места, где мы находимся, или подняться, или подняться, а затем спуститься по какой-нибудь другой тропе. Вот так.

  aroundF z@(MuCx {aboveY = dXs, belowY = dY} :<-: _) = MuCx
    {  aboveY = yOnUp dXs (In (up VY (zZipY z)))
    ,  belowY = contextualize dXs (cxZ $ around VY (zZipY z))
    }  :<-: z

как всегда, существующий элемент заменен всей своей застежкой-молнией. Для belowY часть, мы смотрим, куда еще мы можем пойти в существующем узле: мы найдем либо альтернативный элемент Y-позиции или дальше X - подузлы для изучения, так что мы contextualise них. Для aboveY часть, мы должны работать наш путь обратно в стек X-производные после повторной сборки узла, который мы посещали.

yOnUp :: Diff2 b => [D b X (Mu b y) y] -> Mu b y ->
         [D b X (Mu b (ZF (Mu b) y)) (ZF (Mu b) y)]
yOnUp [] t = []
yOnUp (dX : dXs) (t :: Mu b y)
  =  contextualize dXs (cxZ $ around VX (dX :<- XX t))
  :  yOnUp dXs (In (up VX (dX :<- XX t)))

на каждом этапе пути мы можем либо повернуть куда-то еще, что around, или продолжайте подниматься.

и это все! Я не дал формального доказательства законов, но мне кажется, что операции тщательно поддерживают контекст правильно как они ползут по строению.

что мы узнали?

Дифференцируемость индуцирует понятия вещи в ее контексте, индуцируя комонадическую структуру, где extract дает вам вещь и duplicate исследует контекст ищет другие вещи для контекстуализации. Если у нас есть соответствующая дифференциальная структура для узлов, мы можем разработать дифференциальную структуру для целых деревьев.

Ох, и обрабатывать каждое индивидуальное Ариты типа конструктор отдельно вопиюще ужасен. Лучший способ-работать с функторами между индексированными множествами

f :: (i -> *) -> (o -> *)

где мы делаем o различные виды хранения структуры i различные виды элемента. Это закрытые под Якобианской конструкцией

J f :: (i -> *) -> ((o, i) -> *)

где каждый из полученных (o, i)-structures является частной производной, рассказывая вам, как сделать i-элемент-отверстие в элементе o-структуры. Но это зависимо типизированная забава, в другой раз.