Re: D in the TIOBE top

[Timon Gehr]

On 09/12/2011 06:57 PM, bearophile wrote:
Timon Gehr:
You lose vs haskell because haskell does not recompute the same PowerSet
multiple times.

Are you sure? I have tried with memoization, but now it's slower (about 5.8 
seconds).

Note: to use memoize I have had to add the opCall. Is this really necessary for 
memoization of a struct?


import std.stdio, std.array, std.range, std.functional;

struct PowerSet(T) {
     T[] items;

     static PowerSet opCall(T[] it) {
         PowerSet p;
         p.items = it;
         return p;
     }

     int opApply(int delegate(ref T[]) dg) {
         int result;
         T[] res;
         T[30] buf;

         if (!items.length) {
             result = dg(res);
         } else {
             outer:
             foreach (opt; [items[0..1], []]) {
                 buf[0 .. opt.length] = opt[];
                 alias memoize!PowerSet mPowerSet;
                 foreach (r; mPowerSet(items[1..$])) {
                     buf[opt.length .. opt.length + r.length] = r[];
                     res = buf[0 .. (opt.length + r.length)];
                     result = dg(res);
                     if (result) break outer;
                 }
             }
         }

         return result;
     }
}

void main() {
     size_t count;
     foreach (x; PowerSet!int(array(iota(22))))
         count++;
     writeln(count);
}


Bye,
bearophile

std.functional.memoize uses AAs internally, so that is very slow.

Haskell builds a linked data structure, if you have

result: [...,[2,3],[1,2,3]]

then the [2,3] part is exactly the same for both. Also, if you only look 
at the length, the haskell code probably does not fully evaluate the 
power set.