Como pode Currying ser feito em C ++?

https://stackoverflow.com/questions/152005

02-07-2019
|

Pergunta

O que é currying?

Como pode Currying ser feito em C ++?

Por favor, explique ligantes no recipiente STL?

Solução

Em suma, currying leva uma função f(x, y) e dado um Y fixo, dá uma nova função g(x) onde

g(x) == f(x, Y)

Esta nova função pode ser chamado em situações onde apenas um argumento for fornecido, e passa a chamada para a função f original com o argumento Y fixo.

Os ligantes na STL permitir que você faça isso para funções C ++. Por exemplo:

#include <functional>
#include <iostream>
#include <vector>

using namespace std;

// declare a binary function object
class adder: public binary_function<int, int, int> {
public:
    int operator()(int x, int y) const
    {
        return x + y;
    }
};

int main()
{
    // initialise some sample data
    vector<int> a, b;
    a.push_back(1);
    a.push_back(2);
    a.push_back(3);

    // here we declare a function object f and try it out
    adder f;
    cout << "f(2, 3) = " << f(2, 3) << endl;

    // transform() expects a function with one argument, so we use
    // bind2nd to make a new function based on f, that takes one
    // argument and adds 5 to it
    transform(a.begin(), a.end(), back_inserter(b), bind2nd(f, 5));

    // output b to see what we got
    cout << "b = [" << endl;
    for (vector<int>::iterator i = b.begin(); i != b.end(); ++i) {
        cout << "  " << *i << endl;
    }
    cout << "]" << endl;

    return 0;
}

Outras dicas

1. O que é currying?

Currying simplesmente significa uma transformação de uma função de vários argumentos para uma função de um único argumento. Isso é mais facilmente ilustrada através de um exemplo:

Dê uma f função que aceita três argumentos:

int
f(int a,std::string b,float c)
{
    // do something with a, b, and c
    return 0;
}

Se queremos chamar f, temos de fornecer todos os seus argumentos f(1,"some string",19.7f).

Em seguida, uma versão curry de f, vamos chamá-lo curried_f=curry(f) só espera um único argumento, que corresponde ao primeiro argumento de f, nomeadamente a a argumento. Além disso, f(1,"some string",19.7f) também pode ser escrito usando a versão curry como curried_f(1)("some string")(19.7f). O valor de retorno de curried_f(1) por outro lado, é apenas uma outra função, que manipula o próximo argumento de f. No final, acabamos com uma função ou curried_f exigível que cumpre o seguinte igualdade:

curried_f(first_arg)(second_arg)...(last_arg) == f(first_arg,second_arg,...,last_arg).

2. Como pode Currying ser conseguido em C ++?

O seguinte é um pouco mais complicado, mas funciona muito bem para mim (usando c ++ 11) ... Ele também permite que currying de grau arbitrário assim: auto curried=curry(f)(arg1)(arg2)(arg3) e auto result=curried(arg4)(arg5) mais tarde. Aqui vai:

#include <functional>

namespace _dtl {

    template <typename FUNCTION> struct
    _curry;

    // specialization for functions with a single argument
    template <typename R,typename T> struct
    _curry<std::function<R(T)>> {
        using
        type = std::function<R(T)>;

        const type
        result;

        _curry(type fun) : result(fun) {}

    };

    // recursive specialization for functions with more arguments
    template <typename R,typename T,typename...Ts> struct
    _curry<std::function<R(T,Ts...)>> {
        using
        remaining_type = typename _curry<std::function<R(Ts...)> >::type;

        using
        type = std::function<remaining_type(T)>;

        const type
        result;

        _curry(std::function<R(T,Ts...)> fun)
        : result (
            [=](const T& t) {
                return _curry<std::function<R(Ts...)>>(
                    [=](const Ts&...ts){ 
                        return fun(t, ts...); 
                    }
                ).result;
            }
        ) {}
    };
}

