Warum ist "map insertionsort" nicht gleich "map mergesort"?

In der Typentheorie Podcast ep. 3 , Dan Licata behauptet, dass die Tatsache, dass Insertionsort und Mergesort für jede Eingabe das gleiche Ergebnis liefern, nicht bedeutet, dass das Ergebnis gleich wäre, wenn es als Funktionen höherer Ordnung als Argumente für eine dritte Funktion verwendet würde, dh map insertionsortnicht gleich sein muss map mergesort.

Er erklärt dies mit "weil Sie nicht wissen, dass Insertionsort und Mergesort gleich sind, da Funktionen gleich sind", aber ich verstehe es immer noch nicht.

Warum ist das so? Ein Gegenbeispiel wäre toll!

Es hat mit dem Axiom der Extensionalität zu tun , dh ob Sie es für Funktionen akzeptieren oder nicht.

$$\forall f,g:A \to B,\ ((\forall x:A ,\ f\ x = g\ x) \Leftrightarrow f = g).$$

$\text{map}\ f = \text{map}\ g$

$$(\forall x:A,\ f\ x = g\ x) \implies \forall xs:\text{list}\ A,\ \text{map}\ f\ xs = \text{map}\ g\ xs.$$ $\text{map}\ f = \text{map}\ g$