Есть ли в Haskell автоматический способ запоминания глобальных полиморфных значений?

Question

Полиморфные "константы", вроде 5 :: Num a => a, на самом деле это не константы, а функции аргумента словаря. Следовательно, если вы определите

primes :: Num n => [n]
primes = ...

^{Плохой пример, конечно, здесь нет веских причин для того, чтобы он был полиморфным... что меня действительно интересует, так это если вы пытаетесь глобально запоминать нетривиальную полиморфную функцию, например} memo-trie ^s.
тогда эта последовательность не будет разделена между вызовами с разных сайтов, что не очень хорошо с точки зрения производительности. (Разве это не главная причина, по которой стандарт Хаскелла благословил нас Страшным ограничением мономорфизма?)

Единственный способ, которым я могу увидеть, как обеспечить совместное использование, - это иметь мономорфный "тег" для каждого экземпляра ограничивающего класса. Например

erastothenes :: Num n => [n]
erastothenes = ...

class (Num n) => HasPrimes n where
  -- | @'primes' ≡ 'erastothenes'@
  primes :: [n]

integerPrimes :: [Integer]
integerPrimes = erastothenes

instance HasPrimes Integer where
  primes = integerPrimes

... что нехорошо с точки зрения элегантности.

Есть ли более приятный способ реализовать такую ​​памятку?

Answer 1

Если вы включите ConstraintKinds а также ExistentialQuantification (или же GADTs) вы можете улучшить словари классов классов:

{-# LANGUAGE ConstraintKinds, ExistentialQuantification #-}

data Dict a = a => Dict

Если мы попробуем это

fibs :: Num n => [n]
fibs = 1 : 1 : zipWith (+) fibs (drop 1 fibs)

fibs' :: [Integer]
fibs' = fibs


fibsWithDict :: Dict (Num n) -> [n]
fibsWithDict Dict = fs
  where
    fs = 1 : 1 : zipWith (+) fs (drop 1 fs)

fibs'' :: [Integer]
fibs'' = fibsWithDict Dict

в GHCi мы видим

λ> :set +s
λ> 
λ> fibs !! 29
832040
(2.66 secs, 721235304 bytes)
λ> 
λ> fibs !! 29
832040
(2.52 secs, 714054736 bytes)
λ> 
λ> 
λ> fibs' !! 29
832040
(2.67 secs, 713510568 bytes)
λ> 
λ> fibs' !! 29
832040
(0.00 secs, 1034296 bytes)
λ> 
λ> 
λ> fibs'' !! 29
832040
(0.00 secs, 1032624 bytes)

Так fibs'' это единственная реализация из трех, которая сразу же запоминается.

Обратите внимание, что мы должны сопоставить шаблон на Dict конструктор. В противном случае мы получим ошибку о n не будучи вынужденным иметь Num экземпляр (как и следовало ожидать, если бы наша подпись была просто fibsWithDict :: a -> [n]).

Это полное решение, так как вы можете рассмотреть fibsWithDict Dict быть выражением, которое запоминается сразу при любом типе, который вы к нему добавляете (если это экземпляр Num). Например:

λ> (fibsWithDict Dict !! 29) :: Double
832040.0
(0.00 secs, 1028384 bytes)

РЕДАКТИРОВАТЬ: похоже, что эта явная передача словаря здесь не является необходимым и может быть сделано неявно с помощью ScopedTypeVariables с локальной привязкой:

{-# LANGUAGE ScopedTypeVariables #-}

fibsImplicitDict :: forall a. Num a => [a]
fibsImplicitDict
  = let fs :: [a]
        fs = 1 : 1 : zipWith (+) fs (drop 1 fs)
    in
    fs

(Спасибо Bennofs за понимание здесь!)

Answer 2

Это довольно невозможно по довольно техническим причинам. Классы типов открыты, поэтому полиморфная константа не может во время компиляции обязательно "увидеть", сколько типов удовлетворяет ограничению, поэтому она не может выделить столько мономорфных блоков. С другой стороны, класс типов определенно не может видеть все возможные константы, которые он может генерировать, поэтому мономорфные символы не могут быть размещены в словаре классов типов.

Вам нужно будет явно указать любые типы, для которых вы хотите выделить мономорфный блок.

Answer 3

Можно добавить Typeable ограничение к n и использовать разные таблицы напоминаний для каждого типа земли n, Вы, вероятно, должны были бы использовать Dynamic а также cast много для этого, что является неоптимальным. Это также кажется немного хакерским, тоже.

Конечно, на языке с зависимой типизацией можно смоделировать карту (n : Num) -> [n] который не требует castsс из Dynamic, Может быть, что-то подобное можно смоделировать, используя ГАДЦ и какой-то механизм овеществления.