Ketik untuk “nilai cara bisa berbeda”

Saya mencari konsep dalam teori tipe yang saya yakin mungkin telah dieksplorasi, tetapi tidak tahu nama di baliknya.

Mari kita pertimbangkan bahasa seperti ML dengan tipe produk dan jumlah dan sistem tipe seperti Hindley-Milner. Saya akan menggunakan sintaks OCaml.

Saya bertanya-tanya tentang cara dua nilai yang berbeda dapat berbeda.

Menggunakan

Kasing penggunaan saya adalah menulis pesan kesalahan "lebih jelas" di perpustakaan seperti xUnit: jika dua nilai berbeda ketika mereka diharapkan sama, ini dapat membantu membangun pesan yang lebih jelas lebih baik:

Sebelum:

Nilai berbeda: diharapkan {x = [1;2;3;4], y = "a long string"}, didapat{x = [1;2;3;3], y = "a long string"}

Setelah:

Nilai berbeda: pada posisi .x[3], diharapkan 4, mendapat 3.

(mungkin ada hubungan dengan lensa fungsional karena kami akhirnya membangun lensa ke nilai yang lebih kecil yang berbeda).

Jenis produk

Sebagai contoh:

type p =
  { x : int
  ; y : string
  }

Kesetaraan dapat didefinisikan sebagai:

let equal a b =
  equal_int a.x b.x && equal_string a.y b.y

Tetapi juga dimungkinkan untuk memverifikasi perbedaan:

type delta_p =
  | Equal
  | Diff_x of int * int
  | Diff_y of string * string

let diff_p a b =
  if not (equal_int a.x b.x) then
    Diff_x (a.x, b.x)
  else if not (equal_string a.y b.y) then
    Diff_y (a.y, b.y)
  else
    Equal

(Mungkin masuk akal untuk mendefinisikan suatu delta_inttipe int * intuntuk menunjukkan bahwa itu adalah rekursif)

Jumlah jenis

Untuk tipe penjumlahan ada lebih banyak cara untuk berbeda: memiliki konstruktor yang berbeda, atau nilai yang berbeda

type s = X of int | Y of string

type ctor_s =
  | Ctor_X
  | Ctor_Y

type delta_s =
  | Equal
  | Diff_ctor of ctor_s * ctor_s
  | Diff_X of int * int
  | Diff_Y of string * string

let diff_s a b = match (a, b) with
  | X xa, X xb ->
    if equal_int xa xb then
      Equal
    else
      Diff_X (xa, xb)
  | (* Y case similar *)
  | X _, Y _ -> Diff_ctor (Ctor_X, Ctor_Y)
  | Y _, X _ -> Diff_ctor (Ctor_Y, Ctor_X)

Apa nama konsep ini? Di mana saya bisa belajar lebih banyak tentang ini?

Terima kasih!

Saya pikir Anda sedang mencari varian anti-unifikasi yang diketik . Anti-unifikasi dapat digambarkan sebagai berikut. Pertama, misalkan kita memiliki tata bahasa dari istilah sebagai berikut:

t ::= () | (t, t) | C t | X 

Di sini, ()dan (t, t)menunjukkan unit dan pasangan, C tadalah istilah dengan konstruktor terkemuka, dan Xmerupakan variabel istilah, yang dapat diganti dengan istilah apa pun.

Masalah anti-unifikasi mengatakan, jika Anda memberikan dua istilah t1dan t2, apa istilah paling umum tsehingga ada substitusi s1dan s2seperti itu s1(t) = t1dan s2(t) = t2.

Sebagai contoh konkret, diberikan dua istilah

t1 = Cons(3, Cons(2, Cons(1, Nil)))
t2 = Cons(1, Cons(2, Cons(3, Nil)))

algoritma anti-unifikasi akan mengembalikan anti-pemersatu

t = Cons(X, Cons(2, Cons(Y, Nil)))

karena penggantian s1 = [X:3, Y:1]dan s2 = [X:1, Y:3]diterapkan takan memberi Anda t1dan t2kembali. Sebagai tambahan, kami perlu menentukan "paling tidak umum" karena jika tidak:

t' = Z 

dengan pergantian s1 = [Z:t1]dan s2 = [Z:t2]akan melakukan trik.

gen $: \mathrm{Term} \times \mathrm{Term} \to \mathrm{Var}$

antiunify ()       ()         = ()
antiunify (t1, t2) (t1', t2') = (antiunify t1 t1', antiunify t2 t2')
antiunify (C t)    (C t')     = C (antiunify t t')
antiunify t        t'         = gen(t, t') -- default: t and t' dissimilar 

Menambah algoritma ini untuk mengembalikan dua pergantian s1dan s2saya pergi sebagai latihan.