9

Mi chiedo se ci siano modi generali per convertire tra le funzioni polimorfiche ad-hoc e quelle polimorfiche parametriche. In altre parole, data una funzione polimorfica ad-hoc, come implementare la sua controparte parametrica? e il contrario?buon modo per convertire tra le funzioni polimorfiche ad-hoc e quelle polimorfiche parametriche

prendere sort come un esempio. è facile scrivere sort :: Ord a => [a] -> [a] in termini di sortBy:

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

ma il contrario sembra difficile, finora il migliore che posso fare è di andare un po ' "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 

Ma questo suona più come un hack che una soluzione adeguata.

quindi mi piacerebbe sapere:

  1. ci sono modi migliori per questo esempio specifico?
  2. Quali sono le tecniche generali per la conversione tra funzioni polimorfiche ad-hoc e quelle parametriche?
+1

Se potessimo passare dizionari (ad esempio impliciti in Agda), questo sarebbe banale. Tuttavia, credo che alcune classi/librerie sfruttino il fatto che non possiamo passare i dizionari per garantire alcuni invarianti. Ad esempio, immagina di poter chiamare "DataSet.insert" usando un diverso ordine ogni volta ... – chi

+6

Nota anche che il tuo "hack" funziona in pratica, ma solo se non impacchetti due distinte funzioni 'cmp' in' OrdVal a' valori. Se lo fai, allora l'istanza di 'Ord' non soddisfa le leggi di' Ord'. – chi

risposta

7

Non sto necessariamente dicendo che si dovrebbe fare questo, ma è possibile uso reflection passare intorno alla funzione di confronto, senza dover confezionare in su con ogni elemento della lista:

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

dato (eh) l'infrastruttura di cui sopra, si può quindi scrivere sortBy in termini di sort come segue:

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 

(notare che utilizzando Data.Coerce, evitiamo tutto il potenziale costo di runtime del O involucro)

+2

'Given' è un po 'malvagio, e davvero non ne hai bisogno qui. Aggiungi un fantoccio al nuovo tipo e poi usa "Reifica" invece di "Dato", "reifica" invece di "dare" e "riflettere" invece di "dato". – dfeuer

4

risposta di Cactus si basa sulla Given di classe un po 'ombroso in reflection. È possibile, tuttavia, utilizzare la riflessione senza di essa.

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

Esaminando il Nucleo ha prodotto indica che questo viene compilato in un sottile involucro intorno sortBy. Sembra ancora più sottile usando una classe Reifies basata su Tagged anziché su Proxy, ma a Ed Kmett non piace l'API che produce.

+0

Perché non utilizzare 'coerce' nell'implementazione' sortBy'? – Cirdec

+0

@ Cirdec, non c'è un motivo particolare per non farlo, se lo stai usando altrove. Non ho capito quando ho iniziato che sarebbe stato utile altrove. In ogni caso, generalmente preferisco usare '#.'e'. # 'dove applicabile piuttosto che usare' coerce' direttamente, poiché così facendo si tende a ridurre il numero di firme del tipo richieste e si può rendere il codice più chiaro. Anche quando 'Data.Profunctor.Unsafe' non è disponibile, quei bit dell'istanza' -> 'possono essere copiati facilmente. – dfeuer

+0

L'unica firma di tipo necessaria con due 'coerce's è' sort :: [O s a] -> [O s a] '. Se si definisce 'sortBy cmp = reify cmp $ \ (_ :: Proxy s) -> coercire. (ordina :: [O s a] -> [O s a]). coercisci' non ti devi preoccupare della potenziale assegnazione di una lista intermedia. – Cirdec