Ответ 1
Анализирует ли GHC зависимости выражений, группирует их вместе (например, f и g во втором примере) и использует вывод мономорфных рекурсивных типов в этих группах?
Да, именно так происходит. В отчете Haskell 2010 есть раздел по теме.
Какой алгоритм используется в Haskell (GHC) для получения типов рекурсивных выражений?
Рассмотрим следующие примеры:
Нерекурсивные функции
f x = x
g y = f 'A'
GHC сообщает f :: a -> a
Взаимно рекурсивные функции
f x = const x g
g y = f 'A'
Теперь GHC выводит f :: Char -> Char, хотя тип может быть a -> a только в предыдущем случае.
Полиморфная рекурсия
data FullTree a = Leaf | Bin a (FullTree (a, a))
size :: FullTree a -> Int
size Leaf = 0
size (Bin _ t) = 1 + 2 * size t
Здесь GHC не может вывести тип size, если не указан его явный тип.
Итак, кажется, что Haskell (GHC) не использует полиморфную рекурсию (как описано в Alan Mycroft: схемы полиморфного типа и рекурсивные определения), поскольку он может" t вывести полиморфные типы в примерах 2 и 3. Но в первом случае он правильно определяет наиболее общий тип f. Какая именно процедура? GHC анализирует зависимости выражений, группирует их вместе (например, f и g во втором примере) и использует вывод мономорфного рекурсивного типа в этих группах?