memoize

[Guilherme Vieira]

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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.puremagic.com/pipermail/digitalmars-d/attachments/20110104/dbbaa587/attachment-0001.html>