Longest common subsequences in Haskell. Direct translation of the standard DP algorithm to folds on recursively defined lists. It looks horrible, but it's pretty straightforward. For example, "m01" means an element in the table with (i - 0, j - 1) index, where (i, j) is the current index (although there is no actual table, only lists).

longest_common_subseq.hs

import Data.List (foldl', zipWith4)
 
lcs :: (Eq a) => [a] -> [a] -> [a]
lcs as bs = reverse . snd . last $ foldl' byRow ((0::Int, []):[(0, []) | _ <- as]) bs where
    byRow m11s@(empty:m10s) b = scanl byCol empty (zip3 m11s m10s as) where
        byCol m01@(m01_l, _) ((m11_l, m11_str), m10@(m10_l, _), a)
            | a == b = (m11_l + 1, a : m11_str)
            | otherwise = if m01_l > m10_l then m01 else m10
 
-- Here we use zipWith4 instead of scanl. It's faster by 20-50 percent.
lcs' :: (Eq a) => [a] -> [a] -> [a]
lcs' as bs = reverse . snd . last $ foldl' byRow ((0::Int, []):[(0, []) | _ <- as]) bs where
    byRow m11s@(empty:m10s) b = m01s where
        m01s = empty : zipWith4 byCol m01s m11s m10s as
        byCol m01@(m01_l, _) (m11_l, m11_str) m10@(m10_l, _) a
            | a == b = (m11_l + 1, a : m11_str)
            | otherwise = if m01_l > m10_l then m01 else m10