Как сделать двоичную древовидную застежку-молнию экземпляром Comonad?

Ответ 1

В дифференциальном исчислении обозначение Лейбница вызывает меньше путаницы, чем Ньютон, потому что оно явно относится к переменной, по которой мы дифференцируем. Контексты в вещах даются дифференциацией, поэтому мы должны позаботиться о том, что является контекстуализированным. Здесь есть два понятия "подструктуры": поддеревья и элементы. У каждого из них разные (но связанные) понятия "контекст" и, следовательно, "застежка-молния", где застежка-молния - это пара вещи и ее контекст.

Тип BTZ представлен как понятие молнии для поддеревьев. Тем не менее, застежка-молния, выполненная из конопличной конструкции, работает на застежках-молниях для элементов: extract означает "дать элемент здесь"; duplicate означает "украсить каждый элемент своим контекстом". Поэтому вам нужны контексты элементов. Смутно, что для этих двоичных деревьев застежки-молнии и подделки застежки-молнии изоморфны, но это по какой-то особой причине (а именно, что они образуют cofree comonad).

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

Подсвечники контекста

Подсвечники-контексты для [a] задаются только [a], являясь списком элементов, которые мы проходим, по пути от подсписок до всего списка. Подсвещенный контекст для [3,4] в [1,2,3,4] равен [2,1]. Контексты субнода для рекурсивных данных всегда представляют собой списки, представляющие то, что вы видите на пути от node к корню. Тип каждого шага задается частичной производной формулы для одного node данных относительно рекурсивной переменной. Итак, здесь

[a] = t where             -- t is the recursive variable standing for [a]
  t = 1 + a*t             -- lists of a are either [] or an (a : t) pair
∂/∂t (1 + a*t) = a        -- that one step on a path from node to root
sublist contexts are [a]  -- a list of such steps

Итак, подслист-молния представляет собой пару

data LinLZ a = LinLZ
  {  subListCtxt  :: [a]
  ,  subList      :: [a]
  }

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

plugLinLZ :: LinLZ a -> [a]
plugLinLZ (LinLZ { subListCtxt = [],      subList = ys})  = ys
plugLinLZ (LinLZ { subListCtxt = x : xs,  subList = ys})
  = plugLinLZ (LinLZ { subListCtxt = xs,  subList = x : ys})

Но мы не можем сделать LinLZ a Comonad, потому что (например) из

LinLZ { subListCtxt = [], subList = [] }

мы не можем extract использовать элемент (a a из LinLZ a), только подстрочный.

Контексты элементов списка

Контекст элемента списка - это пара списков: элементы перед элементом в фокусе и элементы после него. Контекст элемента в рекурсивной структуре всегда представляет собой пару: сначала дайте контекст subnode для поднода, где хранится этот элемент, затем укажите контекст для элемента в его node. Мы получаем контекст element-in-its-node, дифференцируя формулу для a node относительно переменной, которая обозначает элементы.

[a] = t where             -- t is the recursive variable standing for [a]
  t = 1 + a*t             -- lists of a are either [] or an (a : t) pair
∂/∂a (1 + a*t) = t = [a]  -- the context for the head element is the tail list

Итак, контекст элемента задается парой

type DL a =
  (  [a]     -- the sublist context for the node where the element is
  ,  [a]     -- the tail of the node where the element is
  )

и элементная молния задается путем спаривания такого контекста с элементом "в отверстии".

data ZL a = ZL
  {  this :: a
  ,  between :: DL a
  }  deriving (Show, Eq, Functor)

Вы можете превратить такую ​​застежку-молнию в список ( "выходить" из элемента), сначала воссоздавая подсписку, где сидит элемент, давая нам подслистскую застежку-молнию, а затем подключая подсписку в свой контекст-подсвет.

outZL :: ZL a -> [a]
outZL (ZL { this = x, between = (zs, xs) })
  = plugLinLZ (LinLZ { subListCtxt = zs, subList = x : xs })

Вставка каждого элемента в контекст

Учитывая список, мы можем связать каждый элемент с его контекстом. Мы получаем список способов "войти" в один из элементов. Мы начинаем вот так:

