Czy istnieje taki "uniwersalny" typ Haskella?

Question

szukam typu Haskell z następującej własności (z użyciem egzotycznych rozszerzeń GHC jest w porządku ze mną ...): Dla wszystkich przesuwny t następujące dwa typy są izomorficzne:

forall a. C a => t a -> a 

i

t A -> A. 

W moim konkretnym przypadku, C jest następujące klasy:

class Floating a => C a where 
    fromDouble :: Double -> a 

Innymi słowy, jakoś chciałby pociągnąć kwantyfikator ogólny nad wszystkimi rodzajami o w klasie C w rodzaju , tak że funkcja t A -> A daje mi funkcję dla wszystkich a. Więc myślę, że szukam „uniwersalnego” instancji klasy C w pewnym sensie ...

Rozważałam wszystkie rodzaje fantazyjnych definicji , wzdłuż linii

newtype A = A (forall b. C b => b) 

lub

data A = forall b. C b => A b 

lub

newtype A = A (forall t b. (Traversable t, C b) => t b -> b), 

lub

data A = FromDouble Double | Plus A A | Tanh A | ... 

lub nawet

data A = A (forall t. Traversable t => t A -> A), 

i wszystkie mogą być łatwo wykonane instancje klasy C, ale nie mają one właściwość muszę (a przynajmniej ja nie widzę w jaki sposób uzyskać tę właściwość z którejkolwiek z moich powyższych definicji).

W dni nieparzyste Jestem przekonany, typ A po prostu nie istnieje, w dni parzyste Jestem przekonany, że z przeciwnej ...

... więc każda pomoc będzie bardzo mile widziane!

---

aby dać pewną motywację do mojego pytania: Ja mocno przechylony na Edward Kmett's ad library dla mojego neural networks library, aw mojej pierwszej próbie, używałem swego rodzaju Numeric.AD.Rank1.Kahn automatycznego różnicowania i wstecznej propagacji błędów. Doprowadziło to do miłego API, ale było mniej wydajne niż jego odwrotny tryb, który niestety używa kwantyfikacji jak w moim pytaniu do kodowania różnych funkcji.

Miałem nadzieję, że mogę mieć to, co najlepsze z obu światów - jeden specyficzny (abstrakcyjny) typ plus efektywność odwrotnego trybu.

Answer 1

Załóżmy, że istnieje taki "uniwersalny" typ A.

Const() jest przesuwny, stąd otrzymujemy izomorfizm między

forall a. C a => Const() a -> a 
-- and 
Const() A -> A 

czyli między (od Const() a jest izomorficzna () i () -> b jest izomorficzna b)

forall a. C a => a 
-- and 
A 

Tak więc, jeśli dowolny A istnieje, musi być izomorficzna z forall a. C a => a.

Pamiętaj, że była to Twoja pierwsza próba rozwiązania - jeśli to nie spełnia wymagań, nic nie będzie.

---

Teraz w konkretnym przypadku

forall a. C a => a 

grubsza oznacza, poprzez definicję C (*) [Uwaga: Oto jestem niesłusznie "zapominając" o Floating a superklasę, Magin cały argument, dużo więcej kruchy]

forall a. (Double -> a) -> a 

która jest izomorficzna Double:

iso :: Double -> forall a. (Double -> a) -> a 
iso x f = f x 
osi :: (forall a. (Double -> a) -> a) -> Double 
osi f = f id 

Udowodnienie, że powyższe jest naprawdę izomorfizmem, nie jest trywialne - myślę, że wymaga ono jakiejś parametryczności, jak w "Recursive types for free!". (Konsekwencja Yonedy? ... Komentarze mile widziane!)

Tak więc, jeśli istnieje rozwiązanie, dla twojego C, musi to być A ~ Double, aż do izomorfizmu.

(*) Rozciągam tu trochę rzeczy. Nie wiem, jak precyzyjnie obliczyć ograniczoną kwantyfikację Haskella, więc uciekam się do wyraźnego wyrażenia słownika, nawet jeśli, jak sądzę, to nie jest dokładnie to samo.