Функциональные языки и поддержка memoization
Какая-либо текущая обрезка популярных функциональных языков имеет хорошую поддержку memoization и если бы я должен был выбрать один на основании его memoisation, который Вы рекомендовали бы и почему?
Обновление: я надеюсь оптимизировать ориентированного графа (где узлы могли быть функциями или данными). Когда узел в графике обновляется, я хотел бы, чтобы значения других узлов были повторно вычислены, только если они зависят узел, который изменился.
Update2: потребуйте свободного или языка/времени выполнения с открытым исходным кодом.
3 ответа
Для Haskell Конал Эллиот опубликовал прекрасную запись в блоге о попытках функциональных записок . Работа необычайно умная и довольно глубокая, и позже Конал распространил ее на полиморфные функции . Независимо от того, какой язык вы используете, этот материал настоятельно рекомендуется, потому что он раскрывает глубокие идеи , лежащие в основе мемоизации функциональных языков.
Однако, глядя на ваше обновление, неясно, действительно ли мемоизация - это то, что вам нужно. Ваша расширенная постановка задачи (распространение обновлений через ориентированный граф) является почти учебным примером инкрементных вычислений , над которыми большая работа была проделана Бобом Харпером и Умутом Акаром . Я считаю, что у них есть бесплатная библиотека, написанная на Standard ML. Посмотрите страницу Умута о самонастраивающихся вычислениях .
Для начала см. this на Haskell.
Для Лиспа этот был первым хитом от Google, который выглядел релевантным.
Для F # этот может быть хорошим местом для начала.
Теперь я закончил поиск в Google. Есть ли у этого хорошая поддержка ? Вы решаете: -)
О, я бы порекомендовал Mathematica, но я понимаю, что многих отталкивает ее цена. Строго говоря, это, вероятно, больше система переписывания терминов, чем система функционального программирования, и она не чиста ни в каком смысле этого слова. Но это действительно мемоизация.
РЕДАКТИРОВАТЬ: Я забыл об Erlang, который сейчас очень популярен - я не знаю, как, но я ожидаю, что он может выполнять запоминание.
Да, вам вообще не нужна мемоизация, вам нужно точное отслеживание зависимостей. Вы можете использовать библиотеку функциональных графов Haskell (fgl) для создания графа, ориентированного на ur, а затем использовать функцию-преемник, чтобы точно знать какие узлы обновлять: http://hackage.haskell.org/cgi-bin/hackage-scripts/package/fgl
Этот документ очень поможет мне понять документацию: {{1 }} http://web.engr.oregonstate.edu/~erwig/fgl/
В модуле Data.Graph.Inductive.Graph функция-преемник называется Succ
Пойдем в другом направлении, одним из популярных функциональных языков, поддерживающих эту функцию, является Excel. :)