Map implementation in F#

Just as a refresher I put together a simple Map implementation and I would love to get some feedback on it.

```
open System
open System.Collections.Generic

type Node = {
key : 'a
value : 'b
left : option>
right : option>
}

type Map(root : option>) =

let comparer = LanguagePrimitives.FastGenericComparer

let rec add (key : 'a) (value : 'b) (node : Node) =
match comparer.Compare (key, node.key) with
| r when r
match node.left with
| Some n ->
match comparer.Compare (key, n.key) with
| r when r > 0 ->
let left = Some {
key = key
value = value
left = node.left
right = None
}
Some { node with left = left }
| _ ->
Some { node with left = add key value n }
| None ->
let left = Some {
key = key
value = value
left = None
right = None
}
Some { node with left = left }
| r when r > 0 ->
match node.right with
| Some n ->
match comparer.Compare (key, n.key) with
| r when r
let right = Some {
key = key
value = value
left = None
right = node.right
}
Some { node with right = right }
| _ ->
Some { node with right = add key value n }
| None ->
let right = Some {
key = key
value = value
left = None
right = None
}
Some { node with right = right }

Second revision

Ok, first of all it would really help if you added some comments. I would also suggest giving your variables names which have more than one letter.

In particular it would be a good idea to describe the algorithms being used. In particular you should document what kind of tree and balancing algorithm you're using.

Speaking of: your tree kind of looks like an AVL tree except that in AVL trees the maximum difference between heights is 1, while you allow a difference of 2. Since you never said that you were trying to implement an AVL tree, I'm not sure whether that's intentional or not.

Some notes on particular pieces of code:

match height left, height right with
| l, r when l >= r -> l + 1
| l, r -> r + 1

That's just a cumbersome way to write max (height left) (height right).

Some {
    key = key
    value = value
    height = node.height + 1
    left = None
    right = None
}

This looks like a mistake. If both the subtrees are empty, then clearly the height is 1 and not dependent on node.

I would also recommend that instead of using Node options you define an actual tree type like this: type ('a * 'b) tree = Node of ('a, 'b) Node | EmptyTree. This way you can refer to empty trees as EmptyTree rather than None and to nodes as Node {...} rather than Some {...}. Of course that's just cosmetics, but I do think it reads much nicer.

First revision

One minor style point is that you might want to call your FromSeq method ofSeq instead as that is what the equivalent function of F#'s Map module is called.

Regarding performance the most obvious problem is that your tree is not balanced in any way. If you create a map from a sorted list of keys, it will degenerate into a linked list and have much worse performance than F#'s standard map class. Just compare the time it takes to create your map from Seq.zip [1..500000] [1..500000] to the time the standard Map needs for the same input.

To address this, you should implement some kind of balancing. For example you may use red-black trees, which is what F#'s standard map uses.

StackExchange Code Review Q#1107, answer score: 8