memoize

[Guilherme Vieira]

On Tue, Jan 4, 2011 at 4:30 AM, Guilherme Vieira <n2.nitrogen at gmail.com>wrote:

> On Tue, Jan 4, 2011 at 3:27 AM, Andrei Alexandrescu <
> SeeWebsiteForEmail at erdani.org> wrote:
>
>> On 1/3/11 11:01 PM, Guilherme Vieira wrote:
>>
>>> On Tue, Jan 4, 2011 at 2:50 AM, Nick Sabalausky <a at a.a> wrote:
>>>
>>>    "Andrei Alexandrescu" <SeeWebsiteForEmail at erdani.org
>>>    <mailto:SeeWebsiteForEmail at erdani.org>> wrote in message
>>>
>>>    news:ifu70u$2dvs$1 at digitalmars.com...
>>>     >I just added a higher-order function memoize to std.functional which
>>> I
>>>     >think is pretty cool. See the docs here:
>>>     >
>>>     >
>>>
>>> http://d-programming-language.org/cutting-edge/phobos/std_functional.html#memoize
>>>     >
>>>     > I'm also thinking of adding that cutting-edge directory as a
>>>    place for
>>>     > storing documentation for commits that are in flux but not
>>> officially
>>>     > released yet.
>>>     >
>>>     >
>>>     > Andrei
>>>
>>>    Neat! This is a great example of why D kicks so much ass :)
>>>
>>>
>>> Uh, yes. It looks like the kind of thing I would do, show to others and
>>> hear they say "Meh.. Whatever". I'm really exponentially developing a
>>> liking to the D community, even though I didn't event get to code
>>> anything serious yet.
>>>
>>> This simply rocks. Keep it up, Andrei!
>>>
>>> --
>>> Atenciosamente / Sincerely,
>>> Guilherme ("n2liquid") Vieira
>>>
>>
>> Glad you folks like it. There's a little story behind this. I first read
>> Dominus' book chapter years ago, around the time I'd decided to write TDPL.
>> Back then I was thinking - it would just be so cool to be able to define
>> generic memoization in D. I tried my hand at an implementation. But D had no
>> tuples, no aliasing for functions, no good variadics, and even if you could
>> find a way to pack parameters, associative arrays had plenty of related
>> issues.
>>
>> I'd given up on that and forgot most about it, until today. It was nice to
>> reckon that getting it done took about a dozen lines and about as many
>> minutes. We really have come a very long way.
>>
>> Nevertheless, I found two issues: one, ParameterTypeTuple doesn't work for
>> overloaded functions, and associative arrays don't work for ubyte[4] keys...
>> still a ways to go.
>>
>>
>> Andrei
>>
>
> Is there really need for ParameterTypeTuple? I figured this works:
>
>  template memoize(alias fun, uint maxSize = uint.max)
>
> {
>
>     auto memoize(Args...)(Args args)
>
>     {
>
>         static typeof(fn(args))[Tuple!(typeof(args))] memo;
>
>         auto t = tuple(args);
>
>         auto p = t in memo;
>
>         if (p) return *p;
>
>         static if (maxSize != uint.max)
>
>         {
>
>             if (memo.length >= maxSize) memo = null;
>
>         }
>
>         auto r = fun(args);
>
>         //writeln("Inserting result ", typeof(r).stringof, "(", r, ") for
>> parameters ", t);
>
>          memo[t] = r;
>
>         return r;
>
>     }
>
> }
>
>
> --
> Atenciosamente / Sincerely,
> Guilherme ("n2liquid") Vieira
>

Dirty fix for the ubyte[4] problem:

struct wrapper(T)

{

    this(T value) { this.value = value; }

    T value;

}


> template memoize(alias fun, uint maxSize = uint.max)

{

    auto memoize(Args...)(Args args)

    {

        static wrapper!(typeof(fn(args)))[Tuple!(typeof(args))] memo;

        auto t = tuple(args);

        auto p = t in memo;

        if (p) return p.value;

        static if (maxSize != uint.max)

        {

            if (memo.length >= maxSize) memo = null;

        }

        auto r = fun(args);

        //writeln("Inserting result ", typeof(r).stringof, "(", r, ") for
> parameters ", t);

        memo[t] = wrapper!(typeof(fn(args)))(r);

        return r;

    }

}


But I think I get why ParameterTypeTuple is important. My version of the
template give ugly error messages when I call a memoized function with the
wrong parameter types. ParameterTypeTuple would make them go away, right?

-- 
Atenciosamente / Sincerely,
Guilherme ("n2liquid") Vieira
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.puremagic.com/pipermail/digitalmars-d/attachments/20110104/fa152e7b/attachment-0001.html>