As part of revising my knowledge of algorithms I decided to implement Longest Common Subsequence problem in Java and then in my new favourite language - 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
What I found satisfyingly great about Haskell is that coding an algorithm both lets you understand the algorithm more and write much more concise code than in an imperative language. However, this code relies heavily on exploiting recursive calls which forms a substantial binary tree of calls. And that makes it a perfect candidate for memoization.
The thing is I cannot really tell how to achieve that. The natural choice for me which resonates with my imperative mind would be to create an auxiliary function with third argument as a cache which would be a Map from ([Char], [Char]) to [Char] and have checks (member ?) on each recursive invocation of the function. And based on the result to just return value from the map or to insert what is to be computed.
Then again, it seems like an impure way of writing Haskell code because that would basically mean emulating state and side effects. What's even worse is that would couple the previously elegant solution with operations on the map. So what's the proper way of dealing with this?
