data.tree | Mathlib porting status

Changes since the initial port

The following section lists changes to this file in mathlib3 and mathlib4 that occured after the initial port. Most recent changes are shown first. Hovering over a commit will show all commits associated with the same mathlib3 commit.

Changes in mathlib3

ed989ff5

(last sync)

Changes in mathlib3port

mathlib3

mathlib3port

69c6a5a1

bump to nightly-2023-09-24-06

mathlib commit https://github.com/leanprover-community/mathlib/commit/ce64cd319bb6b3e82f31c2d38e79080d377be451

5655435f

Diff

@@ -3,9 +3,9 @@ Copyright (c) 2019 mathlib community. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Mario Carneiro, Wojciech Nawrocki
 -/
-import Mathbin.Data.Rbtree.Init
-import Mathbin.Data.Num.Basic
-import Mathbin.Order.Basic
+import Data.Rbtree.Init
+import Data.Num.Basic
+import Order.Basic
 
 #align_import data.tree from "leanprover-community/mathlib"@"69c6a5a12d8a2b159f20933e60115a4f2de62b58"

69c6a5a1

bump to nightly-2023-07-20-09

mathlib commit https://github.com/leanprover-community/mathlib/commit/8ea5598db6caeddde6cb734aa179cc2408dbd345

9c56d0dd

Diff

@@ -2,16 +2,13 @@
 Copyright (c) 2019 mathlib community. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Mario Carneiro, Wojciech Nawrocki
-
-! This file was ported from Lean 3 source module data.tree
-! leanprover-community/mathlib commit 69c6a5a12d8a2b159f20933e60115a4f2de62b58
-! Please do not edit these lines, except to modify the commit id
-! if you have ported upstream changes.
 -/
 import Mathbin.Data.Rbtree.Init
 import Mathbin.Data.Num.Basic
 import Mathbin.Order.Basic
 
+#align_import data.tree from "leanprover-community/mathlib"@"69c6a5a12d8a2b159f20933e60115a4f2de62b58"
+
 /-!
 # Binary tree

69c6a5a1

bump to nightly-2023-06-27-05

mathlib commit https://github.com/leanprover-community/mathlib/commit/8b981918a93bc45a8600de608cde7944a80d92b9

9377c86a

Diff

@@ -61,10 +61,10 @@ instance : Inhabited (Tree α) :=
 
 #print Tree.ofRBNode /-
 /-- Makes a `tree α` out of a red-black tree. -/
-def ofRBNode : Rbnode α → Tree α
-  | Rbnode.leaf => nil
-  | Rbnode.red_node l a r => node a (of_rbnode l) (of_rbnode r)
-  | Rbnode.black_node l a r => node a (of_rbnode l) (of_rbnode r)
+def ofRBNode : Std.RBNode α → Tree α
+  | Std.RBNode.nil => nil
+  | Std.RBNode.node l a r => node a (of_rbnode l) (of_rbnode r)
+  | rbnode.black_node l a r => node a (of_rbnode l) (of_rbnode r)
 #align tree.of_rbnode Tree.ofRBNode
 -/

69c6a5a1

bump to nightly-2023-06-13-21

mathlib commit https://github.com/leanprover-community/mathlib/commit/9fb8964792b4237dac6200193a0d533f1b3f7423

829520ac

Diff

@@ -59,12 +59,14 @@ instance [Repr α] : Repr (Tree α) :=
 instance : Inhabited (Tree α) :=
   ⟨nil⟩
 
+#print Tree.ofRBNode /-
 /-- Makes a `tree α` out of a red-black tree. -/
 def ofRBNode : Rbnode α → Tree α
   | Rbnode.leaf => nil
   | Rbnode.red_node l a r => node a (of_rbnode l) (of_rbnode r)
   | Rbnode.black_node l a r => node a (of_rbnode l) (of_rbnode r)
 #align tree.of_rbnode Tree.ofRBNode
+-/
 
 #print Tree.indexOf /-
 /-- Finds the index of an element in the tree assuming the tree has been
@@ -179,7 +181,6 @@ def right : Tree α → Tree α
 #align tree.right Tree.right
 -/
 
--- mathport name: «expr △ »
 -- Notation for making a node with `unit` data
 scoped infixr:65 " △ " => Tree.node ()

69c6a5a1

bump to nightly-2023-06-01-04

mathlib commit https://github.com/leanprover-community/mathlib/commit/cca40788df1b8755d5baf17ab2f27dacc2e17acb