template <typename R,typename...Ts> auto
curry(const std::function<R(Ts...)> fun)
-> typename _dtl::_curry<std::function<R(Ts...)>>::type
{
    return _dtl::_curry<std::function<R(Ts...)>>(fun).result;
}

template <typename R,typename...Ts> auto
curry(R(* const fun)(Ts...))
-> typename _dtl::_curry<std::function<R(Ts...)>>::type
{
    return _dtl::_curry<std::function<R(Ts...)>>(fun).result;
}

#include <iostream>

void 
f(std::string a,std::string b,std::string c)
{
    std::cout << a << b << c;
}

int 
main() {
    curry(f)("Hello ")("functional ")("world!");
    return 0;
}

OK, como Samer comentou, devo acrescentar algumas explicações sobre a forma como isso funciona. A implementação real é feito na _dtl::_curry, enquanto o modelo de funções curry são apenas invólucros de conveniência. A implementação é recursiva sobre os argumentos do argumento std::function modelo FUNCTION.

Para uma função com apenas um único argumento, o resultado é idêntico ao da função original.

        _curry(std::function<R(T,Ts...)> fun)
        : result (
            [=](const T& t) {
                return _curry<std::function<R(Ts...)>>(
                    [=](const Ts&...ts){ 
                        return fun(t, ts...); 
                    }
                ).result;
            }
        ) {}

Aqui a coisa complicada: Para uma função com mais argumentos, voltamos a lambda cujo argumento é vinculado ao primeiro argumento para a chamada para fun. Finalmente, o currying restante para os argumentos N-1 restantes é delegada à implementação de _curry<Ts...> com um argumento menos template.

Atualização para c ++ 14/17:

Uma nova idéia de abordar o problema da Currying apenas veio a mim ... Com a introdução do if constexpr em c ++ 17 (e com a ajuda de void_t para determinar se uma função está totalmente ao curry), as coisas parecem ficar muito mais fácil:

template< class, class = std::void_t<> > struct 
needs_unapply : std::true_type { };

template< class T > struct 
needs_unapply<T, std::void_t<decltype(std::declval<T>()())>> : std::false_type { };

template <typename F> auto
curry(F&& f) {
  /// Check if f() is a valid function call. If not we need 
  /// to curry at least one argument:
  if constexpr (needs_unapply<decltype(f)>::value) {
       return [=](auto&& x) {
            return curry(
                [=](auto&&...xs) -> decltype(f(x,xs...)) {
                    return f(x,xs...);
                }
            );
        };    
  }
  else {  
    /// If 'f()' is a valid call, just call it, we are done.
    return f();
  }
}

int 
main()
{
  auto f = [](auto a, auto b, auto c, auto d) {
    return a  * b * c * d;
  };

  return curry(f)(1)(2)(3)(4);
}

Veja código em ação no aqui . Com uma abordagem semelhante, aqui é como caril funções com número arbitrário de argumentos.

A mesma ideia parece funcionar também em C ++ 14, se trocar o constexpr if com uma seleção de modelo, dependendo do needs_unapply<decltype(f)>::value teste:

template <typename F> auto
curry(F&& f);

template <bool> struct
curry_on;

template <> struct
curry_on<false> {
    template <typename F> static auto
    apply(F&& f) {
        return f();
    }
};

template <> struct
curry_on<true> {
    template <typename F> static auto 
    apply(F&& f) {
        return [=](auto&& x) {
            return curry(
                [=](auto&&...xs) -> decltype(f(x,xs...)) {
                    return f(x,xs...);
                }
            );
        };
    }
};

template <typename F> auto
curry(F&& f) {
    return curry_on<needs_unapply<decltype(f)>::value>::template apply(f);
}

O exemplo de Simplificação Gregg, usando tr1:

#include <functional> 
using namespace std;
using namespace std::tr1;
using namespace std::tr1::placeholders;

int f(int, int);
..
int main(){
    function<int(int)> g     = bind(f, _1, 5); // g(x) == f(x, 5)
    function<int(int)> h     = bind(f, 2, _1); // h(x) == f(2, x)
    function<int(int,int)> j = bind(g, _2);    // j(x,y) == g(y)
}

