10

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

举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. 在临时多态函数和参数函数之间转换的一般技术是什么？
4

2 回答 2

8

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

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

于 2016-07-12T11:13:57.890 回答
6

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

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

于 2016-07-13T16:07:52.223 回答