4d9eaa85

Diff

@@ -47,16 +47,14 @@ universe u
 
 variable {α : Type u}
 
-/- warning: tree.repr clashes with [anonymous] -> [anonymous]
-Case conversion may be inaccurate. Consider using '#align tree.repr [anonymous]ₓ'. -/
 /-- Construct a string representation of a tree. Provides a `has_repr` instance. -/
-def [anonymous] [Repr α] : Tree α → String
+def repr [Repr α] : Tree α → String
   | nil => "nil"
   | node a t1 t2 => "tree.node " ++ Repr.repr a ++ " (" ++ repr t1 ++ ") (" ++ repr t2 ++ ")"
-#align tree.repr [anonymous]
+#align tree.repr Tree.repr
 
 instance [Repr α] : Repr (Tree α) :=
-  ⟨[anonymous]⟩
+  ⟨Tree.repr⟩
 
 instance : Inhabited (Tree α) :=
   ⟨nil⟩

69c6a5a1

bump to nightly-2023-05-28-06

mathlib commit https://github.com/leanprover-community/mathlib/commit/917c3c072e487b3cccdbfeff17e75b40e45f66cb

ba5d8b97

Diff

@@ -48,11 +48,6 @@ universe u
 variable {α : Type u}
 
 /- warning: tree.repr clashes with [anonymous] -> [anonymous]
-warning: tree.repr -> [anonymous] is a dubious translation:
-lean 3 declaration is
-  forall {α : Type.{u}} [_inst_1 : Repr.{u} α], (Tree.{u} α) -> String
-but is expected to have type
-  forall {α : Type.{u}} {_inst_1 : Type.{v}}, (Nat -> α -> _inst_1) -> Nat -> (List.{u} α) -> (List.{v} _inst_1)
 Case conversion may be inaccurate. Consider using '#align tree.repr [anonymous]ₓ'. -/
 /-- Construct a string representation of a tree. Provides a `has_repr` instance. -/
 def [anonymous] [Repr α] : Tree α → String
@@ -66,12 +61,6 @@ instance [Repr α] : Repr (Tree α) :=
 instance : Inhabited (Tree α) :=
   ⟨nil⟩
 
-/- warning: tree.of_rbnode -> Tree.ofRBNode is a dubious translation:
-lean 3 declaration is
-  forall {α : Type.{u1}}, (Rbnode.{u1} α) -> (Tree.{u1} α)
-but is expected to have type
-  forall {α : Type.{u1}}, (Std.RBNode.{u1} α) -> (Tree.{u1} α)
-Case conversion may be inaccurate. Consider using '#align tree.of_rbnode Tree.ofRBNodeₓ'. -/
 /-- Makes a `tree α` out of a red-black tree. -/
 def ofRBNode : Rbnode α → Tree α
   | Rbnode.leaf => nil

69c6a5a1

bump to nightly-2023-05-28-04

mathlib commit https://github.com/leanprover-community/mathlib/commit/917c3c072e487b3cccdbfeff17e75b40e45f66cb

6797a637

Diff

@@ -159,9 +159,7 @@ theorem numLeaves_eq_numNodes_succ (x : Tree α) : x.numLeaves = x.numNodes + 1
 -/
 
 #print Tree.numLeaves_pos /-
-theorem numLeaves_pos (x : Tree α) : 0 < x.numLeaves :=
-  by
-  rw [num_leaves_eq_num_nodes_succ]
+theorem numLeaves_pos (x : Tree α) : 0 < x.numLeaves := by rw [num_leaves_eq_num_nodes_succ];
   exact x.num_nodes.zero_lt_succ
 #align tree.num_leaves_pos Tree.numLeaves_pos
 -/

69c6a5a1

bump to nightly-2023-03-14-02

mathlib commit https://github.com/leanprover-community/mathlib/commit/2196ab363eb097c008d4497125e0dde23fb36db2

d4b38a42

Diff

@@ -4,7 +4,7 @@ Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Mario Carneiro, Wojciech Nawrocki
 
 ! This file was ported from Lean 3 source module data.tree
-! leanprover-community/mathlib commit ed989ff568099019c6533a4d94b27d852a5710d8
+! leanprover-community/mathlib commit 69c6a5a12d8a2b159f20933e60115a4f2de62b58
 ! Please do not edit these lines, except to modify the commit id
 ! if you have ported upstream changes.
 -/
