30

Делаю рекурсивную лямбда (для определенности - факториал). Вот так все отлично работает:

std::function<int(int)> f = [&f](int n) -> int { return (n) ? n*f(n-1) : 1; };

А вот так - ни в какую:

auto h = [&h](int n) -> int { return (n) ? n*h(n-1) : 1; };

хотя, казалось бы, тип h вывести нет никакой проблемы - специально даже указал возвращаемый int. В чем настолько большая разница, что вывод типа не срабатывает? Казалось бы, из определения (int)->int тип очевиден, после чего можно использовать его в теле лямбды?

И второй вопрос - интересно, а можно ли извратиться до такой степени, чтобы написать анонимную рекурсивную лямбду, т.е. без сохранения ее в переменной - что-то вроде

cout << [&](int n)->int{ ..... }(6) << endl;

P.S. Решение для второго вопроса нашлось - использовать внутри неименованной лямбды именованную (например, тот же f выше), но это все же не совсем то, что хотелось :)

4
  • Ответ - правда на английском, почему.
    – Grundy
    9 фев 2016 в 11:20
  • @Grundy Спасибо! Впрочем, основной ответ - чтобы вывести тип, надо обработать тело лямбды - мне представляется не совсем верным, в том смысле, что тип в данном случае очевиден из объявления, без тела. С другой стороны, возможно, такое общее правило введено в стандарт во избежание каких-то других ситуаций, так что при том, что здесь можно вывести тип, его не выводят специально, для соответствия стандарту.
    – Harry
    9 фев 2016 в 11:38
  • Можете добавить свой ответ и пометить его как выбранный
    – Grundy
    9 фев 2016 в 11:39
  • @Grundy Простите, не понял? я ведь ни на что не ответил. Если вы о моих мыслях о том, что можно, и чего нельзя - то это только мои предположения, я не могу их считать ответом, так как не знаком со стандартом до такой степени.
    – Harry
    9 фев 2016 в 11:44

4 ответа 4

35

Начиная с C++23 у нас появилась возможность явного указания this в аргументах функции (которая предполагает наличие оного) (deducing this), а это, в свою очередь, позволяет создать рекурсивную лямбду:

auto lambda = [](this const auto& self, int n) -> int 
{ 
    return (n) ? n*self(n-1) : 1; 
};

Нижепредставленный текст представляет собой старый ответ, который актуален для более старых версий C++. Сохранён для истории.


Разыграем спектакль, главные действующие лица: компилятор и компилятор, и компилятор, и ... Компилятор встречает следующую строчку:

auto h = [&h](int n) -> int { return (n) ? n*h(n-1) : 1; };

— Ага — говорит, компилятор. Мне нужно сгенерировать класс под лямбду, секундочку:

class lkdlkhbahbahkl_danfaksdf_lamba
{
public:
     int operator()(int n) const
     {
          return (n) ? n*h(n-1) : 1;
     } 
private:
     ???? h;
};

Компилятор встречает первое препятствие, нужно объявить член класса с именем h, но его тип не известен. Надо спросить компилятор!

— Компилятор, скажи мне тип переменной h! — воскликнул компилятор.

— Секундочку — ответил компилятор. А сам подумал, я ведь тип то и не знаю, спрошу-ка я компилятор, что там за тип у этой лямды.

— Компилятор, скажи мне тип лямбды, у меня компилятор спрашивает, ему надо там член класса создать, а он тип не знает — говорит компилятор

— Нет проблем — отвечает компилятор, сейчас, только лямбду сгенерирую...

Ну Вы поняли, как наш спектакль будет продолжен?


Касательно второго вопроса: анонимную рекурсивную лямбду создать нельзя. Если что-то не имеет имени, как сделать рекурсивный вызов?

2
  • 1
    Да, если тип h неизвестен. Но он в принципе известен - int(int)... В любом случае вопрос можно считать решенным. Что до второго вопроса - да, пожалуй... Если нет какого-то специализированного имени типа this. Но пока что почему-то до него не додумались :)
    – Harry
    9 фев 2016 в 20:03
  • Все, понял, что вы имеете в виду! Вы имеете в виду захваченную лямбду, да, а ее тип действительно пока что неизвестен. Все, теперь согласен полностью, спасибо. Убедили :)
    – Harry
    9 фев 2016 в 20:11
18

Начиная с С++14, аргументы в лямбда-выражениях могут использовать вывод типов (генерируется шаблонный operator()):

[](auto f) { f(); }

Это позволяет использовать continuations (продолжения) в лямбда-выражениях:

auto fac = [](int n) {
  auto impl = [](int n, auto continuation) {
    if (n < 2) return 1;
    return n * continuation(n - 1, continuation);
  };
  return impl(n, impl);
};
0
3

Попалась очень интересная статья.

