Запоминающее умножение

Question

Мое приложение умножает векторы после (дорогостоящего) преобразования с использованием БПФ. В результате, когда я пишу

f :: (Num a) => a -> [a] -> [a] 
f c xs = map (c*) xs 

Я только хочу, чтобы вычислить БПФ c один раз, а не для каждого элемента xs. Там действительно нет необходимости хранить БПФ от c для всей программы, только в локальной области.

я попытался определить мой Num экземпляр как:

data Foo = Scalar c 
     | Vec Bool v -- the bool indicates which domain v is in 

instance Num Foo where 
    (*) (Scalar c) = \x -> case x of 
         Scalar d -> Scalar (c*d) 
         Vec b v-> Vec b $ map (c*) v 
    (*) v1 = let Vec True v = fft v1 
      in \x -> case x of 
        Scalar d -> Vec True $ map (c*) v 
        v2 -> Vec True $ zipWith (*) v (fft v2) 

Затем, в приложении, я вызываю функцию, аналогичную f (который работает на произвольных Num с), где c=Vec False v, и я ожидал, что это будет быть столь же быстро, как если бы я взломать f на:

g :: Foo -> [Foo] -> [Foo] 
g c xs = let c' = fft c 
     in map (c'*) xs 

функция g делает запоминание из fft c происходят, и мю ch быстрее, чем вызов f (независимо от того, как я определяю (*)). Я не понимаю, что происходит с f. Является ли это моим определением (*) в примере Num? Имеет ли он какое-то отношение к f, работающему над всеми Nums, и GHC, поэтому не может понять, как частично вычислить (*)?

Примечание: Я проверил вывод ядра для моего экземпляра Num, и (*) действительно представлен как вложенные лямбды с преобразованием FFT на лямбда верхнего уровня. Таким образом, похоже, что это, по крайней мере, способно быть замеченным. Я также попытался как разумно, так и безрассудно использовать шаблоны ударов, чтобы попытаться заставить оценку не иметь никакого эффекта.

Как примечание стороны, даже если я могу понять, как сделать (*) memoize его первый аргумент, есть еще одна проблема с тем, как это определено: Программист хочет использования тип данных Foo должен знать о это возможность memoization. Если она написали

map (*c) xs 

никакой меморандума не возникнет. (Это должно быть написано как (map (c*) xs)) Теперь, когда я думаю об этом, я не совсем уверен, как GHC перепишет версию (*c), так как у меня есть (*). (c*) делает c первым аргументом *, тогда как (*c) делает c вторым аргументом *. Поэтому проблема заключается в том, что неясно, как следует писать умножение для обеспечения memoization. Является ли это просто неотъемлемым недостатком нотации infix (и неявное предположение, что аргументы * являются симметричными)?

Вторая, менее актуальная проблема заключается в том, что корпус re отобразим (v *) в список скаляров. В этом случае (надеюсь), fft of v будет вычисляться и храниться, хотя это необязательно, так как другой множитель является скаляром. Есть ли способ обойти это?

Благодаря

Answer 1

Я считаю, что stable-memo пакет может решить вашу проблему. Это memoizes значения не используя равенство, но ссылочная идентичность:

В то время как большинство памятки комбинаторы memoize на основе равенства, устойчиво-памятка делает это на основе имеет ли тот же самый аргумент был передан в функцию, прежде чем (то есть, тот же аргумент в памяти).

И он автоматически падает memoized значения, когда их ключи сборки мусора:

стабильной памятка не сохраняет ключи он видел до сих пор, что позволяет им быть мусора, если они будут больше не используются. Финализаторы устанавливаются на место, чтобы удалить соответствующие записи из таблицы заметок, если это произойдет.

Так что, если вы определяете что-то вроде

fft = memo fft' 
    where fft' = ... -- your old definition 

вы получите довольно много, что вам нужно: Calling map (c *) xs будет memoize вычисление БПФ внутри первого вызова (*) и он получает повторно при последующих вызовах до (c *). И если c - сбор мусора, то есть fft' c.

Смотрите также this answer к How to add fields that only cache something to ADT?

Answer 2

я вижу две проблемы, которые могут помешать запоминанием:

Во-первых, f имеет перегруженный тип и работает для всех Num экземпляров. Таким образом, f не может использовать memoization, если он не является специализированным (что обычно требует прагмы SPECIALIZE) или inlined (что может происходить автоматически, но более надежно с помощью прагмы INLINE).

Во-вторых, определение (*) для Foo выполняет сопоставление с образцом на первый аргумент, но f умножает с неизвестным c. Таким образом, в пределах f, даже если он специализирован, никакая memoization не может произойти. Еще раз, это очень зависит от f, являющегося встроенным, и конкретным аргументом для c, который будет поставляться, чтобы на самом деле появилась вставка.

Так что я думаю, что это поможет узнать, как именно вы звоните f. Обратите внимание, что если f определяется с использованием двух аргументов, ему нужно дать два аргумента, иначе он не может быть встроен. Это также помогло бы увидеть фактическое определение Foo, как вы сообщаете c и v, которые не входят в сферу действия.