Хороший способ для преобразования между специальными полиморфными функциями и параметрическими полиморфными

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

Учитывая (хех) вышеупомянутую инфраструктуру, вы можете написать 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 обертка)

Answer 2

Ответ Кактуса опирается на несколько тенистый 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, но Эд Кметт не любит API, который производит.