http://www.pdfbooksplanet.org/tags/Chris+Weed/
Функциональное программирование на С++.
Chris Weed.
Всего 100 с небольшим страниц, но написано шикарно!
Абсолютно без вода, только небольшое введение — и код, код, код...
Уже первая глава — рекурсивная форма стандартных алгоритмов.
Понятная даже начинающим.
Неистово рекомендую!

Здравствуйте, LaptevVV, Вы писали:

LVV>http://www.pdfbooksplanet.org/tags/Chris+Weed/
LVV>Функциональное программирование на С++.
LVV>Chris Weed.
LVV>Всего 100 с небольшим страниц, но написано шикарно!
LVV>Абсолютно без вода, только небольшое введение — и код, код, код...
LVV>Уже первая глава — рекурсивная форма стандартных алгоритмов.
LVV>Понятная даже начинающим.
LVV>Неистово рекомендую!


так а это разве правильно — рекурсивная форма алгоритмов на с++? или уже появилась возможность контроля размера стека?

LVV>>Уже первая глава — рекурсивная форма стандартных алгоритмов.
LVV>>Понятная даже начинающим.
LVV>>Неистово рекомендую!
__>так а это разве правильно — рекурсивная форма алгоритмов на с++? или уже появилась возможность контроля размера стека?
Первое, что в книжке объясняется: побочный эффект и чистые функции без побочных эффектов.
Потом берет и пишет рекурсивную форму многих стандартных алгоритмов.
И не просто пишет, а сравнивает со стандартной реализацией в указанной им платформе.
В половине случаев рекурсивная версия оказывается эффективнее.
Потом у него лямды, потом — ленивые вычисления...
В общем, то, что я успел посмотреть-почитать — мне ОЧЕНЬ понравилось.

Здравствуйте, LaptevVV, Вы писали:

LVV>>>Уже первая глава — рекурсивная форма стандартных алгоритмов.
LVV>>>Понятная даже начинающим.
LVV>>>Неистово рекомендую!
__>>так а это разве правильно — рекурсивная форма алгоритмов на с++? или уже появилась возможность контроля размера стека?
LVV>Первое, что в книжке объясняется: побочный эффект и чистые функции без побочных эффектов.
LVV>Потом берет и пишет рекурсивную форму многих стандартных алгоритмов.
LVV>И не просто пишет, а сравнивает со стандартной реализацией в указанной им платформе.
LVV>В половине случаев рекурсивная версия оказывается эффективнее.
LVV>Потом у него лямды, потом — ленивые вычисления...
LVV>В общем, то, что я успел посмотреть-почитать — мне ОЧЕНЬ понравилось.

не, я немного про другое — что на с++ рекурсивный подход использовать мало того, что сомнительно по эффективности, так еще и небезопасно по переполнению стека. вот вы знаете, как удостовериться, что размера стека хватит?

я к тому веду, что такие вещи естественнее изучать на соответствующих языках (меня в свое время впечатлила P.Van Roy, S. Haridi. Concepts, Techniques, and Models of Computer Programming)

Здравствуйте, _hum_, Вы писали:

__>так а это разве правильно — рекурсивная форма алгоритмов на с++? или уже появилась возможность контроля размера стека?

Вообще нет, но многие (все?) компиляторы оптимизируют хвостовую рекурсию в цикл, при включённых оптимизациях.

Здравствуйте, Evgeny.Panasyuk, Вы писали:

EP>Здравствуйте, _hum_, Вы писали:

__>>так а это разве правильно — рекурсивная форма алгоритмов на с++? или уже появилась возможность контроля размера стека?

EP>Вообще нет, но многие (все?) компиляторы оптимизируют хвостовую рекурсию в цикл, при включённых оптимизациях.

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

Здравствуйте, LaptevVV, Вы писали:

LVV>http://www.pdfbooksplanet.org/tags/Chris+Weed/
LVV>Функциональное программирование на С++.
LVV>Chris Weed.
LVV>Всего 100 с небольшим страниц, но написано шикарно!
LVV>Абсолютно без вода, только небольшое введение — и код, код, код...
LVV>Уже первая глава — рекурсивная форма стандартных алгоритмов.
LVV>Понятная даже начинающим.
LVV>Неистово рекомендую!

