Data.MemoCombinators, где я могу найти примеры? - PullRequest
Новая
       18

Data.MemoCombinators, где я могу найти примеры?

8 голосов
/ 18 ноября 2011

Этот пакет имеет некоторые функции для преобразования рекурсивных функций в рекурсивные функции динамического программирования для повышения производительности:

http://hackage.haskell.org/packages/archive/data-memocombinators/0.3/doc/html/Data-MemoCombinators.html#t:Memo

К сожалению, у них есть только пример для простейшего типа функции, и нет примеров того, как использовать функцию из 2 переменных. Где найти пример того, как, например, превратить функцию [Int] -> Int -> Int в функцию динамического программирования? В документации сказано, что memo2 принимает два Memo в качестве первых аргументов, но я не уверен, что это значит.

Решение:

Как описал Хаммар, вместо определения функции как: 

foo :: [Int] -> Int -> Int
foo list value = ...

для использования memo2: 

import qualified Data.MemoCombinators as Memo

foo = Memo.memo2 (Memo.list Memo.integral) Memo.integral foo'
  where ... (define foo' with recursive calls to foo.)

Ответы [ 2 ]

11 голосов
/ 18 ноября 2011

Библиотека определяет тип Memo a, который является «памяткой» для функций, принимающих аргументы типа a.Ключом к пониманию того, как использовать эту библиотеку, является понимание того, как использовать и составлять эти памятки.

В простом случае у вас есть функция с одним аргументом и простой памятник, например, функция Фибоначчи и памятникдля Integral аргументов.В таком случае мы получаем функцию памятки, применяя памятку к функции, которую нужно запомнить: 

 fib = Memo.integral fib'
   where
     fib' 0 = 0
     fib' 1 = 1
     fib' x = fib (x-1) + fib (x-2)

Некоторые памятники принимают аргументы для настройки своего поведения, например arrayRange.В следующем примере fib n будет запоминаться только в том случае, если n находится в диапазоне от 1 до 100. 

fib = Memo.arrayRange (1, 100) fib'
  where ...

В библиотеке также предусмотрены комбинаторы для создания более сложных памятников из простых.Например, list, который превращает памятку для a в памятку для [a].

Наконец, для запоминания функций нескольких аргументов существуют функции memo2 и memo3, которыевозьмите памятку для каждого аргумента плюс функцию и верните памятную функцию.

Итак, чтобы запоминать вашу функцию с двумя аргументами, нам нужно будет использовать memo2.Мы можем использовать памятку integral для аргумента Int, а для аргумента [Int] мы можем использовать list integral.Соединив это вместе, мы получим что-то вроде этого: 

memo2 (list integral) integral foo

Однако вы также можете использовать более специфические памятники, если знаете, что числа находятся в некотором заданном диапазоне.Например, если числа в списке находятся в диапазоне от 1 до 10, а второй аргумент находится в диапазоне от 15 до 20: 

memo2 (list $ arrayRange (1, 10)) (arrayRange (15, 20)) foo

Независимо от того, имеет ли это смысл или нет, зависит от вашего приложения.

2 голосов
/ 18 ноября 2011

По типам и документации, я считаю, 

foo :: [Int] -> Int -> Int

следует запоминать по 

memo2 (list integral) integral foo

(отказ от ответственности: я не использовал мемокомбинаторы данных).

...