Le funzioni di ordine superiore possono mai essere pure?

5

Stavo pensando a funzioni pure, specialmente nel contesto del C ++, che naturalmente non è un linguaggio puramente funzionale, e mi chiedevo se le funzioni di ordine superiore in C ++ possano mai essere considerate pure? Prendiamo ad esempio std::find_if : sarebbe molto puro, tranne che prende un'altra funzione, che potrebbe non essere pura. Non sembra esserci alcun vincolo sul predicato che std::find_if prende che impedisce di fare cose brutte e impure all'interno della funzione, come questo:

const std::vector<int> v = { 1,2,3,4,5 };
auto result = std::find_if(v.begin(), v.end(), [](int arg)
{
   return arg < someGlobalVariable;
} );

Quindi forse qualcuno con più esperienza nei linguaggi di programmazione funzionale potrebbe chiarire questo per me: la nozione di "pure funzioni" ha senso quando si ha a che fare con funzioni di ordine superiore?

EDIT: avrei dovuto dire più chiaramente che non sto cercando una spiegazione della correttezza const in C ++. Volevo solo sapere se la definizione di una funzione pura ha senso quando si parla di funzioni di ordine superiore in C ++. Ho cambiato l'esempio per illustrare che const non sta risolvendo il mio problema qui!

    
posta Mortano 14.08.2015 - 12:03
fonte

2 risposte

3

Hai ragione, questo è un problema quando si vuole ragionare sulla purezza delle funzioni in un linguaggio che consente le funzioni impure. Tecnicamente quasi tutti i linguaggi consentono l'impurità, ma quelli puramente funzionali di solito indicano esplicitamente quelli impuri nel sistema dei tipi, così che la funzione Haskell map :: (a -> b) -> [a] -> [b] , implicitamente, richiede che la funzione da mappare sia pura.

Informalmente, possiamo certamente dire: find_if è puro solo se la funzione predicato è pura. Quindi, come possiamo insegnare il compilatore su questo?

Poiché C ++ non contrassegna le funzioni impure (né quelle pure, se è per questo, ma facciamo finta che stiamo aggiungendo quella funzione), e probabilmente non vogliamo limitare find_if ad accettare solo funzioni pure (poiché ciò sarebbe essere indietro incompatibile), restiamo con quello che chiamerò polimorfismo di purezza . Cioè, find_if è puro se la funzione passata è pura. Non sono a conoscenza di un linguaggio che fa questo, ma in linea di principio non è diverso dal polimorfismo rispetto ai tipi (a.k.a. generici). Sistemi di effetti sufficientemente sofisticati probabilmente hanno capacità equivalenti, solo generalizzati a giudizi sempre più sottili di "puro" e "impuro".

    
risposta data 14.08.2015 - 14:18
fonte
1

Esiste un vincolo sul predicato, ma è applicato testualmente dal testo standard e può essere applicato da un compilatore sufficientemente capace come Quality-of-Implementation.

Molte cose sono protette solo dal fraseggio nello standard. Alcune delle motivazioni sono che mentre è possibile vincolare il predicato a quelli che prendono l'argomento in base al valore o al riferimento const, renderebbe più difficile l'utilizzo dei predicati esistenti e genererà un'orda di adattatori solo per ottenere la funzione adatta.

Similmente, lo standard non proibisce la modifica del predicato, ma avverte che potrebbe e probabilmente ne farà delle copie, quindi la mutazione deve essere eseguita tramite lo stato esterno o acquisito.

Quando si progetta una libreria C ++, si dice comunemente che non è possibile immaginare tutti i posti in cui verrà utilizzato, ma solo che si dovrebbe cercare di non limitarli troppo.

Direi che un concetto o un tratto che dichiarerebbe una funzione pura non otterrebbe nulla dall'implementazione, poiché è già progettato attorno al programmatore promettendo che il predicato non modifica la collezione. Allo stesso modo, una diagnostica che indica che un predicato è impuro potrebbe sparare praticamente su tutto e non aiuta molto.

C ++ 11 25.1 / 6 afferma (parafrasato): Se la sezione Effetti di un algoritmo dice che un valore puntato da un iteratore passato come argomento è modificato, quindi quell'algoritmo ha un requisito di tipo aggiuntivo, deve soddisfare i requisiti di un iteratore mutabile (24.2).

C ++ 11 25.1 / 8 (e / 9) afferma: ... un predicato non può applicare alcuna funzione non costante attraverso l'iteratore dereferenziato.

find_if (25.2.5) non ha una sezione di tali effetti, quindi anche se il predicato fosse autorizzato a mutare, non sarebbe ancora legale.

    
risposta data 14.08.2015 - 13:05
fonte

Leggi altre domande sui tag