Вот что меня настораживает так это такие книги. Они решают искуственные проблемы искуствееными методами. И все рады как это круто.
Есть нормальные языки для работы в таком стиле, зачем всё пихать в одну кучу?
На любом полном языке можно писать фортраном. Так что радоватья особо нечему.
C++ идёт неведомо куда, он создаёт всё новые и новые трудности которые потом пытается преодолеть.
Если вам надо мето-программирование и другие моделирования до синтеза кода, так что мешает это разделить на разные этапы
зачем всё пихить в один этап компиляции?
Например надо тебе колекцию с заданными свойствами, указал требование тебе синтезирует оптимальную колекцию, и используй.
Запросил оптимизировать и выкинуть лишее. Вуаля. Двигайся дальше.
Надо поменял требование получил другую рализацию, проверил скороть и потребление на реальном железе и данных сделал выводы.
Для чего таскать весь лишний мусор в виде шаблонов на все случаи, которые вместо облегчения жизни станут лютым гемороем.
И использовать их не по назначению, а для получения функционала которого изначально нет в языке.

ps: Послушал выступление негра из MS про модули. Это признание в том что они неосилили задачу и скорее всего не осилят, учитывая всё навороты и прибабахи которые хотят отставить в этих модулях.

pps: Я бы добавил в C++ функционал depedecated на функции языка что бы от них можно было избавлятся или хотябы проверять что их нет в коде.

Здравствуйте, _hum_, Вы писали:

__>Здравствуйте, LaptevVV, Вы писали:

__> на с++ рекурсивный подход использовать мало того, что сомнительно по эффективности,
в принципе рекурсия при fastcall может быть эффективнее выделения памяти на куче и обгоняет многие алгоритмы с ветвлением которое проц не может предсказать. но никакой гарантии нет. если понимать что у компилятора под капотом то можно получить выигрыш по скорости, применив рекурсию. но если не понимать, то можно очень сильно проиграть

__> так еще и небезопасно по переполнению стека. вот вы знаете, как удостовериться, что размера стека хватит?
это да. стека мало, причем непредсказуемо мало. на разных платформах его разное кол-во и по современным меркам зачастую ничтожное. даже если нам известно сколько стека выделяет ось нашему потоку, то в общем случае нам неизвестно сколько скушали остальные функции на момент вызова нашей. если рекурсивная функция А вызывает рекурсивную функцию Б, то мне становится страшно.


__>я к тому веду, что такие вещи естественнее изучать на соответствующих языках
+1
есть куча языков где рекурсия кушает не стек, а кучу. хотя накладные расходы на вызов функции в общем случае неизвестны. даже если это рекурсивный обход каталогов, то очень может быть что накладные расходы скушают всю кучу...

Здравствуйте, мыщъх, Вы писали:

__>>я к тому веду, что такие вещи естественнее изучать на соответствующих языках
М>+1
М>есть куча языков где рекурсия кушает не стек, а кучу.

Это скорее относится к компиляторам, чем к языку. Например есть такие штуки как Split Stacks, Segmented Stacks.

Здравствуйте, Evgeny.Panasyuk, Вы писали:

EP>Здравствуйте, мыщъх, Вы писали:

__>>>я к тому веду, что такие вещи естественнее изучать на соответствующих языках
М>>+1
М>>есть куча языков где рекурсия кушает не стек, а кучу.

EP>Это скорее относится к компиляторам, чем к языку. Например есть такие штуки как Split Stacks, Segmented Stacks.

а есть _универсальный_ рецепт для си (си++) ?
давайте исходить из того, что мы пишем код не под конкретный компилятор.
нерекурсивный подход скорее всего будет работать везде. рекурсивный же это хождение по минному полю. умеючи можно и рекурсивно. но все-таки слишком рисковано.

Здравствуйте, мыщъх, Вы писали:

М>а есть _универсальный_ рецепт для си (си++) ?
М>давайте исходить из того, что мы пишем код не под конкретный компилятор.

