Namaran

Code daily. Without assist.

2026-10-25

Typo.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 + dist xs ys

main :: IO ()
main = print (dist "color" "colour")

dist は、1文字の挿入・削除・置換をそれぞれ1回と数えて、一方の文字列をもう一方に変える最小の回数を返すつもりの関数です。main は "color" と "colour" の距離を出力します。いまの出力は 2 です。本来の出力は 1 です。

Answer

Wrong

  | otherwise = 1 + dist xs ys

先頭の文字が違うとき、この行は両方の先頭を1文字ずつ捨てて1を足します。これは置換だけを数える動きで、2つの文字列は位置をそろえたまま比べ続けます。"color" と "colour" は colo まで一致し、次の r と u が違うので置換で1、残りの "" と "r" で長さの1が足されて 2 になります。実際には u を1文字挿入すれば済むので、距離は 1 です。途中で1文字ずれた文字列は、ずれた位置から後ろが全部食い違って見えます。

Right

  | otherwise = 1 + minimum [dist xs ys, dist xs (y : ys), dist (x : xs) ys]

置換に加えて、左の文字列の先頭を削除する dist xs (y : ys) と、右の文字列の先頭を左に挿入する dist (x : xs) ys を試し、いちばん少ないものを選びます。r と u の位置で挿入の道を選ぶと、残りは "r" と "r" の比較になって 0 が返り、全体で 1 になります。この距離をレーベンシュタイン距離(Levenshtein distance)といいます。1

  1. 直したあとの dist も、同じ部分の距離を何度も計算し直すので、長い文字列では時間が長さに対して指数的に増えます。実用には、表の1行前だけを持って行ごとに埋める書き方を使います。