Haskell и другие языки функционального программирования построены вокруг предпосылки отсутствия состояния. Я до сих пор не знаком с тем, как работает функциональное программирование и концепции, поэтому мне было интересно, возможно ли реализовать алгоритмы DP в режиме FP.
Какие конструкторы функционального программирования могут быть использованы для этого?
Обычный способ сделать это - ленивая мемуаризация. В некотором смысле функция рекурсивного фибоначчи может считаться динамическим программированием, поскольку она вычисляет результаты из перекрывающихся подзадач. Я понимаю, что это усталый пример, но здесь вкус. Он использует библиотеку data-memocombinators для ленивой memoization.
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' просто "грубая сила" проблемы, но вычисляет ее подзадачи, используя memoized fib. Другие алгоритмы DP написаны в этом же стиле, используя разные структуры memo, но та же самая идея просто вычислить результат в прямом функциональном способе и memoizing.
Изменить. Я, наконец, сдался и решил предоставить memoizable typeclass. Это означает, что memoizing теперь проще:
import Data.MemoCombinators.Class (memoize)
fib = memoize fib'
where
fib' :: Integer -> Integer -- but type sig now required
...
Попробуйте следовать типу, вы можете просто 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, мы запускаем "динамический", а затем просматриваем ответ из нашей таблицы.
Чтобы использовать эту функцию для вычисления фибоначчи, мы бы немного ее использовали
fib = findTable (dynamic helper n) n
where
helper t i =
if i <= 1
then i
else findTable t (i-1) + findTable t (i-2)
Не беспокойтесь о понимании этой функции fib сейчас. Это станет немного понятнее, поскольку мы исследуем "динамический".
Во-вторых, какие предварительные условия нам нужно знать, чтобы понять эту функцию?. Я предполагаю, что вы более или менее знакомы с синтаксисом, [0..x] - укажите список от 0 до x, подписи типа → в типе, такие как Int → Table → ... versus → в анонимных функциях, таких как \coord → ... Если вам это не нравится, они могут мешать.
Еще одним предварительным условием для решения является эта таблица поиска. Мы не хотим беспокоиться о том, как это работает, но предположим, что мы можем создавать их из списков пар ключ-значение, а также искать в них записи:
newTable :: [(k,v)] -> Table v k
findTable :: Table v k -> k -> v
Три примечания:
Наконец, как эта функция действительно работает? Что здесь происходит? Мы можем немного увеличить размер функции,
t = newTable (map (\coord -> (coord, compute t coord)) [0..bnd])
и методично разделить его. Идя извне, у нас есть t = newTable (...), который, кажется, говорит нам, что мы строим таблицу из какого-то списка. Скучный. Как насчет списка?
map (\coord -> (coord, compute t coord)) [0..bnd]
Здесь у нас есть функция отображения более высокого порядка, идущая вниз по списку от 0 до bnd и создавая в результате новый список. Чтобы вычислить новый список, он использует функцию \coord → (координировать, вычислять t-координацию). Имейте в виду контекст: мы пытаемся создать таблицу из ключевых пар значений, поэтому, если вы изучаете кортеж, координата первой части должна быть ключом, а координата второй части t должна быть значением. Вторая часть - это то, где все становится захватывающим. Позвольте немного увеличить масштаб
compute t coord
Мы создаем таблицу из пар ключ-значение, и значение, которое мы подключаем к этим таблицам, происходит от запуска "compute t coord". Что-то, о чем я не упоминал ранее, заключается в том, что вычисление принимает таблицу и ключ в качестве входных данных и сообщает нам, какое значение мы должны вставлять в таблицу, другими словами, какое значение мы должны связывать с этим ключом. Идея затем, чтобы вернуть ее к динамическому программированию, заключается в том, что функция вычисления использует предыдущие значения из таблицы, чтобы вычислить это новое значение, которое мы должны подключить.
И это все! Чтобы сделать динамическое программирование в Haskell, мы можем создать какую-то таблицу, последовательно подключая значения к ячейкам, используя функцию, которая просматривает предыдущие значения из таблицы. Легко, правда?... или это?
Возможно, у вас такой же опыт, как и у меня. Поэтому я хочу поделиться своим текущим ходом с этой функцией. Когда я впервые прочитал эту функцию, это показалось мне своего рода интуитивным смыслом, и я не думал об этом больше. Затем я прочитал его ближе и сделал своего рода двойной прием, подожди, что?! Как это может работать? Посмотрите на этот фрагмент кода здесь.
compute t coord
Чтобы вычислить значение в данной ячейке и, таким образом, заполнить таблицу, мы передаем t, ту самую таблицу, которую мы пытаемся создать в первую очередь. Если функциональное программирование касается неизменности, как вы указываете, как может эта деятельность использовать ценности, которые мы еще не вычислили, возможно, работает? Если у вас есть немного FP под вашим поясом, вы можете спросить себя, как я, "это ошибка?", Разве это не должно быть "сгибом" вместо "карты"?
Ключ здесь - ленивая оценка. Маленькая магия, которая позволяет создать неизменную ценность из кусочков самого себя, сводится к лени. Будучи своего рода долговременным желтым ремнем Хаскеллера, я все еще нахожу понятие лени немного озадаченным. Поэтому я должен позволить кому-то еще взять здесь.
Тем временем я просто говорю себе, что все в порядке. Я довольствуюсь визуализацией таблицы как своего рода точкой с большим количеством стрелок, торчащих из нее. В качестве примера возьмем fib:
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, когда мы действительно просим об этом.
Надеюсь, что с другими на StackOverflow вы пойдете дальше меня и не останетесь бормочащим смутно "э-э-э-эй, лень что-то". Это действительно неважно: -)
Если вы хотите использовать 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" - это рекурсивная функция, а "таблица" массива - это матрица всех возможных значений. Поскольку Haskell ленив, вычисляются только значения ответа "f". Другими словами, это рекурсия с memoization. Поэтому используйте Data.Memocombinators, который является одним и тем же, но уже написан кем-то другим:)
Динамическое программирование в haskell можно выразить элегантно благодаря лени, см. первый пример на этой странице
Алгоритмы динамического программирования обычно используют идею сокращения проблемы до более простой задачи (задач). Его проблемы могут быть сформулированы как некоторый базовый факт (скажем, кратчайший путь от квадратной ячейки к себе имеет длину 0) плюс набор повторяющихся правил, которые точно показывают, как уменьшить проблему "найти кратчайший путь из ячейки (i,j) до (0,0)" к проблеме " найдите кратчайшие пути из ячеек (i-1,j), (i,j-1) в (0,0), выберите лучший. AFAIK это легко выразить в программе функционального стиля; никакое государство не вовлечено.