componentes funcionais

Tr1 permitem que você escrever código de estilo funcional rico em C ++. Como assim, C ++ 0x permitirá in-line funções lambda para fazer isso assim:

int f(int, int);
..
int main(){
    auto g = [](int x){ return f(x,5); };      // g(x) == f(x, 5)
    auto h = [](int x){ return f(2,x); };      // h(x) == f(2, x)
    auto j = [](int x, int y){ return g(y); }; // j(x,y) == g(y)
}

E, embora C ++ não fornece a análise de efeito colateral rico que algumas linguagens de programação funcional orientada executar, análise de const e C ++ 0x lambda sintaxe pode ajudar:

struct foo{
    int x;
    int operator()(int y) const {
        x = 42; // error!  const function can't modify members
    }
};
..
int main(){
    int x;
    auto f = [](int y){ x = 42; }; // error! lambdas don't capture by default.
}

Espero que ajude.

Tenha um olhar em Boost.Bind o que torna o processo mostrado por Greg mais versátil:

transform(a.begin(), a.end(), back_inserter(b), bind(f, _1, 5));

Isso vincula 5 ao segundo argumento do f.

É importante notar que este é não currying (em vez, é a aplicação parcial). No entanto, usando currying de uma maneira geral é difícil em C ++ (na verdade, ele só recentemente tornou-se possível a todos) e aplicação parcial é muitas vezes usado em seu lugar.

Outras respostas muito bem explicar ligantes, por isso não vou repetir essa parte aqui. Eu só irá demonstrar como currying e aplicação parcial pode ser feito com lambdas em C ++ 0x.

Exemplo de código: (Explicação nos comentários)

#include <iostream>
#include <functional>

using namespace std;

const function<int(int, int)> & simple_add = 
  [](int a, int b) -> int {
    return a + b;
  };

const function<function<int(int)>(int)> & curried_add = 
  [](int a) -> function<int(int)> {
    return [a](int b) -> int {
      return a + b;
    };
  };

int main() {
  // Demonstrating simple_add
  cout << simple_add(4, 5) << endl; // prints 9

  // Demonstrating curried_add
  cout << curried_add(4)(5) << endl; // prints 9

  // Create a partially applied function from curried_add
  const auto & add_4 = curried_add(4);
  cout << add_4(5) << endl; // prints 9
}

Se você estiver usando C ++ 14 é muito fácil:

template<typename Function, typename... Arguments>
auto curry(Function function, Arguments... args) {
    return [=](auto... rest) {
        return function(args..., rest...);
    }
}

Você pode então usá-lo como este:

auto add = [](auto x, auto y) { return x + y; }

// curry 4 into add
auto add4 = curry(add, 4);

add4(6); // 10

Currying é uma maneira de reduzir uma função que recebe múltiplas argumentos em uma sequência de funções aninhadas com um argumento cada:

full = (lambda a, b, c: (a + b + c))
print full (1, 2, 3) # print 6

# Curried style
curried = (lambda a: (lambda b: (lambda c: (a + b + c))))
print curried (1)(2)(3) # print 6

Currying é bom porque você pode definir funções que são simplesmente wrappers em torno de outras funções com valores pré-definidos, e em seguida, passar em torno das funções simplificadas. C ++ ligantes STL fornecer uma aplicação do presente in C ++.

Alguns grandes respostas aqui. Eu pensei que eu gostaria de acrescentar minha própria porque era divertido brincar com o conceito.

aplicação de função parcial : O processo de "ligar" uma função com apenas alguns de seus parâmetros, adiando o resto para ser preenchido mais tarde. O resultado é outra função com menos parâmetros.

Currying : É uma forma especial de aplicação de função parcial, onde você só pode "ligar" um único argumento de cada vez. O resultado é outra função com exatamente 1 menos parâmetro.

O código que estou prestes a presente é aplicação de função parcial a partir do qual currying é possível, mas não é a única possibilidade. Ele oferece algumas vantagens sobre o anterior currying implementações (principalmente porque é a aplicação de função parcial e não currying, heh).

