Как заставить Haskell вычислять правильный полиморфный тип? - PullRequest
Новая
       9

Как заставить Haskell вычислять правильный полиморфный тип?

7 голосов
/ 01 декабря 2009

Я только что понял, насколько полезной может быть маленькая on -функция.

Ex: 

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)?

1 Ответ

3 голосов
/ 01 декабря 2009 
{-# 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> <b>:t on' (==)</b>
on' (==) :: (Eq a) => (forall d. c d -> a) -> c e -> c f -> Bool
Prelude> <b>:t on' (==) length</b>
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
...