Packages
caffeine_lang
5.4.3
6.3.1
6.3.0
6.2.2
6.2.1
6.2.0
6.1.2
6.1.1
6.1.0
6.0.0
5.6.0
5.5.0
5.4.4
5.4.3
5.4.2
5.4.1
5.4.0
5.3.0
5.2.0
5.1.1
5.1.0
5.0.12
5.0.11
5.0.10
5.0.8
5.0.7
5.0.6
5.0.5
5.0.4
5.0.1
5.0.0
4.10.0
4.9.0
4.8.3
4.8.2
4.8.1
4.8.0
4.7.9
4.7.8
4.7.7
4.7.6
4.7.5
4.6.7
4.6.6
4.6.5
4.6.4
4.6.3
4.6.2
4.6.0
4.5.1
4.5.0
4.4.4
4.4.3
4.4.1
4.4.0
4.3.7
4.3.6
3.0.6
3.0.5
3.0.4
3.0.3
3.0.2
3.0.1
3.0.0
2.0.5
2.0.4
2.0.3
2.0.2
2.0.1
2.0.0
1.0.2
1.0.1
0.1.0
0.0.24
0.0.23
0.0.22
0.0.21
0.0.20
0.0.19
0.0.18
0.0.17
0.0.16
0.0.15
0.0.14
0.0.13
0.0.12
0.0.11
0.0.10
0.0.9
0.0.8
0.0.7
0.0.6
0.0.5
0.0.4
0.0.2
0.0.1
A compiler for generating reliability artifacts from service expectation definitions.
Current section
Files
Jump to
Current section
Files
src/caffeine_lang/string_distance.gleam
/// String distance utilities for "did you mean?" suggestions.
import gleam/float
import gleam/int
import gleam/list
import gleam/option.{type Option}
import gleam/string
/// Computes the Levenshtein edit distance between two strings.
pub fn levenshtein(a: String, b: String) -> Int {
let a_graphemes = string.to_graphemes(a)
let b_graphemes = string.to_graphemes(b)
let b_len = list.length(b_graphemes)
// Initial row: [0, 1, 2, ..., b_len]
// Build [0, 1, 2, ..., b_len] by iterating downward and prepending.
let initial_row =
int.range(from: b_len, to: -1, with: [], run: fn(acc, i) { [i, ..acc] })
let result_row =
list.index_fold(a_graphemes, initial_row, fn(prev_row, a_char, i) {
build_row(prev_row, b_graphemes, a_char, i + 1)
})
// Last element of the final row is the distance.
case list.last(result_row) {
Ok(d) -> d
// Cannot happen: row always has at least one element.
Error(Nil) -> 0
}
}
/// Builds one row of the Levenshtein matrix.
fn build_row(
prev_row: List(Int),
b_graphemes: List(String),
a_char: String,
initial_val: Int,
) -> List(Int) {
let #(row, _) =
build_row_loop(prev_row, b_graphemes, a_char, [initial_val], initial_val)
list.reverse(row)
}
fn build_row_loop(
prev_row: List(Int),
b_remaining: List(String),
a_char: String,
acc: List(Int),
prev_val: Int,
) -> #(List(Int), Int) {
case b_remaining, prev_row {
[], _ -> #(acc, prev_val)
[b_char, ..b_rest], [diag, ..prev_rest] -> {
let above = case prev_rest {
[v, ..] -> v
[] -> 0
}
let cost = case a_char == b_char {
True -> 0
False -> 1
}
let val = int.min(prev_val + 1, int.min(above + 1, diag + cost))
build_row_loop(prev_rest, b_rest, a_char, [val, ..acc], val)
}
_, [] -> #(acc, prev_val)
}
}
/// Returns the closest match from a list of candidates, if within threshold.
/// Threshold: distance <= max(2, ceil(length(target) * 0.4)).
pub fn closest_match(
target: String,
candidates: List(String),
) -> Option(String) {
let target_len = string.length(target)
let threshold =
int.max(2, float.truncate(int.to_float(target_len) *. 0.4 +. 0.99))
let result =
list.fold(candidates, option.None, fn(best, candidate) {
let dist = levenshtein(target, candidate)
case dist > threshold {
True -> best
False ->
case best {
option.None -> option.Some(#(candidate, dist))
option.Some(#(_, best_dist)) ->
case dist < best_dist {
True -> option.Some(#(candidate, dist))
False -> best
}
}
}
})
case result {
option.Some(#(name, _)) -> option.Some(name)
option.None -> option.None
}
}