A aplicação de mais de uma função vazia:

auto sum0 = [](){return 0;};
std::cout << partial_apply(sum0)() << std::endl;

A aplicação de múltiplos argumentos de cada vez:

auto sum10 = [](int a, int b, int c, int d, int e, int f, int g, int h, int i, int j){return a+b+c+d+e+f+g+h+i+j;};
std::cout << partial_apply(sum10)(1)(1,1)(1,1,1)(1,1,1,1) << std::endl; // 10

Suporte constexpr que permite static_assert de tempo de compilação:
```
static_assert(partial_apply(sum0)() == 0);
```
Uma mensagem de erro útil se você acidentalmente ir longe demais no fornecimento argumentos:
```
auto sum1 = [](int x){ return x;};
partial_apply(sum1)(1)(1);
```
erro: static_assert falhou "A tentativa de aplicar muitos argumentos!"

Outras respostas acima lambdas de retorno que se ligam um argumento e, em seguida, voltar mais lambdas. Esta abordagem envolve essa funcionalidade essencial em um objeto que pode ser chamado. Definições para operator() permitir que o lambda interna para ser chamado. modelos variádicos nos permitem verificar se há alguém que vai longe demais, e uma função de conversão implícita para o tipo de resultado da chamada de função nos permite imprimir o resultado ou comparar o objeto para um primitivo.

Código:

namespace detail{
template<class F>
using is_zero_callable = decltype(std::declval<F>()());

template<class F>
constexpr bool is_zero_callable_v = std::experimental::is_detected_v<is_zero_callable, F>;
}

template<class F>
struct partial_apply_t
{
    template<class... Args>
    constexpr auto operator()(Args... args)
    {
        static_assert(sizeof...(args) == 0 || !is_zero_callable, "Attempting to apply too many arguments!");
        auto bind_some = [=](auto... rest) -> decltype(myFun(args..., rest...))
        {
           return myFun(args..., rest...);
        };
        using bind_t = decltype(bind_some);

        return partial_apply_t<bind_t>{bind_some};
    }
    explicit constexpr partial_apply_t(F fun) : myFun(fun){}

    constexpr operator auto()
    {
        if constexpr (is_zero_callable)
            return myFun();
        else
            return *this; // a callable
    }
    static constexpr bool is_zero_callable = detail::is_zero_callable_v<F>;
    F myFun;
};

Demonstração ao vivo

Alguns mais notas:

Eu escolhi usar is_detected principalmente para diversão e prática; que serve o mesmo que um tipo normal característica faria aqui.
Não poderia ser definitivamente mais trabalho para apoiar o encaminhamento perfeito por motivos de desempenho
O código é C ++ 17 porque requer o apoio constexpr lambda em C + +17
- E parece que GCC 7.0.1 não é completamente lá ainda, seja, então eu usei Clang 5.0.0

Alguns testes:

auto sum0 = [](){return 0;};
auto sum1 = [](int x){ return x;};
auto sum2 = [](int x, int y){ return x + y;};
auto sum3 = [](int x, int y, int z){ return x + y + z; };
auto sum10 = [](int a, int b, int c, int d, int e, int f, int g, int h, int i, int j){return a+b+c+d+e+f+g+h+i+j;};

std::cout << partial_apply(sum0)() << std::endl; //0
static_assert(partial_apply(sum0)() == 0, "sum0 should return 0");
std::cout << partial_apply(sum1)(1) << std::endl; // 1
std::cout << partial_apply(sum2)(1)(1) << std::endl; // 2
std::cout << partial_apply(sum3)(1)(1)(1) << std::endl; // 3
static_assert(partial_apply(sum3)(1)(1)(1) == 3, "sum3 should return 3");
std::cout << partial_apply(sum10)(1)(1,1)(1,1,1)(1,1,1,1) << std::endl; // 10
//partial_apply(sum1)(1)(1); // fails static assert
auto partiallyApplied = partial_apply(sum3)(1)(1);
std::function<int(int)> finish_applying = partiallyApplied;
std::cout << std::boolalpha << (finish_applying(1) == 3) << std::endl; // true

