haskell - 在临时多态函数和参数多态函数之间转换的好方法

Question

我想知道是否有通用方法可以在临时多态函数和参数多态函数之间进行转换。换句话说，给定一个特殊的多态函数，如何实现它的参数对应？反过来呢？

拍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

但这听起来更像是一种技巧，而不是正确的解决方案。

所以我想知道:

这个具体例子有更好的方法吗？

在临时多态函数和参数函数之间转换的一般技术是什么？

Answer 1

我不一定说你应该这样做，但你可以使用 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

给定(呵呵)上述基础设施，您可以编写 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 包装器的所有潜在运行时成本)