// NOTE: from https://groups.google.com/forum/#!topic/ats-lang-users/8Q8cpFpzQ54
#include
"share/atspre_staload.hats"
fun min_3(x : int, y : int, z : int) : int =
min(x, (min(y, z)))
fun bool2int(x : char, y : char) : int =
if x = y then
0
else
1
// Ported over from
// https://en.wikibooks.org/wiki/Algorithm_Implementation/Strings/Levenshtein_distance#C
fn levenshtein {m:nat}{n:nat}(s1 : string(m), s2 : string(n)) : int =
let
val s1_l: size_t(m) = length(s1)
val s2_l: size_t(n) = length(s2)
fun loop1 () : arrayref(int, m + 1) = let
val (pf_arr, pf_gc | p_arr) = array_ptr_alloc<int> (succ(s1_l))
//
val p1_arr = ptr1_succ<int> (p_arr)
prval (pf1_at, pf_arr) = array_v_uncons {int?} (pf_arr)
val () = ptr_set<int> (pf1_at | p_arr, 0)
//
var i: int = 0
prval [larr:addr] EQADDR () = eqaddr_make_ptr (p1_arr)
var p = p1_arr
prvar pf0 = array_v_nil {int} ()
prvar pf1 = pf_arr
//
val () =
while* {i:nat | i <= m} .<m-i>. (
i: int (i)
, p: ptr (larr + i*sizeof(int))
, pf0: array_v (int, larr, i)
, pf1: array_v (int?, larr+i*sizeof(int), m-i)
) : (
pf0: array_v (int, larr, m)
, pf1: array_v (int?, larr+i*sizeof(int), 0)
) => (
i < sz2i(s1_l)
) {
//
prval (pf_at, pf1_res) = array_v_uncons {int?} (pf1)
prval () = pf1 := pf1_res
//
val c = (g0ofg1)i
val () = ptr_set<int> (pf_at | p, c)
val () = p := ptr1_succ<int> (p)
//
prval () = pf0 := array_v_extend {int} (pf0, pf_at)
val () = i := i + 1
//
} // end of [val]
//
prval () = pf_arr := pf0
prval () = array_v_unnil {int?} (pf1)
prval pf_arr = array_v_cons {int} (pf1_at, pf_arr)
//
val res = arrayptr_encode (pf_arr, pf_gc | p_arr)
in
arrayptr_refize(res)
end
val column = loop1 ()
fun loop2 { i : nat | i > 0 && i <= n+1 } .<n-i+1>. (x : int(i)) : void =
if x <= sz2i(s2_l) then
{
val () = column[0] := x
val () = let
fun inner_loop { j : nat | j > 0 && j <= m+1 } .<m-j+1>. (y
: int(j), last_diag : int) :
void =
if y <= sz2i(s1_l) then
let
var old_diag = column[y]
val () = column[y] := min_3( column[y] + 1
, column[y - 1] + 1
, last_diag + bool2int(s1[y
- 1], s2[x - 1])
)
in
inner_loop(y + 1, old_diag)
end
in
inner_loop(1, x - 1)
end
val () = loop2(x + 1)
}
val () = loop2(1)
in
column[s1_l]
end
implement
main0 () = let
var actual0 = levenshtein("abcd", "abdc")
var expected0 = levenshtein("abcd", "abdc")
val () = assert (actual0 = 2)
var actual1 = levenshtein("exclude", "excude")
var expected1 = 1
val () = assert (actual1 = expected1)
in
println!("hi")
end