Почему добавление сигнатуры полиморфного типа снижает производительность?

Question

Вот простая функция для вычисления чисел Фибоначчи:

fib :: [Int]
fib = 1 : 1 : zipWith (+) fib (tail fib)

В ghci я могу быстро вычислить ряд. Фактически, некоторые эксперименты показывают, что вычисления выполняются приблизительно за линейное время.

ghci> last $ take 100000 fib
354224848179261915075         -- takes under a second

Если я вместо этого изменю сигнатуру типа на полиморфную:

fib :: Num a => [a]
fib = 1 : 1 : zipWith (+) fib (tail fib)

Тогда алгоритм становится медленнее. На самом деле, похоже, что теперь он работает в экспоненциальном времени!

Означает ли переключение на полиморфную сигнатуру типа то, что список полностью пересчитывается на каждом этапе? Если так, то почему?

Answer 1

Это из-за словарного перевода.

fib :: [Int]

является константой верхнего уровня.

Но это:

fib :: Num a => [a]
fib = 1 : 1 : zipWith (+) fib (tail fib)

это просто функция верхнего уровня, которая будет применяться к Num словарь во время выполнения. Вот так:

fib d = 1 : 1 : zipWith (d.+) (fib d) (tail (fib d))

Поэтому, если вы скомпилируете это без каких-либо оптимизаций, так что никакой специализации не произойдет, вы получите экспоненциальное временное фиби, поскольку список перестраивается с нуля при каждом вызове функции - это больше не ленивая структура данных.

Answer 2

Да, подпись полиморфного типа означает, что она пересчитывается на каждом этапе. Ядро, произведенное GHC-7.4.2 с -O2:

lvl_rcZ :: GHC.Integer.Type.Integer
[GblId, Str=DmdType]
lvl_rcZ = __integer 1

Rec {
PolyFib.fib [Occ=LoopBreaker]
  :: forall a_a9W. GHC.Num.Num a_a9W => [a_a9W]
[GblId, Arity=1, Str=DmdType L]
PolyFib.fib =
  \ (@ a_aal) ($dNum_aam :: GHC.Num.Num a_aal) ->
    GHC.Types.:
      @ a_aal
      (GHC.Num.fromInteger @ a_aal $dNum_aam lvl_rcZ)
      (GHC.Types.:
         @ a_aal
         (GHC.Num.fromInteger @ a_aal $dNum_aam lvl_rcZ)
         (GHC.List.zipWith
            @ a_aal
            @ a_aal
            @ a_aal
            (GHC.Num.+ @ a_aal $dNum_aam)
            (PolyFib.fib @ a_aal $dNum_aam)
            (case PolyFib.fib @ a_aal $dNum_aam of _ {
               [] -> GHC.List.tail1 @ a_aal;
               : _ xs_abD -> xs_abD
             })))
end Rec }

Причина в том, что не представляется возможным кэшировать список чисел Фибоначчи для каждого типа, принадлежащего Num, а также fib явно полиморфное значение, следовательно, оно не кэшируется вообще.

Если вы хотите кэшировать его хотя бы для вычислений каждого типа, используйте локальный список

pfibs :: Num a => [a]
pfibs = res
  where
    res = 1 : 1 : zipWith (+) res (tail res)

делает кеширование для каждого вычисления (так pfibs !! 500 например, быстро), так как теперь список является мономорфным в каждом вычислении. Он будет по-прежнему пересчитываться для каждого запроса (если вы не связываете его с мономорфным именем), но не для каждого отдельного элемента списка.

*PolyFib> pfibs !! 999999 :: Int
-4249520595888827205
(0.31 secs, 137462088 bytes)