В рамках пересмотра моих знаний об алгоритмах я решил реализовать задачу Longest Common Subsequence в 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] и имела бы проверки (member) ?) при каждом рекурсивном вызове функции. И на основании результата просто вернуть значение из карты или вставить то, что должно быть вычислено.
Опять же, это похоже на нечестный способ написания кода Haskell, потому что это в основном означает эмуляцию состояние и побочные эффекты. Что еще хуже, это соединит ранее элегантное решение с операциями на карте. Так как правильно с этим бороться?