Parsing a list of tuples with mutliple data types in SML

Question

So I am wanting a list of tuples that include a int key, and an int or boolean value:

[(0, 1), (1, 2), (2, true), (3, 4), ...]

I have been trying to write functions that would add a tuple to the list, as well as return a value given a key. For example:

getValue(2, [(0,1),(1,true),(2,3),(3,4)]); -> returns 3
getValue(1, [(0,1),(1,true),(2,3),(3,4)]); -> returns true
addValue([(0,1),(1,true),(2,3),(3,4)], (4, false)); -> [(0,1),(1,true),(2,3),(3,4),(4,false)]
addValue([(0,1),(1,true),(2,3),(3,4)], (2, 5)); -> [(0,1),(1,true),(2,5),(3,4)]

Here is the code I've produced so far, which works fine when strictly using int's or bools. When I combine them it gives me the error "operator and operand do not agree".

fun getValue (key1, list) =
  let
    fun parse [] = 0
      | parse ((key, v)::list) =
          if key1 = key then v
          else parse list;
  in
    parse list
  end;

fun addValue([], (key1, v1)) = [(key1, v1)]
  | addValue((key, v)::a, (key1, v1)) =
        if key1 = key then (key1, v1)::a
        else (key, v)::addValue(a, (key1, v1));

I'm very new to SML, and this may not even be possible. Just wanted to ask around. Thanks!

EDIT

What would be the reason this doesn't work?

datatype denotable_value =  Boolean of bool 
                          | Integer of int;

fun accessStore ( loc1, (env, s : (int * denotable_value) list) ) =
    let
        val msg = "Error: accessEnv " ^ Int.toString(loc1) ^ " not found.";

    fun aux [] = error msg
      | aux ( (loc, v)::s ) =
            if loc1 = loc then v
            else aux s;
    in
        aux s
    end;

accessStore(0, ([], [(0, 1), (1, true), (2, 3)]));

user_978917 · Answer

Indeed, what you describe is not possible; Standard ML uses static typing exclusively, which means that every expression needs to have a unique and well-defined type in order for the value to be understood at runtime. [(0, 1)] is OK, and has type (int * int) list; and [(2, true)] is OK, and has type (int * bool) list; but [(0, 1), (2, true)] is not OK, because an expression like (List.nth ([(0, 1), (2, true)], i) (which takes the ith element of the list) would have to be int * int or int * bool depending on the value of i, and that's just not how the type system works.

Instead, what you do is define a new algebraic data type for values that need to be either integers or booleans:

datatype intOrBool = INT of int | BOOL of bool

and wrap those values in that type using the appropriate constructor:

[(0, INT 1), (1, INT 2), (2, BOOL true), (3, INT 4)] : (int * intOrBool) list

(Of course, you'll want to use better names — more appropriate to your application — than intOrBool, INT, and BOOL; but hopefully the above gives you the idea.)

Parsing a list of tuples with mutliple data types in SML

1 Answers