@@ -15,6 +15,9 @@ import Mathbin.Order.Basic
 /-!
 # Binary tree
 
+> THIS FILE IS SYNCHRONIZED WITH MATHLIB4.
+> Any changes to this file require a corresponding PR to mathlib4.
+
 Provides binary tree storage for values of any type, with O(lg n) retrieval.
 See also `data.rbtree` for red-black trees - this version allows more operations
 to be defined and is better suited for in-kernel computation.

ed989ff5

bump to nightly-2023-03-12-14

mathlib commit https://github.com/leanprover-community/mathlib/commit/f24cc2891c0e328f0ee8c57387103aa462c44b5e

9acddc1c

Diff

@@ -29,12 +29,14 @@ additional data. We provide the notation `a △ b` for making a `tree unit` with
 -/
 
 
+#print Tree /-
 /-- A binary tree with values stored in non-leaf nodes. -/
 inductive Tree.{u} (α : Type u) : Type u
   | nil : Tree
   | node : α → Tree → Tree → Tree
   deriving has_reflect, DecidableEq
 #align tree Tree
+-/
 
 namespace Tree
 
@@ -42,25 +44,39 @@ universe u
 
 variable {α : Type u}
 
+/- warning: tree.repr clashes with [anonymous] -> [anonymous]
+warning: tree.repr -> [anonymous] is a dubious translation:
+lean 3 declaration is
+  forall {α : Type.{u}} [_inst_1 : Repr.{u} α], (Tree.{u} α) -> String
+but is expected to have type
+  forall {α : Type.{u}} {_inst_1 : Type.{v}}, (Nat -> α -> _inst_1) -> Nat -> (List.{u} α) -> (List.{v} _inst_1)
+Case conversion may be inaccurate. Consider using '#align tree.repr [anonymous]ₓ'. -/
 /-- Construct a string representation of a tree. Provides a `has_repr` instance. -/
-def repr [Repr α] : Tree α → String
+def [anonymous] [Repr α] : Tree α → String
   | nil => "nil"
   | node a t1 t2 => "tree.node " ++ Repr.repr a ++ " (" ++ repr t1 ++ ") (" ++ repr t2 ++ ")"
-#align tree.repr Tree.repr
+#align tree.repr [anonymous]
 
 instance [Repr α] : Repr (Tree α) :=
-  ⟨Tree.repr⟩
+  ⟨[anonymous]⟩
 
 instance : Inhabited (Tree α) :=
   ⟨nil⟩
 
+/- warning: tree.of_rbnode -> Tree.ofRBNode is a dubious translation:
+lean 3 declaration is
+  forall {α : Type.{u1}}, (Rbnode.{u1} α) -> (Tree.{u1} α)
+but is expected to have type
+  forall {α : Type.{u1}}, (Std.RBNode.{u1} α) -> (Tree.{u1} α)
+Case conversion may be inaccurate. Consider using '#align tree.of_rbnode Tree.ofRBNodeₓ'. -/
 /-- Makes a `tree α` out of a red-black tree. -/
-def ofRbnode : Rbnode α → Tree α
+def ofRBNode : Rbnode α → Tree α
   | Rbnode.leaf => nil
   | Rbnode.red_node l a r => node a (of_rbnode l) (of_rbnode r)
   | Rbnode.black_node l a r => node a (of_rbnode l) (of_rbnode r)
-#align tree.of_rbnode Tree.ofRbnode
+#align tree.of_rbnode Tree.ofRBNode
 
+#print Tree.indexOf /-
 /-- Finds the index of an element in the tree assuming the tree has been
 constructed according to the provided decidable order on its elements.
 If it hasn't, the result will be incorrect. If it has, but the element
@@ -73,7 +89,9 @@ def indexOf (lt : α → α → Prop) [DecidableRel lt] (x : α) : Tree α → O
     | Ordering.eq => some PosNum.one
     | Ordering.gt => PosNum.bit1 <$> index_of t₂
 #align tree.index_of Tree.indexOf
+-/
 
+#print Tree.get /-
 /-- Retrieves an element uniquely determined by a `pos_num` from the tree,
 taking the following path to get to the element:
 - `bit0` - go to left child
@@ -85,57 +103,67 @@ def get : PosNum → Tree α → Option α
   | PosNum.bit0 n, node a t₁ t₂ => t₁.get n
   | PosNum.bit1 n, node a t₁ t₂ => t₂.get n
 #align tree.get Tree.get
+-/
 
