Re: Using local variable for memoizing in recursion

[Karim Belabas <Karim.Belabas@math.u-bordeaux.fr>]

* Дмитрий Рыбас [2019-07-15 09:24]:
> As it appered that I did not subscribe (sent request to the wrong address),
> I couldn't answer...
> 
> Well, going back to memoizing, Bill wrote:
> 
> You can use local():
> 
> p(n,k)=
> {
>   local(M=Map());
>   memo_p(n,k);
> }
> 
> Using local() is partial solution: one has to use the same (shared) name of
> variable in both calling and called functions. Is it possible to declare
> local variable in function a() and somehow pass it's name (or other
> reference) to function b() ?

Starting from version 2.12 you can use a call by reference with container
arguments:

  memo_p(~M, n, k) =  \\ notice the 'tilde', M is modified in place
  ...

  p(n,k)=
  {
    my(M = Map());
    memo_p(~M, n,k); \\ notice the 'tilde' in the caller
  }

> Or better, somehow put recursive function b() inside function a() that
> creates map, calls recursive function and the destroys everything except
> returned result?

This is much more cumbersome, but can be made to work:

  a(n,k) =
  {
    my(M = Map());
    my(b = (N,K)-> my(z); if(mapisdefined(M,[N,K],&z),return(z));
                   self()(N-1,K-1)); \\ self() is used for a recursive call
    b(n,k);
  }

Note that the closure b() has access to variable M which is lexically scoped
to a()'s body. For clarity, I defined b() with two parameters N,K, but it
also had access to n,k from the argument list of a(). So I could equally
have used

    my(b = ()->...);
    b();

self() is necessary to define an anonymous recursive function [ we can't use
b() for the recursive call because the closure is not yet assigned to b ]

Cheers,

    K.B.
--
Karim Belabas, IMB (UMR 5251)  Tel: (+33) (0)5 40 00 26 17
Universite de Bordeaux         Fax: (+33) (0)5 40 00 21 23
351, cours de la Liberation    http://www.math.u-bordeaux.fr/~kbelabas/
F-33405 Talence (France)       http://pari.math.u-bordeaux.fr/  [PARI/GP]
`