Дифференциация структуры данных, построение интуиции

Ответ 1

Какой контекст одной дыры для X в X? Нет выбора: it (-), представляемый типом единицы.

Какой контекст для одной дыры для X в X * X? Это что-то вроде (-, x2) или (x1, -), поэтому оно представляется X + X (или 2 * X, если хотите).

Какое одно отверстие для X в X * X * X? Это что-то вроде (-, x2, x3) или (x1, -, x3) или (x1, x2, -), представимое X * X + X * X + X * X или (3 * X ^ 2, если вам нравится).

В более общем смысле F * G с отверстием представляет собой либо F с отверстием и G неповрежденным, либо F неповрежденным, и G с дыркой.

Рекурсивные типы данных часто определяются как фиксированные точки многочленов.

data Tree = Leaf | Node Tree Tree

действительно говорит Tree = 1 + Tree * Tree. Дифференциация полинома сообщает вам контексты для непосредственных поддеревьев: без поддеревьев в Листе; в Node, это либо отверстие слева, дерево справа, либо дерево слева, отверстие справа.

data Tree' = NodeLeft () Tree | NodeRight Tree ()

Чтобы многочлен дифференцировался и отображался как тип. Таким образом, контекст для поддерева в дереве представляет собой список шагов дерева.

type TreeCtxt = [Tree']
type TreeZipper = (Tree, TreeCtxt)

Здесь, например, есть функция (незапрашиваемый код), которая ищет дерево для поддеревьев, передающих заданное тестовое поддерево.

search :: (Tree -> Bool) -> Tree -> [TreeZipper]
search p t = go (t, []) where
  go :: TreeZipper -> [TreeZipper]
  go z = here z ++ below z
  here :: TreeZipper -> [TreeZipper]
  here [email protected](t, _) | p t       = [z]
                | otherwise = []
  below (Leaf,     _)  = []
  below (Node l r, cs) = go (l, NodeLeft () r : cs) ++ go (r, NodeRight l () : cs)

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

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

Ответ 2

Моя интерпретация такова, что производная (застежка-молния) T является типом всех экземпляров, которые напоминают "форму" T, но с точно одним элементом, замененным "дырой".

Например, список -

List t = 1     []
       + t     [a]
       + t^2   [a,b]
       + t^3   [a,b,c]
       + t^4   [a,b,c,d]
       + ...   [a,b,c,d,...]

если мы заменим любой из этих "a", "b", "c" и т.д. отверстием (представленным как @), мы получим

List' t = 0      empty list doesn't have hole
        + 1      [@]
        + 2*t    [@,b]     or [a,@]
        + 3*t^2  [@,b,c]   or [a,@,c]   or [a,b,@]
        + 4*t^3  [@,b,c,d] or [a,@,c,d] or [a,b,@,d] or [a,b,c,@]
        + ...

Другой пример: дерево

data Tree t = TEmpty | TNode t (Tree t) (Tree t)
-- Tree t = 1 + t (Tree t)^2

поэтому добавление отверстия генерирует тип:

{-

Tree' t = 0                    empty tree doesn't have hole
        + (Tree X)^2           the root is a hole, followed by 2 normal trees
        + t*(Tree' t)*(Tree t) the left tree has a hole, the right is normal
        + t*(Tree t)*(Tree' t) the left tree is normal, the right has a hole

          @    or      x     or     x    
         / \          / \          / \   
        a   b       @?   b        a   @?
       /\   /\     / \   /\      /\   /\ 
      c  d e  f   @? @? e  f    c  d @? @?
-}

data Tree' t = THit (Tree t) (Tree t)
             | TLeft t (Tree' t) (Tree t)
             | TRight t (Tree t) (Tree' t)

Третий пример, иллюстрирующий правило цепи, - это дерево rose (вариационное дерево):

data Rose t = RNode t [Rose t]
-- R t = t*List(R t)

производная говорит R' t = List(R t) + t * List'(R t) * R' t, что означает

{-

R' t = List (R t)        the root is a hole
     + t                 we have a normal root node,
       * List' (R t)       and a list that has a hole,
       * R' t              and we put a holed rose tree at the list hole

        x
        |
       [a,b,c,...,p,@?,r,...]
                    |
                   [@?,...]

-}

data Rose' t = RHit [Rose t] | RChild t (List' (Rose t)) (Rose' t)

Обратите внимание, что data List' t = LHit [t] | LTail t (List' t).

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

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

locateL :: (t -> Bool) -> [t] -> Maybe (t, List' t)
locateL _ [] = Nothing
locateL f (x:xs) | f x       = Just (x, LHit xs)
                 | otherwise = do
                                  (el, ctx) <- locateL f xs
                                  return (el, LTail x ctx)

locateR :: (t -> Bool) -> Rose t -> Maybe (t, Rose' t)
locateR f (RNode a child)
      | f a       = Just (a, RHit child)
      | otherwise = do 
                      (whichChild, listCtx) <- locateL (isJust . locateR f) child
                      (el, ctx) <- locateR f whichChild
                      return (el, RChild a listCtx ctx)

и мутировать (подключить отверстие) с помощью контекстной информации:

updateL :: t -> List' t -> [t]
updateL x (LHit xs) = x:xs
updateL x (LTail a ctx) = a : updateL x ctx

updateR :: t -> Rose' t -> Rose t
updateR x (RHit child) = RNode x child
updateR x (RChild a listCtx ctx) = RNode a (updateL (updateR x ctx) listCtx)