Функциональные языки и поддержка memoization

Какая-либо текущая обрезка популярных функциональных языков имеет хорошую поддержку memoization и если бы я должен был выбрать один на основании его memoisation, который Вы рекомендовали бы и почему?

Обновление: я надеюсь оптимизировать ориентированного графа (где узлы могли быть функциями или данными). Когда узел в графике обновляется, я хотел бы, чтобы значения других узлов были повторно вычислены, только если они зависят узел, который изменился.

Update2: потребуйте свободного или языка/времени выполнения с открытым исходным кодом.

13
задан Joel 8 March 2010 в 14:54
поделиться

3 ответа

Для Haskell Конал Эллиот опубликовал прекрасную запись в блоге о попытках функциональных записок . Работа необычайно умная и довольно глубокая, и позже Конал распространил ее на полиморфные функции . Независимо от того, какой язык вы используете, этот материал настоятельно рекомендуется, потому что он раскрывает глубокие идеи , лежащие в основе мемоизации функциональных языков.

Однако, глядя на ваше обновление, неясно, действительно ли мемоизация - это то, что вам нужно. Ваша расширенная постановка задачи (распространение обновлений через ориентированный граф) является почти учебным примером инкрементных вычислений , над которыми большая работа была проделана Бобом Харпером и Умутом Акаром . Я считаю, что у них есть бесплатная библиотека, написанная на Standard ML. Посмотрите страницу Умута о самонастраивающихся вычислениях .

7
ответ дан 2 December 2019 в 00:31
поделиться

Для начала см. this на Haskell.

Для Лиспа этот был первым хитом от Google, который выглядел релевантным.

Для F # этот может быть хорошим местом для начала.

Теперь я закончил поиск в Google. Есть ли у этого хорошая поддержка ? Вы решаете: -)

О, я бы порекомендовал Mathematica, но я понимаю, что многих отталкивает ее цена. Строго говоря, это, вероятно, больше система переписывания терминов, чем система функционального программирования, и она не чиста ни в каком смысле этого слова. Но это действительно мемоизация.

РЕДАКТИРОВАТЬ: Я забыл об Erlang, который сейчас очень популярен - я не знаю, как, но я ожидаю, что он может выполнять запоминание.

4
ответ дан 2 December 2019 в 00:31
поделиться

Да, вам вообще не нужна мемоизация, вам нужно точное отслеживание зависимостей. Вы можете использовать библиотеку функциональных графов 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. :)

3
ответ дан 2 December 2019 в 00:31
поделиться
Другие вопросы по тегам:

Похожие вопросы: