Wann sind höherwertige Typen nützlich?

Ich mache seit einer Weile Entwickler in F # und es gefällt mir. Ein Schlagwort, von dem ich weiß, dass es in F # nicht existiert, sind höherwertige Typen. Ich habe Material über höherwertige Typen gelesen und glaube, ich verstehe deren Definition. Ich bin mir nur nicht sicher, warum sie nützlich sind. Kann jemand einige Beispiele dafür nennen, was höherwertige Typen in Scala oder Haskell einfach machen, die Problemumgehungen in F # erfordern? Was wären die Problemumgehungen auch für diese Beispiele ohne höherwertige Typen (oder umgekehrt in F #)? Vielleicht bin ich es einfach so gewohnt, es zu umgehen, dass ich das Fehlen dieser Funktion nicht bemerke.

(Ich denke) Ich verstehe, dass Sie anstelle von myList |> List.map foder myList |> Seq.map f |> Seq.toListhöherwertigen Typen einfach schreiben können myList |> map fund es wird a zurückgegeben List. Das ist großartig (vorausgesetzt es ist richtig), scheint aber irgendwie kleinlich zu sein? (Und könnte es nicht einfach durch Zulassen einer Funktionsüberladung geschehen?) Normalerweise konvertiere ich Seqtrotzdem und kann danach in alles konvertieren, was ich will. Vielleicht bin ich es einfach zu gewohnt, daran zu arbeiten. Aber gibt es ein Beispiel, bei dem höherwertige Typen Sie entweder bei Tastenanschlägen oder bei der Typensicherheit wirklich retten?

