在ad-hoc多态函数和参数多态函数之间进行转换的好方法

Question

我想知道是否有一般方法在ad-hoc多态函数和参数多态函数之间进行转换.换句话说,给定一个ad-hoc多态函数,如何实现其参数对应？反过来呢？

取sort,例如,它很容易写sort :: Ord a => [a] -> [a]在以下方面sortBy:

sort :: Ord a => [a] -> [a]
sort = sortBy compare

但另一种方式似乎很棘手,到目前为止,我能做的最好的事情是有点"面向对象":

import qualified Data.List as L

data OrdVal a = OV (a -> a -> Ordering) a

instance Eq (OrdVal a) where
    (OV cmp a) == (OV _ b) = a `cmp` b == EQ

instance Ord (OrdVal a) where
    (OV cmp a) `compare` (OV _ b) = a `cmp` b

sortBy :: (a -> a -> Ordering) -> [a] -> [a]
sortBy cmp = map unOV . L.sort . map (OV cmp)
  where
    unOV (OV _ v) = v

但这听起来更像是一个黑客而不是正确的解决方案.

所以我想知道:

1. 这个具体的例子有更好的方法吗？
2. 在ad-hoc多态函数和参数多态函数之间进行转换的一般技术是什么？

Answer 1

我不一定说你应该这样做,但你可以使用反射来传递比较函数,而不必将它与列表的每个元素打包在一起:

{-# LANGUAGE UndecidableInstances #-}
import Data.Reflection

newtype O a = O a

instance Given (a -> a -> Ordering) => Eq (O a) where
    x == y = compare x y == EQ

instance Given (a -> a -> Ordering) => Ord (O a) where
    compare (O x) (O y) = given x y

鉴于(港灯)以上的基础设施,就可以写sortBy在条款sort如下:

import Data.Coerce
import Data.List (sort)

sortBy :: (a -> a -> Ordering) -> [a] -> [a]
sortBy cmp = give cmp $ from . sort . to
  where
    to :: [a] -> [O a]
    to = coerce

    from :: [O a] -> [a]
    from = coerce

(请注意,通过使用Data.Coerce,我们可以避免O包装器的所有潜在运行时成本)

Answer 2

Cactus的答案依赖于有点阴暗的Given课程reflection.但是,没有它可以使用反射.

{-# LANGUAGE ScopedTypeVariables, MultiParamTypeClasses, UndecidableInstances #-}

module SortReflection where

import Data.Reflection
import Data.List (sort)
import Data.Proxy
import Data.Coerce

newtype O s a = O {getO :: a}

instance Reifies s (a -> a -> Ordering) => Eq (O s a) where
  a == b = compare a b == EQ

instance Reifies s (a -> a -> Ordering) => Ord (O s a) where
  compare = coerce (reflect (Proxy :: Proxy s))

sortBy :: forall a . (a -> a -> Ordering) -> [a] -> [a]
sortBy cmp = reify cmp $
  \(_ :: Proxy s) -> coerce (sort :: [O s a] -> [O s a])

检查生成的Core表明这会编译成一个薄的包装器sortBy.它使用Reifies基于Tagged而不是的类来看起来更薄Proxy,但Ed Kmett不喜欢生成的API.