+#print Tree.getOrElse /-
 /-- Retrieves an element from the tree, or the provided default value
 if the index is invalid. See `tree.get`. -/
 def getOrElse (n : PosNum) (t : Tree α) (v : α) : α :=
   (t.get n).getD v
 #align tree.get_or_else Tree.getOrElse
+-/
 
-/- warning: tree.map -> Tree.map is a dubious translation:
-lean 3 declaration is
-  forall {α : Type.{u1}} {β : Type.{u2}}, (α -> β) -> (Tree.{u1} α) -> (Tree.{u2} β)
-but is expected to have type
-  forall {α : Type.{u2}} {β : Type.{u1}}, (α -> β) -> (Tree.{u2} α) -> (Tree.{u1} β)
-Case conversion may be inaccurate. Consider using '#align tree.map Tree.mapₓ'. -/
+#print Tree.map /-
 /-- Apply a function to each value in the tree.  This is the `map` function for the `tree` functor.
 TODO: implement `traversable tree`. -/
 def map {β} (f : α → β) : Tree α → Tree β
   | nil => nil
   | node a l r => node (f a) (map l) (map r)
 #align tree.map Tree.map
+-/
 
+#print Tree.numNodes /-
 /-- The number of internal nodes (i.e. not including leaves) of a binary tree -/
 @[simp]
 def numNodes : Tree α → ℕ
   | nil => 0
   | node _ a b => a.numNodes + b.numNodes + 1
 #align tree.num_nodes Tree.numNodes
+-/
 
+#print Tree.numLeaves /-
 /-- The number of leaves of a binary tree -/
 @[simp]
 def numLeaves : Tree α → ℕ
   | nil => 1
   | node _ a b => a.numLeaves + b.numLeaves
 #align tree.num_leaves Tree.numLeaves
+-/
 
+#print Tree.height /-
 /-- The height - length of the longest path from the root - of a binary tree -/
 @[simp]
 def height : Tree α → ℕ
   | nil => 0
   | node _ a b => max a.height b.height + 1
 #align tree.height Tree.height
+-/
 
+#print Tree.numLeaves_eq_numNodes_succ /-
 theorem numLeaves_eq_numNodes_succ (x : Tree α) : x.numLeaves = x.numNodes + 1 := by
   induction x <;> simp [*, Nat.add_comm, Nat.add_assoc, Nat.add_left_comm]
 #align tree.num_leaves_eq_num_nodes_succ Tree.numLeaves_eq_numNodes_succ
+-/
 
+#print Tree.numLeaves_pos /-
 theorem numLeaves_pos (x : Tree α) : 0 < x.numLeaves :=
   by
   rw [num_leaves_eq_num_nodes_succ]
   exact x.num_nodes.zero_lt_succ
 #align tree.num_leaves_pos Tree.numLeaves_pos
+-/
 
+#print Tree.height_le_numNodes /-
 theorem height_le_numNodes : ∀ x : Tree α, x.height ≤ x.numNodes
   | nil => le_rfl
   | node _ a b =>
@@ -143,25 +171,31 @@ theorem height_le_numNodes : ∀ x : Tree α, x.height ≤ x.numNodes
       (max_le (trans a.height_le_numNodes <| a.numNodes.le_add_right _)
         (trans b.height_le_numNodes <| b.numNodes.le_add_left _))
 #align tree.height_le_num_nodes Tree.height_le_numNodes
+-/
 
+#print Tree.left /-
 /-- The left child of the tree, or `nil` if the tree is `nil` -/
 @[simp]
 def left : Tree α → Tree α
   | nil => nil
   | node _ l r => l
 #align tree.left Tree.left
+-/
 
+#print Tree.right /-
 /-- The right child of the tree, or `nil` if the tree is `nil` -/
 @[simp]
 def right : Tree α → Tree α
   | nil => nil
   | node _ l r => r
 #align tree.right Tree.right
+-/
 
 -- mathport name: «expr △ »
 -- Notation for making a node with `unit` data
 scoped infixr:65 " △ " => Tree.node ()
 
+#print Tree.unitRecOn /-
 /-- Recursion on `tree unit`; allows for a better `induction` which does not have to worry
   about the element of type `α = unit` -/
 @[elab_as_elim]
