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

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

但这听起来更像是一个黑客，而不是适当的解决方案。

所以我想知道：

1. 对于这个特定示例，有更好的方法吗？
2. 在临时多态函数和参数函数之间进行转换的一般技术是什么？

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

给定（呵呵）上述基础结构，然后您可以按sort编写sortBy，如下所示：

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

仙人掌的答案依赖于reflection中有些阴暗的Given类。但是，如果没有它，可以使用反射。

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

检查生成的内核表明，这会编译为围绕sortBy的薄包装器。使用基于 Tagged 而不是 Proxy 的 Reifies 类看起来更薄，但 Ed Kmett 不喜欢生成的 API。