It seems people (Andrei too) are slowly adding more comments in that Reddit
thread.
A sub-thread:
http://www.reddit.com/r/programming/comments/kaxjq/the_d_programming_language_is_back_in_tiobes_top/c2iycwb
It starts with this question:
> How would you write this kind of Python in D?
>
> from struct import Struct
> def decode(buf):
> while buf:
> s = Struct(buf[0])
> val, = s.unpack(buf[1 : 1 + s.size])
> yield val
> buf = buf[1 + s.size:]
>
> Or this:
>
> def powerset(items):
> if not items:
> yield []
> return
> item, rest = items[0], items[1:]
> for opt in [[item], []]:
> for r in powerset(rest):
> yield opt + r
>
> btw, I like Haskell even more, and in it, the latter example is:
>
> powerset [] = return []
> powerset (x:xs) = do
> o <- [[x], []]
> r <- powerset xs
> return $ o ++ r
>
> Or, you can re-use the filterM function, and get:
>
> powerset = filterM (\x -> [True,False])
This is the lazy Haskell program, it's not so basic as it looks:
powerset [] = return []
powerset (x:xs) = do
o <- [[x], []]
r <- powerset xs
return $ o ++ r
main = print $ powerset [1, 2, 3]
It outputs:
[[1,2,3],[1,2],[1,3],[1],[2,3],[2],[3],[]]
The second Haskell version of the same program:
import Control.Monad (filterM)
powerset = filterM (\x -> [True,False])
main = print $ powerset [1, 2, 3]
An eager D version, with arrays:
import std.stdio: writeln;
auto powerSet(T)(T[] items) {
auto r = new T[][](1, 0);
foreach (e; items) {
T[][] rs;
foreach (x; r)
rs ~= x ~ [e];
r ~= rs;
}
return r;
}
void main() {
writeln(powerSet([1, 2, 3]));
}
That outputs:
[[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]
The lazyness has some advantages. If I call the D version with:
writeln(powerSet(array(iota(22))).length);
And the Haskell version with:
main = print $ length $ powerset [0..21]
The D code (GHC -O3) takes 9.7 seconds and 430 MB RAM
The Haskell code takes about 1.8 seconds and less than 200 MB of RAM.
The second Haskell version (with filterM) takes about 2.4 seconds and about 240
MB RAM.
A lazy D version:
import std.stdio, std.array, std.range;
struct PowerSet(T) {
T[] items;
int opApply(int delegate(ref T[]) dg) {
int result;
T[] res;
if (!items.length) {
result = dg(res);
} else {
outer:
foreach (opt; [items[0..1], []])
foreach (r; PowerSet(items[1..$])) {
res = opt ~ r;
result = dg(res);
if (result) break outer;
}
}
return result;
}
}
void main() {
// can't use this because the silly walkLength()
// doesn't recognize opApply yet:
// http://d.puremagic.com/issues/show_bug.cgi?id=5691
//writeln(walkLength(PowerSet!int(array(iota(22)))));
size_t count;
foreach (x; PowerSet!int(array(iota(22))))
count++;
writeln(count);
}
The lazy D version runs in about 22 seconds, using less than 10 MB. DMD
performs no advanced lazy optimizations here.
A more complex version that does't yield distinct sub-arrays to allocate less
memory:
import std.stdio, std.array, std.range;
struct PowerSet(T) {
T[] items;
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[];
foreach (r; PowerSet(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);
}
This runs in about 4.5 seconds, and uses less than 10 MB RAM.
With the syntax sugar I have suggested here:
http://d.puremagic.com/issues/show_bug.cgi?id=5660
the recursive lazy D version becomes something like this, that is not too much
bad looking (untested):
yield(T[]) powerSet(T)(T[] items) {
if (!items.length)
yield [];
else
foreach (opt; [items[0..1], []])
foreach (r; powerSet(items[1..$]))
yield opt ~ r;
}
Bye,
bearophile
