LINUX.ORG.RU

Pure functional


0

1

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

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

★★★★★

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

korvin_ ★★★★★ ()

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

anonymous ()
Ответ на: комментарий от korvin_

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

vertexua ★★★★★ ()
Ответ на: комментарий от JackYF

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

vertexua ★★★★★ ()

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

Это одно

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

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

addewyd ()

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

pathfinder ★★★★ ()

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! смотрите там же, а лучше не смотрите, а напишите их сами, ибо элементарно.

mix_mix ★★★★★ ()
Ответ на: комментарий от korvin_

> Хаскелл же

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

mix_mix ★★★★★ ()
Ответ на: комментарий от mix_mix

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

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

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

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

korvin_ ★★★★★ ()
Ответ на: комментарий от mix_mix

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

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

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

anonymous ()

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

quasimoto ★★★★ ()
Ответ на: комментарий от korvin_

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. Даёшь подсветку для хаскелла! :)

mix_mix ★★★★★ ()
Ответ на: комментарий от quasimoto

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

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

mix_mix ★★★★★ ()

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

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

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

anonymous ()
Ответ на: комментарий от anonymous

Меркурий:

:- func fib(int) = int.

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

:- pragma memo(fib/1).

anonymous ()
Ответ на: комментарий от mix_mix

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

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

korvin_ ★★★★★ ()
Ответ на: комментарий от quasimoto

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

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

kyz ()
Ответ на: комментарий от kyz

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

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

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

quasimoto ★★★★ ()
Ответ на: комментарий от quasimoto

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

anonymous ()
Ответ на: комментарий от anonymous

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

kyz ()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.