C++ работает везде — и на современных десктопах, и на микроконтроллерах, и даже на древних компьютерах типа Commodore 64.
Поэтому писать под что-то конкретное, по-крайней относительно памяти, таки придётся.

М>нерекурсивный подход скорее всего будет работать везде.

Если под нерекурсивным понимается цикл без выделения памяти (а-ля оптимизация хвостовой рекурсии) — то да, везде.
Если же речь про тот же стэк но в куче — то нужно понимать что на конечном устройстве может и не быть никакой кучи без доп.движений, а вот стэк скорей всего будет. В среднем же по больнице стэк в куче будет более универсальным.

М>рекурсивный же это хождение по минному полю. умеючи можно и рекурсивно.

Ну да, при желании можно и рекурсивно, например:
1. убеждаться в оптимизации хвостовой рекурсии
2. выделять много адресного пространства под стэк
3. использовать фрагментированные стэки
4. ограничивать глубину рекурсии логарифмом, например как в нормальных реализациях quicksort

М>но все-таки слишком рисковано.

Вопрос зачем.

LVV>>В общем, то, что я успел посмотреть-почитать — мне ОЧЕНЬ понравилось.
__>не, я немного про другое — что на с++ рекурсивный подход использовать мало того, что сомнительно по эффективности, так еще и небезопасно по переполнению стека. вот вы знаете, как удостовериться, что размера стека хватит?
Это не вопрос парадигмы и стиля программирования.
А в означенной мной книжке речь идет о функциональном стиле кода в С++.
__>я к тому веду, что такие вещи естественнее изучать на соответствующих языках (меня в свое время впечатлила P.Van Roy, S. Haridi. Concepts, Techniques, and Models of Computer Programming)
Вот за это — спасибо!
Уже посмотрел — книжка блеск!

Здравствуйте, LaptevVV, Вы писали:

LVV>>>В общем, то, что я успел посмотреть-почитать — мне ОЧЕНЬ понравилось.
__>>не, я немного про другое — что на с++ рекурсивный подход использовать мало того, что сомнительно по эффективности, так еще и небезопасно по переполнению стека. вот вы знаете, как удостовериться, что размера стека хватит?
LVV>Это не вопрос парадигмы и стиля программирования.
LVV>А в означенной мной книжке речь идет о функциональном стиле кода в С++.
__>>я к тому веду, что такие вещи естественнее изучать на соответствующих языках (меня в свое время впечатлила P.Van Roy, S. Haridi. Concepts, Techniques, and Models of Computer Programming)
LVV>Вот за это — спасибо!
LVV>Уже посмотрел — книжка блеск!

ага. именно после таких книг понимаешь, что пытаться демонстрировать (в том числе студентам) приемы декларативного программирования на императивном языке — это как играть в хоккей на траве

Здравствуйте, _hum_, Вы писали:

__>ага. именно после таких книг понимаешь, что пытаться демонстрировать (в том числе студентам) приемы декларативного программирования на императивном языке — это как играть в хоккей на траве

Книжка отличная, но почему бы не демонстрировать? C++ — язык мейнстрима, на нём пишутся быстрые программы, его многие знают. Если тем, кто его знает, можно с его помощью показать какие-то красивые идеи, которые они потом смогут использовать, то почему бы это не сделать? Можно, конечно, их показывать на Хаскеле или Ерланге, но пользователи оных, во-первых, и так хорошо знают про рекурсию, а во-вторых, "узок круг этих людей, страшно далеки они от народа".

__>так не всегда же к хвостовой можно свети — это раз. а во-вторых, если нет гарантии, то код подойдет только для баловства.

К хвостовой сводятся только элементарные циклы, это не очень интересно.
А полную гарантию даёт только похоронное бюро

Здравствуйте, LaptevVV, Вы писали:

LVV>http://www.pdfbooksplanet.org/tags/Chris+Weed/

Жалко, что она выложена на какие-то жлобские файлохранилища.
Варез? (украдено у амазона?)

LVV>Всего 100 с небольшим страниц, но написано шикарно!
LVV>Абсолютно без вода, только небольшое введение — и код, код, код...

Вся вода — в коде.

