haskell - 如何让 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 但现在甚至无法通过类型检查)。

我知道这个限制是由于使用了 first-rank types ，但是如何克服呢？有人可以制定 on 的实现吗？可以正确处理多态函数(使用通用量化/rank-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)

这导致

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

On the other hand, this signature also makes flip on' id illegal, which is somewhat less than desirable.

---

{-# 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 [|(==)|] [|length|]) [1,2,3] ["a","b","c"]
真的
前奏> $(onE [|(==)|] [|id|]) 4 5
错误的