Problem with the use of Binary Map Data Structure in SML

Question

I want to create an ordered map with multiples nodes in SML . All i have found until now , exist here : https://www.smlnj.org/doc/smlnj-lib/Manual/binary-map-fn.html . So , i am trying something like this :

structure S = BinaryMapFn(struct
    type ord_key = int
    val compare = Int.compare
  end);

and then , i am trying to insert for example 2 nodes with value 0 and key values 1 and 2 , respectively :

S.insert(S.empty,1,0);
S.insert(S.empty,2,0);

output:val it = T {cnt=1,key=2,left=E,right=E,value=0} : int S.map

S.numItems(it);

output:val it = 1 : int

So, i am assuming by the output of numItems that it creates 2 binary maps with 1 node each and not a single one . I am pretty sure i am missing something , but there is not enough material and examples related to that structure .

Answer 1

The thing to look at is the type of the insert function, as well as empty in the signature ORD_MAP to which BinaryMapFn conforms.

val empty : 'a map 
val insert : ('a map * Key.ord_key * 'a) -> 'a map 

So, insert takes a (fromMap, key, x) and returns a new map which contains the elements of fromMap with x/key added as well with duplicate keys handled in some fashion.

To get a map with 2 elements, rather than using S.empty in both calls, you need to pass the return value of the first call as a parameter to the second.

note: It is worth noting that the smlnj-lib documentation is very old, and out of date, but i'm unaware of a newer link, so it is best to consult the source.