Читать по сто раз один и тот же паттерн хвостовой рекурсии — тоскливо.
Например, очевидно же, что all_of, any_of, none_of отличаются друг от друга только операцией.
И более того, выражаются друг через друга, по правилам де Моргана

template<class It, class Pred>
bool all_of(It begin, It end, Pred&& pred) {
  return begin == end ? true
                      : pred(*begin) && all_of(next(begin), end, pred);
}

template<class It, class Pred>
bool none_of(It begin, It end, Pred&& pred) {
  return all_of(begin, end, not_(pred));
}

template<class It, class Pred>
bool any_of(It begin, It end, Pred&& pred) {
  return !none_of(begin, end, pred);
}

Здравствуйте, cures, Вы писали:

C>Здравствуйте, _hum_, Вы писали:

__>>так не всегда же к хвостовой можно свети — это раз. а во-вторых, если нет гарантии, то код подойдет только для баловства.

C>К хвостовой сводятся только элементарные циклы, это не очень интересно.
CPS же

Здравствуйте, kov_serg, Вы писали:

_>ps: Послушал выступление негра из MS про модули. Это признание в том что они неосилили задачу и скорее всего не осилят, учитывая всё навороты и прибабахи которые хотят отставить в этих модулях.

Наконец, хотя этот предмет не из приятных, я должен упомянуть PL/1, язык программирования, документация которого обладает устрашающими размерами и сложностью. Использование PL/1 больше всего напоминает полет на самолете с 7000 кнопок, переключателей и рычагов в кабине. Я совершенно не представляю себе, как мы можем удерживать растущие программы в голове, когда из-за своей полнейшей вычурности язык программирования — наш основной инструмент, не так ли! — ускользает из-под контроля нашего интеллекта. И если мне понадобится описать влияние, которое PL/1 может оказывать на своих пользователей, ближайшее сравнение, которое приходит мне в голову, — это наркотик. Я помню лекцию в защиту PL/1, прочитанную на симпозиуме по языкам программирования высокого уровня человеком, который представился одним из его преданных пользователей. Но после похвал в адрес PL/1 в течение часа он умудрился попросить добавить к нему около пятидесяти новых "возможностей", не предполагая, что главный источник его проблем кроется в том, что в нем уже и так слишком уж много "возможностей". Выступающий продемонстрировал все неутешительные признаки пагубной привычки, сводящейся к тому, что он впал в состояние умственного застоя и может теперь только просить еще, еще, еще. Если FORTRAN называют детским расстройством, то PL/1, с его тенденциями роста подобно опасной опухоли, может оказаться смертельной болезнью

Э.Дейкстра, Смиренный программист, 1972

Здравствуйте, LaptevVV, Вы писали:

LVV>Абсолютно без вода, только небольшое введение — и код, код, код...
LVV>Уже первая глава — рекурсивная форма стандартных алгоритмов.

Я нет какой-нибудь книжки о том, как использовать стиральную машину для перемешки салатов?

Я к тому, что каждому инструменту свое применение.

Здравствуйте, _hum_, Вы писали:

__>не, я немного про другое — что на с++ рекурсивный подход использовать мало того, что сомнительно по эффективности, так еще и небезопасно по переполнению стека. вот вы знаете, как удостовериться, что размера стека хватит?

Ну вот автор книжки ссылается на фундаментальнейшую теорему "Ей-богу, так!".

The Apple LLVM version 6.1.0 compiler was used to compile the samples in this book using the “-O3” option that includes tail-call optimization.

Такая оптимизация действительно может иметь место, но как удостовериться, что со всей этой рекурсией мы действительно не отстрелим себе ногу, и что делать пользователям других компиляторов — об этом ни слова.

Книга по большей части написана в виде <summary>\r\n<code>.
Лучше бы автор вместо нее просто сделал репозиторий.
И еще бы привел код, использованный для сравнения производительности.
А то все таблица Run-time Results похожа на сравнение порошков.

Здравствуйте, Pzz, Вы писали:

Pzz>Я нет какой-нибудь книжки о том, как использовать стиральную машину для перемешки салатов?
Есть отличное прменение для ультразвуковой стиральной машины в функциональном стиле
http://alkohacker.ru/samy-j-by-stry-j-retsept-samogona-braga-za-1-sutki

