0

I've been following Haskell tutorials online, and I think it's really cool that the head, tail, init, and last are all built-in. I thought as a test, it'd be really cool if I could write the Longest Common Subsequence algorithm in one line. My code is as follows:

lcs x y = if length x == 0 || length y == 0 then 0 else if (last x) == (last y) then (lcs (init x) (init y))+1 else (lcs (init x) y + lcs x (init y))

I've applied parenthesis liberally, but when I call lcs "abc" "abd" I get 6, which obviously isn't right.

jack gallerdude galler
  • 317
  • 1
  • 2
  • 6
  • 1
    You've tagged this question with as "dynamic programming", but this algorithm is not the dynamic programming algorithm and will be **slow**. Don't expect the compiler to automatically convert this to the dynamic programming algorithm. – Daniel Wagner Jul 22 '20 at 14:12

1 Answers1

3

You want max, not +, in your else branch. Using length instead of null and last/init instead of head/tail will also be noticeably slower. The idiomatic form would look like this:

lcs [] _ = 0
lcs _ [] = 0
lcs xs@(x:xt) ys@(y:yt)
    | x == y = lcs xt yt + 1
    | otherwise = max (lcs xs yt) (lcs xt ys)

I've replaced the uses of null, head, and tail with pattern matching, as is common. The single-line version is likely more readable using those functions than using pattern matching, which is why I mentioned them at all.

You will get another, much more significant speed boost by memoizing this function, e.g. using an array or similar.

Daniel Wagner
  • 145,880
  • 9
  • 220
  • 380