2个回答
24
什么是X中的一个一洞上下文？答案是 (-)，用单元类型表示。
X*X 中的一个一洞上下文是类似于(-，x2)或(x1，-)之类的东西，因此可以用 X+X（或者 2*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。
递归数据类型通常被定义为多项式的不动点。
那就是把多项式求导后渲染成一种类型。因此，树中子树的上下文就是这些Tree'步骤的列表。
例如，这里有一个函数（未经尝试的代码），它可以搜索树以寻找通过给定测试子树的子树。
"below"的作用是生成与给定Tree相关的Tree居民。
数据类型的区分是使程序像“搜索”等更加通用的好方法。
X*X 中的一个一洞上下文是类似于(-，x2)或(x1，-)之类的东西，因此可以用 X+X（或者 2*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
这句话实际上是在说树等于1加上树乘以树。对多项式进行微分可以告诉你关于直接子树的上下文：在叶子节点中没有子树；在节点中，左侧为空洞，右侧为树，或者左侧为树，右侧为空洞。
data Tree' = NodeLeft () Tree | NodeRight Tree ()
那就是把多项式求导后渲染成一种类型。因此，树中子树的上下文就是这些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)
"below"的作用是生成与给定Tree相关的Tree居民。
数据类型的区分是使程序像“搜索”等更加通用的好方法。
- Conor
1
太棒了。非常直观的解释。我喜欢作者自己回答论文问题的方式。我将寻找在我的工作中应用数据类型导数的地方。 - dsg
12
我的理解是，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 = 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'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 (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)
- kennytm
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接
e^X = 1 + X + X^2/2 + X^3/3! + ...。你怎么除以一个类型呢？:) - kennytmexp被定义为方程F'(X) = F(X)的解（作为方程的“通用”解，无论是初始还是终端，就像列表是方程L(X) = 1 + A L(X)的解一样）。我不知道哪些函子满足它（如果有的话），也不知道它们的用途。 - Alexandre C.