Suporte ao C ++ 11 para funções de lista de ordem superior

13

A maioria das linguagens de programação funcional (por exemplo, Common Lisp, Scheme / raquete, Clojure, Haskell, Scala, Ocaml, SML) suporta algumas funções comuns de ordem superior em listas, como map, filter, takeWhile, dropWhile, foldl, foldr(ver, por exemplo Common Lisp, Scheme / Racket, Folha de referência lado a lado do Clojure , a documentação de Haskell , Scala , OCaml e SML .)

O C ++ 11 possui métodos ou funções padrão equivalentes nas listas? Por exemplo, considere o seguinte snippet Haskell:

let xs = [1, 2, 3, 4, 5]
let ys = map (\x -> x * x) xs

Como posso expressar a segunda expressão no padrão C ++ moderno?

std::list<int> xs = ... // Initialize the list in some way.
std::list<int> ys = ??? // How to translate the Haskell expression?

E as outras funções de ordem superior mencionadas acima?
Eles podem ser expressos diretamente em C ++?

Giorgio
fonte
Sim, mas eles operam com conceitos mais gerais do que a implementação específica de uma lista duplamente vinculada. Assim como as operações do Python nesta área. Eu prefiro isso do que estar vinculado a uma estrutura de dados específica. Já tentou fazer essas operações em, digamos, uma Data.Sequenceem Haskell? É relativamente feio.
"É relativamente feio.": Comparado com o que?
Giorgio
Comparado com a mesma operação [a]. Você precisa ocultar a função prelúdio, percorrer o prelúdio ou escolher um nome diferente e menos intuitivo.
Talvez você esteja certo, mas o tópico desta pergunta é como expressar funções de ordem superior da lista comum em C ++, não como implementar funções análogas no Data.Sequence em Haskell.
Giorgio
1
@ delnan Eu diria que Haskell é muito mais geral em sua abordagem. Functor, Foldablee Traversableconsiga isso da maneira mais abstrata possível. Data.Sequenceé uma instância de tudo isso, então você pode fazer fmap (\x -> x * x) xs. mapé fmapespecializado para iniciantes.
Alec

Respostas:

16

Ainda mais, o C ++ possui essas funções, consulte o algoritmo (ou com as adições do C ++ 11 cabeçalho do ):

std::transform
std::for_each
std::remove_copy_if

Eles podem ser facilmente utilizados com qualquer recipiente.

Por exemplo, seu código pode ser expresso assim (com lambdas C ++ 11 para facilitar a codificação):

std::vector<int> x = {1, 2, 3, 4, 5};
std::vector<int> y;
std::transform(x.begin(), x.end(), std::back_inserter(y), [](int elem){ return elem * elem; });

Menos intuitivo, mas você pode facilmente envolver a std::transformchamada em uma função que retornaria um novo contêiner (com movesemântica para melhor desempenho).

m0nhawk
fonte
Obrigado. Gostaria de simplificar alguns códigos que escrevi há alguns dias e isso poderia realmente ajudar a torná-los muito mais curtos. Apenas uma pequena pergunta: por que você precisa passar x.begin () e x.end ()? Não seria suficiente apenas passar o vetor x?
Giorgio
std::transformleva dois iteradores, portanto, você pode pegar uma fatia de um contêiner (lembre-se de que possui aritmética de iteradores).
M0nhawk 18/10/12
Então você tem duas operações em uma: pegando uma fatia e aplicando uma transformação.
Giorgio
Anteriormente, você tem dois iteradores e aplica a transformação aos elementos entre eles. Iteradores não são comuns na programação funcional.
M0nhawk 18/10/12
2
Eu não conheci essas bibliotecas, em C ++ o algoritmo baseado em iterador é muito útil. Você pode fazer uma capa de, no seu caso, std::transformcomo: Y<U> map(T<U>, std::function<Y(U)>).
M0nhawk