into :: [a] -> [ZL a]
into xs = moreInto (LinLZ { subListCtxt = [], subList = xs })

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

moreInto :: LinLZ a -> [ZL a]
moreInto (LinLZ { subListCtxt = _,   subList = [] })      = []
moreInto (LinLZ { subListCtxt = zs,  subList = x : xs })
  =  ZL { this = x, between = (zs, xs) } 
  :  moreInto (LinLZ { subListCtxt = x : zs,  subList = xs })

Обратите внимание, что выход эхосигнала соответствует форме текущего subList. Кроме того, молния в x имеет место this = x. Кроме того, генерирующая молния для декорирования xs имеет subList = xs и правильный контекст, что мы прошли мимо x. Тестирование,

into [1,2,3,4] =
  [  ZL {this = 1, between = ([],[2,3,4])}
  ,  ZL {this = 2, between = ([1],[3,4])}
  ,  ZL {this = 3, between = ([2,1],[4])}
  ,  ZL {this = 4, between = ([3,2,1],[])}
  ]

Комонадная структура для элементов списка элементов

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

instance Comonad ZL where

extract дает нам элемент, который мы посещаем.

  extract = this

В duplicate застежку-молнию заменим текущий элемент x на всю текущую молнию zl (чья this = x)...

  duplicate [email protected](ZL { this = x, between = (zs, ys) }) = ZL
    {  this = zl

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

    ,  between =
         (  outward (LinLZ { subListCtxt = zs, subList = x : ys })
         ,  moreInto (LinLZ { subListCtxt = x : zs, subList = ys })
         )
    }

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

    where
      outward (LinLZ { subListCtxt = [], subList = _ }) = []
      outward (LinLZ { subListCtxt = z : zs, subList = ys })
        =  ZL { this = z, between = (zs, ys) }
        :  outward (LinLZ { subListCtxt = zs, subList = z : ys })

Итак, получим

duplicate ZL {this = 2, between = ([1],[3,4])}
  = ZL
  {  this = ZL {this = 2, between = ([1],[3,4])}
  ,  between =
     (  [  ZL {this = 1, between = ([],[2,3,4])}  ]
     ,  [  ZL {this = 3, between = ([2,1],[4])}
        ,  ZL {this = 4, between = ([3,2,1],[])}
        ]
     )
  }

где this находится в 2 ", и мы between" переходим к 1 "и" переходим к 3 или переходим к 4 ".

Итак, структура comonadic показывает нам, как мы можем перемещаться между разными элементами, находящимися внутри списка. Подсветовая структура играет ключевую роль в поиске узлов, где находятся элементы, но структура молнии duplicate d является элементом застежки-молнии.

А как насчет деревьев?

Отступление: отмеченные деревья уже есть comonads

Позвольте мне реорганизовать ваш тип двоичных деревьев, чтобы выявить некоторую структуру. Буквально давайте вытаскиваем элемент, который накладывает лист или вилку как общий фактор. Выделим также функтор (TF), который объясняет эту структуру поддерева листа или фолка.

data TF t = Leaf | Fork (t, t) deriving (Show, Eq, Functor)
data BT a = a :& TF (BT a) deriving (Show, Eq, Functor)

То есть, каждое дерево node имеет метку, будь то лист или вилка.

Если у нас есть структура, в которой каждая node имеет метку и blob подструктур, мы имеем comonad: cofree comonad. Позвольте мне реорганизовать немного больше, абстрагируя TF...

data CoFree f a = a :& f (CoFree f a) deriving (Functor)

... так что мы имеем общий f, где мы имели TF раньше. Мы можем восстановить наши конкретные деревья.

data TF t = Leaf | Fork (t, t) deriving (Show, Eq, Functor)
type BT = CoFree TF
deriving instance Show a => Show (BT a)
deriving instance Eq a => Eq (BT a)

И теперь, раз и навсегда, мы можем дать конструкцию cofree comonad. Поскольку каждое поддерево имеет корневой элемент, каждый элемент может быть украшен деревом, корень которого он есть.

