Nachbedingung für Kartenfunktionen

Question

Haben die Kartenfunktionen (Seq.map, List.map usw.) eine implizite Nachbedingung, dass die Ausgabe die gleiche Anzahl von Elementen wie die Eingabe hat? Gehen wir weiter, wenn wir eine Art der Tree.map-Funktion hatten, gibt es eine Annahme, dass die "Form" der Eingangs- und Ausgangsbäume gleich ist?

Der Grund, warum ich frage, ist, dass ich immer eine solche Annahme gemacht habe (und ich vermute, dass eine Menge Code, der Sequenzen überlagert auch tut), aber dann entdeckte ich, dass Set.map einen kleineren Satz zurückgeben kann Mapping-Funktion erzeugt Duplikate. Entweder ist meine Annahme ungültig oder Set sollte nicht als Sequenz für Zuordnungszwecke behandelt werden. Welches ist es?

Answer 1

Viele Gesichtspunkte, hier sind mein:

Wir denken alle map Funktionen/Methoden als spezifische Fälle von Haskell fmap von Functors. Aus dieser Definition können wir annehmen, dass die Struktur erhalten bleibt (plus einige andere interessante Eigenschaften).

Aber in .NET gibt es keine Typeclasses so können wir map über ‚eingeschränkt Funktoren‘ definieren, ist die Folge einige Functor Eigenschaften nicht beibehalten werden, aber da generische Code gibt es keine, die die Auswirkungen betroffen sein werden, ist begrenzt.

So nichts hindert uns map über zu definieren:

• Sets (Einschränkung: Die Funktion muss 'a ->' b, wenn 'ein und' b: Vergleich und sollte injective sein)
• Strings (Einschränkung: sollte die Funktion sein Char-> char)
• nullables (Einschränkung: die Funktion sollte 'a ->' b, wobei ‚b ist kein Referenztyp)

Beachten Sie, dass in s In einigen Fällen gibt es Einschränkungen sowohl auf Typ- als auch auf Wertebene, zum Beispiel gilt für die Einschränkung auf Typ-Ebene, dass beide Typen "a" und "b" einen Vergleich haben sollten, während die Funktion über den Funktionswert injective lauten sollte.

Wenn die Sprache in der Lage ist, die Beschränkungen auf Typenebene auszudrücken, gibt der Compiler einen Fehler aus, wenn diese Anforderungen nicht erfüllt werden.

Für Funktionswerte gibt es keine Einschränkungen bei der Kompilierung, obwohl wir Komponententests erstellen können, wenn wir sicherstellen wollen, dass sie korrekt sind. Aber was würde passieren, wenn wir diese Funktionen nicht einschränken wollen?

Nun, solange wir, dass einige Functor Eigenschaften verstehen nicht, dass es eingehalten werden ist nichts falsch in eine Karte über einen eingeschränkten Functor verwenden.

So können wir eine map über Strukturen wie sortierte Listen definieren, natürlich können wir nicht davon ausgehen, dass map a >> map b in diesen Fällen immer gleich map (a >> b) sein wird. Die Einschränkung hier ist, dass die Funktion monotonically increasing sein sollte.

HINWEIS: Haskell ein package mit einer eingeschränkten Funktors ist und eine Instanz für Sets

Answer 2

Ja, normalerweise würden Sie erwarten, dass map formschützend (und damit größenerhaltend) ist. Aber für Sets kann das natürlich nicht gelten, da Sets einige zusätzliche Gesetze befolgen müssen (wie es keine doppelten Elemente gibt). Set.map (f : X -> bool) wird also die Größe des Sets nicht beibehalten, wenn es auf ein Set mit mehr als zwei Elementen angewendet wird. .

Answer 3

Ja, ich würde erwarten, dass eine map-Funktion die Struktur der Eingabe respektiert (obwohl viele Implementierungen wahrscheinlich keinen expliziten Test haben würden).

Im Falle Set.map, könnte man diese gegebene Implementierung (parametrisch) argumentieren map selbst richtig ist, aber das Argument-Funktion hat injective für die Gesamt Abbildungsfunktion sein zu strukturerhalt. Also wirklich, für Sets, ist es eine kombinierte Eigenschaft der 2 Funktionen.

Es wäre leicht, Set.map mit einigen Validierung, die Tests auf Injektivität der Argument-Funktion, wie es angewendet wird.

Answer 4

Sätze sind ein bisschen schwierig, weil Sie nur eine Menge von Dingen erstellen können, für die Sie testen können, ob sie gleich sind. Tatsächlich werden F # -Sets tatsächlich als Bäume dargestellt, daher müssen Sie in der Lage sein, sie zu vergleichen.

Das bedeutet auch, dass die map Funktion für Sätze als map Funktion für Listen nicht das gleiche ist:

List.map : ('a -> 'b) -> 'a list -> 'b list 
Set.map : ('a -> 'b) -> Set<'a> -> Set<'b>) when 'a : comparison and 'b : comparison 

Die Tatsache, dass Sie in der Lage sein müssen, um die 'b Werte vergleichen erklärt, warum die map Funktion auf Sets kann mehr als eine normale map Funktion auf Listen und Sequenzen. Es ist also kein normaler Kartenbetrieb!

(Natürlich gibt es andere Möglichkeiten, dies in F # zu brechen - die map Funktion eine leere Liste zurückkehren kann - aber dann der abgeleitete Typ des Ergebnisses 'c list wäre das würde so auch andere Art von Karte sein).

Answer 5

Der Begriff Map stammt aus der Mathematik und bezieht sich einfach auf eine Funktion. An sich gibt es keine Aussage darüber, wie die Ergebnisse dargestellt werden. Ich würde annehmen, dass die Antwort davon abhängt, auf welcher Art der Inhalt abgebildet wird.

Also entweder meine Annahme ist ungültig, oder Set sollte nicht als eine Sequenz für Zuordnungszwecke behandelt werden. Welches ist es?

Ich würde sagen, dass die Annahme im Allgemeinen nicht gültig ist, aber sollte gelten, wo es vernünftigerweise angewendet werden kann.Wenn beispielsweise eine Struktur eine Struktur benötigt, die von den enthaltenen Werten abhängt, und eine solche Struktur einer anderen Struktur zugeordnet ist, kann es unmöglich sein, ein gültiges Ergebnis zu erstellen, das die Baumstruktur beibehält.

Sie können jedoch einen Satz als eine Sequenz für Zuordnungszwecke behandeln, genau wie alles, das in IEnumerable<> konvertiert werden kann. Verwenden Sie einfach Seq.map anstelle von Set.map.