auto plus2 = partial_apply(sum3)(1)(1);
std::cout << std::boolalpha << (plus2(1) == 3) << std::endl; // true
std::cout << std::boolalpha << (plus2(3) == 5) << std::endl; // true

Eu implementei currying com modelos variádicos também (veja a resposta de Julian). No entanto, eu não fazer uso de recursão ou std::function. Nota: Ele usa um número de C ++ 14 recursos

.

O exemplo fornecido (função main) na verdade é executado em tempo de compilação, provando que o método currying não trunfo otimizações essenciais pelo compilador.

O código pode ser encontrado aqui: https://gist.github.com/Garciat/c7e4bef299ee5c607948

com este arquivo helper: https://gist.github.com/Garciat/cafe27d04cfdff0e891e

O código ainda precisa (muito) trabalho, que pode ou não pode completar em breve. De qualquer maneira, estou postando isso aqui para referência futura.

código de postar em ligações Die caso (embora não deve):

#include <type_traits>
#include <tuple>
#include <functional>
#include <iostream>

// ---

template <typename FType>
struct function_traits;

template <typename RType, typename... ArgTypes>
struct function_traits<RType(ArgTypes...)> {
    using arity = std::integral_constant<size_t, sizeof...(ArgTypes)>;

    using result_type = RType;

    template <size_t Index>
    using arg_type = typename std::tuple_element<Index, std::tuple<ArgTypes...>>::type;
};

// ---

namespace details {
    template <typename T>
    struct function_type_impl
      : function_type_impl<decltype(&T::operator())>
    { };

    template <typename RType, typename... ArgTypes>
    struct function_type_impl<RType(ArgTypes...)> {
        using type = RType(ArgTypes...);
    };

    template <typename RType, typename... ArgTypes>
    struct function_type_impl<RType(*)(ArgTypes...)> {
        using type = RType(ArgTypes...);
    };

    template <typename RType, typename... ArgTypes>
    struct function_type_impl<std::function<RType(ArgTypes...)>> {
        using type = RType(ArgTypes...);
    };

    template <typename T, typename RType, typename... ArgTypes>
    struct function_type_impl<RType(T::*)(ArgTypes...)> {
        using type = RType(ArgTypes...);
    };

    template <typename T, typename RType, typename... ArgTypes>
    struct function_type_impl<RType(T::*)(ArgTypes...) const> {
        using type = RType(ArgTypes...);
    };
}

template <typename T>
struct function_type
  : details::function_type_impl<typename std::remove_cv<typename std::remove_reference<T>::type>::type>
{ };

// ---

template <typename Args, typename Params>
struct apply_args;

template <typename HeadArgs, typename... Args, typename HeadParams, typename... Params>
struct apply_args<std::tuple<HeadArgs, Args...>, std::tuple<HeadParams, Params...>>
  : std::enable_if<
        std::is_constructible<HeadParams, HeadArgs>::value,
        apply_args<std::tuple<Args...>, std::tuple<Params...>>
    >::type
{ };

template <typename... Params>
struct apply_args<std::tuple<>, std::tuple<Params...>> {
    using type = std::tuple<Params...>;
};

// ---

template <typename TupleType>
struct is_empty_tuple : std::false_type { };

template <>
struct is_empty_tuple<std::tuple<>> : std::true_type { };

// ----

template <typename FType, typename GivenArgs, typename RestArgs>
struct currying;

template <typename FType, typename... GivenArgs, typename... RestArgs>
struct currying<FType, std::tuple<GivenArgs...>, std::tuple<RestArgs...>> {
    std::tuple<GivenArgs...> given_args;

    FType func;

    template <typename Func, typename... GivenArgsReal>
    constexpr
    currying(Func&& func, GivenArgsReal&&... args) :
      given_args(std::forward<GivenArgsReal>(args)...),
      func(std::move(func))
    { }

