performance - 如何在 Haskell 中记忆 LCS

Question

作为修改我的算法知识的一部分，我决定用 Java 实现最长公共子序列问题，然后用我最喜欢的新语言——Haskell。

lcs :: (Eq a) => [a] -> [a] -> [a]

lcs [] _ = []
lcs _ [] = []

lcs (x:xs) (y:ys) = 
    if (x == y) then x : lcs xs ys
    else longer (lcs xs (y:ys), lcs (x:xs) ys)
    where longer (a, b) = if (length a > length b) then a else b

我对 Haskell 的满意之处在于，与命令式语言相比，对算法进行编码既可以让您更多地理解算法，又可以编写更简洁的代码。但是，此代码严重依赖于利用递归调用，从而形成了大量的调用二叉树。这使它成为记忆的完美候选者。

问题是我无法真正说出如何实现这一目标。对我来说，与我的命令式思维产生共鸣的自然选择是创建一个带有第三个参数的辅助函数作为缓存，它是从 ([Char], [Char]) 到 [Char] 的 Map 并检查 ( member?)函数的每次递归调用。并根据结果从地图中返回值或插入要计算的内容。

再说一次，这似乎是一种编写 Haskell 代码的不纯粹方式，因为这基本上意味着模拟状态和副作用。更糟糕的是，这会将以前优雅的解决方案与地图上的操作结合起来。那么处理这个问题的正确方法是什么？

标签： performancefunctionhaskellmemoizationlcs