Use case for rank-3 (of higher) polymorphism?

Ik heb een paar use-cases gezien voor rang-2-polymorfisme (het meest opvallende voorbeeld is de ST monad ), maar geen voor een hogere rangorde dan dat. Weet iemand van zo'n gebruikscasus?

24

2 antwoord

Ik kan misschien helpen, hoewel zulke beesten onvermijdelijk een beetje betrokken zijn. Hier is een patroon dat ik soms gebruik bij het ontwikkelen van gebottelde syntaxis met binding en de Bruijn-indexering, gebotteld.

mkRenSub ::
  forall v t x y.                      -- variables represented by v, terms by t
    (forall x. v x -> t x) ->            -- how to embed variables into terms
    (forall x. v x -> v (Maybe x)) ->    -- how to shift variables
    (forall i x y.                       -- for thingies, i, how to traverse terms...
      (forall z. v z -> i z) ->              -- how to make a thingy from a variable
      (forall z. i z -> t z) ->              -- how to make a term from a thingy
      (forall z. i z -> i (Maybe z)) ->      -- how to weaken a thingy
      (v x -> i y) ->                    -- ...turning variables into thingies
      t x -> t y) ->                     -- wherever they appear
    ((v x -> v y) -> t x -> t y, (v x -> t y) -> t x -> t y)
                                                 -- acquire renaming and substitution
mkRenSub var weak mangle = (ren, sub) where
  ren = mangle id var weak         -- take thingies to be vars to get renaming
  sub = mangle var id (ren weak)   -- take thingies to be terms to get substitution

Normaal gesproken zou ik typeklassen gebruiken om het ergste van de mera te verbergen, maar als je de woordenboeken uitpakt, is dit wat je zult vinden.

Het punt is dat mangle een rang-2 bewerking is die een notie neemt van ding dat is uitgerust met geschikte operaties die polymorf zijn in de variabele reeksen waarover ze werken: bewerkingen die variabelen toewijzen aan dingetjes worden omgezet in term-transformatoren . Het hele ding laat zien hoe u mangle kunt gebruiken om zowel hernoemen als vervangen te genereren.

Hier is een concreet voorbeeld van dat patroon:

data Id x = Id x

data Tm x
  = Var (Id x)
  | App (Tm x) (Tm x)
  | Lam (Tm (Maybe x))

tmMangle :: forall i x y.
             (forall z. Id z -> i z) ->
             (forall z. i z -> Tm z) ->
             (forall z. i z -> i (Maybe z)) ->
             (Id x -> i y) -> Tm x -> Tm y
tmMangle v t w f (Var i) = t (f i)
tmMangle v t w f (App m n) = App (tmMangle v t w f m) (tmMangle v t w f n)
tmMangle v t w f (Lam m) = Lam (tmMangle v t w g m) where
  g (Id Nothing) = v (Id Nothing)
  g (Id (Just x)) = w (f (Id x))

subst :: (Id x -> Tm y) -> Tm x -> Tm y
subst = snd (mkRenSub Var (\ (Id x) -> Id (Just x)) tmMangle)

We voeren de term traversal slechts eenmaal uit, maar op een zeer algemene manier, dan krijgen we substitutie door het mkRenSub-patroon in te zetten (dat de algemene traversal op twee verschillende manieren gebruikt).

Overweeg voor een ander voorbeeld polymorfe bewerkingen tussen typebeheerders

type (f :-> g) = forall x. f x -> g x

An IMonad (indexed monad) is some m :: (* -> *) -> * -> * equipped with polymorphic operators

ireturn :: forall p. p :-> m p
iextend :: forall p q. (p :-> m q) -> m p :-> m q

dus die operaties zijn rang 2.

Nu is elke bewerking die wordt geparametriseerd door een willekeurige geïndexeerde monade, rang 3. Dus, bijvoorbeeld, het construeren van de gebruikelijke monadische compositie,

compose :: forall m p q r. IMonad m => (q :-> m r) -> (p :-> m q) -> p :-> m r
compose qr pq = iextend qr . pq

vertrouwt op rang 3-kwantificering, zodra u de definitie van IMonad uitpakt.

Moraal van het verhaal: als je eenmaal programmeert in een hogere orde dan polymorfe/geïndexeerde begrippen, worden je woordenboeken van handige kit rang 2 en worden je generieke programma's rang 3. Dit is natuurlijk een escalatie die zich opnieuw kan voordoen.

30
toegevoegd
Welnu, ik ben gewend functies op eenvoudige typen te vervangen door geïndexeerde families van functies op afhankelijke typen, dus waar rang 2 verschijnt in het "normale" leven, verwacht ik rang 3. Maar zal ik de enige zijn die hier antwoord op geeft? vraag..?
toegevoegd de auteur pigworker, de bron
Op de een of andere manier wist ik dat Conor degene zou zijn die deze vraag zou beantwoorden :-)
toegevoegd de auteur luqui, de bron

Misschien wel het beste einde van een samenvatting die ik nog heb gelezen: "Multiplate vereist alleen rangorde 3 polymorfisme naast het normale typeklassemechanisme van Haskell." . (Oh, alleen rang-3 polymorfisme, geen big deal!)

9
toegevoegd
Wow, bovendien voor het mechanisme van de typeklasse!
toegevoegd de auteur Tom Crockett, de bron