¿Cómo hacer que Haskell calcule el tipo polimórfico correcto?

Question

Me acabo de dar cuenta de lo útil que puede ser la pequeña función on.

Ex:

orderByLength = sortBy (compare `on` length) 

Pero, por desgracia, los tipos inferidos puede ser algo contrario a la intuición.

De acuerdo con la definición misma

f `on` g = \x y -> f (g x) (g y) 

uno podría, por ejemplo, reemplazar

(==) `on` length 

con

\x y -> (length x) == (length y) 

Pero ambos tienen diferentes tipos!

El primero tiene [a] -> [a] -> Bool mientras que el segundo tiene el tipo correcto, más genérico de [a] -> [b] -> Bool.

Esto no permite términos obviamente correctos como (on (==) length) [1, 2, 3] ["a", "b", "c"] (que debería dar como resultado True pero ahora incluso falla la comprobación de tipos).

Sé que esta restricción surge debido al uso de first-rank types, pero ¿cómo superar esto? ¿Alguien puede formular una implementación de on que pueda manejar correctamente las funciones polimórficas (utilizando los tipos de cuantificación/rango universales n)?

Answer 1

{-# LANGUAGE Rank2Types #-} 
on' :: (a -> a -> b) -> (forall d. c d -> a) -> c e -> c f -> b 
on' f g x y = f (g x) (g y) 

Este resultado en

 
Prelude> :t on' (==) 
on' (==) :: (Eq a) => (forall d. c d -> a) -> c e -> c f -> Bool 
Prelude> :t on' (==) length 
on' (==) length :: [e] -> [f] -> Bool 

Por otro lado, esta firma también hace flip on' id ilegal, que es algo menos que deseable.

---

{-# LANGUAGE TemplateHaskell #-} 
import Language.Haskell.TH 
onE f g = do 
    x <- newName "x" 
    y <- newName "y" 
    lamE [varP x, varP y] $ f `appE` (g `appE` varE x) `appE` (g `appE` varE y) 

 
Prelude> :set -XTemplateHaskell 
Prelude> $(onE [|(==)|] [|length|]) [1,2,3] ["a","b","c"] 
True 
Prelude> $(onE [|(==)|] [|id|]) 4 5 
False