如何让Haskell计算出正确的多态类型？

Question

我刚刚意识到小on功能有多么有用.

例如:

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但现在甚至无法进行类型检查).

我知道这个限制是由于使用了一流类型而引起的,但是如何克服这个问题呢？有人可以制定一个on可以正确处理多态函数的实现(使用通用量化/秩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)

这导致

前奏> :t on' (==)
on' (==) :: (Eq a) => (forall d.cd -> a) -> ce -> cf -> Bool
Prelude> :t on' (==) 长度
on' (==) 长度 :: [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)

前奏> :set -XTemplateHaskell
前奏> $(onE [|(==)|] [|长度|]) [1,2,3] ["a","b","c"]
真的
前奏> $(onE [|(==)|] [|id|]) 4 5
错误的