Специализация полиморфных функций

Question

В своем разговоре «Занятия, Джим, но не так, как мы их знаем» Саймон Пейтон-Джонс рассказывает о том, как классы классов реализуются в GHC, имея полиморфные функции, берущие дополнительный параметр, который является словарем с правильным функции для типа (ов), заданного функции.

Затем он сказал, что GHC часто оптимизирует функции с помощью специальных функций и не передает этот словарь во время выполнения. Затем он сказал, что это не всегда возможно, потому что Haskell имеет полиморфную рекурсию, поэтому, даже если у вас есть целая программа, вы не можете полностью устранить все полиморфизм.

Что он имел в виду? Каков пример программы, в которой неизвестно, какие типы полиморфной функции будут переданы во время компиляции?

Answer 1

Вот типичный пример полиморфной рекурсии. Скажем, у нас есть тип данных, подобный список, но каждый элемент имеет тип вдвое «большой», как и предыдущий:

data Poly a = Nil | Cons a (Poly (a,a)) deriving Show 

foo :: Poly Int 
foo = Cons 3 (Cons (4,5) (Cons ((6,7),(8,9)) Nil)) 

length' :: Poly a -> Int 
length' Nil = 0 
length' (Cons _ xs) = 1 + length' xs 

Обратите внимание, что рекурсивный вызов length' имеет другой тип из исходного вызова ,

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