Кому хочется подробностей - читайте... Приведу только 4 варианта кода.

Вариант 1 - с объявлением типа.

std::function<int(int)> fact;

fact = [&](int n) {
    if (n <= 1) return n;
    return n*fact(n - 1);
};

cout << fact(4) << endl;
cout << fact(5) << endl;
cout << fact(6) << endl;

Вариант 2

auto fact = [](int n, auto&& fact) {
    if (n <= 1) return n;
    return n* fact(n - 1, fact);
};

cout << fact(4,fact) << endl;
cout << fact(5,fact) << endl;
cout << fact(6,fact) << endl;

Вариант - фактически предложенный @Abyx

auto f = [&](int n) {

    auto fact = [](int n, auto&& fact) {
        if (n <= 1) return n;
        return n* fact(n - 1, fact);
    };

    return fact(n, fact);
};

cout << f(4) << endl;
cout << f(5) << endl;
cout << f(6) << endl;

Вариант 3 - работает, когда лямбда ничего не захватывает. Я бы сказал, что очень похож на первый вариант...

using fact_t = int(*)(int);
static fact_t fact = [](int n) {
    if (n <= 1) return n;
    return n*fact(n - 1);
};

cout << fact(4) << endl;
cout << fact(5) << endl;
cout << fact(6) << endl;

Еще раз рекомендую почитать статью - весьма интересна...

1

написать анонимную рекурсивную лямбду, т.е. без сохранения ее в переменной

#include <iostream>

int main() {
    auto fact = [](int n) {
        return [](auto f, int n) {
            return f(f, n);
        }(
            [](auto f, int n) -> int { return (n > 0) ? n * f(f, n - 1) : 1; },
            n
        );
    };

    int n;
    std::cin >> n;
    std::cout << fact(n) << '\n';
}
$ g++ -std=c++14 -pedantic -Wall -Wextra -Werror -Wwrite-strings -Wconversion y-combinator.cpp

$ echo 5 | ./a.out 
120

Ниже тот же самый код, разбитый на три определения:

y_comb (Y combinator) вызывает функцию f передавая её саму в качестве аргумента. Прием позволяет делать рекурсивные вызовы без обращения к глобальным именам.

fact_rec - рекурсивный факториал совместимый с y_comb. Первый аргумент - функция для рекурсивного вызова, второй - целое число, факториал которого надо вычислить.

fact - интерфейс для вызова факториала.

#include <iostream>

int main() {
    auto y_comb = [](auto f, int n) { return f(f, n); };

    auto fact_rec = [](auto f, int n) -> int {
        return (n > 0) ? n * f(f, n - 1) : 1;
    };

    auto fact = [y_comb, fact_rec](int n) { return y_comb(fact_rec, n); };

    int n;
    std::cin >> n;
    std::cout << fact(n) << '\n';
}
5
  • Наверное я совсем постарел и уже не понимаю, для чего вообще могли понадобиться лямбды, когда еще со времен алгола известны вложенные функции (кстати, реализованные в GCC)
    – avp
    14 янв 2023 в 10:29
  • @avp, в стандартных C и С++ не было замыканий, что доставляет жуткие неудобства. Вложенные функции - хорошо. Но они не настоящие функции - их нельзя вернуть из контекста в котором они создавались. Из-за того что контекст хранится на аппаратном стеке и будет уничтожен, делая вложенную функцию бесполезной. Поправить можно, разместив контекст вне аппаратного стека. Для этого надо поменять компилятор (он станет зависим от динамической памяти, чего в стандартном C не было никогда). Узел завязан так туго, что в C++ введён новый тип чего-то что можно вычислить - лямбды. 14 янв 2023 в 10:46
  • Хотите сказать, что лямбду можно вызывать вне контекста? (понятно, я имею в виду запомнить ее адрес и затем вызвать откуда-то еще. И она будет работать? (если не захватывет локальные перменные, то будет. Но точно так же будет работать и вызванная вне контекста nested function (по крайней мере в той реализации, что я когда-то смотрел))) На самом деле я не понимаю почему в С++ нельзя было ввести nested functions
    – avp
    14 янв 2023 в 11:03
  • @avp, пусть мы сделали nested function у которой можно взять адрес и тип которой будет совместим с обычной функцией с той же сигнатурой. Как защититься от возврата указателя? Думаю, что никак. Как обеспечить вызов через указатель? Сложно, так технически вам нужно передать дополнительные аргументы - ссылки на локальные переменные контекста. В С++ обе проблемы решены просто - лямбды-не функции. Это отличный вопрос для ru.SO. 14 янв 2023 в 11:27
  • 1
    Кажется я понял вашу точку зрения. Лямбды нужны для того, чтобы усложнить стрельбу по своим ногам.
    – avp
    14 янв 2023 в 11:44

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.