2026-10-25
Suggest.hs
dist :: String -> String -> Int
dist [] ys = length ys
dist xs [] = length xs
dist (x : xs) (y : ys)
| x == y = dist xs ys
| otherwise = 1 + minimum [dist xs ys, dist xs (y : ys), dist (x : xs) ys]
suggest :: String -> [String] -> String
suggest typo ws = snd (minimum [(dist typo w, w) | w <- ws])
main :: IO ()
main = putStrLn (suggest "nad" ["mad", "and", "bad"])
これは何を出力するでしょうか?
Answer
bad です。
dist は、1文字の挿入・削除・置換をそれぞれ1回と数えて、一方の文字列をもう一方に変える最小の回数を求めます。この値をレーベンシュタイン距離(Levenshtein distance)といいます。先頭の文字が違うときの3つの再帰呼び出しが、置換・削除・挿入にあたります。"mad" と "bad" は、どちらも "nad" の先頭を1文字置き換えれば作れるので、距離は 1 です。
"and" は "nad" の先頭2文字を入れ替えた語ですが、dist の操作に入れ替えはありません。n と a を2回置き換えるか、先頭の n を消して d の前に n を挿入するかで、どちらも2回かかります。入れ替えを1回と数えると "and" も距離 1 になり、3つの中で最小の (1, "and") を選んで and と答えることになります。
minimum が比べるのは (距離, 候補) のタプルで、タプルの順序は1つ目の要素で比べ、等しければ2つ目の要素で比べる辞書式順序(lexicographic order)です。(1, "mad") と (1, "bad") は距離が並ぶので文字列どうしの比較になり、"bad" のほうが小さくなります。候補の並び順は結果に関係しません。距離が同じなら先に並んでいる候補が選ばれると読むと、mad と答えることになります。