@@ -169,11 +203,14 @@ def unitRecOn {motive : Tree Unit → Sort _} (t : Tree Unit) (base : motive nil
     (ind : ∀ x y, motive x → motive y → motive (x △ y)) : motive t :=
   t.recOn base fun u => u.recOn ind
 #align tree.unit_rec_on Tree.unitRecOn
+-/
 
+#print Tree.left_node_right_eq_self /-
 theorem left_node_right_eq_self : ∀ {x : Tree Unit} (hx : x ≠ nil), x.left △ x.right = x
   | nil, h => by trivial
   | a △ b, _ => rfl
 #align tree.left_node_right_eq_self Tree.left_node_right_eq_self
+-/
 
 end Tree

ed989ff5

bump to nightly-2023-02-21-16

mathlib commit https://github.com/leanprover-community/mathlib/commit/bd9851ca476957ea4549eb19b40e7b5ade9428cc

1107b979

Changes in mathlib4

mathlib3

mathlib4

ed989ff5

doc: document some notation (#11922)

We cannot literally use @[inherit_doc] in these cases, but we can slightly modify the underlying docstring or a turn a regular comment into a doc comment.

1c8ae07c

Diff

@@ -145,7 +145,7 @@ def right : Tree α → Tree α
   | node _ _l r => r
 #align tree.right Tree.right
 
--- Notation for making a node with `Unit` data
+/-- A node with `Unit` data -/
 scoped infixr:65 " △ " => Tree.node ()
 
 -- Porting note: workaround for leanprover/lean4#2049

ed989ff5

chore: move some aliases earlier (#11122)

d1a1aa1b

Diff

@@ -3,11 +3,11 @@ Copyright (c) 2019 mathlib community. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Mario Carneiro, Wojciech Nawrocki
 -/
-import Std.Data.RBMap.Basic
 import Mathlib.Data.Num.Basic
-import Mathlib.Order.Basic
 import Mathlib.Init.Data.Ordering.Basic
+import Mathlib.Init.Order.LinearOrder
 import Mathlib.Util.CompileInductive
+import Std.Data.RBMap.Basic
 
 #align_import data.tree from "leanprover-community/mathlib"@"ed989ff568099019c6533a4d94b27d852a5710d8"

ed989ff5

style: homogenise porting notes (#11145)

Homogenises porting notes via capitalisation and addition of whitespace.

It makes the following changes:

converts "--porting note" into "-- Porting note";
converts "porting note" into "Porting note".

8be0b69c

Diff

@@ -148,7 +148,7 @@ def right : Tree α → Tree α
 -- Notation for making a node with `Unit` data
 scoped infixr:65 " △ " => Tree.node ()
 
--- porting note: workaround for leanprover/lean4#2049
+-- Porting note: workaround for leanprover/lean4#2049
 compile_inductive% Tree
 
 @[elab_as_elim]

ed989ff5

chore: fix imports (#8538)

f659b7bb

Diff

@@ -3,7 +3,7 @@ Copyright (c) 2019 mathlib community. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Mario Carneiro, Wojciech Nawrocki
 -/
-import Std.Data.RBMap
+import Std.Data.RBMap.Basic
 import Mathlib.Data.Num.Basic
 import Mathlib.Order.Basic
 import Mathlib.Init.Data.Ordering.Basic

ed989ff5

chore: banish Type _ and Sort _ (#6499)

We remove all possible occurences of Type _ and Sort _ in favor of Type* and Sort*.

This has nice performance benefits.

32de3f67

Diff

@@ -152,7 +152,7 @@ scoped infixr:65 " △ " => Tree.node ()
 compile_inductive% Tree
 
 @[elab_as_elim]
-def unitRecOn {motive : Tree Unit → Sort _} (t : Tree Unit) (base : motive nil)
+def unitRecOn {motive : Tree Unit → Sort*} (t : Tree Unit) (base : motive nil)
     (ind : ∀ x y, motive x → motive y → motive (x △ y)) : motive t :=
     -- Porting note: Old proof was `t.recOn base fun u => u.recOn ind` but
     -- structure eta makes it unnecessary (https://github.com/leanprover/lean4/issues/777).

ed989ff5

chore: script to replace headers with #align_import statements (#5979)

depends on: #5966

Co-authored-by: Eric Wieser <wieser.eric@gmail.com> Co-authored-by: Scott Morrison <scott.morrison@gmail.com>

89aa3a3b

Diff

@@ -2,11 +2,6 @@
 Copyright (c) 2019 mathlib community. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Mario Carneiro, Wojciech Nawrocki
-
-! This file was ported from Lean 3 source module data.tree
-! leanprover-community/mathlib commit ed989ff568099019c6533a4d94b27d852a5710d8
-! Please do not edit these lines, except to modify the commit id
-! if you have ported upstream changes.
 -/
 import Std.Data.RBMap
 import Mathlib.Data.Num.Basic
@@ -14,6 +9,8 @@ import Mathlib.Order.Basic
 import Mathlib.Init.Data.Ordering.Basic
 import Mathlib.Util.CompileInductive
 
+#align_import data.tree from "leanprover-community/mathlib"@"ed989ff568099019c6533a4d94b27d852a5710d8"
+
 /-!
 # Binary tree

ed989ff5

feat: add compile_inductive% and compile_def% commands (#4097)

Add a #compile inductive command to compile the recursors of an inductive type, which works by creating a recursive definition and using @[csimp].

Co-authored-by: Parth Shastri <31370288+cppio@users.noreply.github.com> Co-authored-by: Mario Carneiro <di.gama@gmail.com>

63c31ccb

Diff

@@ -12,6 +12,7 @@ import Std.Data.RBMap
 import Mathlib.Data.Num.Basic
 import Mathlib.Order.Basic
 import Mathlib.Init.Data.Ordering.Basic
+import Mathlib.Util.CompileInductive
 
 /-!
 # Binary tree
@@ -151,25 +152,7 @@ def right : Tree α → Tree α
 scoped infixr:65 " △ " => Tree.node ()
 
 -- porting note: workaround for leanprover/lean4#2049
-section recursor_workarounds
-
-/-- A computable version of `Tree.recOn`. Workaround until Lean has native support for this. -/
-def recOnC {α} {motive : Tree α → Sort u} (t : Tree α) (base : motive Tree.nil)
-  (ind : (a : α) → (l : Tree α) → (r : Tree α) → motive l → motive r → motive (Tree.node a l r))
-  : motive t :=
-  match t with
-  | nil => base
-  | Tree.node a l r => ind a l r (recOnC l base ind) (recOnC r base ind)
-
-@[csimp]
-lemma recOn_Unit_eq_recOnC : @Tree.recOn = @Tree.recOnC := by
-  ext α motive t base ind
-  induction t with
-  | nil => rfl
-  | node a l r ihl ihr =>
-    rw [Tree.recOnC, ←ihl, ←ihr]
-
-end recursor_workarounds
+compile_inductive% Tree
 
 @[elab_as_elim]
 def unitRecOn {motive : Tree Unit → Sort _} (t : Tree Unit) (base : motive nil)

ed989ff5

chore: tidy various files (#3110)

0bcbc985

Diff

@@ -51,7 +51,7 @@ instance : Inhabited (Tree α) :=
 
 open Std (RBNode)
 
-/-- Makes a `tree α` out of a red-black tree. -/
+/-- Makes a `Tree α` out of a red-black tree. -/
 def ofRBNode : RBNode α → Tree α
   | RBNode.nil => nil
   | RBNode.node _color l key r => node key (ofRBNode l) (ofRBNode r)
@@ -88,8 +88,8 @@ def getOrElse (n : PosNum) (t : Tree α) (v : α) : α :=
   (t.get n).getD v
 #align tree.get_or_else Tree.getOrElse
 
-/-- Apply a function to each value in the tree.  This is the `map` function for the `tree` functor.
-TODO: implement `traversable tree`. -/
+/-- Apply a function to each value in the tree.  This is the `map` function for the `Tree` functor.
+TODO: implement `Traversable Tree`. -/
 def map {β} (f : α → β) : Tree α → Tree β
   | nil => nil
   | node a l r => node (f a) (map f l) (map f r)
@@ -147,7 +147,6 @@ def right : Tree α → Tree α
   | node _ _l r => r
 #align tree.right Tree.right
 
--- mathport name: «expr △ »
 -- Notation for making a node with `Unit` data
 scoped infixr:65 " △ " => Tree.node ()

ed989ff5

feat: Port Data.Tree (#2587)

Co-authored-by: Eric Wieser <wieser.eric@gmail.com>

c1167dd0

`data.tree` ⟷ `Mathlib.Data.Tree`

Changes since the initial port

Changes in mathlib3

Changes in mathlib3port

Changes in mathlib4

Dependencies 4

data.tree ⟷ Mathlib.Data.Tree

Changes since the initial port

Changes in mathlib3

Changes in mathlib3port

Changes in mathlib4

Dependencies 4

`data.tree` ⟷ `Mathlib.Data.Tree`