È possibile codificare una funzione generica di "sollevamento" in Haskell?

Question

Non sono il più grande fan delle vararg, ma ho sempre pensato che sia gli stili applicativo (f <$> x <*> y) sia l'idioma ([i| f x y |]) hanno troppi simboli. Di solito preferisco andare al modo liftA2 f x y, ma anch'io penso che A2 sia un po 'brutto. Da this question, ho imparato che è possibile implementare le funzioni vararg in Haskell. In questo modo, è possibile utilizzare lo stesso principio per implementare una funzione di sollevamento, in modo tale che:

lift f a b == pure f <*> a <*> b 

Ho provato a sostituire il + dal <*> sul codice citato:

class Lift r where 
    lift :: a -> r 

instance Lift a where 
    lift = id 

instance (Lift r) => Lift (a -> r) where 
    lift x y = lift (x <*> y) 

Ma non riuscivo a ottenere i tipi destra ...

Answer 1

si noti che è possibile concatenare qualsiasi numero di <*>, per ottenere una funzione della forma

f (a0 -> .. -> an) -> (f a0 -> .. -> f an) 

Se abbiamo il tipo a0 -> .. -> an e f a0 -> .. -> f an, possiamo calcolare f da questo. Siamo in grado di codificare questo rapporto, e il tipo più generale, come segue

class Lift a f b | a b -> f where 
    lift' :: f a -> b 

Come ci si potrebbe aspettare, l'istanza "caso ricorsivo" sarà semplicemente applicare <*> una volta, poi recurse:

instance (a ~ a', f' ~ f, Lift as f rs, Applicative f) 
     => Lift (a -> as) f (f' a' -> rs) where 
    lift' f a = lift' $ f <*> a 

La base il caso è quando non c'è più funzione. Dal momento che non si può effettivamente affermi "a non è un tipo di funzione", questo si basa su casi di sovrapposizione:

instance (f a ~ b) => Lift a f b where 
    lift' = id 

A causa di regole di selezione esempio GHCs, sarà sempre possibile selezionare il caso ricorsivo, se possibile.

Allora la funzione che si desidera è lift' . pure:

lift :: (Lift a f b, Applicative f) => a -> b 
lift x = lift' (pure x) 

Questo è dove la dipendenza funzionale su Lift diventa molto importante. Poiché f è menzionato solo nel contesto, questa funzione sarebbe mal tipata a meno che non siamo in grado di determinare che cosa è f che conosce solo a e (che appaiono nella parte destra di =>).

ciò richiede diverse estensioni:

{-# LANGUAGE 
    OverlappingInstances 
    , MultiParamTypeClasses 
    , UndecidableInstances 
    , FunctionalDependencies 
    , ScopedTypeVariables 
    , TypeFamilies 
    , FlexibleInstances 
    #-} 

e, come al solito con funzioni variadic Haskell, normalmente l'unico modo per selezionare un'istanza è di dare una firma di tipo esplicito.

lift (\x y z -> x * y + z) readLn readLn readLn :: IO Int 

Il modo in cui ho scritto, GHC sarà lieto di accettare lift che è polimorfa negli argomenti per f (ma non f stesso).

lift (+) [1..5] [3..5] :: (Enum a, Num a) => [a] 

A volte il contesto è sufficiente per inferire il tipo corretto. Si noti che il tipo di argomento è di nuovo polimorfico.

main = lift (\x y z -> x * y + z) readLn readLn readLn >>= print 

---

Come di GHC> = 7,10, OverlappingInstances è stato deprecato e il compilatore emetterà un avvertimento. Probabilmente verrà rimosso in una versione successiva. Questo può essere risolto rimuovendo OverlappingInstances dal {-# LANGUAGE .. #-} pragma e cambiando il 2 ° istanza

instance {-# OVERLAPS #-} (f a ~ b) => Lift a f b where 

Answer 2

Presumo che preferisce utilizzare lift senza annotazioni di tipo. In questo caso ci sono fondamentalmente due opzioni:

primo, se usiamo OverlappingInstances, funzioni polimorfiche bisogno di annotazioni:

{-# LANGUAGE 
    OverlappingInstances, 
    MultiParamTypeClasses, 
    UndecidableInstances, 
    FunctionalDependencies, 
    FlexibleInstances, 
    TypeFamilies 
    #-} 

import Control.Applicative 

class Applicative f => ApN f a b | a b -> f where 
    apN :: f a -> b 

instance (Applicative f, b ~ f a) => ApN f a b where 
    apN = id 

instance (Applicative f, ApN f a' b', b ~ (f a -> b')) => ApN f (a -> a') b where 
    apN f fa = apN (f <*> fa) 

lift :: ApN f a b => a -> b 
lift a = apN (pure a) 

-- Now we can't write "lift (+) (Just 0) Nothing" 
-- We must annotate as follows: 
-- lift ((+) :: Int -> Int -> Int) (Just 0) Nothing 
-- Monomorphic functions work fine though: 
-- lift (||) (Just True) (Just True) --> results in "Just True" 

In secondo luogo, se invece utilizziamo IncoherentInstances, lift funzionerà senza annotazioni nemmeno su funzioni polimorfiche. Tuttavia, alcune cose complicate non verranno ancora verificate, ad esempio (lift . lift) (+) (Just (Just 0)) Nothing.

{-# LANGUAGE 
    IncoherentInstances, MultiParamTypeClasses, 
    UndecidableInstances,ScopedTypeVariables, 
    AllowAmbiguousTypes, FlexibleInstances, TypeFamilies 
    #-} 

import Control.Applicative 

class Applicative f => ApN f a b where 
    apN :: f a -> b 

instance (Applicative f, b ~ f a) => ApN f a b where 
    apN = id 

instance (Applicative f, ApN f a' b', b ~ (f a -> b')) => ApN f (a -> a') b where 
    apN f fa = apN (f <*> fa) 

lift :: forall f a b. ApN f a b => a -> b 
lift a = (apN :: f a -> b) (pure a) 

-- now "lift (+) (Just 0) (Just 10)" works out of the box 

ho presentato due soluzioni invece di quello con IncoherentInstances perché IncoherentInstances è un'estensione piuttosto grezzo che dovrebbe essere evitato se possibile. Probabilmente qui va bene, ma ho pensato che valesse la pena di fornire una soluzione alternativa, comunque.

---

In entrambi i casi io uso lo stesso trucco per aiutare l'inferenza e ridurre le annotazioni: provo a spostare di informazioni dai responsabili di istanza per i vincoli di istanza. Così, invece di

instance (Applicative f) => ApN f a (f a) where 
    apN = id 

scrivo

instance (Applicative f, b ~ f a) => ApN f a b where 
    apN = id 

Inoltre l'altra istanza io uso un parametro pianura b nella testa istanza e aggiungo b ~ (f a ~ b') ai vincoli.

Il motivo è che GHC verifica innanzitutto se esiste una testina di istanza corrispondente e tenta di risolvere i vincoli solo dopo che è avvenuta una corrispondenza corretta. Vogliamo mettere meno peso sulla testata dell'istanza e lasciare che il risolutore dei vincoli risolva le cose (perché è più flessibile, può ritardare i giudizi e può usare i vincoli di altre parti del programma).