[erlang-questions] behavior of funktions

[Paul Mineiro]

To summarize a previous thread, using the y combinator one can make a
generic memoization routine in Erlang, which can be used with different
recursive functions.

Attached is an example with fib.

-- p


On Mon, 23 Jul 2007, Christian S wrote:

> A good example is probably this erlang implementation of fibonacci:
>
> fib(0) -> 0;
> fib(1) -> 1;
> fib(N) -> fib(N-1) + fib(N-2).
>
> Pretty much verbatim from http://en.wikipedia.org/wiki/Fibonacci_number
>
> If you call f(10), it will in turn call f(9) and f(8), and f(9) will
> call f(8) (again) and f(7), it then continues like this. A whole lot
> of redundant computations to get values we already
> computed once.
>
> Erlang does nothing to help you here, the number of calls to compute
> f(N) will be
> (2^N)-1 and most of them redundant. Adding 'memoization' explicitly to
> cache the values of
> f(N) isnt that easy in Erlang, if you still want to have
> pretty/clear/succinct code.
>
> 2007/7/23, Johannes <dajo.mail@REDACTED>:
> > i never thought of not-side-effect-free functions in that case ;)
> > maybe i chosed a bad example.
> > My question is, if there is a function, wich is called more than one
> > time with the same arguments, how often is it evaluated(not 'called')?
> > it's clear, that a its impossible to save all function results the whole
> > time a programm is running, but how is it for example in a rekursion ??
> _______________________________________________
> erlang-questions mailing list
> erlang-questions@REDACTED
> http://www.erlang.org/mailman/listinfo/erlang-questions
>

"A hot dog and bun, you have to have a style and strategy that's
different from a chicken wing, which is different from a matzo ball,"
he says. "Athletics are not really about superior fitness. They're about
superior refinement of skill. That's what Babe Ruth did. That's what
this is."

http://en.wikipedia.org/wiki/Competitive_eating
-------------- next part --------------
-module (memo).
-export ([y/1, memoize/1, fib/1]).

y (F) -> F (fun (X) -> (y (F)) (X) end).

memoize (Tab, F) ->
  fun (B) ->
    fun (C) ->
      case ets:lookup (Tab, C) of
        [] ->
          R = (F (B)) (C),
          ets:insert (Tab, { C, R }),
          R;
        [ { C, R } ] ->
          R
      end
    end
  end.

memoize (F) ->
  fun (X) ->
    Tab = ets:new (?MODULE, [ private ]),
    Ans = (y (memoize (Tab, F))) (X),
    ets:delete (Tab),
    Ans
  end.

fibimpl (P) ->
  fun (0) -> 1;
      (1) -> 1;
      (N) when N > 1 -> P (N - 1) + P (N - 2)
  end.

fib (N) -> (memoize (fun fibimpl/1)) (N).