nthRow n len = n : replicate (len - 1) 0

updateRow prev n letter word 
  = reverse $ foldl (\l@(last:_) (j1,j,cl) 
                     -> minimum [1 + last, 1 + j, 
                                 j1 + (if letter == cl then 0 else 1)] : l) [n] p
  where
    p = zip3 prev (tail prev) word

leven a b = last $ foldl (\x(n,letter) 
                          -> updateRow x n letter b) [0..(length b)] (zip [0..] a)

main = print $ leven (show [1..1000]) (show [2..1001])