shepmaster · March 11, 2020 05:21 · Sep 4, 2016 · Sep 1, 2016
diff --git a/rust-notes.md b/rust-notes.md
@@ -0,0 +1,15 @@
+1. The features are unused and should be removed. Otherwise can't use stable Rust.
+1. I tend to avoid trait bounds on types (`enum` / `struct`) and only put them on the functions that really need it. Technically, `depth` doesn't need `PartialEq`, so I might split the `impl` block into different pieces.
+1. Prefer `where` clauses for longer trait bounds. I just use them all the time; allowing ;
+1. Spaces after `:`.
+1. Accept `&Tree` for `depth`; there's no need to take ownership.
+1. Return a `usize` instead of `i32` (depth is conceptually limited by RAM) and there's no way it can be negative.
+1. Use `println!` instead of `print`; you want newlines.
+
+**Optional**
+
+1. Instead of taking ownership of the tree to insert into it, accept a mutable reference. Otherwise, there are many deallocations / allocations.
+
+**Questions**
+
+Is is acceptable to insert the same value twice?
diff --git a/tree.rs b/tree.rs
@@ -1,41 +1,71 @@
-#![feature(box_syntax, box_patterns)]
-
 use std::cmp::max;
 
-// Recursive structs must be referenced or be Box'd
-enum Tree<T:PartialOrd> {
+enum Tree<T>{
     Empty,
-    Node(T,  Box<Tree<T>>,  Box<Tree<T>>)
+    Node(T, Box<Tree<T>>, Box<Tree<T>>)
 }
 
-fn depth<T:PartialOrd>(tree:Tree<T>) -> i32 {
-    match tree {
-        Tree::Empty => 0,
-        Tree::Node(_, left, right) =>
-            1 + max(depth(*left), depth(*right))
+impl<T> Tree<T>
+    where T: PartialOrd
+{
+    fn depth(&self) -> usize {
+        match *self {
+            Tree::Empty => 0,
+            Tree::Node(_, ref left, ref right) =>
+                1 + max(left.depth(), right.depth())
+        }
     }
-}
 
-fn insert<T: PartialOrd>(x: T, tree:Tree<T>) ->  Tree<T> {
-    match tree {
-        Tree::Empty =>
-            Tree::Node(x, Box::new(Tree::Empty), Box::new(Tree::Empty)),
-        Tree::Node(value, left, right) =>
-            if x < value {
-                Tree::Node(value, Box::new(insert(x, *left)), right)
-            } else {
-                Tree::Node(value, left, Box::new(insert(x, *right)))
+    fn insert(self, value: T) -> Self {
+        match self {
+            Tree::Empty => {
+                Tree::Node(value, Box::new(Tree::Empty), Box::new(Tree::Empty))
+            },
+            Tree::Node(old_value, left, right) => {
+                if value < old_value {
+                    Tree::Node(old_value, Box::new(left.insert(value)), right)
+                } else {
+                    Tree::Node(old_value, left, Box::new(right.insert(value)))
+                }
             },
+        }
+    }
+
+    fn insert_mut(&mut self, value: T) -> &mut Self {
+        match *self {
+            Tree::Empty => {
+                *self = Tree::Node(value, Box::new(Tree::Empty), Box::new(Tree::Empty));
+            },
+            Tree::Node(ref old_value, ref mut left, ref mut right) => {
+                if &value < old_value {
+                    left.insert_mut(value);
+                } else {
+                    right.insert_mut(value);
+                }
+            }
+        }
+
+        self
     }
 }
 
 fn main() {
-    let tree = insert(2,
-        insert(6,
-            insert(3,
-                insert(4,
-                    insert(5, Tree::Empty)))));
-
-    let num = depth(tree);
-    print!("Depth is: {}", num);
-}
+    let tree = Tree::Empty
+        .insert(5)
+        .insert(4)
+        .insert(3)
+        .insert(6)
+        .insert(2);
+
+    println!("Depth is: {}", tree.depth());
+
+    let mut tree = Tree::Empty;
+    tree
+        .insert_mut(5)
+        .insert_mut(4)
+        .insert_mut(3)
+        .insert_mut(6)
+        .insert_mut(2);
+
+    println!("Depth is: {}", tree.depth());
+}
diff --git a/README.md b/README.md
@@ -0,0 +1,8 @@
+Here's two implementations of a binary search tree in OCaml and Rust. The Rust version was written to 
+deliberately look as close to the OCaml as possible (and it'd get pretty close if I used `match`
+instead of OCaml's variants). I'm pretty sure my OCaml implementation is idiomatic, and I'd like some advice on 
+what steps I'd probably take to make the Rust example more idiomatic. My objective is to talk about how 
+close the examples can be to each other as well as how different the examples can be (hopefully demonstrating
+strengths for both.)
+
+Any other thoughts or ideas are also helpful and super appreciated!
diff --git a/tree.ml b/tree.ml
@@ -0,0 +1,19 @@
+type 'a tree =
+    | Empty
+    | Node of 'a * 'a tree * 'a tree
+;;
+
+let rec depth =  function
+    | Empty -> 0
+    | Node(_, left, right) -> 1 + max (depth left) (depth right)
+;;
+
+let rec insert x = function
+    | Empty -> Node(x, Empty, Empty)
+    | Node(value, left, right) ->
+        if x < value then Node (value, insert x left, right)
+        else Node (value, left, insert x right)
+;;
+
+let root = insert 5 Empty |> insert 4 |> insert 3 in
+        print_string (string_of_int (depth root));;
diff --git a/tree.rs b/tree.rs
@@ -0,0 +1,41 @@
+#![feature(box_syntax, box_patterns)]
+
+use std::cmp::max;
+
+// Recursive structs must be referenced or be Box'd
+enum Tree<T:PartialOrd> {
+    Empty,
+    Node(T,  Box<Tree<T>>,  Box<Tree<T>>)
+}
+
+fn depth<T:PartialOrd>(tree:Tree<T>) -> i32 {
+    match tree {
+        Tree::Empty => 0,
+        Tree::Node(_, left, right) =>
+            1 + max(depth(*left), depth(*right))
+    }
+}
+
+fn insert<T: PartialOrd>(x: T, tree:Tree<T>) ->  Tree<T> {
+    match tree {
+        Tree::Empty =>
+            Tree::Node(x, Box::new(Tree::Empty), Box::new(Tree::Empty)),
+        Tree::Node(value, left, right) =>
+            if x < value {
+                Tree::Node(value, Box::new(insert(x, *left)), right)
+            } else {
+                Tree::Node(value, left, Box::new(insert(x, *right)))
+            },
+    }
+}
+
+fn main() {
+    let tree = insert(2,
+        insert(6,
+            insert(3,
+                insert(4,
+                    insert(5, Tree::Empty)))));
+
+    let num = depth(tree);
+    print!("Depth is: {}", num);
+}
No results found