Памятка с дополнительным параметром в Haskell

Question

У меня есть рекурсивная функция f, которая принимает два параметра x и y. Функция однозначно определяется первым параметром; второй просто облегчает ситуацию.

Теперь я хочу сохранить меморандум о том, что функция w.r.t. это первый параметр, игнорируя второй. (I.e. f оценивается не более одного для каждого значения x)

Что такое самый простой способ сделать это? На данный момент я просто определяю массив, содержащий все значения, рекурсивно, но это несколько ad-hoc-решение. Я бы предпочел какой-то комбинатор memoisation, который я могу просто бросить в свою функцию.

EDIT: для уточнения функции f берет пару целых чисел и список. Первое целое число - это некоторое значение параметра, второе - индекс элемента в некотором глобальном списке xs для потребления.

Чтобы избежать индексации списка, я прохожу частично потребленной список f как хорошо, но, очевидно, инвариант в том, что, если первый параметр (m, n), второй всегда будет drop n xs, поэтому результат однозначно определяется первый параметр.

Просто использование комбинатора memoisation на частично примененной функции не будет работать, так как это оставит неоценимый thunk \xs -> …, лежащий вокруг. Я мог бы, вероятно, обернуть два параметра в виде данных, чей экземпляр Eq игнорирует второе значение (и аналогично для других экземпляров), но это похоже на очень специальное решение. Нет ли более простого способа?

EDIT2: Конкретная функция Я хочу memoise:

g :: [(Int, Int)] -> Int -> Int 
g xs n = f 0 n 
    where f :: Int -> Int -> Int 
     f _ 0 = 0 
     f m n 
      | m == length xs = 0 
      | w > n   = f (m + 1) n 
      | otherwise  = maximum [f (m + 1) n, v + f (m + 1) (n - w)] 
      where (w, v) = xs !! m 

Чтобы избежать дорогостоящей операции индексирования, я вместо того, чтобы передать частично потребленной список f, а также:

g' :: [(Int, Int)] -> Int -> Int 
g' xs n = f xs 0 n 
    where f :: [(Int, Int)] -> Int -> Int -> Int 
     f []   _ _ = 0 
     f _   _ 0 = 0 
     f ((w,v) : xs) m n 
      | w > n   = f xs (m + 1) n 
      | otherwise  = maximum [f xs (m + 1) n, v + f xs (m + 1) (n - w)] 

мемоизация из f wrt параметр списка, конечно, не нужен, поскольку список не влияет (нравственно) на результат. Поэтому мне хотелось бы, чтобы воспоминание просто игнорировало параметр списка.

Answer 1

Ваша функция излишне сложна. Вам не нужно индекс m на все:

foo :: [(Int, Int)] -> Int -> Int 
foo []   _ = 0 
foo _   0 = 0 
foo ((w,v):xs) n 
    | w > n  = foo xs n 
    | otherwise = foo xs n `max` foo xs (n - w) + v 

Теперь, если вы хотите memoize foo тогда как аргументы должны быть рассмотрены (как это должно быть).

Мы будем использовать метод monadic memoization mixin для memoize foo:

1. Во-первых, мы создаем uncurried версию foo (потому что мы хотим, чтобы memoize оба аргумента):

   foo' :: ([(Int, Int)], Int) -> Int 
   foo' ([],  _) = 0 
   foo' (_,  0) = 0 
   foo' ((w,v):xs, n) 
       | w > n  = foo' (xs, n) 
       | otherwise = foo' (xs, n) `max` foo' (xs, n - w) + v 
   

2. Следующая , мы монадифицируем функцию foo' (потому что мы хотим нарезать таблицу заметок в функции):

   foo' :: Monad m => ([(Int, Int)], Int) -> m Int 
   foo' ([],  _) = return 0 
   foo' (_,  0) = return 0 
   foo' ((w,v):xs, n) 
       | w > n  = foo' (xs, n) 
       | otherwise = do 
        a <- foo' (xs, n) 
        b <- foo' (xs, n - w) 
        return (a `max` b + v) 
   

3. Затем мы открываем самореференцию в foo' (потому что мы хотим, чтобы вызвать функцию memoized):

   type Endo a = a -> a 
   
   foo' :: Monad m => Endo (([(Int, Int)], Int) -> Int) 
   foo' _ ([],  _) = return 0 
   foo' _ (_,  0) = return 0 
   foo' self ((w,v):xs, n) 
       | w > n    = foo' (xs, n) 
       | otherwise   = do 
        a <- self (xs, n) 
        b <- self (xs, n - w) 
        return (a `max` b + v) 
   

4. Мы будем использовать следующее запоминание подмешать к memoize нашей функции foo':

   type Dict a b m = (a -> m (Maybe b), a -> b -> m()) 
   
   memo :: Monad m => Dict a b m -> Endo (a -> m b) 
   memo (check, store) super a = do 
       b <- check a 
       case b of 
        Just b -> return b 
        Nothing -> do 
         b <- super a 
         store a b 
         return b 
   

5. Наш словарь (памятка таблица) будет использовать State монады и структуру Map данных:

   import Prelude hiding (lookup) 
   import Control.Monad.State 
   import Data.Map.Strict 
   
   mapDict :: Ord a => Dict a b (State (Map a b)) 
   mapDict = (check, store) where 
       check a = gets (lookup a) 
       store a b = modify (insert a b) 
   

6. Наконец, мы объединим все, чтобы создать memoized функцию memoFoo:

   import Data.Function (fix) 
   
   type MapMemoized a b = a -> State (Map a b) b 
   
   memoFoo :: MapMemoized ([(Int, Int)], Int) Int 
   memoFoo = fix (memo mapDict . foo') 
   

7. Мы можем восстановить исходную функцию foo следующим образом:

   foo :: [(Int, Int)] -> Int -> Int 
   foo xs n = evalState (memoFoo (xs, n)) empty 
   

Надежда, которая помогает ,