Pzz>Я к тому, что каждому инструменту свое применение.
Категорически поддерживаю. Растраивает только то что раньше C++ можно было применить куда угодно,
а теперь С++(n+1) уже даже на winxp не работает и это видимо не предел.
Но у C++ есть очень отличная черта он поддерживает C. А это очень живучий и не требовательный язык.

Здравствуйте, kov_serg, Вы писали:

Pzz>>Я к тому, что каждому инструменту свое применение.
_>Категорически поддерживаю. Растраивает только то что раньше C++ можно было применить куда угодно,
_>а теперь С++(n+1) уже даже на winxp не работает

Работает — используй GCC или Clang, либо настрой MSVS 2015 соответствующим образом — там ЕМНИП загвоздка с используемой версией SDK.

_>и это видимо не предел.

Не надо сгущать краски — это лишь особенность Windows SDK — соответственно и у C те же самые проблемы
C++17, который официально ещё даже не вышел, уже работает даже не древнем железе типа Commodore 64:
https://www.youtube.com/watch?v=zBkNBP00wJE

LVV>>http://www.pdfbooksplanet.org/tags/Chris+Weed/
К>Жалко, что она выложена на какие-то жлобские файлохранилища.
К>Варез? (украдено у амазона?)
Мне знакомый аспирант презентовал.
Могу прислать. На какой ящик?
К>Вся вода — в коде.
К>Читать по сто раз один и тот же паттерн хвостовой рекурсии — тоскливо.
Повторение — мать учения...

LVV>Неистово рекомендую!

Лаптев, эти говно-книги можно читать до бесконечности. Программировать надо а не создавать себе искуственные трудности а затем героически их преодолевать.

_>Вот что меня настораживает так это такие книги. Они решают искуственные проблемы искуствееными методами. И все рады как это круто.

+1.

_>C++ идёт неведомо куда, он создаёт всё новые и новые трудности которые потом пытается преодолеть.

+1 но только он уже там.

Вообще спасибо за сказанное. Понимание оного отличает инженеров от неинженеров.

LVV>>Неистово рекомендую!
ОК>Лаптев, эти говно-книги можно читать до бесконечности. Программировать надо а не создавать себе искуственные трудности а затем героически их преодолевать.
С вами все понятно: че тут думать — трясти надо...

Здравствуйте, Evgeny.Panasyuk, Вы писали:

EP>Здравствуйте, kov_serg, Вы писали:

Pzz>>>Я к тому, что каждому инструменту свое применение.
_>>Категорически поддерживаю. Растраивает только то что раньше C++ можно было применить куда угодно,
_>>а теперь С++(n+1) уже даже на winxp не работает
_>>и это видимо не предел.

EP>Работает — используй GCC или Clang, либо настрой MSVS 2015 соответствующим образом — там ЕМНИП загвоздка с используемой версией SDK.

Вы видимо не в курсе. Вы можете использовать любую SDK. Он работать всё равно не будет.
Линковщик специально не хочет генерировать исполняемые файлы под winxp. И без плясок с бубном в виде editbin не пашет.
Visual Studio 97 win9x+ (в win7 уже не пашет, с надписью имеются известные проблемы и падает при открытии проекта)
Visual Studio 2003 winnt+
Visual Studio 2005,2008 winxp+
Visual Studio 2010-2015 win7+
clang win7+
mingw win7+ -- полностью зависит от msvcrt.dll которая win7+, своих статических библиотек нет. И не будет политика партии запрещает.
cygwin win7+ -- старых репозиториев нет, те что в архивах там нет C++11

http://louis.steelbytes.com/vs2008_vs_win40.html
https://supportxpdotcom.wordpress.com/2012/03/28/what-makes-apps-developed-with-visual-c-11-beta-not-run-on-windows-xp

Если даже вы скажете линковщику хочу winxp от ответит отказом.

