AFTD Auto-Formalizing Theoretical Domains

plane_tree_subtrees

def

The collection of all rooted subtrees T_v of a plane tree T.

Statement

def plane_tree_subtrees : PlaneTree → List PlaneTree
Defined in
arXiv:2611.10154 Sec. 2.2
Verified
10 Nov 2026
Axioms
none listed
Built on 1
  • PlaneTreeA finite plane tree is either a leaf or an internal node with a list of child plane trees.
Used by 4

Read back from the Lean

The function plane_tree_subtrees, which maps a plane tree t : PlaneTree to a list of plane trees (List PlaneTree), defined by recursion on sizeOf t such that: - For PlaneTree.leaf, it returns [PlaneTree.leaf]. - For PlaneTree.node cs (where cs : List PlaneTree is the list of children), it returns a list whose head is PlaneTree.node cs and whose tail is the concatenation in order of plane_tree_subtrees c for each child c in cs (i.e., cs.flatMap plane_tree_subtrees).

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

Lean source view module on GitHub

/-- The list of all full rooted subtrees of a plane tree. -/
def plane_tree_subtrees : PlaneTree → List PlaneTree
  | .leaf => [.leaf]
  | .node cs => .node cs :: (cs.attach.flatMap (fun ⟨c, _⟩ => plane_tree_subtrees c))
termination_by t => sizeOf t
See it in the graphDiscuss this resultChallenge it