Pure functional

Хаскелл же

но вообще-то мемоизация доступна наверное на любом языке.

maple имеет такую опцию, хоть оно и не pure functional.

Хаскелль хаскеллем... Предлагаю закончить теории и обговорить практику. Умеет ли хаскелль это на самом деле? Или если это надо отдельно включать, то как? Нагуглить тяжело, так как вопрос поставить не получается. Вот предлагаю пообщаться.

Да куча.

Даже в Perl есть модуль memoize. И да, он работает на практике :)

Кажись даже в хаскелле нельзя делать это автоматически. Вручную могу и в С. И без всякого pure functional. Если вручую, то я сам могу знать, что оно без побочных эффектов. Даже с ними могу иногда такое реализовать

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

Это одно

Теория теорией, но какие реализации/языки этим реально пользуются? Например на каких языках можно написать рекурсивную функцию Фибоначчи в лоб и ожидать что оно будет работать эффективно, не перевычислять заново значения.

.. а это совсем другое

Как вариант можно помолиться на опцию -fipa-pure-const. Но боги GCC так непостоянны.

SICP, упражнение 3.27

(define (memoize f)
  (let ((table (make-table)))
    (lambda (x)
      (let ((previously-computed-result (lookup x table)))
        (or previously-computed-result
            (let ((result (f x)))
              (insert! x result table)
              result))))))

Определения make-table, lookup и insert! смотрите там же, а лучше не смотрите, а напишите их сами, ибо элементарно.

> Хаскелл же

Интересно, а что делать если одна функция у меня «a -> a», а другая «a -> b -> b»? Статическая типизация тут только мешается.

> Интересно, а что делать если одна функция у меня «a -> a», а другая «a -> b -> b»? Статическая типизация тут только мешается.

http://www.haskell.org/haskellwiki/Memoization

vertexua, нагуглить почему-то не тяжело:

http://www.haskell.org/pipermail/haskell-cafe/2008-January/038009.html

О! Есть знаете какие интересные примеры использования мемоизации, например, во время синтаксического анализа.

Из простого для реализации, но трудоёмкого алгоритма, например Эрли, при помощи мемоизации получают эффективный алгоритм.

Пример в работе Питера Норвига - вот только забыл как называется.

даже на tcl это можно делать:
http://wiki.tcl.tk/10779

А как автоматический мемоизатор (кстати, ничего общего с pure functional) поймёт, что запоминать результаты функции A - полезно, а функции B - вредно? Например функцию A будут постоянно вызывать с разными значениями в пределах всей области определения (профит), а функцию B вызовет один раз какой-нибудь любитель для значения 1000.000.000, при этом будет зря израсходована память на целых 999.999.999 значений. Т.е. мемоизатору нужно хотя бы директива - мол эту функцию мемоизировать, где-то вроде была (или планировалась) библиотека на TH в которой есть макрос $(memoize ...).

http://www.haskell.org/haskellwiki/Memoization

Ну «memoFix :: ((a -> b) -> (a -> b)) -> a -> b», конечно, никуда не годится - если у функции параметром больше, то придётся ещё один вариант функции реализовывать. Действительно красив только локальный вариант:

memoized_fib :: Int -> Integer
memoized_fib =
   let fib 0 = 0
       fib 1 = 1
       fib n = memoized_fib (n-2) + memoized_fib (n-1)
   in  (map fib [0 ..] !!)

P.S. Даёшь подсветку для хаскелла! :)

> А как автоматический мемоизатор (кстати, ничего общего с pure functional) поймёт, что запоминать результаты функции A - полезно, а функции B - вредно?

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

Меркурий: [code] :- func fib(int) = int.

fib(N) = (N > 1 ->     fib(N - 1) + fib(N - 2);     N     ).

:- pragma memo(fib/1). [/code]

Меркурий:

:- func fib(int) = int.

fib(N) = (N > 1 ->
	   fib(N - 1) + fib(N - 2);
	   N
	  ).

:- pragma memo(fib/1).

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

s/ой «макрос»/ую функцию/

>B вызовет один раз какой-нибудь любитель для значения 1000.000.000, при этом будет зря израсходована память на целых 999.999.999 значений.

не знаешь что такое ассоциативный массив?

не знаешь что такое ассоциативный массив?

Не понял, при чём тут это? В этом трэде речь, в общем, о двух подходах к вычислению - straight computation когда вычисление представляется своим алгоритмом (энергичным/ленивым, не важно) с той или иной сложностью и каждый раз совершается снова; и memoization когда сначала всё считается (досчитывается) и в дальнейшем обеспечивается O(1) доступ к результатам. Понятно что в первом случае будет меньший расход по памяти (а относительно до/после - нулевой расход, т.к. все промежуточные результаты убираются вручную или сборщиком) и большие затраты на время вычисления, во втором случае - наоборот, уже вычисленные значения не нужно повторно вычислять, но, понятное дело, нужно их где-то хранить. При мемоизации рекурсивной функции будет возникать ситуация накапливания предыдущих результатов (если только не удалять предыдущие не соседние (в смысле рекурсии) результаты, что не очень хорошо) - расходования памяти.

А выбор между двумя подходами зависит от харрактера функции и должен делаться руками.

Вы не понимаете сути мемоизации.

ой, сорри:( это не вам хотел написать.

>Вы не понимаете сути мемоизации. точно, ступил