Динамическое программирование на Хаскеле

Динамическое программирование это подход к решению задач основанный на рекуррентной формуле решения и одном или нескольких стартовых значениях. Задача решается методами динамического программирования если решения подзадач меньшего размера может быть использовано для вычисления решения исходной задачи. Алгоритмы DP обладают полиномиальной сложностью, что намного превосходит другие способы решения задач такого рода.
Для примера, классическая DP-задача 'Размен монет':
Вам даны монеты определенного достоинства (V1, V2, V3…, VN) необходимо посчитать, какое минимальное количество монет потребуется чтобы набрать заданную сумму S. Количество монет каждого достоинства не ограничено.
Рекуррентная формула для решения этой задачи:

  
D(S) = 1 + MIN (D(S-Vi))   

Где D(S) это минимальное количество монет которое потребуется чтобы набрать сумму S
Как мы это можем реализовать в императивном стиле?

  
    public int change(int[] coins, int s) {
        int[] dp = new int[s + 1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;
        for ( int i = 1; i <= s; i++) {
            for (int j = 0; j < coins.length; j++) {
                if (coins[j] <= i && dp[i - coins[j]] + 1 < dp[i]) {
                    dp[i] = dp[i - coins[j]] + 1;
                }
            }
        }
        return dp[s];
    }

В основе этого решения лежит запоминание предыдущих результатов.
Как это решить на Haskell? Ведь мы уже не можем использовать изменяемые массивы или хэш-таблицы. Зато Haskell нам дает в руки такой мощный инструмент как lazy-evaluation. Lazy-evaluation это тоже в своем роде 'запоминание’ только в обратную сторону. Итак решение:

  
import Array

change :: [Int] -> Int -> Int
change xs n = dp!n
   where
       dp = listArray (0,n) [ cell i | i<-[0..n]]
       cell 0 = 0
       cell i = succ$minl [dp!(i-x)| x<-xs, i>=x]
  
  
minl :: [Int] -> Int
minl [] =  0
minl xs =  minimum xs

Что здесь происходит? Прежде всего, мы создаем массив с решениями

  
dp = listArray (0,n) [ cell i | i<-[0..n]]

Но в чем особенность? Особенность в том, что значения в этом массиве появляются по-требованию.

  
cell i = succ$minl [dp!(i-x)| x<-xs, i>x]

Здесь, справа налево, мы вычисляем i-ый элемент массива. Сначала выбираем все монеты достоинство которых меньше либо равно вычисляемой суммы, потом для каждого такого значения смотрим оптимальное решение в массиве. Заметьте, решения там может еще не быть, но оно будет вычислено для нас по-требованию, причем будет вычисленно лишь однажды и лишь для тех значений, которые нам на самом деле нужны! Находим минимальное решение и прибавляем к нему единицу (succ)
Маленькая утилитная функция, которую пришлось ввести minl нужна лишь потому, что стандартная функция minimum не работает с пустыми массивами.

Заключение

В статьях и литературе динамическое программирование как правило приводится с примерами в императивном стиле. Я попытался привести пример решения классической DP задачи в функциональном стиле, который, надеюсь, может оказаться для кого-то полезным.