SML: просканируйте список отношений, чтобы получить все переходные ассоциации.

У меня есть список environment, в котором сохраняются связи между переменными и значениями, например env = [("x", 1), ("y", 2), ("z", 3), ...]. У меня также есть еще один список подстановок (который возвращается функцией управления сопоставлением с образцом), в котором сохраняются связи между переменными и образцом, например s = [("v", Var_p "z"), ("w", Var_p "v"), ("u", Var_p "w"), ...]. Рассмотрим первую пару ("v", Var_p "z"): моя функция должна проверить значение, соответствующее z, в среде, создать новую связь между значениями v и z (то есть ("v", 3)) и поместить ее в среду. Мой код для этой функции следующий.

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;

Здесь s — список подстановок, а exists и lookup — функции, которые проверяют наличие переменной в среде и ищут соответствующее значение соответственно. Проблема с этой функцией в том, что она отлично работает только для прямых ассоциаций (в примере она помещает в среду прямую ассоциацию между v и 3). Очевидно, что это не работает для транзитивных ассоциаций, если я не вызываю их несколько раз (которых я заранее не знаю, сколько их). Чтобы вспомнить пример, к концу этой функции мой список окружения должен быть env = [("x", 1), ("y", 2), ("z", 3), ("v", 3), ("w", 3), ("u", 3), ...].

Не могли бы вы дать мне подсказку о том, как изменить эту функцию, чтобы она нормально работала и с транзитивными ассоциациями?

Заранее спасибо!


list relation sml transitive-dependency smlnj
person Dree    schedule 09.06.2013    source источник

Ответы (1)


arrow_upward
1
arrow_downward

Во-первых, сложно дать точную подсказку, так как неизвестны функции lookup, augment_env_with_vars и некоторые типы.

Однако, исходя из того, что вы предоставили, это можно сделать так:

Возьмите 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)

Результат 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

Однако, если какая-либо переменная в вашем списке подстановок стоит перед ее определением, new_env завершится ошибкой. Чтобы решить эту проблему, просто просмотрите список замен перед обращением к lookup_env:

Возьмите 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)

Результат 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

Обратите внимание на переставленные «u» и «w» во втором примере.

person barti_ddu    schedule 11.06.2013