haskell - 在即席多态函数和参数多态函数之间进行转换的好方法

我想知道是否存在在即席多态函数和参数多态函数之间进行转换的一般方法。换句话说，给定特定的多态函数，如何实现其参数对应项？那反过来呢？

以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

但这听起来更像是hack，而不是适当的解决方案。

所以我想知道:

有针对此特定示例的更好方法吗？

在即席多态函数和参数多态函数之间进行转换的一般技术是什么？

最佳答案

我不一定要说您应该这样做，但是您可以使用reflection传递比较功能，而不必将其与列表的每个元素打包在一起:

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

给定(heh)以上基础结构，您可以按照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包装程序的所有潜在运行时成本)