Функциональная альтернатива кешированию известных «ответов»

Question

Я думаю, что лучший способ сформировать этот вопрос - это пример ... так что фактическая причина, по которой я решил спросить об этом, из-за Problem 55 on Project Euler. В этой проблеме он просит найти число Лычелских чисел ниже 10 000. На императивном языке я бы получил список чисел, ведущих к окончательному палиндрому, и надавил эти числа на список вне моей функции. Затем я проверял каждый входящий номер, чтобы узнать, является ли он частью этого списка, и если да, просто прекратите тест и сделайте вывод, что число не является числом Лычреля. Я бы сделал то же самое с номерами, отличными от лихреля, и их предыдущими числами.

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

Мне просто интересно, есть ли какой-то инструмент, который мне не хватает здесь, или существуют ли какие-либо стандарты в качестве способа сделать это? Я читал, что Haskell вроде «естественно кэширует» (например, если бы я хотел определить нечетные числа как odds = filter odd [1..], я мог бы ссылаться на это, когда захочу, но, похоже, он усложняется, когда мне нужно динамически добавлять элементы в список

Любые предложения о том, как решить эту

Благодаря

PS:.?. Я не прошу ответа на задачи проекта Эйлера, я просто хочу, чтобы узнать Haskell в бит лучше!

Answer 1

Я считаю, что вы ищете memoizing. Есть несколько способов сделать это. Один довольно простой способ - это пакет MemoTrie. Альтернативно, если вы знаете, что ваш входной домен является ограниченным набором чисел (например, [0,10000)), вы можете создать массив, в котором значения будут являться результатом вашего вычисления, а затем вы можете просто индексировать в массив с вашим вводом. Подход Array не будет работать для вас, хотя, хотя ваши входные номера ниже 10 000, последующие итерации могут тривиально увеличиваться более чем на 10 000.

Сказав это, когда я решил проблему 55 в Haskell, я вообще не делал никаких заметок. Он оказался достаточно быстрым, чтобы запустить (до) 50 итераций на всех входных номерах. Фактически, запуск этого сейчас занимает 0,2 секунды для завершения работы на моей машине.