Applying a function to a custom type in F#

Question

On my journey to learning F#, I've run into a problem I cant solve. I have defined a custom type:

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

I have made a function which takes a tree, traverses it, and adds the elements it visits to a list, and returns it:

let rec inOrder tree = 
 seq{
 match tree with
  | Node (data, left, right) ->
   yield! inOrder left
   yield  data;
   yield! inOrder right
  | Empty -> ()
 }
 |> Seq.to_list;

Now I want to create a function, similar to this, which takes a tree and a function, traverses it and applies a function to each node, then returns the tree:

mapInOrder : ('a -> 'b) -> 'a BinTree -> 'b BinTree

This seems easy, and it probably is! But I'm not sure how to return the tree. I've tried this:

let rec mapInOrder f tree = 
 match tree with
 | Node(data, left, right) ->
  mapInOrder f left
  Node(f(data), left, right)
  mapInOrder f right
 | Empty -> ()

but this returns a unit. I havent worked with custom types before, so I'm probably missing something there!

Answer 1

Try this:

let rec mapInOrder f = function
  | Node(a,l,r) ->
      let newL = mapInOrder f l
      let b = f a
      let newR = mapInOrder f r
      Node(b,newL,newR)
  | Empty -> Empty

If the function is side-effect free, then traversal order is unimportant and you can instead write:

let rec map f = function
  | Node(a,l,r) -> Node(f a, map f l, map f r)
  | Empty -> Empty

Answer 2

A match is an expression. It returns the value of the matching case. That implies that all match cases must have the same type. The match expression itself then has that type.

In your first attempt, your Empty clause returned (), and thus had unit type--not the tree type you were looking for.

Since mapInOrder just returns the match result, it too took on unit return type.

The Node clause was fine because its return value is the result of calling mapInOrder, so it also took on unit type and the requirement that all match clauses have the same type was satisfied.

A key change in kvb's suggestion was making the Empty clause return a tree instead of unit. Once you do that, you get compiler errors and warnings pointing to the other problems.

You can often work through issues like this by explicitly coding the type you'd like, and then seeing where the compile errors and warnings show up.