5
\$\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\$

2 Answers 2

Reset to default
8
\$\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\$
1
  • \$\begingroup\$ Suggestion: don't bother binding names to patterns that aren't used. E.g. Node (Empty, nodeValue, Empty) -> Empty => Node (Empty, _, Empty) -> Empty \$\endgroup\$ Commented Sep 21, 2024 at 23:40
2
\$\begingroup\$

Taking Étienne Millon's answer a bit further, we can use _ when binding parts of patterns we don't care about.

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, _, Empty) -> 
      Empty
  | Node (Empty, _, right) -> 
      right
  | Node (left, _, Empty) -> 
      left
  | Node (left, nodeValue, right) -> 
      let newValue = minValue right in
      Node (left, newValue, deleteNode right newValue)

And then let's reorder the patterns a bit. The basic logic is unaffected. We can also eliminate the redundant cases involving returning the right branch.

let rec deleteNode tree value = 
  match tree with 
  | 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)
  | Empty -> Empty
  | Node (Empty, _, right) -> 
      right
  | Node (left, _, Empty) -> 
      left
  | Node (left, nodeValue, right) -> 
      let newValue = minValue right in
      Node (left, newValue, deleteNode right newValue)

OCaml allows us to "or" patterns together when the same names are bound in all of the patterns. That is not the case for Empty, Node (Empty, _, right), and Node (left, _, Empty) but it can be.

let rec deleteNode tree value = 
  match tree with 
  | 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)
  | Empty as t
  | Node (Empty, _, t) 
  | Node (t, _, Empty) -> 
      t
  | Node (left, nodeValue, right) -> 
      let newValue = minValue right in
      Node (left, newValue, deleteNode right newValue)

A final thought is that it's fairly idiomatic if one looks at the standard library as a guide for the deleteNode function to take the value to delete as its first argument.

let rec deleteNode value = function 
  | Node (left, nodeValue, right) when value < nodeValue ->
      Node (deleteNode value lef, nodeValue, right)
  | Node (left, nodeValue, right) when value > nodeValue ->
      Node (left, nodeValue, deleteNode value right)
  | Empty as t
  | Node (Empty, _, t) 
  | Node (t, _, Empty) -> 
      t
  | Node (left, nodeValue, right) -> 
      let newValue = minValue right in
      Node (left, newValue, deleteNode newValue right)

This facilitates using the |> and @@ operators to clean up code and make it easier to understand.

E.g.

my_tree |> deleteNode 4 |> deleteNode 3 |> deleteNode 5

Vs.

deleteNode (deleteNode (deleteNode my_tree 4) 3) 5
\$\endgroup\$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.