good way to convert between ad-hoc polymorphic functions and parametric polymorphic ones

Question

I'm wondering if there are general ways to convert between ad-hoc polymorphic functions and parametric polymorphic ones. In other words, given an ad-hoc polymorphic function, how to implement its parametric counterpart? and what about the other way around?

take sort as an example. it's easy to write sort :: Ord a => [a] -> [a] in terms of sortBy:

sort :: Ord a => [a] -> [a]
sort = sortBy compare

but the other way around seems tricky, so far the best I can do is to go a bit "object-oriented":

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

But this sounds more like a hack than proper solution.

so I'd like to know:

1. are there better ways for this specific example?
2. what are the general techniques for converting between ad-hoc polymorphic functions and parametric ones?

Answer 1

I'm not necessarily saying you should do this, but you can use reflection to pass around the comparison function without having to package it up with each element of the list:

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

Given (heh) the above infrastructure, you can then write sortBy in terms of sort as follows:

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

(note that by using Data.Coerce, we avoid all potential runtime cost of the O wrapper)