CODEWITHSUNDEEP
listsmlsmlnj
Ankit Shubham
Ankit Shubham

Reputation: 3599

Keeping null value in tuple of a list in sml

I want to create a map kind of data structure using list having specification :(string*int) list where first element is key and second element is value. Initially when I create this map, I just want to give key with no value. How can I pass null value in this case? For example, I need something like this when initializing:

val gamma = [("a",_),("b",_),("c",_)] :(string*int) list

Of course, I should be able to edit the value corresponding to certain key. For example, I should be able to change

[("a",_),("b",_),("c",_)]

to ,say something like:

[("a",20),("b",30),("c",40)]

Upvotes: 1

Views: 888

Answers (1)

John Coleman
John Coleman

Reputation: 51998

If all of the valid ints in the list are strictly positive you could use 0 as a null value, or perhaps ~1 if 0 is valid but negatives are not. Otherwise, you could use an int option. Something like:

fun set key value [] = []
|   set key value ((k,v)::pairs) = 
        if k = key then (k, SOME value) :: pairs
        else (k,v) :: (set key value pairs)

fun lookup key ((k,v)::pairs) =
        if k = key then v else lookup key pairs

fun initDict keys = map (fn k => (k,NONE)) keys;

Then, for example:

- val gamma = initDict ["a","b","c"]: (string * int option) list;
val gamma = [("a",NONE),("b",NONE),("c",NONE)] : (string * int option) list

You can "change" the values like thus:

= set "b" 30 gamma;
[("a",NONE),("b",SOME 30),("c",NONE)] : (string * int option) list

Values can be read like this:

- lookup "a" gamma;
val it = NONE : int option
- lookup "b" gamma;
val it = SOME 30 : int option

Note that lookup throws an error if the key isn't in the dictionary. Since we are using NONE as a null value for entries it can't also function as a flag for the absence of a key.

The actual values can be extracted from the options using the valOf operator:

- valOf (lookup "b" gamma);
val it = 30 : int

The scare quotes around "change" above were because with this approach set constructs a new list and binds it to the name gamma rather than changing gamma in place. If this list is at all large, this (as well as the constant linear searches over the list) would become quite inefficient. At some stage you might want to start using mutable data structures (e.g. sorted arrays of refs).

Upvotes: 2

Related Questions