trucchi per Typeclass generalizzata funzione multi-parametro sollevamento

Question

Per sollevare una funzione Haskell in una codifica lambda calcolo di ordine superiore. Questo è preso quasi alla lettera dalla codifica Typless Tagless Final di Oleg.

class Lam r where 
    emb :: a -> r a 
    (^) :: r (r a -> r a) -> (r a -> r a) 
    lam :: (r a -> r a) -> r (r a -> r a) 

instance Lam Identity where 
    emb = Identity 
    f^x = f >>= ($ x) 
    lam f = return (f . return =<<) -- call-by-value 

eval = runIdentity 

posso incorporare tipi Haskell arbitrarie in Lam utilizzando emb, ma non posso usare (^) per l'applicazione allora. Inoltre, le funzioni sollevate si comporterebbero pigramente. Invece, devo sollevarli per applicazione.

emb1 :: (Applicative r, Lam r) 
    => (a -> b) -> r (r a -> r b) 
emb1 f = lam $ \ra -> f <$> ra 

emb2 :: (Applicative r, Lam r) 
    => (a -> b -> c) -> r (r a -> r (r b -> r c)) 
emb2 f = lam $ \ra -> lam $ \rb -> f <$> ra <*> rb 

emb3 :: (Applicative r, Lam r) 
    => (a -> b -> c -> d) 
    -> r (r a -> r (r b -> r (r c -> r d))) 
emb3 f = lam $ \ra -> lam $ \rb -> lam $ \rc -> f <$> ra <*> rb <*> rc 

>>> eval $ emb2 (+)^emb 1^emb 2 
3 

Tuttavia, questo è un granché. Mi piacerebbe creare una funzione di sollevamento generica che funzioni per qualsiasi funzione di arbit. Mi sento come sarebbe possibile utilizzando qualcosa di simile ad Printf 's PrintfType o fixed-vector' Cont tipi s. Posso specificare quello che voglio con funzioni di tipo

type family Low h  o 
type instance Low ()  o = o 
type instance Low (a, h) o = a -> Low h o 

type family Lift r h  o 
type instance Lift r()  o = o 
type instance Lift r (a, h) o = r a -> r (Lift r h o) 

class Emb r h o where 
    embed :: Low h o -> r (Lift r h o) 

instance (Lam r) => Emb r() o where 
    embed = emb 

instance (Lam r, Applicative r, Emb r h o) => Emb r (a, h) o where 
    embed = ? 

ma ho molto attaccato tramite questo metodo, di solito a causa di problemi iniettività. Sono stato in grado di risolvere l'iniettività con una combinazione davvero orribile di wrapper newtype e variabili di tipo scoped, ma non è mai stato effettivamente selezionato.

È possibile esprimere in Haskell?

Answer 1

Si consiglia di guardare lo Ordinary and one-pass CPS transformation nello stile senza tag finale. Il trucco è generalizzare il tipo di freccia nella lingua dell'oggetto. Il fatto che spesso usiamo il costruttore di tipo di Haskell -> per i tipi di funzione nella lingua dell'oggetto (da incorporare) è una coincidenza e una comodità. Generalmente, le funzioni oggetto non si associano semplicemente alle funzioni Haskell. Il codice in questo articolo di cui contiene ESymantics

-- How to interpret arrows and other types 
type family Arr (repr :: * -> *) (a :: *) (b :: *) :: * 

class ESymantics repr where 
    int :: Int -> repr Int 
    add :: repr Int -> repr Int -> repr Int 

    lam :: (repr a -> repr b) -> repr (Arr repr a b) 
    app :: repr (Arr repr a b) -> repr a -> repr b 

Ora abbiamo abbastanza libertà di interpretare a seconda Arr una particolare rist. L'articolo di riferimento interpreta Arr per l'istanza CPS.

Modifica: In effetti si può ottenere lo stesso effetto - ridefinire il significato della freccia per un linguaggio oggetto - senza introdurre il tipo Arr (con i suoi problemi di iniettività) e senza ESemantics. Il suddetto collegamento, alle trasformazioni CPS ordinarie e one-pass, mostra il nuovo codice, utilizzando la Semantica standard e reinterpretando il significato del costruttore del tipo funzione. Non ci sono più problemi di iniettività.