«Поделиться» или «кэшировать» выражение, параметризованное только неоднозначными типами?
У меня сложный вопрос;
Итак, я знаю, что GHC будет «кэшировать» (из-за отсутствия лучшего термина) определения верхнего уровня и вычислять их только один раз, например. :
myList :: [Int]
myList = fmap (*10) [0..10]
Даже если я использую myList в нескольких местах, GHC заметит, что у значения нет параметров, поэтому он может поделиться им и не будет «перестраивать» список.
Я хочу сделать это, но с вычислением, которое зависит от контекста уровня типа; упрощенный пример:
dependentList :: forall n. (KnownNat n) => [Nat]
dependentList = [0..natVal (Proxy @n)]
Итак, самое интересное здесь то, что для dependentList не существует «единого» кэшируемого значения; но как только тип применяется, он сводится к константе, поэтому теоретически после запуска проверки типов GHC может распознать, что все несколько мест зависят от «одного и того же» dependentList; например (используя TypeApplications)
main = do
print (dependentList @5)
print (dependentList @10)
print (dependentList @5)
Мой вопрос в том, признает ли GHC, что он может использовать оба списка 5? Или он вычисляет каждый отдельно? Технически было бы даже возможно вычислить эти значения во время компиляции, а не во время выполнения, возможно ли заставить GHC сделать это?
Мой случай немного сложнее, но должен следовать тем же ограничениям, что и в примере, однако мое значение, подобное dependentList, требует больших вычислений.
Я вовсе не против того, чтобы делать это с помощью класса типов, если это позволяет; кэширует ли GHC и повторно использует словари классов типов? Может быть, я мог бы запечь его в константу в словаре класса типов, чтобы получить кеширование?
Идеи кто-нибудь? Или у кого-нибудь есть чтение для меня, чтобы посмотреть, как это работает?
Я бы предпочел сделать это таким образом, чтобы компилятор мог это понять, а не использовать ручную мемоизацию, но я открыт для идей :)
Спасибо за ваше время!
Хороший план; Добавил результаты в конец вопроса
Похоже, это работает, когда вы используете класс типов; не идеально, но довольно интересно :) Еще посмотрю, смогу ли я отодвинуть оценку еще дальше; как время компиляции! @кроки
Ответы 1
По предложению @crokeea я провел эксперимент; здесь попытка использовать константу верхнего уровня с полиморфной переменной неоднозначного типа, а также фактическую константу просто для удовольствия, каждая из которых содержит «след»
dependant :: forall n . KnownNat n => Natural
dependant = trace ("eval: " ++ show (natVal (Proxy @n))) (natVal (Proxy @n))
constantVal :: Natural
constantVal = trace "constant val: 1" 1
main :: IO ()
main = do
print (dependant @1)
print (dependant @1)
print constantVal
print constantVal
Итоги плачевные:
λ> main
eval: 1
1
eval: 1
1
constant val: 1
1
1
Так что ясно, что он переоценивает полиморфную константу каждый раз, когда она используется.
Но если мы запишем константы в класс типов (по-прежнему используя неоднозначные типы), окажется, что он будет разрешать значения словаря только один раз для каждого экземпляра, что имеет смысл, когда вы знаете, что GHC передает один и тот же dict для одних и тех же экземпляров класса. Конечно, он повторно запускает код для разных экземпляров:
class DependantClass n where
classNat :: Natural
instance (KnownNat n) => DependantClass (n :: Nat) where
classNat = trace ("dependant class: " ++ show (natVal (Proxy @n))) (natVal (Proxy @n))
main :: IO ()
main = do
print (classNat @1)
print (classNat @1)
print (classNat @2)
Результат:
λ> main
dependant class: 1
1
1
dependant class: 2
2
Что касается того, чтобы заставить GHC делать это во время компиляции, похоже, вы сделали бы это с lift от TemplateHaskell, используя эта техника.
К сожалению, вы не можете использовать это в определении класса типов, так как TH будет жаловаться, что '@n' должен быть импортирован из другого модуля (yay TH), и это неизвестно во время компиляции. Вы МОЖЕТЕ сделать это везде, где вы ИСПОЛЬЗУЕТЕ значение класса типов, но оно будет оценивать его один раз за подъем, и вам придется поднимать ВЕЗДЕ, где вы его используете, чтобы получить преимущества; довольно непрактично.
Некоторые первоначальные мысли: попробуйте поместить
traceвdependentList, чтобы увидеть, сколько раз он оценивается. Если он оценивался несколько раз, вы можете попробовать специализироватьdependentListдля нескольких конкретных типов.