2
\$\begingroup\$

I am currently exploring OCaml and wrote the following implementation of deleting a node from a binary tree

let rec deleteNode tree' value = 
  match tree' with 
  | Empty -> Empty
  | Node(left, nodeValue, right) -> 
      if value < nodeValue then
        Node((deleteNode left value), nodeValue, right)
      else if value > nodeValue then 
        Node(left, nodeValue, (deleteNode right value))
      else if left = Empty && right = Empty then 
        Empty
      else if left = Empty then 
        right
      else if right = Empty then
        left
      else 
        let newValue = minValue right in
        Node(left, newValue, (deleteNode right newValue))

Where my tree type is

type tree = 
  | Empty
  | Node of tree * int * tree

I am looking for a review of my code so that I can improve my OCaml and functional skills.

\$\endgroup\$
3
\$\begingroup\$

Syntax

There are no hard rules on this, but I would change a couple things in your syntax:

  • avoid ' in identifiers. Especially in that case, you can use tree instead of tree' (there is no collision with the type name).
  • usually there's a space before constructor arguments, like Node (left, nodeValue, right) (really up to convention, but I'd say it's more common).
  • parentheses around function application are not necessary, so it's more idiomatic to write Node (deleteNode left value, nodeValue, right). You can also extract a binding: let newLeft = deleteNode left value in Node (newLeft, nodeValue, right)
  • camel case is rare is ocaml (I know, that's weird!). For example the standard library uses names like print_endline etc. So, I'd use node_value, etc.

Replace conditionals with guards

Every time a if is in a pattern matching branch, you can extract it into a guard. The syntax is | pattern when condition ->.

By applying this to the first ifs, we can arrive to this state:

let rec deleteNode tree' value = 
  match tree' with 
  | Empty -> Empty
  | Node (left, nodeValue, right) when value < nodeValue ->
        Node((deleteNode left value), nodeValue, right)
  | Node (left, nodeValue, right) when value > nodeValue ->
        Node(left, nodeValue, (deleteNode right value))
  | Node (left, nodeValue, right) -> 
      if left = Empty && right = Empty then 
        Empty
      else if left = Empty then 
        right
      else if right = Empty then
        left
      else 
        let newValue = minValue right in
        Node(left, newValue, (deleteNode right newValue))

Use deep pattern matching

You can replace the x = Empty tests by pattern matching. In other words, patterns can contain patterns. By applying this to all the conditionals, we get:

let rec deleteNode tree' value = 
  match tree' with 
  | Empty -> Empty
  | Node (left, nodeValue, right) when value < nodeValue ->
        Node((deleteNode left value), nodeValue, right)
  | Node (left, nodeValue, right) when value > nodeValue ->
        Node(left, nodeValue, (deleteNode right value))
  | Node (Empty, nodeValue, Empty) -> 
        Empty
  | Node (Empty, nodeValue, right) -> 
        right
  | Node (left, nodeValue, Empty) -> 
        left
  | Node (left, nodeValue, right) -> 
        let newValue = minValue right in
        Node(left, newValue, (deleteNode right newValue))

 Remove redundant cases

That's more obvious with pattern matching, but the Node (Empty, nodeValue, right) cases also applies when right = Empty, so we can delete the more specific Node (Empty, nodeValue, Empty) case.

That's about it! Have a nice journey exploring OCaml.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.