Czy jest możliwe kodowanie ogólnej funkcji "podnoszenia" w Haskell?

Question

Nie jestem największym fanem varargs, ale zawsze uważałem, że zarówno style aplikacyjne (f <$> x <*> y), jak i idiom ([i| f x y |]) mają zbyt wiele symboli. Zwykle wolę chodzić na drogę liftA2 f x y, ale ja też uważam, że A2 jest trochę brzydka. Od this question dowiedziałem się, że możliwe jest zaimplementowanie funkcji vararg w Haskell. W ten sposób, możliwe jest użycie tej samej zasady w celu wdrożenia funkcji podnoszenia, tak że:

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

Próbowałem zastępując + przez <*> na kodzie cyt:

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) 

Ale I nie udało się dostać rodzaje rację ...

Answer 1

Uwaga, można łańcuch dowolną liczbę <*>, aby uzyskać funkcję postaci

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

Jeśli mamy typ a0 -> .. -> an i f a0 -> .. -> f an, możemy obliczyć z tego f. Możemy zakodować tę relację, a najbardziej ogólny typ, co następuje

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

Jak można się spodziewać, „rekurencyjne przypadek” wystąpienie po prostu zastosować <*> raz, potem 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 

Podstawa przypadek jest wtedy, gdy nie ma więcej funkcji. Ponieważ nie można rzeczywiście stwierdzić „a nie jest typem funkcji”, to opiera się na nakładających przypadkach:

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

powodu zasad selekcji instancja GHCs, rekurencyjne sprawa zawsze będzie wybrany, jeśli to możliwe.

Następnie funkcja chcesz to lift' . pure:

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

To gdzie zależność funkcjonalna na Lift staje się bardzo ważne. Ponieważ f jest wymienione tylko w kontekście, funkcja ta byłaby źle wpisana, chyba że możemy ustalić, co f zna tylko a i b (które pojawiają się po prawej stronie =>).

wymaga kilka rozszerzeń:

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

i, jak zwykle o zmiennej liczbie argumentów funkcji w Haskell, zazwyczaj jedynym sposobem, aby wybrać instancję jest dać wyraźny podpis typu.

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

Sposób Pisałem go, GHC chętnie akceptują lift który jest polimorficzny w argumentach do f (ale sama w sobie nie f).

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

Czasami kontekst jest wystarczający do określenia właściwego typu. Zwróć uwagę, że typ argumentu jest ponownie polimorficzny.

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

---

Od GHC> = 7,10, OverlappingInstances została zaniechana i kompilator wyśle ​​ostrzeżenie. Prawdopodobnie zostanie usunięty w późniejszej wersji. Można to naprawić poprzez usunięcie OverlappingInstances od {-# LANGUAGE .. #-} Pragma i zmieniając 2. wystąpienie do

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

Answer 2

Zakładam wolisz używać lift bez typu adnotacji. W tym przypadku nie są w zasadzie dwie opcje:

Pierwszy, jeśli używamy OverlappingInstances, funkcje polimorficzne potrzebują adnotacji:

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

drugie, gdybyśmy zamiast używać IncoherentInstances, lift będzie działać bez adnotacji nawet o funkcjach polimorficznych. Jednak niektóre skomplikowane rzeczy nadal nie zostaną sprawdzone, na przykład (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 

przedstawiłem dwa rozwiązania, a nie tylko jednego z IncoherentInstances ponieważ IncoherentInstances jest raczej surowy rozszerzenie, które należy unikać, jeśli to możliwe. To chyba dobrze, ale pomyślałem, że warto dostarczyć alternatywne rozwiązanie.

---

W obu przypadkach używam tej samej sztuczki, aby pomóc zmniejszyć wnioskowania i adnotacje: Staram się przenieść informacje z głowami Instancji ograniczeń instancji. Więc zamiast

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

piszę

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

Również w drugiej instancji używam zwykłego b parametr w głowie instancji i dodać b ~ (f a ~ b') ograniczeniom.

Powodem tego jest to, że GHC najpierw sprawdza, czy istnieje odpowiednia głowa instancji, i próbuje rozwiązać ograniczenia dopiero po pomyślnym dopasowaniu. Chcemy umieścić najmniejszy ciężar na głowie instancji i pozwolić rozwiązaniu ograniczeń na sortowanie (ponieważ jest bardziej elastyczny, może opóźnić podejmowanie decyzji i może wykorzystywać ograniczenia z innych części programu).