Как алгоритмы динамического программирования реализованы в идиоматическом Haskell?

Question

Haskell и другие функциональные языки программирования построены вокруг предпосылки не поддерживать состояние. Я все еще плохо знаком с тем, как работает функциональное программирование, и с концепциями в нем, поэтому мне было интересно, можно ли реализовать алгоритмы DP способом FP.

Какие функциональные программные конструкции можно использовать для этого?

Answer 1

Обычный способ сделать это - ленивая запись в память. В некотором смысле рекурсивную функцию Фибоначчи можно считать динамическим программированием, потому что она вычисляет результаты из перекрывающихся подзадач. Я понимаю, что это усталый пример, но вот вкус. Он использует библиотеку 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 
    ...

Если вам нужно следовать типу, вы можете просто memoize что угодно. Вы все еще можете использовать старый способ, если вам это нравится.

Answer 2

Алгоритмы Раби и Лапалма : подход функционального программирования имеет хорошую главу об этом, которая иллюстрирует некоторые концепции 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 проблему, мы запускаем «динамический» и затем ищем ответ из нашей таблицы.

Чтобы использовать эту функцию для вычисления Фибоначчи, мы запустили бы ее немного какthis

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 -> ..., по сравнению с -> в анонимных функциях, таких как \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]

Здесь у нас есть функция map высшего порядка, которая перемещается по списку от 0 до bnd и в результате создает новый список.Чтобы вычислить новый список, он использует функцию \ координировать -> (координаты, вычислить t координаты).Имейте в виду контекст: мы пытаемся построить таблицу из ключевых пар значений, поэтому, если вы изучаете кортеж, координата первой части должна быть ключом, а вычисление t координаты второй части должно быть значением.Это вторая часть, где вещи становятся захватывающими.Давайте увеличим немного дальше

compute t coord

Мы создаем таблицу из пар ключ-значение, и значение, которое мы подключаем к этим таблицам, получается из запуска "compute tordin".Что-то, что я не упомянул ранее, - это то, что compute принимает таблицу и ключ в качестве входных данных и сообщает нам, какое значение мы должны вставить в таблицу, другими словами, какое значение мы должны связать с этим ключом.Идея возврата к динамическому программированию заключается в том, что функция вычисления использует предыдущие значения из таблицы для вычисления того нового значения, которое мы должны добавить.

И это все!Чтобы выполнять динамическое программирование в Haskell, мы можем создать некую таблицу, последовательно вставляя значения в ячейки, используя функцию, которая ищет предыдущие значения из таблицы.Легко, правда? ... или это так?

Возможно, у тебя такой же опыт, как и у меня.Поэтому я хочу поделиться своим текущим достижением в борьбе с этой функцией.Когда я впервые прочитал эту функцию, она показалась мне интуитивно понятной, и я не думал об этом больше.Потом я прочитал это поближе и сделал что-то двойное, подожди, что ?!Как это может работать?Посмотрите еще раз на этот фрагмент кода.

compute t coord

Чтобы вычислить значение в данной ячейке и таким образом заполнить таблицу, мы передаем t, ту самую таблицу, которую пытаемся создатьна первом месте.Как вы указываете, если функциональное программирование связано с неизменностью, то как может работать этот бизнес с использованием значений, которые мы еще не вычислили?Если у вас есть немного FP за поясом, вы можете спросить себя, как и я, «это ошибка?», Не должно ли это быть «сгиб» вместо «карты»?

Ключ здесь - ленивая оценка.Немного магии, которая делает возможным создание неизменной ценности из кусочков самого себя, все сводится к лени.Будучи своего рода гаскеллером с долгим желтым поясом, я все еще нахожу понятие лени немного странным.Поэтому мне придется позволить кому-то другому занять здесь место.

А пока я просто говорю себе, что это нормально.Я довольствуюсь визуализацией таблицы как точки с множеством торчащих из нее стрел.Взяв в качестве примера fib:

o
|
|--0--> 1
|
|--1--> 1
|
|--2--> 2
|
|--3--> 2
.
.
.

Куски таблицы, которые мы еще не видели, являются неоткрытой территорией.Когда мы в первый раз спускаемся по списку, он все не обнаружен1071 *

Когда мы хотим вычислить последовательные значения, мы всегда только оглядываемся на уже открытые части таблицы (динамическое программирование, эй-эй!).Главное, что нужно помнить, это то, что мы на 100% работаем с неизменяемыми ценностями, никаких хитростей, кроме лени.«t» действительно означает таблицу, а не «таблицу в ее текущем состоянии на итерации 42».Просто мы обнаруживаем только те фрагменты таблицы, которые сообщают нам, какое значение соответствует 42, когда мы фактически запрашиваем его.

Надеемся, что с другими в StackOverflow вы пойдете дальше меняоставил невнятно бормотание "хм да, лень что-то или другое" Это действительно не имеет большого значения: -)

Answer 3

Если вы хотите использовать 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, который точно такой же, но уже написан кем-то другим:)

Answer 4

Динамическое программирование в haskell можно выразить элегантно благодаря лени, см. Первый пример на на этой странице

Answer 5

Алгоритмы динамического программирования обычно используют идею сведения проблемы к более простой проблеме. Его проблемы могут быть сформулированы как некий базовый факт (скажем, кратчайший путь от квадратной ячейки к себе имеет длину 0) плюс набор повторяющихся правил, которые точно показывают, как уменьшить задачу "найти кратчайший путь из ячейки (i,j) на (0,0) " на проблему " найти кратчайшие пути из ячеек (i-1,j), (i,j-1) на (0,0); выберите лучший ". AFAIK это можно легко выразить в функциональном стиле программы; государство не вовлечено.