Воспоминание умножения

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

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 s), где c=Vec False v, и я ожидал, что это будет так же быстро, как если бы я взломал f в:

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

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

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

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

map (*c) xs

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

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

Спасибо

Ответ 1

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

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

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

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

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

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

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

См. также этот ответ в Как добавить поля, которые кэшируют что-то только в ADT?

Ответ 2

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

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

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

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