以下是我为自己制作的一些图,以便更好地理解重写规则在树微积分中的工作原理,灵感来自于HN 上这篇有用的评论。
注意:根据此评论,Tree Calculus 的作者是 Barry Jay 教授,这里是他的Tree Book的链接。
树演算适用于二叉树,我将它们绘制为黑色节点和连接它们的线,根在顶部,子节点在下面。没有子节点的节点称为叶子,我将其绘制为黑色圆圈。具有单个子节点的节点称为茎,我将其绘制为黑色三角形。有两个子节点的节点称为叉子,我将其绘制为黑色方块。这些二叉树可以是任意深度。
有一个操作可以应用于两棵树之间,如虚线箭头所示。我认为它是“将左树与右树组合”,但在树微积分中,它本质上是“将左树的函数应用到右树的单个参数”。
我使用彩色形状作为“变量”,它们代表“任何种类的树,我们不在乎什么”。
这里是“归约规则”。规则(0a)
规则 (0b)
规则(1)
规则(2)
规则 (3a)
规则 (3b)
规则 (3c)
以下是树微积分的作者如何编码布尔值(位)和列表。
他将整数编码为布尔值列表——从最低有效位开始的任意长的二进制位列表。他将字符串编码为整数列表,每个整数代表一个 Unicode 代码点。