忽略，这是一个糟糕的算法（应memoizing，我到达那个第二）...
使用O（1）原语，而不是为O（n）
一个问题是你使用了一大堆调用O（n）的列表（haskell列表是单独链接列表）。一个更好的数据结构会给你O（1）操作，我用Vector：
import qualified Data.Vector as V
-- standard levenshtein distance between two lists
editDistance :: Eq a => [a] -> [a] -> Int
editDistance s1 s2 = editDistance' 1 1 1 (V.fromList s1) (V.fromList s2)
-- weighted levenshtein distance
-- ins, sub and del are the costs for the various operations
editDistance' :: Eq a => Int -> Int -> Int -> V.Vector a -> V.Vector a -> Int
editDistance' del sub ins s1 s2
| V.null s2 = ins * V.length s1
| V.null s1 = ins * V.length s2
| V.last s1 == V.last s2 = editDistance' del sub ins (V.init s1) (V.init s2)
| otherwise = minimum [ editDistance' del sub ins s1 (V.init s2) + del -- deletion
, editDistance' del sub ins (V.init s1) (V.init s2) + sub -- substitution
, editDistance' del sub ins (V.init s1) s2 + ins -- insertion
]
是O（N）的列表包括初始化，length的操作，和last（虽然INIT能够偷懒的最小）。所有这些操作都是使用Vector的O（1）。
虽然真正的标杆应该使用Criterion，一个快速和肮脏的基准：
str2 = replicate 15 'a' ++ replicate 25 'b'
str1 = replicate 20 'a' ++ replicate 20 'b'
main = print $ editDistance str1 str2
显示矢量版本需要0.09秒而串采取1.6秒，所以我们节省了大约一个数量级，甚至没有看你的editDistance算法。
现在怎么样记忆结果？
更大的问题显然是需要记忆。我将此作为了解monad-memo包裹的机会 - 我的上帝真的太棒了！对于一个额外的约束条件（您需要Ord a），您基本上不费力气就可以进行记忆。代码：
import qualified Data.Vector as V
import Control.Monad.Memo
-- standard levenshtein distance between two lists
editDistance :: (Eq a, Ord a) => [a] -> [a] -> Int
editDistance s1 s2 = startEvalMemo $ editDistance' (1, 1, 1, (V.fromList s1), (V.fromList s2))
-- weighted levenshtein distance
-- ins, sub and del are the costs for the various operations
editDistance' :: (MonadMemo (Int, Int, Int, V.Vector a, V.Vector a) Int m, Eq a) => (Int, Int, Int, V.Vector a, V.Vector a) -> m Int
editDistance' (del, sub, ins, s1, s2)
| V.null s2 = return $ ins * V.length s1
| V.null s1 = return $ ins * V.length s2
| V.last s1 == V.last s2 = memo editDistance' (del, sub, ins, (V.init s1), (V.init s2))
| otherwise = do
r1 <- memo editDistance' (del, sub, ins, s1, (V.init s2))
r2 <- memo editDistance' (del, sub, ins, (V.init s1), (V.init s2))
r3 <- memo editDistance' (del, sub, ins, (V.init s1), s2)
return $ minimum [ r1 + del -- deletion
, r2 + sub -- substitution
, r3 + ins -- insertion
]
您会看到memoization是如何需要一个“键”（请参阅MonadMemo类）？我将所有参数打包成一个很大的丑陋元组。它也需要一个“价值”，这是你的结果Int。然后，只需使用“备忘录”功能即可即插即用您想要记忆的值。
对于基准我用较短，但较大的距离，字符串：
$ time ./so # the memoized vector version
12
real 0m0.003s
$ time ./so3 # the non-memoized vector version
12
real 1m33.122s
千万别想运行非memoized字符串版本，我想，这将需要大约15分钟在最低限度。至于我，我现在喜欢monad-memo - 感谢Eduard的包装！
编辑：String和Vector之间的差异在memoized版本中没有那么多，但当距离达到200左右时仍然增长到2倍，所以仍然值得。
编辑：也许我应该解释为什么更大的问题是“明显”记忆结果。好吧，如果你看一下原始算法的心脏：
[ editDistance' ... s1 (V.init s2) + del
, editDistance' ... (V.init s1) (V.init s2) + sub
, editDistance' ... (V.init s1) s2 + ins]
这是相当清楚的editDistance' s1 s2结果在3调用editDistance'一个电话......每一个来电editDistance'三次......还有三个时间......和AHHH！指数爆炸！幸运的是，大多数电话是相同的！例如（使用-->的“电话”和eD为editDistance'）：
eD s1 s2 --> eD s1 (init s2) -- The parent
, eD (init s1) s2
, eD (init s1) (init s2)
eD (init s1) s2 --> eD (init s1) (init s2) -- The first "child"
, eD (init (init s1)) s2
, eD (init (init s1)) (init s2)
eD s1 (init s2) --> eD s1 (init (init s2))
, eD (init s1) (init s2)
, eD (init s1) (init (init s2))
只需通过考虑父母和两个孩子立即可以看到通话ed (init s1) (init s2)做三次。另一个孩子与父母共享呼叫，所有的孩子都与另一个孩子（和他们的孩子，提示Monty Python skit）共享许多呼叫。
这将是一个有趣的，也许有启发性的练习，使runMemo类似的函数返回所使用的缓存结果的数量。
哇，这是伟大的。我以前听说过莫诺化，但我从来没有想到这很容易！当你说“忽略这是一个不好的算法（应该记忆，我到那一秒）......”，你是指算法的整体结构还是仅仅是应该使用记忆的事实？对我来说，算法本身看起来不错。 :) – bzn 2011-04-01 21:14:57
bzn：我只是认为这不是记忆的事实。如果您之前没有看过记忆，那么请参阅[Haskell wiki]（http://www.haskell.org/haskellwiki/Memoization），CS算法手册，或两者。如果没有记忆，你可以多次计算大部分值，但是记忆只能计算一次，否则就会查找以前计算的结果。例如，要计算列表的第一个元素（'editDist s1（init s2）'），函数最终将计算'editDist（init s1）（init s2）'。这是调用者列表中的第二个元素，并且是被调用者列表中的第三个元素！ – 2011-04-01 22:09:07
@bzn我添加了一个编辑，谈论为什么这个问题是“显然”memoization。 – 2011-04-01 22:39:07