如何讓Haskell計算正確的多態類型？

Question

我剛剛意識到小功能可以使用的功能有多大。

例：

orderByLength = sortBy (compare `on` length) 

但不幸的是，推斷的類型可以是有點反直覺。

按照非常定義

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

一個可以例如更換

(==) `on` length 

與

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

但兩者有不同的類型！

第一個有[a] -> [a] -> Bool，而第二個有正確的，更通用的[a] -> [b] -> Bool類型。

這不允許明顯正確的術語，如(on (==) length) [1, 2, 3] ["a", "b", "c"]（它應該產生True，但現在甚至無法進行類型檢查）。

我知道這個限制是由於使用first-rank types而出現的，但是如何克服這個問題？有人可以制定一個能夠正確處理多態函數（使用通用量化/等級-n類型）的實現on嗎？

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) 

這導致

 
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 

在另一方面，該簽名也使得flip on' id非法的，這是比預期稍差。

---

{-# 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