    template <typename... Args>
    constexpr
    auto operator() (Args&&... args) const& {
        using ParamsTuple = std::tuple<RestArgs...>;
        using ArgsTuple = std::tuple<Args...>;

        using RestArgsPrime = typename apply_args<ArgsTuple, ParamsTuple>::type;

        using CanExecute = is_empty_tuple<RestArgsPrime>;

        return apply(CanExecute{}, std::make_index_sequence<sizeof...(GivenArgs)>{}, std::forward<Args>(args)...);
    }

    template <typename... Args>
    constexpr
    auto operator() (Args&&... args) && {
        using ParamsTuple = std::tuple<RestArgs...>;
        using ArgsTuple = std::tuple<Args...>;

        using RestArgsPrime = typename apply_args<ArgsTuple, ParamsTuple>::type;

        using CanExecute = is_empty_tuple<RestArgsPrime>;

        return std::move(*this).apply(CanExecute{}, std::make_index_sequence<sizeof...(GivenArgs)>{}, std::forward<Args>(args)...);
    }

private:
    template <typename... Args, size_t... Indices>
    constexpr
    auto apply(std::false_type, std::index_sequence<Indices...>, Args&&... args) const& {
        using ParamsTuple = std::tuple<RestArgs...>;
        using ArgsTuple = std::tuple<Args...>;

        using RestArgsPrime = typename apply_args<ArgsTuple, ParamsTuple>::type;

        using CurryType = currying<FType, std::tuple<GivenArgs..., Args...>, RestArgsPrime>;

        return CurryType{ func, std::get<Indices>(given_args)..., std::forward<Args>(args)... };
    }

    template <typename... Args, size_t... Indices>
    constexpr
    auto apply(std::false_type, std::index_sequence<Indices...>, Args&&... args) && {
        using ParamsTuple = std::tuple<RestArgs...>;
        using ArgsTuple = std::tuple<Args...>;

        using RestArgsPrime = typename apply_args<ArgsTuple, ParamsTuple>::type;

        using CurryType = currying<FType, std::tuple<GivenArgs..., Args...>, RestArgsPrime>;

        return CurryType{ std::move(func), std::get<Indices>(std::move(given_args))..., std::forward<Args>(args)... };
    }

    template <typename... Args, size_t... Indices>
    constexpr
    auto apply(std::true_type, std::index_sequence<Indices...>, Args&&... args) const& {
        return func(std::get<Indices>(given_args)..., std::forward<Args>(args)...);
    }

    template <typename... Args, size_t... Indices>
    constexpr
    auto apply(std::true_type, std::index_sequence<Indices...>, Args&&... args) && {
        return func(std::get<Indices>(std::move(given_args))..., std::forward<Args>(args)...);
    }
};

// ---

template <typename FType, size_t... Indices>
constexpr
auto curry(FType&& func, std::index_sequence<Indices...>) {
    using RealFType = typename function_type<FType>::type;
    using FTypeTraits = function_traits<RealFType>;

    using CurryType = currying<FType, std::tuple<>, std::tuple<typename FTypeTraits::template arg_type<Indices>...>>;

    return CurryType{ std::move(func) };
}

template <typename FType>
constexpr
auto curry(FType&& func) {
    using RealFType = typename function_type<FType>::type;
    using FTypeArity = typename function_traits<RealFType>::arity;

    return curry(std::move(func), std::make_index_sequence<FTypeArity::value>{});
}

// ---

int main() {
    auto add = curry([](int a, int b) { return a + b; });

    std::cout << add(5)(10) << std::endl;
}

Esses links são relevantes:

A página Lambda Calculus na Wikipedia tem um claro exemplo de currying
http://en.wikipedia.org/wiki/Lambda_calculus#Motivation

Este artigo trata currying em C / C ++
http://asg.unige.ch/site/papers/Dami91a.pdf

Licenciado em: CC-BY-SA com atribuição

Não afiliado a StackOverflow