dist.erl

#!/usr/bin/env escript
-module(dist).
-compile([export_all]).

% optimized combinators

int(true) -> 1;
int(_) -> 0.
rev(L) -> lists:reverse(L).
rtr(L) -> rev(tl(rev(L))).
last(L) -> [lists:last(L)].
htr(L) -> [hd(tl(rev(L)))].
rtt(L) -> rev(tl(tl(rev(L)))).

% Levenshtein distance

dist(A,A)  -> 0;
dist(A,[]) -> length(A);
dist([],B) -> length(B);
dist(A,B)  -> dist(get({A,B}),A,B).

dist(undefined,A,B)  -> dist(1000,A,B);
dist(T,_,_) when T < 1000 -> T;
dist(_,A,B) ->
    T2 = lists:min([dist(A,rtr(B)),dist(rtr(A),B),dist(rtr(A),rtr(B))-int(last(A)==last(B))]) + 1,
    case length(A)>1 andalso length(B)>1 andalso last(A)==htr(B) andalso htr(A)==last(B) of
         true -> lists:min([T2,dist(rtt(A),rtt(B))+1]);
         false -> put({A,B},T2),T2 end.

main([A,B]) -> io:format("Distance: ~p~n",[timer:tc(fun() -> dist(A,B) end)]).