instance Functor f => Comonad (CoFree f) where
  extract   (a :& _)     = a                         -- extract root element
  duplicate [email protected](a :& ft)  = t :& fmap duplicate ft    -- replace root element by whole tree

Приведем пример

aTree =
  0 :& Fork
  (  1 :& Fork
     (  2 :& Leaf
     ,  3 :& Leaf
     )
  ,  4 :& Leaf
  )

duplicate aTree =
  (0 :& Fork (1 :& Fork (2 :& Leaf,3 :& Leaf),4 :& Leaf)) :& Fork
  (  (1 :& Fork (2 :& Leaf,3 :& Leaf)) :& Fork
     (  (2 :& Leaf) :& Leaf
     ,  (3 :& Leaf) :& Leaf
     )
  ,  (4 :& Leaf) :& Leaf
  )

См? Каждый элемент соединен с его поддеревом!

Списки не вызывают cofree comonad, потому что не каждый node имеет элемент: в частности, [] не имеет элемента. В cofree comonad всегда есть элемент, где вы находитесь, и вы можете видеть дальше в древовидную структуру, но не дальше.

В элементе zipper comonad всегда есть элемент, где вы находитесь, и вы можете видеть вверх и вниз.

Субтитры и контексты элементов в бинарных деревьях

алгебраически

d/dt (TF t) = d/dt (1 + t*t) = 0 + (1*t + t*1)

поэтому мы можем определить

type DTF t = Either ((), t) (t, ())

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

plugF :: t -> DTF t -> TF t
plugF  t  (Left   ((), r))  = Fork (t, r)
plugF  t  (Right  (l, ()))  = Fork (l, t)

Если мы создадим экземпляр t и сопоставим с меткой node, мы получим один шаг контекста поддерева

type BTStep a = (a, DTF (BT a))

который изоморфен Partial в вопросе.

plugBTinBT :: BT a -> BTStep a -> BT a
plugBTinBT t (a, d) = a :& plugF t d

Итак, поддерево-контекст для одного BT a внутри другого задается [BTStep a].

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

data DBT a = DBT
  {  below  :: TF (BT a)    -- the rest of the element node
  ,  above  :: [BTStep a]   -- the subtree context of the element node
  }  deriving (Show, Eq)

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

instance Functor DBT where
  fmap f (DBT { above = a, below = b }) = DBT
    {  below = fmap (fmap f) b
    ,  above = fmap (f *** (either
         (Left   . (id *** fmap f))
         (Right  . (fmap f *** id)))) a  
    }

Теперь я могу сказать, что такое элементная молния.

data BTZ a = BTZ
  {  here  :: a
  ,  ctxt  :: DBT a
  }  deriving (Show, Eq, Functor)

Если вы думаете "что нового?", вы правы. У нас есть контекст поддерева, above, вместе с поддеревом, заданным here и below. И это потому, что единственными элементами являются те, которые обозначают узлы. Разделение node вверх на элемент и его контекст такое же, как разбиение его на его метку и ее блоб подструктур. То есть, мы получаем это совпадение для cofree comonads, но не в целом.

Однако это совпадение - только отвлечение! Как мы видели со списками, мы не нуждаемся в элементарных застежках-молниях, чтобы они были такими же, как и подзоны-молнии, чтобы сделать элементы-молнии комонадой.

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

down :: BT a -> BT (BTZ a)
down t = downIn t []

downIn :: BT a -> [BTStep a] -> BT (BTZ a)
downIn (a :& ft) ads =
  BTZ { here = a, ctxt = DBT { below = ft, above = ads } }
  :& furtherIn a ft ads

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

furtherIn :: a -> TF (BT a) -> [BTStep a] -> TF (BT (BTZ a))
furtherIn a Leaf           ads  = Leaf
furtherIn a (Fork (l, r))  ads  = Fork
  (  downIn l ((a, Left   ((), r)) : ads)
  ,  downIn r ((a, Right  (l, ())) : ads)
  )

Посмотрите, что furtherIn сохраняет древовидную структуру, но подходит к контексту поддерева, когда он посещает поддерево.

Пусть двойная проверка.

