recursivas - potencia en haskell

¿Qué algoritmo se usa en Haskell(GHC) para derivar tipos de expresiones recursivas?

Question

Considere los siguientes ejemplos:

Funciones no recursivas

 f x = x
g y = f ''A''

GHC infiere f :: a -> a

Funciones recursivas mutuas

 f x = const x g
g y = f ''A''

Ahora GHC infiere f :: Char -> Char , aunque el tipo podría ser a -> a justo en el caso anterior.

Recursion polimorfa

 data FullTree a = Leaf | Bin a (FullTree (a, a))
size :: FullTree a -> Int
size Leaf = 0
size (Bin _ t) = 1 + 2 * size t

Aquí, GHC no puede inferir el tipo de size , a menos que se indique su tipo explícito.

Así que parece que Haskell (GHC) no usa la recursión polimórfica (como se describe en Alan Mycroft: esquemas de tipo polimórfico y definiciones recursivas ), porque no puede inferir tipos polimórficos en los ejemplos 2 y 3. Pero en el primer caso es correcto. Infiere el tipo más general de f . ¿Cuál es el procedimiento exacto? ¿GHC analiza las dependencias de las expresiones, las agrupa (como f y g en el segundo ejemplo) y utiliza la inferencia de tipo de recursión monomórfica en estos grupos?

Answer 1

¿GHC analiza las dependencias de las expresiones, las agrupa (como f y g en el segundo ejemplo) y utiliza la inferencia de tipo de recursión monomórfica en estos grupos?

Sí, exactamente esto sucede. El informe Haskell 2010 tiene una section sobre el tema.