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!