/SUBSYSTEM:WINDOWS,4.0 /OSVERSION:4.0 => warning LNK4010: invalid subsystem version number 4.00; default subsystem version assumed
/SUBSYSTEM:WINDOWS,5.01 /OSVERSION:5.1 => warning LNK4010: invalid subsystem version number 5.01; default subsystem version assumed

Пока только editbin помогает, но и его вылечат.
Так что все новые и модные фичи потихоньку выдавливают старые версии винды. С технической стороны никаких проблем
может только с реализацией многопоточности в C++11 на conditional_variables, но можно костыль прикрутить
или просто не многопоточность. Но нет.

Так что, скоро будет только Win10+ к бабке не ходи. Ах да и comodor64.

EP>Не надо сгущать краски — это лишь особенность Windows SDK — соответственно и у C те же самые проблемы
EP>C++17, который официально ещё даже не вышел, уже работает даже не древнем железе типа Commodore 64:
EP>https://www.youtube.com/watch?v=zBkNBP00wJE
Дык при желании можно сделать любую целевую платформу на llvm, но это вам придётся делать самому.
Бинарный код оно генерит, и он спокой но мог бы работать. Но он искуственно сделано так что бы он не работал.
И телеметрия которая появилась в 15 студии — вы просили — нате. Вобщем выглядит это очень весело.
Даже какой нибуть ср$#@й PHP будет хотель win7+. Почему, как вы думаете? Кому-то ведь это надо.

Так что просто попробуйте сами собрать консольный hello_world с лямбдами в 2015 студии и запустить в виртуалке на winxp и прифигеете.

Здравствуйте, мыщъх, Вы писали:

М>а есть _универсальный_ рецепт для си (си++) ?

Его ни для какого языка нет. Дадут тебе платформу, где всей памяти меньше необходимого, и приплыли.

Здравствуйте, Олег К., Вы писали:

LVV>>Неистово рекомендую!

ОК>Лаптев, эти говно-книги можно читать до бесконечности. Программировать надо а не создавать себе искуственные трудности а затем героически их преодолевать.

Им не программировать, им учить (читай — мучить) студентов сиплюсплюсом, который все хочет превратиться в Хаскель.

Здравствуйте, kov_serg, Вы писали:

EP>>Работает — используй GCC или Clang, либо настрой MSVS 2015 соответствующим образом — там ЕМНИП загвоздка с используемой версией SDK.

_>Вы видимо не в курсе. Вы можете использовать любую SDK. Он работать всё равно не будет.
_>Линковщик специально не хочет генерировать исполняемые файлы под winxp. И без плясок с бубном в виде editbin не пашет.
_>Visual Studio 97 win9x+ (в win7 уже не пашет, с надписью имеются известные проблемы и падает при открытии проекта)
_>Visual Studio 2010-2015 win7+

А что, в 2015 Студии Platform toolset уже нет?

	В VS2013 их есть

и оно под ХР таки работает.

Здравствуйте, samius, Вы писали:

S>Здравствуйте, cures, Вы писали:

C>>Здравствуйте, _hum_, Вы писали:

__>>>так не всегда же к хвостовой можно свети — это раз. а во-вторых, если нет гарантии, то код подойдет только для баловства.

C>>К хвостовой сводятся только элементарные циклы, это не очень интересно.
S>CPS же

интересно, спасибо. только по прочтению я все же так и не понял,

существует ли алгоритм преобразования любой чистой рекурсивной функции в функцию с хвостовой рекурсией, причем с ростом накладных расходов на стек у преобразованной функции не более O(размер всех аргументов)?

иными словами, можно ли ожидать, что хороший компилятор (гипотетически) при необходимости всегда может сам преобразовать любую рекурсию в хвостовую?

Здравствуйте, LaptevVV, Вы писали:

LVV>Понятная даже начинающим.

Кстати насчёт понятности.
Вот, например, реализация рекурсивных лямбд.

Внезапная императивность.
1) Создаётся пустая обёртка,
2) затем её копия (!) захватывается лямбдой,
3) затем эту лямбду присваивают исходному (!) экземпляру.

Почему? Ну, мне* понятно, почему. Потому же, почему в ML есть разница между let и let rec.
Только в С++ let rec почти отсутствует, и вот именно здесь мы налетаем на illformed с типами, а если бы не налетели, то налетели бы на undefined со значением.
*) потому что я не начинающий

