«Поделиться» или «кэшировать» выражение, параметризованное только неоднозначными типами? - PullRequest
Новая
       17

«Поделиться» или «кэшировать» выражение, параметризованное только неоднозначными типами?

0 голосов
/ 21 января 2019

У меня каверзный вопрос;

Итак, я знаю, что 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 кеширует и повторно использует словари классов типов? Может быть, я мог бы превратить это в константу в dict класса типов, чтобы получить кеширование?

Идеи у кого-нибудь? Или кто-нибудь читает мне, как это работает?

Я бы предпочел сделать это таким образом, чтобы компилятор мог понять это, а не использовать ручное запоминание, но я открыт для идей:)

Спасибо за ваше время!

1 Ответ

0 голосов
/ 21 января 2019

Как подсказал @crockeea, я провел эксперимент; Вот попытка использовать константу верхнего уровня с полиморфной переменной неоднозначного типа, а также фактическую константу просто для забавы, каждая из которых содержит «след» 

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), и он не известен конкретно во время компиляции. Вы МОЖЕТЕ делать это везде, где ИСПОЛЬЗУЕТЕ значение класса типов, но оно будет оцениваться один раз за лифт, и вам придется поднимать ВСЕГДА, где вы используете его, чтобы получить преимущества; довольно непрактично.

...