As funções de ordem superior podem ser puras?

5

Eu estava pensando em funções puras especialmente no contexto de C ++, que obviamente não é uma linguagem puramente funcional, e queria saber se funções de ordem superior em C ++ podem ser consideradas puras? Tomemos, por exemplo, std::find_if : seria muito puro, exceto que é necessária outra função, que pode não ser pura. Parece não haver nenhuma restrição no predicado std::find_if que impede de fazer coisas desagradáveis e impuras dentro da função, assim:

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

Então, talvez alguém com mais experiência em linguagens de programação funcional possa esclarecer isso para mim: a noção de 'funções puras' faz sentido ao lidar com funções de ordem superior?

EDIT: Eu deveria ter declarado mais claramente que eu não estou procurando uma explicação sobre a exatidão do const em C ++. Eu só queria saber se a definição de uma função pura faz sentido quando se fala de funções de ordem superior em C ++. Eu mudei o exemplo para ilustrar que const não está resolvendo meu problema aqui!

    
por Mortano 14.08.2015 / 12:03
fonte

2 respostas

3

Você está certo, isso é um problema quando alguém quer raciocinar sobre pureza de funções em uma linguagem que permite funções impuras. Tecnicamente, quase todas as linguagens permitem a impureza, mas as puramente funcionais geralmente marcam explicitamente as impuras no sistema de tipos, de modo que a função Haskell map :: (a -> b) -> [a] -> [b] , implicitamente, requer que a função a ser mapeada seja pura.

Informalmente, certamente podemos dizer: find_if é puro apenas se a função predicado for pura. Então, como podemos ensinar o compilador sobre isso?

Como o C ++ não marca funções impuras (nem as puras, a propósito, mas vamos fingir que estamos adicionando esse recurso), e provavelmente não queremos restringir find_if para aceitar apenas funções puras (já que isso ser incompatível com o passado), ficamos com o que vou chamar de polimorfismo de pureza . Ou seja, find_if é puro se a função passada for pura. Não tenho conhecimento de uma linguagem que faça isso, mas, em princípio, não é diferente do polimorfismo em relação aos tipos (também conhecidos como genéricos). Sistemas de efeitos suficientemente sofisticados provavelmente têm capacidade equivalente, apenas generalizados para julgamentos cada vez mais refinados do que "puros" e "impuros".

    
por 14.08.2015 / 14:18
fonte
1

Há uma restrição no predicado, mas é reforçada textualmente pelo texto padrão e pode ser reforçada por um compilador com capacidade suficiente como Qualidade de Implementação.

Muitas coisas só são guardadas por frases no padrão. Algumas das razões são que, embora seja possível restringir o predicado para aqueles que usam o argumento por valor ou referência const, tornaria mais difícil usar predicados existentes e gerar uma horda de adaptadores apenas para que a função caiba.

Similarmente, o padrão não proíbe a modificação do predicado, mas ele adverte que ele pode e provavelmente fará cópias dele, então a mutação precisa ser feita via estado externo ou capturado.

Ao criar uma biblioteca em C ++, é comum dizer que você não pode imaginar todos os lugares em que ela será usada, apenas que você deve tentar não restringi-los demais.

Eu diria que um conceito ou traço que declararia uma função pura não ganharia nada com a implementação, já que ela já foi projetada em torno do programador, prometendo que o predicado não modifica a coleção. Da mesma forma, um diagnóstico que indique que um predicado é impuro dispararia em praticamente tudo e não ajuda muito.

C ++ 11 25.1 / 6 states (parafraseado): Se a seção Effects de um algoritmo diz que um valor apontado por qualquer iterador passado como um argumento é modificado, então esse algoritmo tem um requisito de tipo adicional, ele deve satisfazer os requisitos de um iterador mutável (24.2).

C ++ 11 25.1 / 8 (e / 9) declara: ... um predicado pode não aplicar qualquer função não constante através do iterador não referenciado.

find_if (25.2.5) não tem essa seção de efeitos, portanto, mesmo que o predicado sofresse mutação, ainda assim não seria legal.

    
por 14.08.2015 / 13:05
fonte