Внезапные голые указатели на стековые переменные.
Вот тут уже у меня мозг заскрипел. Надо отслеживать корректность времени жизни всех экземпляров обёртки — как оригинального, так и захваченных во всех копиях лямбды.
Ну, скрестим пальцы, что там всё хорошо.

shared_ptr на функцию, скопировавшую лямбду, захватившую обёртку. Что там с кольцевыми ссылками? Мамой клянус?

Наконец, абсолютная беззащитность перед некорректным использованием — как следствие императивности.
Действительно, — стоит нам не присвоить лямбду, или перепутать порядок использования, — и привет.

func_wrapper<void()> f;
switch(rand()%3) {
case 0:
  foo(f,f);
  break;
case 1:
  f = [f]() {};
  foo(f,f);
  break;
case 2:
  foo(f = [f](){}, f);
};

Мне кажется, что вот такие вещи просто обязательно надо раскрывать.


Ну и наконец, старый приём с Y-комбинатором. Собственно, let rec в ML именно так и устроен.

const auto fib = [](int n) {
  const auto f = [](auto&& g, int n) -> int { return n<2 ? n : g(g,n); };  // тип результата невозможно вывести, поэтому указываем явно
  return f(f,n);
};

Здравствуйте, LaptevVV, Вы писали:

К>>Варез? (украдено у амазона?)
LVV>Мне знакомый аспирант презентовал.
LVV>Могу прислать. На какой ящик?

Думаешь, мне богиня программирования нашептала во сне отдельные страницы этой книжки?
Или я всё-таки побрил Оккама и скачал целиком с варезохранилища, попутно заметив ссылку на амазон?

К>>Вся вода — в коде.
К>>Читать по сто раз один и тот же паттерн хвостовой рекурсии — тоскливо.
LVV>Повторение — мать учения...

Ну, методически, оно верно.

Продолжаю вдумчивое чтение.
Вот с мемоизатором комбинатор неподвижной точки удалось сделать. Но как!

struct MyFib { // это важно! именованный класс, а не посторонняя абы какая функция

  // именованный класс потребовался для ручного решения неподвижной точки типа
  int operator()(memoizer<int(int),MyFib>& m, int x) const { 
    return x < 2 ? x : m(x-1) + m(x-2);
  }

  // хотя можно было и отдать это компилятору (но всё равно изолировать через класс)
  template<class M>
  int operator(M&& m, int x) const {.....}

  // раз уж знаем про мемоизатор, то почему бы не сделать членом?
  // раз уж членом, то вспомним про mutable (в книжке забыли)
};
auto my_fib = memoize<int(int)>(MyFib);

Между тем, есть же возможность мемоизировать голые функции

// вот почему нам нужна изоляция через имя: иначе отхватываем рекурсивный тип мемоизатора
int fib_(memoizer<int(int), int(memoizer<int(int), memoizer<.....>)> m, int x) {
  return x<2 ? x : m(x-1) + m(x-2);
}

// попробуем через шаблон:
template<class M> int fib_(M&& m, int x) {.....}
auto fib = memoize<int(int)>(fib_); // так тоже нельзя, шаблон - не первоклассная сущность

// зато предобъявление хорошо работает!
int fib_(int);
auto fib = memoize_nonrecursive<int(int)>(fib_); // первая версия мемоизатора, без неподвижной точки
int fib_(int x) { return x < 2 ? x : fib(x-1) + fib(x-2); }

// то же самое можно и с классом
struct Fib {
  mutable memoizer_nonrecursive_member<int(int),Fib> m_; // сделаем ещё одну версию мемоизатора
  Fib() : m_(wrap{},this) {} // трюк с инициализацией указателем на несозданного самого себя
        { m_.setup(this);  } // (или двухфазную инициализацию сделать...)
  int operator(int x) const {.....};
} fib;

