Как алгоритмы динамического программирования реализованы в идиоматическом Haskell?
Haskell и другие функциональные языки программирования построены вокруг предпосылки не поддерживать состояние. Я все еще новичок в том, как работает функциональное программирование и концепции в нем, поэтому мне было интересно, возможно ли реализовать алгоритмы DP в FP.
Какие функциональные программные конструкции могут быть использованы для этого?
6 ответов
Обычный способ сделать это - через ленивое напоминание. В некотором смысле рекурсивную функцию Фибоначчи можно считать динамическим программированием, потому что она вычисляет результаты из перекрывающихся подзадач. Я понимаю, что это усталый пример, но вот вкус. Он использует библиотеку data-memocombinators для отложенного запоминания.
import qualified Data.MemoCombinators as Memo
fib = Memo.integral fib'
where
fib' 0 = 0
fib' 1 = 1
fib' n = fib (n-1) + fib (n-2)
fib это запомненная версия, и fib' просто "грубой силой" проблемы, но вычисляет ее подзадачи, используя запомнили fib, Другие алгоритмы DP написаны в том же стиле, с использованием различных структур мемо, но с той же идеей простого вычисления результата простым функциональным способом и запоминания.
Изменить: я наконец сдался и решил предоставить запоминающийся класс типов. Это означает, что запоминание стало проще:
import Data.MemoCombinators.Class (memoize)
fib = memoize fib'
where
fib' :: Integer -> Integer -- but type sig now required
...
Instaead о необходимости следовать типу, вы можете просто memoize что-нибудь. Вы все еще можете использовать старый способ, если вам это нравится.
Алгоритмы Раби и Лапалме : подход функционального программирования имеет хорошую главу, в которой иллюстрируются некоторые концепции FP, которые нужно использовать, а именно функции высшего порядка и ленивая оценка. Я предполагаю, что для меня нормально воспроизводить упрощенную версию их функции более высокого порядка.
Он упрощен тем, что работает только с функциями, которые принимают Int в качестве входных данных и выдают Int в качестве выходных. Поскольку мы используем Int двумя различными способами, я сделаю для них синонимы "Ключ" и "Значение". Но не забывайте, что, поскольку это синонимы, вполне возможно использовать ключи и значения и наоборот. Они используются только для удобства чтения.
type Key = Int
type Value = Int
dynamic :: (Table Value Key -> Key -> Value) -> Key -> Table Value Key
dynamic compute bnd = t
where t = newTable (map (\coord -> (coord, compute t coord)) [0..bnd])
Давайте немного разберем эту функцию.
Во-первых, что делает эта функция? Из сигнатуры типа видно, что она как-то манипулирует таблицами. Действительно, первый аргумент "вычислить" - это функция (следовательно, динамическая - это функция "более высокого порядка"), которая генерирует какое-то значение из таблицы, а второй аргумент - это просто некая верхняя граница, указывающая нам, где остановиться. И как результат, "динамическая" функция дает нам своего рода таблицу. Если мы хотим получить ответ на какую-то проблему, дружественную к DP, мы запускаем "dynamic", а затем ищем ответ из нашей таблицы.
Чтобы использовать эту функцию для вычисления Фибоначчи, мы бы запустили ее примерно так
fib = findTable (dynamic helper n) n
where
helper t i =
if i <= 1
then i
else findTable t (i-1) + findTable t (i-2)
Пока не беспокойтесь о понимании этой функции выдумки. Это станет немного понятнее, когда мы исследуем "динамику".
Во-вторых, какие предпосылки нам нужно знать, чтобы понять эту функцию? Я предполагаю, что вы более или менее знакомы с синтаксисом: [0..x] для обозначения списка от 0 до x, - - в сигнатурах типа, таких как Int -> Table -> ... по сравнению с - > в анонимных функциях, таких как \ordin ->... Если вам это неудобно, они могут помешать.
Еще одним предварительным условием для решения этой проблемы является таблица соответствия. Мы не хотим беспокоиться о том, как это работает, но давайте предположим, что мы можем создавать их из списков пар ключ-значение, а также искать записи в них:
newTable :: [(k,v)] -> Table v k
findTable :: Table v k -> k -> v
Здесь нужно отметить три вещи:
- Для простоты мы не используем эквивалент из стандартной библиотеки Haskell
- findTable завершится сбоем, если вы попросите его найти несуществующее значение из таблицы. Мы можем использовать более причудливую версию, чтобы избежать этого, если это необходимо, но это тема для другого поста.
- Как ни странно, я не упомянул какую-либо функцию "добавить значение в таблицу", хотя в книге и стандартных библиотеках Haskell она есть. Почему бы и нет?
Наконец, как эта функция на самом деле работает? Что тут происходит? Мы можем немного увеличить масштаб функции,
t = newTable (map (\coord -> (coord, compute t coord)) [0..bnd])
и методично разорвать его на части. Если смотреть снаружи, у нас есть t = newTable (...), который, кажется, говорит нам, что мы строим таблицу из какого-то списка. Скучный. Как насчет списка?
map (\coord -> (coord, compute t coord)) [0..bnd]
Здесь у нас есть функция карты более высокого порядка, которая перемещается по списку от 0 до bnd и в результате создает новый список. Чтобы вычислить новый список, он использует функцию \ координировать -> (координаты, вычислить t координаты). Помните о контексте: мы пытаемся построить таблицу из ключевых пар значений, поэтому, если вы изучаете кортеж, координата первой части должна быть ключом, а вычисление t координаты второй части должно быть значением. Это вторая часть, где вещи становятся захватывающими. Давайте увеличим немного дальше
compute t coord
Мы создаем таблицу из пар ключ-значение, и значение, которое мы подключаем к этим таблицам, получается из-за выполнения команды "вычислить t координаты". Что-то, что я не упомянул ранее, - это то, что compute принимает таблицу и ключ в качестве входных данных и сообщает нам, какое значение мы должны вставить в таблицу, другими словами, какое значение мы должны связать с этим ключом. Идея возврата к динамическому программированию заключается в том, что функция вычисления использует предыдущие значения из таблицы для вычисления того нового значения, которое мы должны добавить.
И это все! Чтобы выполнять динамическое программирование в Haskell, мы можем создать некую таблицу, последовательно вставляя значения в ячейки, используя функцию, которая ищет предыдущие значения из таблицы. Легко, правда?... или это?
Возможно, у вас есть такой же опыт, как у меня. Поэтому я хочу поделиться своим текущим прогрессом в борьбе с этой функцией. Когда я впервые прочитал эту функцию, она показалась мне интуитивно понятной, и я не думал об этом больше. Потом я прочитал его поближе и сделал что-то двойное, подожди, что?! Как это может работать? Посмотрите еще раз на этот фрагмент кода здесь.
compute t coord
Чтобы вычислить значение в данной ячейке и таким образом заполнить таблицу, мы передаем t, ту самую таблицу, которую мы пытаемся создать в первую очередь. Как вы указываете, если функциональное программирование связано с неизменностью, то как может работать этот метод использования значений, которые мы еще не вычислили? Если у вас есть немного FP за поясом, вы можете спросить себя, как и я, "это ошибка?", Не должно ли это быть "сгиб" вместо "карта"?
Ключ здесь - ленивая оценка. Немного магии, которая позволяет создавать неизменную ценность из кусочков самого себя, сводится к лени. Будучи своего рода Хаскеллером с долгим желтым поясом, я все еще нахожу понятие лени немного странным. Так что я должен позволить кому-то еще занять здесь.
А пока я просто говорю себе, что это нормально. Я довольствуюсь визуализацией таблицы как некой точки с множеством торчащих из нее стрел. Взяв Фиб в качестве примера:
o
|
|--0--> 1
|
|--1--> 1
|
|--2--> 2
|
|--3--> 2
.
.
.
Куски таблицы, которую мы еще не видели, являются неизведанной территорией. Когда мы впервые идем вниз по списку, все это не обнаружено
o
.
.
.
Когда мы хотим вычислить первое значение, нам не нужно больше ничего знать о таблице, потому что я <= 1.
helper t i =
if i <= 1
then i
else findTable t (i-1) + findTable t (i-2)
o
|
|--0--> 1
.
.
.
Когда мы хотим вычислить последовательные значения, мы всегда оглядываемся только на уже открытые части таблицы (динамическое программирование, эй-эй!). Главное, что нужно помнить, это то, что мы на 100% работаем с неизменяемыми ценностями, без излишеств, кроме лени. "t" действительно означает таблицу, а не "таблицу в ее текущем состоянии на итерации 42". Просто мы обнаруживаем только те фрагменты таблицы, которые говорят нам, каково значение, соответствующее 42, когда мы фактически запрашиваем его.
Надеюсь, с другими на Stackru вы пойдете дальше, чем я, и вас не оставят невнятно бормотать "хм, да, лень что-то или другое" Это действительно не имеет большого значения:-)
Если вы хотите использовать DP с 2 или 3 параметрами (например, при обработке строк), вы можете использовать неизменяемый массив:
import Data.Array.IArray
answer :: String -> Int
answer s = table ! (1, l)
where
l = length s
--signatyres are needed, because GHC doesn't know what kind of Array we need
--string is stored in Array because we need quick access to individual chars
a :: Array Int Char
a = listArray (1, l) s
table :: Array (Int, Int) Int
table = listArray ((1, 1), (l, l)) [f i j | i <- [1..l], j <- [1..l]]
f i j | i > j = 0
| i == j = 1
| (a ! i) == (a ! j) = 2 + table ! (i+1, j-1)
| otherwise = maximum [table ! (i+1, j), table ! (i, j-1)]
Этот код решает следующую задачу: по заданной строке S найти подпоследовательность S максимальной длины, которая будет являться палиндромом (подпоследовательность не должна быть непрерывной).
По сути, 'f' - это функция восстановления, а массив 'table' - это матрица всех ее возможных значений. Поскольку Haskell ленив, вычисляются только необходимые для ответа значения 'f'. Другими словами, это рекурсия с запоминанием. Так что используйте Data.Memocombinators, который точно такой же, но уже написан кем-то другим:)
Динамическое программирование в haskell можно выразить элегантно благодаря лени, см. Первый пример на этой странице
Алгоритмы динамического программирования обычно используют идею сведения проблемы к более простой задаче. Его проблемы могут быть сформулированы как некий базовый факт (скажем, кратчайший путь от квадратной ячейки к себе имеет длину 0) плюс набор повторяющихся правил, которые точно показывают, как уменьшить проблему "найти кратчайший путь из ячейки" (i,j) в (0,0) " к проблеме " найти кратчайшие пути из клеток (i-1,j) , (i,j-1) в (0,0) ; выбрать лучшее ". AFAIK это может быть легко выражено в программе функционального стиля; без участия государства.
Просматривая ответы, я почувствовал себя немного странно, если мы говорим о рекурсии + кэшировании или просто о динамическом программировании (DP).
Потому что, если это просто DP, следующий код делает именно это: https://jelv.is/blog/Lazy-Dynamic-Programming/
basic a b = d m n
where (m, n) = (length a, length b)
d i 0 = i
d 0 j = j
d i j
| a !! (i - 1) == b !! (j - 1) = ds ! (i - 1, j - 1)
| otherwise = minimum [ ds ! (i - 1, j) + 1
, ds ! (i, j - 1) + 1
, ds ! (i - 1, j - 1) + 1
]
ds = Array.listArray bounds
[d i j | (i, j) <- Array.range bounds]
bounds = ((0, 0), (m, n))
И эта версия DP не слишком отличается от других языков, потому что, если бы я попробовал ее на Javascript, она была бы немного многословной, но писала бы похожим образом.
function levenshtein(str1, str2) {
const m = str1.length + 1
const n = str2.length + 1
const mat = new Array(m).fill(0).map(() =>
new Array(n).fill(0)
)
for (let i = 0; i < m; i++) {
mat[i][0] = i
}
for (let j = 0; j < n; j++) {
mat[0][j] = j
}
for (let i = 1; i < m; i++) {
const ic = str1[i-1]
for (let j = 1; j < n; j++) {
const jc = str2[j-1]
if (ic == jc) {
mat[i][j] = mat[i-1][j-1]
} else {
mat[i][j] = Math.min(
mat[i-1][j],
mat[i][j-1],
mat[i-1][j-1]
) + 1
}
}
}
return mat[m-1][n-1]
}
Поэтому мне интересно, вопрос об использовании рекурсии + кэширования?