Теперь про то, как ставятся задачи в упомянутом SICP. Там потребность в обобщении актуализируется с самого начала. То есть, сначала обучаемому показывают механизмы абстракции, а потом неявно подталкивают к обобщениям, заставляя решать родственные задачи. Причём делают это мягко и намёками, так, чтобы внимательный ученик сам почувствовал подвох и задумался над более общим решением.
Возвращаясь к примеру. В SICP похожая задача задаётся в следующем контексте: есть потоки (streams), которые суть отложенные вычисления с мемоизацией. То есть, это как бы обычные списки, но хвост списка вычисляется только по необходимости (и результат запоминается). Таким образом, если мы хотим получить только первых 10 элементов списка, то и вычислим только 10. Ленивые вычисления позволяют задавать бесконечные структуры, которые незамедлительно используются в "математических" целях: скажем, задаётся список integers, потенциально содержащий "все целые числа" (на самом же деле - содержит лишь обещание предоставить каждое следующее число по требованию).
Далее, над потоками вводится ряд операций, позволяющих довольно широкий спектр манипуляций. Чтобы не вдаваться в подробности, просто приведу текст двух заданий, поскольку речь ведь о постановке задач, а не о частных абстракциях:
Упражнение 3.71.
Числа, которые можно выразить в виде суммы двух кубов более, чем одним способом, иногда называют числами Рамануджана (Ramanujan numbers), в честь математика Шринивасы Рамануджана. Упорядоченные потоки пар предлагают изящное решение для задачи порождения таких чисел. Чтобы найти число, которое можно двумя разными способами записать в виде суммы двух кубов, требуется только породить поток пар натуральных чисел (i, j), взвешенных согласно сумме i^3 + j^3, и искать в этом потоке две пары подряд с одинаковым весом.
Напишите процедуру для порождения чисел Рамануджана. Первое такое число 1729. Каковы следующие пять?
Упражнение 3.72.
Используя метод, подобный описанному в упражнении 3.71, породите поток всех чисел, которые можно записать как сумму двух квадратов тремя различными способами (и покажите, каковы эти способы).
Как я говорил раньше, упражнение 3.72 является вариацией на тему задания топикстартера. Только тут всё повёрнуто другой стороной: требуется породить упорядоченный по весу поток пар и отфильтровать его таким образом, чтобы остались только те пары, значение суммы квадратов которых встречается трижды во всём (бесконечном) потоке.
В общем, легко заметить, что задача 72 аналогична задаче 71 за исключением того, что требуется найти не "двухкратное и более" вхождение пар с одним весом, а строго трёхкратное; а также, в качестве функции веса (то есть, упорядочивающей функции) используется не сумма кубов, а сумма квадратов. По-моему, намёк на то, "а нельзя ли это как-нибудь обобщить?" - весьма явный. Речь, разумеется, не об обобщении, связанном с весами, - оно к этому моменту уже существует. А о том, чтобы находить числа, представляемые k способами или k+ способами.
Намёк становится ещё более явным именно от такой постановки задачи - обработка списков-потоков. Ведь вытащить два элемента из головы и сравнить - это ещё куда ни шло (кстати, решение отчасти ошибочно, поскольку потенциально может приводить к дублированию результата).
Но решать задачу "найти ровно три вхождения" - означает, вытаскивать до 4х элементов из потока. Выглядит уж очень ненатурально и "дубово".
