On Tue, Jan 4, 2011 at 4:30 AM, Guilherme Vieira <[email protected]>wrote:
> On Tue, Jan 4, 2011 at 3:27 AM, Andrei Alexandrescu < > [email protected]> wrote: > >> On 1/3/11 11:01 PM, Guilherme Vieira wrote: >> >>> On Tue, Jan 4, 2011 at 2:50 AM, Nick Sabalausky <[email protected]> wrote: >>> >>> "Andrei Alexandrescu" <[email protected] >>> <mailto:[email protected]>> wrote in message >>> >>> news:[email protected]... >>> >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
