数据结构差异化，直觉构建

Question

根据本文，微分适用于数据结构。

根据这个答案：

微分，数据类型 D 的导数（给出为 D'）是具有单个“洞”的 D 结构类型，即不包含任何数据的可区分位置。令人惊讶的是，这满足了与微积分微分相同的规则。

规则是：

 1 = 0
 X′ = 1
 (F + G)′ = F' + G′
 (F • G)′ = F • G′ + F′ • G
 (F ◦ G)′ = (F′ ◦ G) • G′

参考论文有点太复杂，我无法获得直觉。 这在实践中意味着什么？一个具体的例子就太好了。

Answer 1

X in an X 的单孔上下文是什么？没有选择：它是 (-)，由单位类型表示。

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。对多项式进行微分可以告诉您直接子树的上下文：叶子中没有子树；在节点中，它要么是左边的洞，右边的树，或者是左边的树，右边的洞。

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 z@(t, _) | p t       = [z]
                | otherwise = []
  below (Leaf,     _)  = []
  below (Node l r, cs) = go (l, NodeLeft () r : cs) ++ go (r, NodeRight l () : cs)

“下面”的作用是生成与给定树相关的树的居民。

区分数据类型是使“搜索”等程序变得通用的好方法。

Answer 2

我的解释是，T 的导数（拉链）是类似于 T 的“形状”的所有实例的类型，但恰好有 1 个元素被“洞”替换。

例如，列表是

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)

说明链式规则的第三个例子是玫瑰树（可变树）：

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

导数说R' t = 列表(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's 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（列表）。

（这些可能与传统类型不同，其中拉链是“方向”列表，但它们是同构的。）

---

导数是记录如何对结构中的位置进行编码的系统方法，例如我们可以使用以下命令进行搜索：（没有完全优化）

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)