Post-condizione per funzioni mappa

Question

Le funzioni di mappa (Seq.map, List.map ecc.) Hanno una post-condizione implicita che l'output ha lo stesso numero di elementi dell'input? Andando oltre, se avessimo un qualche tipo di funzione Tree.map, c'è il presupposto che la "forma" degli alberi di input e output sia la stessa?

La ragione per cui mi chiedo è che ho sempre fatto una tale ipotesi (e ho il sospetto che un sacco di codice che mappa su sequenze non troppo), ma poi ho scoperto che Set.map può restituire un insieme ridotto se il la funzione di mappatura produce duplicati. Quindi la mia ipotesi non è valida, o Set non deve essere trattato come una sequenza per scopi di mappatura. Cos'è questo?

Answer 1

molti punti di vista, ecco la mia:

Possiamo pensare a tutti map funzioni/metodi come casi specifici di Haskell di fmap di Functors. Da quella definizione possiamo supporre che la struttura sarà preservata (più alcune altre proprietà interessanti).

Ma in .NET non ci sono Typeclasses così possiamo definire map over 'Funtori ristrette', la conseguenza è alcune Functor proprietà non saranno conservati, ma dal momento che non esiste un codice generico che saranno interessate l'impatto è limitato.

Quindi nulla ci impedisce di definire map sopra:

• Sets (limitazione: la funzione deve essere 'a ->' b quando 'una e' b: Confronto e dovrebbe essere injective)
• Strings (limitazione: la funzione dovrebbe essere caratte-> char)
• nullables (limitazione: la funzione dovrebbe essere 'a ->' b dove 'b non è un tipo di riferimento)

si noti che in s Alcuni casi ci sono restrizioni sia a livello di tipo che a livello di valore, ad esempio per impostare la restrizione a livello di tipo è entrambi i tipi 'a e' b devono avere confronto mentre la restrizione sul valore della funzione è che la funzione deve essere injective.

Se la lingua è in grado di esprimere i vincoli di livello del tipo, il compilatore genera un errore quando questi requisiti non sono soddisfatti.

Per i valori delle funzioni non ci sono restrizioni in fase di compilazione, anche se possiamo creare test di unità se vogliamo assicurarci che siano corretti. Ma cosa succederebbe se non ci preoccupassimo di limitare queste funzioni?

Bene, a condizione che comprendiamo che alcune proprietà di Functor non verranno rispettate, non c'è niente di sbagliato nell'usare una mappa su un numero limitato Functor.

Così possiamo definire un map su strutture come liste ordinate, naturalmente, non si può supporre che map a >> map b sarà sempre equivalente a map (a >> b) in questi casi. La restrizione qui è che la funzione dovrebbe essere monotonically increasing.

NOTA: per Haskell c'è una package con un funtore limitato e un'istanza per i set di

Answer 2

Sì, generalmente ti aspetteresti che lo map sia preservativo della forma (e quindi di conservazione delle dimensioni). Ma per gli insiemi, questo ovviamente non può essere considerato generale in quanto gli insiemi devono obbedire ad alcune leggi aggiuntive (come non ci sono elementi duplicati - quindi Set.map (f : X -> bool) chiaramente non conserverà la dimensione del set se è applicato a un set con più di due elementi in esso) .

Answer 3

Sì, mi aspetto una funzione map per rispettare la struttura dell'input (anche se molte implementazioni probabilmente non avrebbero un test esplicito).

Nel caso di Set.map, si potrebbe sostenere che dato attuazione (parametrica) map sé è corretto, ma l'argomento della funzione deve essere injective per la generale funzione di mappatura essere struttura-conservazione. In effetti, per gli insiemi, è una proprietà combinata delle 2 funzioni.

Sarebbe facile avvolgere Set.map con una convalida che verifica l'injectivity della funzione argomento come viene applicata.

Answer 4

I set sono un po 'complicati, perché è possibile creare solo un set di cose per cui è possibile verificare se sono uguali. In effetti, i set F # sono effettivamente rappresentati come alberi, quindi è necessario essere in grado di confrontarli.

Questo significa anche che la funzione map per i set non è la stessa della funzione di map per gli elenchi:

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

Il fatto che si deve essere in grado di confrontare i valori 'b spiega perché il map la funzione sui set può fare più di una normale funzione map su liste e sequenze. Quindi, non è una normale operazione mappa!

(Naturalmente, ci sono altri modi possibili per rompere questo in F # - la funzione map potrebbe restituisce un elenco vuoto - ma poi il tipo derivato del risultato sarebbe 'c list modo che sarebbe anche diversi tipi di carta).

Answer 5

Il termine mappa deriva dalla matematica e si riferisce semplicemente a una funzione. Di per sé, non fa una dichiarazione su come i risultati sono rappresentati. Suppongo che la risposta dipenda dal tipo di mappatura dei contenuti.

Quindi, la mia ipotesi non è valida oppure Set non deve essere considerato come una sequenza per scopi di mapping. Cos'è questo?

Direi che l'ipotesi non è valida in generale, ma dovrebbe valere dove può essere ragionevolmente applicata.Ad esempio, se un albero richiede una struttura che dipende dai valori contenuti e uno di questi alberi viene mappato su un altro, può essere impossibile creare un risultato valido che mantenga la struttura dell'albero.

Tuttavia, è possibile trattare un set come sequenza per scopi di mapping, proprio come qualsiasi cosa convertibile in IEnumerable<>. È sufficiente utilizzare Seq.map anziché Set.map.