(这个响应使用数据修复库,因为我无法编译递归方案。)
我们可以将两棵树的差异建模为一个基于原始函子的“差异函子”的展开或非同态。
考虑以下类型:
data DiffF func r = Diff (Fix func) (Fix func)
| Nodiff (func r)
deriving (Functor)
type ExprDiff = Fix (DiffF ExprF)
这个想法是,只要ExprDiff
和原始Expr
树保持相同的“通用结构”,那么在遇到不同之前,我们将跟随它,但一旦遇到差异,我们就会切换到Diff
叶子节点,该节点存储了我们发现不同的两个子树。
实际比较函数如下:
diffExpr :: Expr -> Expr -> ExprDiff
diffExpr e1 e2 = ana comparison (e1,e2)
where
comparison :: (Expr,Expr) -> DiffF ExprF (Expr,Expr)
comparison (Fix (Const i),Fix (Const i')) | i == i' =
Nodiff (Const i')
comparison (Fix (Add a1 a2),Fix (Add a1' a2')) =
Nodiff (Add (a1,a1') (a2,a2'))
comparison (something, otherthing) =
Diff something otherthing
"种子"是指我们想要比较的表达式对。如果我们只需要一个谓词
Expr -> Expr -> Bool
,我们可以后续使用一个合成函数来检测
Diff
分支的存在。请注意保留HTML标记。