树拉链next_exn两种实现差异及down_exn左兄弟设空的疑问

树拉链定义及示例 #

type 'a ntree = Node of 'a * 'a ntree list

type 'a context =
  | Top
  | Context of 'a ntree list * 'a * 'a context * 'a ntree list

type 'a tree_zipper = TZ of 'a context * 'a ntree

let tz1 = TZ (Context (
                [Node ("*", [Node ("a", []); Node ("b", [])])],  (*left siblings in reverse order *)
                "+", (*value of parent node *)
                Top, (*parent's context *)
                []), (*right sibling in order *)
              Node ("*", [Node ("c", []); Node ("d", [])]));;

一、两种next_exn实现的差异 #

本人实现的next_exn #

let next_exn (TZ (c, t)) = (* on the right, not possible when context is top or right = []*)
  match c with
  | Top -> failwith "right of top node"
  | Context (left, v, up, []) -> failwith "right of last child" (*explain*)
  | Context (left, v, up, r::right) -> TZ (Context (t::left, v, up, right), r)

参考实现的next_exn #

let next_exn (TZ (c, t)) = (* on the right, not possible when context is top or right = []*)
  match c with
  | Top -> failwith "right of top node"
  | Context(left, v, up, r::right) -> TZ (Context(t::left, v, up, right), r)
  | _ -> failwith "right of last child"

这两种实现逻辑完全等价，不存在功能差异：

• 两者都优先处理了Top上下文的错误场景（根节点无法向右移动）；
• 对于Context类型的上下文，用户实现显式匹配了right为空的情况（触发最后一个子节点向右移动的错误），参考实现则通过通配符_覆盖了所有未匹配的Context场景（本质就是right为空的情况）；
• 合法移动的分支（right非空）处理逻辑完全一致：将当前节点加入左兄弟逆序列表，然后切换到右侧第一个兄弟节点。

只是模式匹配的写法和顺序不同，但覆盖的场景、触发的错误条件、执行的核心逻辑完全相同。

二、down_exn中左兄弟列表设为[]的原因 #

down_exn实现代码 #

let down_exn (TZ (c, t)) = 
  match t with (* go to first child *)
  | Node (_, []) -> failwith "down of leaf"
  | Node (v, d::ds) -> TZ (Context([], v, c, ds), d)

down_exn的作用是将拉链定位到当前节点的第一个子节点。根据树拉链的定义，Context的第一个参数是当前节点的左兄弟逆序列表：

• 第一个子节点在父节点的子节点列表中处于最左侧，没有任何位于它左边的兄弟节点，因此左兄弟列表自然为空；
• 后续如果从第一个子节点向右移动（调用next_exn），当前节点会被加入到左兄弟列表中，符合逆序存储左兄弟的设计规则。

所以这里将左兄弟列表初始化为[]是完全符合树拉链的结构设计的。

内容的提问来源于stack exchange，提问作者v_head