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

Полиморфные "константы", такие как 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

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

Есть ли лучший способ реализовать такую memoisation?

Ответы

Ответ 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)

EDIT: похоже, что эта явная передача в словаре не нужна здесь и может быть выполнена неявно с помощью ScopedTypeVariables с локальной привязкой:

{-# LANGUAGE ScopedTypeVariables #-}

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

(Благодаря знаниям для понимания здесь!)

Ответ 2

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

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

Ответ 3

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

В зависимости от типизированного языка, конечно, можно моделировать карту (n : Num) -> [n], которая не требует casts из Dynamic. Возможно, что-то подобное может быть смоделировано с использованием GADT и какого-то механизма reification.