Die Art eines Typs ist also sein einfacher Typ. Zum Beispiel Inthat kind, *was bedeutet, dass es ein Basistyp ist und durch Werte instanziiert werden kann. Nach einer losen Definition eines höherwertigen Typs (und ich bin nicht sicher, wo F # die Linie zeichnet, also lassen Sie es uns einfach einschließen) sind polymorphe Container ein großartiges Beispiel für einen höherwertigen Typ.

data List a = Cons a (List a) | Nil

Der Typkonstruktor Listhat eine Art, * -> *was bedeutet, dass ihm ein konkreter Typ übergeben werden muss, um einen konkreten Typ zu erhalten: List Intkann Einwohner haben wie [1,2,3], Listkann sich aber nicht.

Ich gehe davon aus, dass die Vorteile von polymorphen Behältern offensichtlich sind, aber es gibt nützlichere * -> *Arten als nur die Behälter. Zum Beispiel die Beziehungen

data Rel a = Rel (a -> a -> Bool)

oder Parser

data Parser a = Parser (String -> [(a, String)])

beide haben auch nett * -> *.

Wir können dies in Haskell jedoch weiterführen, indem wir Typen mit noch höherwertigen Arten haben. Zum Beispiel könnten wir einen Typ mit Art suchen (* -> *) -> *. Ein einfaches Beispiel hierfür könnte sein, Shapedass versucht wird, einen Container der Art zu füllen * -> *.

data Shape f = Shape (f ())

[(), (), ()] :: Shape List

Dies ist beispielsweise zur Charakterisierung von Traversables in Haskell nützlich , da sie immer in Form und Inhalt unterteilt werden können.

split :: Traversable t => t a -> (Shape t, [a])

Als weiteres Beispiel betrachten wir einen Baum, der nach der Art des Zweigs parametrisiert ist. Zum Beispiel könnte ein normaler Baum sein

data Tree a = Branch (Tree a) a (Tree a) | Leaf

Aber wir können sehen, dass der Verzweigungstyp ein Pairvon Tree as enthält, und so können wir dieses Stück parametrisch aus dem Typ extrahieren

data TreeG f a = Branch a (f (TreeG f a)) | Leaf

data Pair a = Pair a a
type Tree a = TreeG Pair a

Dieser TreeGTypkonstruktor hat kind (* -> *) -> * -> *. Wir können es verwenden, um interessante andere Variationen wie a zu machenRoseTree

type RoseTree a = TreeG [] a

rose :: RoseTree Int
rose = Branch 3 [Branch 2 [Leaf, Leaf], Leaf, Branch 4 [Branch 4 []]]

Oder pathologische wie a MaybeTree

data Empty a = Empty
type MaybeTree a = TreeG Empty a

nothing :: MaybeTree a
nothing = Leaf

just :: a -> MaybeTree a
just a = Branch a Empty

Oder ein TreeTree

type TreeTree a = TreeG Tree a

treetree :: TreeTree Int
treetree = Branch 3 (Branch Leaf (Pair Leaf Leaf))

Ein weiterer Ort, an dem dies auftaucht, sind "Algebren von Funktoren". Wenn wir ein paar Schichten der Abstraktheit fallen lassen, könnte dies besser als eine Falte betrachtet werden, wie z sum :: [Int] -> Int. Algebren werden über den Funktor und den Träger parametrisiert . Der Funktor hat Art * -> *und der Träger Art *insgesamt

data Alg f a = Alg (f a -> a)

hat Art (* -> *) -> * -> *. Algnützlich wegen seiner Beziehung zu Datentypen und darauf aufgebauten Rekursionsschemata.

-- | The "single-layer of an expression" functor has kind `(* -> *)`
data ExpF x = Lit Int
            | Add x x
            | Sub x x
            | Mult x x

-- | The fixed point of a functor has kind `(* -> *) -> *`
data Fix f = Fix (f (Fix f))

type Exp = Fix ExpF

exp :: Exp
exp = Fix (Add (Fix (Lit 3)) (Fix (Lit 4))) -- 3 + 4

fold :: Functor f => Alg f a -> Fix f -> a
fold (Alg phi) (Fix f) = phi (fmap (fold (Alg phi)) f)

Obwohl sie theoretisch möglich sind, habe ich noch nie einen Konstruktor mit noch höherwertigem Typ gesehen. Wir sehen manchmal Funktionen dieses Typs wie mask :: ((forall a. IO a -> IO a) -> IO b) -> IO b, aber ich denke, Sie müssen sich mit Typ-Prolog oder abhängig typisierter Literatur befassen, um diesen Grad an Komplexität in Typen zu erkennen.

Betrachten Sie die FunctorTypklasse in Haskell, in der fsich eine höherwertige Typvariable befindet:

class Functor f where
    fmap :: (a -> b) -> f a -> f b

Was diese Art Unterschrift sagt , ist , dass fmap den Typ - Parameter eines ändert sich fvon azu b, aber Blätter fwie es war. Wenn Sie also fmapüber eine Liste verwenden, erhalten Sie eine Liste, wenn Sie sie über einen Parser verwenden, erhalten Sie einen Parser und so weiter. Und dies sind statische Garantien zur Kompilierungszeit.

Ich kenne F # nicht, aber lassen Sie uns überlegen, was passiert, wenn wir versuchen, die FunctorAbstraktion in einer Sprache wie Java oder C # auszudrücken , mit Vererbung und Generika, aber ohne höherwertige Generika. Erster Versuch:

interface Functor<A> {
    Functor<B> map(Function<A, B> f);
}

Das Problem bei diesem ersten Versuch ist, dass eine Implementierung der Schnittstelle jede implementierte Klasse zurückgeben darf Functor. Jemand könnte eine schreiben, FunnyList<A> implements Functor<A>deren mapMethode eine andere Art von Sammlung zurückgibt, oder sogar etwas anderes, das überhaupt keine Sammlung ist, aber immer noch eine Functor. Wenn Sie die mapMethode verwenden, können Sie für das Ergebnis keine subtypspezifischen Methoden aufrufen, es sei denn, Sie übertragen sie auf den Typ, den Sie tatsächlich erwarten. Wir haben also zwei Probleme:

1. Das Typsystem erlaubt es uns nicht, die Invariante auszudrücken, dass die mapMethode immer dieselbe FunctorUnterklasse wie der Empfänger zurückgibt .
2. Daher gibt es keine statisch typsichere Möglichkeit, eine Nichtmethode Functorfür das Ergebnis von aufzurufen map.

Es gibt andere, kompliziertere Möglichkeiten, die Sie ausprobieren können, aber keine davon funktioniert wirklich. Sie können beispielsweise versuchen, den ersten Versuch zu erweitern, indem Sie Untertypen definieren Functor, die den Ergebnistyp einschränken:

interface Collection<A> extends Functor<A> {
    Collection<B> map(Function<A, B> f);
}

interface List<A> extends Collection<A> {
    List<B> map(Function<A, B> f);
}

interface Set<A> extends Collection<A> {
    Set<B> map(Function<A, B> f);
}

interface Parser<A> extends Functor<A> {
    Parser<B> map(Function<A, B> f);
}

// …

Dies hilft zu verhindern, dass Implementierer dieser schmaleren Schnittstellen den falschen Typ Functorvon der mapMethode zurückgeben. Da es jedoch keine Begrenzung für die Anzahl der FunctorImplementierungen gibt, die Sie haben können, gibt es keine Begrenzung für die Anzahl der engeren Schnittstellen, die Sie benötigen.

( BEARBEITEN: Und beachten Sie, dass dies nur funktioniert, weil es Functor<B>als Ergebnistyp angezeigt wird und die untergeordneten Schnittstellen es eingrenzen können. AFAIK Wir können also nicht beide Verwendungen Monad<B>in der folgenden Schnittstelle eingrenzen:

interface Monad<A> {
    <B> Monad<B> flatMap(Function<? super A, ? extends Monad<? extends B>> f);
}

In Haskell mit höherrangigen Variablen ist dies (>>=) :: Monad m => m a -> (a -> m b) -> m b.)

Ein weiterer Versuch besteht darin, rekursive Generika zu verwenden, um zu versuchen, dass die Schnittstelle den Ergebnistyp des Subtyps auf den Subtyp selbst beschränkt. Spielzeugbeispiel:

/**
 * A semigroup is a type with a binary associative operation.  Law:
 *
 * > x.append(y).append(z) = x.append(y.append(z))
 */
interface Semigroup<T extends Semigroup<T>> {
    T append(T arg);
}

class Foo implements Semigroup<Foo> {
    // Since this implements Semigroup<Foo>, now this method must accept 
    // a Foo argument and return a Foo result. 
    Foo append(Foo arg);
}

class Bar implements Semigroup<Bar> {
    // Any of these is a compilation error:

    Semigroup<Bar> append(Semigroup<Bar> arg);

    Semigroup<Foo> append(Bar arg);

    Semigroup append(Bar arg);

    Foo append(Bar arg);

}

Aber diese Art von Technik (die für Ihren normalen OOP-Entwickler ziemlich geheimnisvoll ist, zum Teufel auch für Ihren normalen funktionalen Entwickler) kann die gewünschte FunctorEinschränkung auch noch nicht ausdrücken :

interface Functor<FA extends Functor<FA, A>, A> {
    <FB extends Functor<FB, B>, B> FB map(Function<A, B> f);
}

Das Problem hierbei ist, dass dies nicht darauf beschränkt ist FB, dasselbe zu haben Fwie FA- so dass List<A> implements Functor<List<A>, A>die mapMethode beim Deklarieren eines Typs immer noch a zurückgeben kann NotAList<B> implements Functor<NotAList<B>, B>.

Letzter Versuch in Java unter Verwendung von Rohtypen (nicht parametrisierte Container):

interface FunctorStrategy<F> {
    F map(Function f, F arg);
} 

Hier Fwerden nicht parametrisierte Typen wie just Listoder instanziiert Map. Dies garantiert, dass a FunctorStrategy<List>nur a zurückgeben kann List- Sie haben jedoch die Verwendung von Typvariablen zum Verfolgen der Elementtypen der Listen aufgegeben.

Das Herzstück des Problems ist, dass Sprachen wie Java und C # nicht zulassen, dass Typparameter Parameter haben. Wenn Tes sich in Java um eine Typvariable handelt, können Sie schreiben Tund List<T>, aber nicht T<String>. Höher sortierte Typen heben diese Einschränkung auf, so dass Sie so etwas haben können (nicht vollständig durchdacht):

interface Functor<F, A> {
    <B> F<B> map(Function<A, B> f);
}

class List<A> implements Functor<List, A> {

    // Since F := List, F<B> := List<B>
    <B> List<B> map(Function<A, B> f) {
        // ...
    }

}

Und insbesondere dieses Bit ansprechen:

(Ich denke) Ich verstehe, dass Sie anstelle von myList |> List.map foder myList |> Seq.map f |> Seq.toListhöherwertigen Typen einfach schreiben können myList |> map fund es wird a zurückgegeben List. Das ist großartig (vorausgesetzt es ist richtig), scheint aber irgendwie kleinlich zu sein? (Und könnte es nicht einfach durch Zulassen einer Funktionsüberladung geschehen?) Normalerweise konvertiere ich Seqtrotzdem und kann danach in alles konvertieren, was ich will.

Es gibt viele Sprachen, die die Idee der mapFunktion auf diese Weise verallgemeinern , indem sie sie so modellieren, als ob es bei der Zuordnung im Kern um Sequenzen geht. Ihre Bemerkung ist in diesem Sinne: Wenn Sie einen Typ haben, der die Konvertierung von und nach unterstützt Seq, erhalten Sie die Kartenoperation "kostenlos", indem Sie sie wiederverwenden Seq.map.

In Haskell ist die FunctorKlasse jedoch allgemeiner; es ist nicht an den Begriff der Sequenzen gebunden. Sie können fmapTypen implementieren , die keine gute Zuordnung zu Sequenzen aufweisen, z. B. IOAktionen, Parser-Kombinatoren, Funktionen usw.:

instance Functor IO where
    fmap f action =
        do x <- action
           return (f x)

 -- This declaration is just to make things easier to read for non-Haskellers 
newtype Function a b = Function (a -> b)

instance Functor (Function a) where
    fmap f (Function g) = Function (f . g)  -- `.` is function composition

Das Konzept des "Mappings" ist wirklich nicht an Sequenzen gebunden. Es ist am besten, die Funktorgesetze zu verstehen:

(1) fmap id xs == xs
(2) fmap f (fmap g xs) = fmap (f . g) xs

Sehr informell:

1. Das erste Gesetz besagt, dass Mapping mit einer Identity / Noop-Funktion dasselbe ist wie nichts zu tun.
2. Das zweite Gesetz besagt, dass jedes Ergebnis, das Sie durch zweimaliges Mapping erzielen können, auch durch einmaliges Mapping erzielt werden kann.

Aus diesem Grund möchten Sie fmapden Typ beibehalten. Sobald Sie mapOperationen erhalten, die einen anderen Ergebnistyp erzeugen, wird es sehr viel schwieriger, solche Garantien zu geben.

Ich möchte hier in einigen ausgezeichneten Antworten keine Informationen wiederholen, aber es gibt einen wichtigen Punkt, den ich hinzufügen möchte.

Normalerweise benötigen Sie keine höherwertigen Typen, um eine bestimmte Monade oder einen bestimmten Funktor (oder einen anwendbaren Funktor oder Pfeil oder ...) zu implementieren. Dabei fehlt jedoch meistens der Punkt.

Im Allgemeinen habe ich festgestellt, dass Menschen, die die Nützlichkeit von Funktoren / Monaden / Was auch immer nicht erkennen, oft daran denken, dass sie nacheinander an diese Dinge denken . Functor / monad / etc-Operationen fügen einer Instanz wirklich nichts hinzu (anstatt bind, fmap usw. aufzurufen, könnte ich einfach alle Operationen aufrufen, die ich zum Implementieren von bind, fmap usw. verwendet habe). Was Sie wirklich für diese Abstraktionen wollen, ist, dass Sie Code haben können, der generisch mit jedem Funktor / Monade / etc. Funktioniert.

In einem Kontext, in dem ein derartiger generischer Code weit verbreitet ist, bedeutet dies, dass Ihr Typ jedes Mal, wenn Sie eine neue Monadeninstanz schreiben, sofort Zugriff auf eine große Anzahl nützlicher Operationen erhält , die bereits für Sie geschrieben wurden . Das ist der Punkt , der Monaden zu sehen (und functors, und ...) überall; nicht so , dass ich verwenden kann , bindanstatt concatund mapzu implementieren myFunkyListOperation(was mir nichts an mir gewinne), sondern vielmehr so , dass , wenn ich nach Bedarf kommen myFunkyParserOperationund myFunkyIOOperationich kann ich den Code wiederverwenden ursprünglich Sägen in Bezug auf den Listen , weil es tatsächlich Monade-generic ist .

Um jedoch über einen parametrisierten Typ wie eine Monade mit Typensicherheit hinweg zu abstrahieren , benötigen Sie höherwertige Typen (wie auch in anderen Antworten hier erläutert).

Für eine spezifischere .NET-spezifische Perspektive habe ich vor einiger Zeit einen Blog-Beitrag darüber geschrieben. Der springende Punkt dabei ist, dass Sie bei höherwertigen Typen möglicherweise dieselben LINQ-Blöcke zwischen IEnumerablesund IObservableswiederverwenden können. Ohne höherwertige Typen ist dies jedoch nicht möglich.

Das Beste, was Sie bekommen können (ich habe es nach dem Posten des Blogs herausgefunden), ist, Ihr eigenes zu erstellen IEnumerable<T>und IObservable<T>beide von einem zu erweitern IMonad<T>. Dies würde es Ihnen ermöglichen, Ihre LINQ-Blöcke wiederzuverwenden, wenn sie gekennzeichnet sind IMonad<T>, aber dann ist es nicht mehr typsicher, da Sie damit mischen und anpassen können IObservablesund sich IEnumerablesinnerhalb desselben Blocks befinden, was zwar faszinierend klingt, um dies zu ermöglichen, Sie dies jedoch tun würden im Grunde nur ein undefiniertes Verhalten bekommen.

Ich schrieb einen späteren Beitrag darüber, wie Haskell dies einfach macht. (Ein No-Op, wirklich - das Beschränken eines Blocks auf eine bestimmte Art von Monade erfordert Code; das Aktivieren der Wiederverwendung ist die Standardeinstellung).

Das am häufigsten verwendete Beispiel für höherwertigen Polymorphismus in Haskell ist die MonadSchnittstelle.Functorund Applicativesind auf die gleiche Weise höher gesinnt, also werde ich zeigen Functor, um etwas Prägnantes zu zeigen.

class Functor f where
    fmap :: (a -> b) -> f a -> f b

Untersuchen Sie nun diese Definition und sehen Sie sich an, wie die Typvariable fverwendet wird. Sie werden sehen, dass fdies keinen Wert bedeuten kann. Sie können Werte in dieser Typensignatur identifizieren, da sie Argumente und Ergebnisse einer Funktion sind. Also die Typvariablen aundb sind also Typen, die Werte haben können. So sind die Typausdrücke f aund f b. Aber nicht fselbst. fist ein Beispiel für eine höherwertige Typvariable. Angesichts dessen* ist die Art von Typen, die Werte haben können, fmuss die Art haben * -> *. Das heißt, es braucht einen Typ, der Werte haben kann, weil wir aus früheren Untersuchungen wissen, dass aund bWerte haben müssen. Und das wissen wir auch f aundf b muss Werte haben, daher wird ein Typ zurückgegeben, der Werte haben muss.

Das macht die f in der Definition Functorverwendete Variable eines höherwertigen Typs.

Das Applicative und MonadSchnittstellen fügen mehr hinzu, aber sie sind kompatibel. Dies bedeutet, dass sie auch Typvariablen mit Art bearbeiten * -> *.

Die Arbeit an höherwertigen Typen führt zu einer zusätzlichen Abstraktionsebene - Sie müssen nicht nur Abstraktionen über Basistypen erstellen. Sie können auch Abstraktionen über Typen erstellen, die andere Typen ändern.