// полиморфные лямбды - в отличие от шаблонов, имеют конкретный тип!
// просто у них operator() шаблонный
auto fib_ = [](auto&& m, int x) -> int { return x < 2 ? x : m(x-1) + m(x-2); };
auto fib = memoize_recursive<int(int)>(fib_);
// или, в одну строку
auto fib = memoize_recursive<int(int)>([](auto&& m, int x) {....});

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

auto fib = fix<int(int)>([](auto&& f, int x) {.....});

Вдогонку про мемоизацию.
С ней связан ряд проблем.

1. Побочные эффекты. Надо сразу договориться, что мемоизируемая функция чиста по входам, и нам пофиг на её побочные плоды.
Ну и тут просто грех не вспомнить ещё об одном декораторе: трассировщике.

Домашнее задание для читателей книги:
— написать декоратор, печатающий входы и результаты вычислений

auto p = memoize(trace("fib", [](auto&& f, int x) {...}));
p(5);

печатает        подразумевается
fib(5) = ... // fib(3)+fib(4)
fib(3) = ... // fib(1)+fib(2)
fib(1) = ...
fib(1) = 1
fib(2) = ... // fib(0)+fib(1)
fib(0) = ...
fib(0) = 0
fib(2) = 1
fib(3) = 2
fib(4) = ... // fib(2)+fib(3)
fib(4) = 3
fib(5) = 5

— декоратор, делающий отступ на глубину рекурсии

fib(5) = ... // fib(3)+fib(4)
  fib(3) = ... // fib(1)+fib(2)
    fib(1) = ...
    fib(1) = 1
    fib(2) = ... // fib(0)+fib(1)
      fib(0) = ...
      fib(0) = 0
    fib(2) = 1
  fib(3) = 2
  fib(4) = ... // fib(2)+fib(3)
  fib(4) = 3
fib(5) = 5

Какие есть способы пропихнуть величину отступа в функцию? (Я навскидку могу предложить три способа, два из которых допиливают мемоизатор, а один — только трассировщика).

2. Управление кэшем. Чтобы он не рос бесконечно, надо предпринимать меры по его очистке.
Это может быть как внешняя операция, строго между вызовами, так и автоматизированная внутренняя, прямо по ходу рекурсивного вызова функции.
(То есть, мы соглашаемся на очень долгую работу функции, но противимся тому, чтобы она случайно выжрала всю память. Время-то у нас — неограниченный ресурс).

3. Зацикливание. Хороший мемоизатор может проверить, что функция не зациклилась.
Для этого надо вести журнал ожидаемых, но ещё не выполненных действий.

4. Многопоточность. Это не только синхронизация доступа к кэшу, но и независимая диагностика зацикливаний для каждого потока отдельно.

Книга — трэш. На серию блог постов с натяжкой потянет.

> Each recursive algorithm was run vs. the STL implementation on a long sequence in a
> vector, list, and set. The following chart shows which algorithm was faster when run with
> a large number of iterations.

Афтар не написал ни каким компилятором, ни на какой платформе, ни с какими флагами оптимизации компилировал, не приводит ни одной тестовой программы, и даже количественых результатов тестов нет, только same/recursive/STL.

U>Афтар не написал ни каким компилятором, ни на какой платформе, ни с какими флагами оптимизации компилировал, не приводит ни одной тестовой программы, и даже количественых результатов тестов нет, только same/recursive/STL.
Написал. Пункт содержания Compiler

Книжка шикарная настолько, что Кодт ее конкретно разбирает...

Здравствуйте, LaptevVV, Вы писали:

LVV>http://www.pdfbooksplanet.org/tags/Chris+Weed/
LVV>Функциональное программирование на С++.
LVV>Chris Weed.
LVV>Всего 100 с небольшим страниц, но написано шикарно!

10x a lot !

Здравствуйте, _hum_, Вы писали:

__>так а это разве правильно — рекурсивная форма алгоритмов на с++? или уже появилась возможность контроля размера стека?

Иногда полезнее не думать о том, правильно что-то или неправильно.
Иногда полезнее просто сделать хоть как-то. "Хоть как-то" -- это означает не тяп-ляп,
а "любая реализация алгоритма".
Это не значит, что программист халтурит. Просто есть такие алгоритмы, которые можно сформулировать
только так, а не иначе.