SML: Scan a relation list to get all the transitive associations

Question

I have an environment list which keeps associations between variables and values, such as env = [("x", 1), ("y", 2), ("z", 3), ...]. I also have another substitution list (which is returned by a pattern matching control function) that keeps associations between variables and pattern, such as s = [("v", Var_p "z"), ("w", Var_p "v"), ("u", Var_p "w"), ...]. Let's consider the first pair ("v", Var_p "z"): my function should check the value corresponding to zin the environment, create a new association between v and z's value (i. e. ("v", 3)) and put it into the environment. My code for this function is the following.

fun augment_env ([], e : env) = e
  | augment_env (s :: srest, e : env) =
     let
        val (a, b) = s
     in
        case b of
           Const_p i => [] @ augment_env_with_vars (srest, e)
         | Var_p x =>
            if (exists (e, x)) then (a, lookup (e, x)) :: augment_env_with_vars (srest, e)
     end;

Here, s is the substitution list and exists and lookup are functions which check the existence of a variable in the environment and look for the corresponding value, respectively. The problem with this function is that works fine only for direct associations (in the example, it puts the direct association between v and 3 into the environment). It obviously doesn't work for the transitive associations unless I call it multiple times (which I don't know in advance how many they are). To recall the example, by the end of this function, my environment list should be env = [("x", 1), ("y", 2), ("z", 3), ("v", 3), ("w", 3), ("u", 3), ...].

Could you please give me a hint about how to modify this function to work fine with the transitive associations, too?

Thanks in advance!

Answer 1

First, it is hard to give precise hint since functions lookup, augment_env_with_vars and some types are unknown.

However, guessing from what you've provided, it could be done like:

Take 1

type const = int
type var = string
type env = (var * const) list
datatype value = Const_p of const | Var_p of var

exception Not_found

fun lookup_env (e, v) =
    case e of
        [] => raise Not_found
      | (a, b)::xs => if a = v then b else lookup_env (xs, v)

fun new_env (l, e) =
    case l of
        [] => e
      | (a, b)::xs =>
        case b of
            Const_p _ => new_env (xs, e)
          | Var_p b => new_env (xs, e @ [(a, lookup_env (e, b))])

(* test *)

val e = [("x", 1), ("y", 2), ("z", 3)]
val s = [("v", Var_p "z"), ("w", Var_p "v"), ("u", Var_p "w")]

val test = new_env (s, e)

Result 1

val e = [("x",1),("y",2),("z",3)] : (string * int) list
val s = [("v",Var_p "z"),("w",Var_p "v"),("u",Var_p "w")]
  : (string * value) list
val test = [("x",1),("y",2),("z",3),("v",3),("w",3),("u",3)]
  : (var * int) list

However, if any variable in your substitution list comes before its definition, new_env will fail. To solve this, just scan the substitution list before referring to lookup_env:

Take 2

fun lookup_var (l, v) =
    case l of
        [] => v
      | (a, b)::xs =>
        case b of
            Const_p _ => lookup_var (xs, v)
          | Var_p b => lookup_var (if a = v then (l, b) else (xs, v))

fun new_env2 (l, e) =
    case l of
        [] => e
      | (a, b)::xs =>
        case b of
            Const_p _ => new_env2 (xs, e)
          | Var_p b => new_env2 (xs, e @ [(a, lookup_env (e, lookup_var (l, b)))])

(* test *)

val e = [("x", 1), ("y", 2), ("z", 3)]
val s2 = [("v", Var_p "z"), ("u", Var_p "w"), ("w", Var_p "v")]

val test2 = new_env2 (s2, e)

Result 2

val e = [("x",1),("y",2),("z",3)] : (string * int) list
val s2 = [("v",Var_p "z"),("u",Var_p "w"),("w",Var_p "v")]
  : (string * value) list
val test2 = [("x",1),("y",2),("z",3),("v",3),("u",3),("w",3)]
  : (var * int) list

Note the swapped "u" and "w" in the second example.