April 24th, 2008:

While I usually tend to avoid posting blog-entries on non-technical stuff, mostly because I do not think that I would add much to the world by hyping about the latest thing, I will have to make an exception.

I found the following movie on Youtube and found it very touching. Granted, the music does add an emotional overtone to it all that makes it all the more touching. If I weren’t so shy in public, I’d try something similar. I think it’s a great idea and it certainly brought a smile to my face. The story in the sideline regarding it is also quite interesting.

Free Hugs Campaign

Seeing how lately the levenschtein distance is so popular, I thought I’d add a haskell version to the mix.

The code below is pretty self-explanatory, using the typical memoization pattern. I do wonder, however, what would happen if somehow GHC supported lazily-resizable arrays. Perhaps then you could do this on infinite lists and only ask the levenschtein distance up to a certain index.

module Lev where
import Data.Array

levenshtein :: (Eq a) => [a] -> [a] -> Integer
levenshtein xs ys = arr ! (lenx, leny)
  where arr :: (Array (Int, Int) Integer)
        arr                   = array ((0,0), (lenx, leny))
                                  [((ix, iy), worker ix iy) |
                                    ix <- [0..lenx], iy <- [0..leny] ]
        lenx                  = length xs
        leny                  = length ys
        arrx                  = listArray (1, lenx) xs
        arry                  = listArray (1, leny) ys
        worker 0      iy      = fromIntegral iy
        worker ix     0       = fromIntegral ix
        worker ix     iy      = minimum [1 + arr ! (ix-1, iy),
                                         1 + arr ! (ix, iy-1),
                                         cost ix iy + arr ! (ix-1, iy-1)]
        cost ix iy            = if (arrx ! ix) == (arry ! iy) then 0 else 1