Implementation of binary search tree in OCaml and Rust (modeled after the OCaml solution).

README.md

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!

tree.ml

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));;

tree.rs

#![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);
}

This is cool!! What's the 'a in the OCaml-- is that a lifetime????

Here's one way to make the rust more idiomatic: https://gist.github.com/anonymous/7216b276410e84db3be86c1647d6f856

I'm going to have Jake try it too, to see if he comes up with something different :) Let me know if you have any questions about why I changed what!

Ah!!! That impl refactor is totally what I'm looking for! I really wasn't happy with creating that tree when compared to OCaml's Pipe operator, but that refactor is totally where it's at! Thank you so much! I'd love to see what Jake thinks as well!

I'm really enjoying where the comparing and contrasting of a simple problem is evolving. I may do another small comparison problem, but I'm also thinking about easy changes that people to add some interaction to help people feel good about what they're learning. I want to be very careful not to "blow anyone's mind" because I want people to leave feeling empowered to experiment and enthusiastic. Do you have any thoughts on that?

The 'a in OCaml indicates a generic type. I can pass anything that OCaml knows how to compare (comes from the Pervasives module I think?) Rust is able to just start handling it by implementing PartialOrd on the struct. I actually prefer how Rust operates here; my research doesn't lead me to an obvious way to extend/add Pervasives for a more complex type (granted I could have easily just missed it), but it's pretty obvious what my structs need to provide in Rust. I like it!

I want people to leave feeling empowered to experiment and enthusiastic. Do you have any thoughts on that?

That sounds perfect :)