アドホック多型関数とパラメトリック多形関数間を変換する良い方法

Question

アドホック多形関数とパラメトリック多形関数間を変換する一般的な方法があるのだろうかと思います。言い換えれば、アドホック多形関数を考えると、パラメトリックな対応をどのように実装するのでしょうか？他の方法はどうですか？

sortを例にとります。それはsortByの面でsort :: Ord a => [a] -> [a]を書くのは簡単です：

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

私は必ずしもあなたがこれを行う必要があります言っていないんだけど、あなたはリストの各要素でそれをパッケージ化することなく、比較関数の周囲を通過する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 

次のように与えられた（あわや）上記のインフラ、あなたはその後、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 

Answer 2

サボテンの答えはreflectionにやや日陰Givenクラスに依存している（Data.Coerceを使用することによって、我々はOラッパーのすべての潜在的な実行時のコストを避けることに注意してください）。しかし、それを使わずにリフレクションを使うことは可能です。生成コアを調べる

{-# 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周りに薄いラッパーにコンパイルすることを示しています。 Proxyの代わりにTaggedに基づいてReifiesクラスを使用するとさらに薄くなりますが、Ed Kmettは生成するAPIが嫌いです。