down aTree =
  BTZ {  here  = 0, ctxt = DBT {
         below = Fork (1 :& Fork (2 :& Leaf,3 :& Leaf),4 :& Leaf),
         above = []}} :& Fork
  (  BTZ {  here = 1, ctxt = DBT {
            below = Fork (2 :& Leaf,3 :& Leaf),
            above = [(0,Left ((),4 :& Leaf))]}} :& Fork
     (  BTZ {  here = 2, ctxt = DBT {
               below = Leaf,
               above = [(1,Left ((),3 :& Leaf)),(0,Left ((),4 :& Leaf))]}} :& Leaf
     ,  BTZ {  here = 3, ctxt = DBT {
               below = Leaf,
               above = [(1,Right (2 :& Leaf,())),(0,Left ((),4 :& Leaf))]}} :& Leaf
     )
  ,  BTZ {  here = 4, ctxt = DBT {
            below = Leaf,
            above = [(0,Right (1 :& Fork (2 :& Leaf,3 :& Leaf),()))]}} :& Leaf)

См? Каждый элемент имеет весь контекст, а не только дерево под ним.

Двоичные застежки-молнии образуют Comonad

Теперь, когда мы можем украсить элементы их контекстами, создадим экземпляр Comonad. Как и раньше...

instance Comonad BTZ where
  extract = here

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

  duplicate [email protected](BTZ { here = a, ctxt = DBT { below = ft, above = ads }}) = BTZ
    {  here = z
    ,  ctxt = DBT
         {  below = furtherIn a ft ads  -- move somewhere below a
         ,  above = go_a (a :& ft) ads  -- go above a
         }
    } where

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

    go_a t []          = []
    go_a t (ad : ads)  = go_ad t ad ads : go_a (plugBTinBT t ad) ads
    go_ad t (a, d) ads =
      (  BTZ { here = a, ctxt = DBT { below = plugF t d, above = ads } }  -- visit here
      ,  go_d t a d ads                                                   -- try other subtree
      )

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

    go_d t a (Left ((), r)) ads = Left ((), downIn r ((a, Right (t, ())) : ads))
    go_d t a (Right (l, ())) ads = Right (downIn l ((a, Left ((), t)) : ads), ())

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

Посмотрим. Здесь мы посетили 1:

duplicate (BTZ {here = 1, ctxt = DBT {
                below = Fork (2 :& Leaf,3 :& Leaf),
                above = [(0,Left ((),4 :& Leaf))]}}) =
  BTZ {here = BTZ {here = 1, ctxt = DBT {
                   below = Fork (2 :& Leaf,3 :& Leaf),
                   above = [(0,Left ((),4 :& Leaf))]}}, ctxt = DBT {
       below = Fork (BTZ {here = 2, ctxt = DBT {
                          below = Leaf,
                          above = [(1,Left ((),3 :& Leaf)),(0,Left ((),4 :& Leaf))]}} :& Leaf
                    ,BTZ {here = 3, ctxt = DBT {
                          below = Leaf,
                          above = [(1,Right (2 :& Leaf,())),(0,Left ((),4 :& Leaf))]}} :& Leaf
                   ),
       above = [(BTZ {here = 0, ctxt = DBT {
                      below = Fork (1 :& Fork (2 :& Leaf,3 :& Leaf),4 :& Leaf),
                      above = []}}
                ,Left ((),BTZ {here = 4, ctxt = DBT {
                               below = Leaf,
                               above = [(0,Right (1 :& Fork (2 :& Leaf,3 :& Leaf),()))]}} :& Leaf)
                )
               ]}}

В целях тестирования законов comonad на небольшой выборке данных, проверим:

fmap (\ z -> extract (duplicate z) == z) (down aTree)
  = True :& Fork (True :& Fork (True :& Leaf,True :& Leaf),True :& Leaf)
fmap (\ z -> fmap extract (duplicate z) == z) (down aTree)
  = True :& Fork (True :& Fork (True :& Leaf,True :& Leaf),True :& Leaf)
fmap (\ z -> fmap duplicate (duplicate z) == duplicate (duplicate z)) (down aTree)
  = True :& Fork (True :& Fork (True :& Leaf,True :& Leaf),True :& Leaf)