## digitalmars.D - Huffman coding comparison

bearophile <bearophileHUGS lycos.com> writes:
```Now and then it's very useful to compare how to write in D2 a small interesting
program written in another language, the comparison can help find problems,
possible improvements, performance problems, and so on.

Time ago I have tried to convert to D2 a small Python program that finds the
Huffman encoding of a given string, but Phobos2 was not mature enough, and I
didn't produce a good enough D2 program. I have tried again and this time
things are good enough.

The original Python code comes from the rosettacode site (that contains
comparisons of many different programs implemented in many different
languages), the point of the Python version is not performance, but to show
elegant & compact code (there are ways to write this code shorter in Python but
this code must has to be readable, it's not a code golf site).

This the Python 2.x version:

from heapq import heappush, heappop, heapify
from collections import defaultdict

def encode(symb2freq):
"""Huffman encode the given dict mapping symbols to weights"""
heap = [[float(wt), [sym, ""]] for sym, wt in symb2freq.iteritems()]
heapify(heap)
while len(heap) > 1:
lo = heappop(heap)
hi = heappop(heap)
for pair in lo[1:]:
pair[1] = '0' + pair[1]
for pair in hi[1:]:
pair[1] = '1' + pair[1]
heappush(heap, [lo[0] + hi[0]] + lo[1:] + hi[1:])
return sorted(heappop(heap)[1:], key=lambda p: (len(p[1]), p))

txt = "this is an example for huffman encoding"
symb2freq = defaultdict(int)
for ch in txt:
symb2freq[ch] += 1
huff = encode(symb2freq)
print "Symbol\tWeight\tHuffman Code"
for p in huff:
print "%s\t%s\t%s" % (p[0], symb2freq[p[0]], p[1])

It contains a demo string, and it prints (tabs set to 4 spaces):

Symbol  Weight  Huffman Code
6   101
n   4   010
a   3   1001
e   3   1100
f   3   1101
h   2   0001
i   3   1110
m   2   0010
o   2   0011
s   2   0111
g   1   00000
l   1   00001
p   1   01100
r   1   01101
t   1   10000
u   1   10001
x   1   11110
c   1   111110
d   1   111111

After few experiments I have produced this working D2 version that uses just
Phobos2:

import std.stdio, std.algorithm, std.typecons;

/// Huffman encode the given dict mapping symbols to weights
auto encode(TFreq, TSymb)(TFreq[TSymb] symb2freq) {
alias Tuple!(TSymb, "symb", string, "code") Pair;
alias Tuple!(TFreq, "freq", Pair[], "pairs") Block;
Block[] blocks;
foreach (symb, freq; symb2freq)
blocks ~= Block(freq, [Pair(symb, "")]);
auto heap = BinaryHeap!(Block[], "b < a")(blocks);

while (heap.length > 1) {
auto lo = heap.pop(1)[0];
auto hi = heap.pop(1)[0];
foreach (ref pair; lo.pairs)
pair.code = '0' ~ pair.code;
foreach (ref pair; hi.pairs)
pair.code = '1' ~ pair.code;
heap.push(Block(lo.freq + hi.freq, lo.pairs ~ hi.pairs));
}
auto r = heap.pop(1)[0].pairs;
schwartzSort!((x){ return x.code.length; })(r);
return r;
}

void main() {
auto txt = "this is an example for huffman encoding";
int[char] symb2freq;
foreach (c; txt)
symb2freq[c]++;
auto huff = encode(symb2freq);
writeln("Symbol\tWeight\tHuffman Code");
foreach (p; huff)
writefln("%s\t%s\t%s", p.symb, symb2freq[p.symb], p.code);
}

That prints:

Symbol  Weight  Huffman Code
n   4   010
6   101
a   3   1001
e   3   1100
o   2   0011
i   3   1110
h   2   0001
f   3   1101
s   2   0111
m   2   0010
t   1   10000
g   1   00000
r   1   01101
p   1   01100
l   1   00001
u   1   10001
x   1   11110
d   1   111111
c   1   111110

Some notes (later I can send them to Andrei):

The D2 version is longer, but this size difference can be acceptable. The D2
version looks good enough (this is just a small test program. In a real D2
unittests, and when it's necessary I try to write more efficient code).

It is not fully equivalent to the Python version, to print the same thing the
Schwartz sorting has to use  (x){return tuple(x.code.length, x);}.

For me for one thing the D program is better than the Python version: the
Python std lib doesn't define a mutable named tuple like that one in D2 (there
is only one immutable and dynamically typed one), this forces the Python code
to use all those [0] and [1:]. Anonymous structures sometimes make Python code
shorter, but they can be less explicit too. Of course it's easy to define in
Python a function like Tuple of Phobos2 that accepts optional field names too.

The "std.typecons" module, that contains Tuple and tuple can be named something
simpler to remember as "std.tuples".

I will keep missing array comprehensions in D. In the meantime other languages
have got some forms of them (but Python ones use the best syntax still).

In translating the program I have not found significant problems. The only bug
I have found was caused by the different ordering of the Python/Phobos2 heaps,
so I have had to use "b<a" in D2. This is not a bug, but I have to keep it in
mind in future usages of heaps across the two languages. I don't know why the
two languages have chosen different orderings here, if someone of you knows I'd
like to know it.

Another small problem I have found was caused by BinaryHeap.pop(). I'd like it
to pop and return a single item, instead of an array of given length of items,
because this is done quite more often than popping many items. If the need to
pop many items is important, then a different method can be defined, as npop().

Maybe BinaryHeap can be moved to the collections module.

array(map(...)) is so common that an amap(...) can be considered.

A helper function like this one can be useful:
auto binaryHeap(alias less="a < b", Range)(Range items) {
return BinaryHeap!(Range, less)(items);
}
Note that the 'less' is before the Range, so in that program you can write:
auto heap = binaryHeap!("b < a")(s2w);
auto heap = BinaryHeap!(Block[], "b < a")(s2w);
And in many cases you just write:
auto heap = binaryHeap(items);

I have seen that this doesn't work, but something like this can be useful (but
I am not sure, I don't love strings used this way):
schwartzSort!("a.code.length")(r);

In Python there is both list.sort() and sorted(), the second creates a new
list. In my dlibs1 I have similar functions. They allow you to write:
return schwartzSorted!((x){ return x.code.length; })(...items);
auto r = ...items;
schwartzSort!((x){ return x.code.length; })(items);
return items;
So I'd like sorted and schwartzSorted in Phobos2.

While debugging this program I have found that array(iota(0, 10)) is an uint[]
instead of being an int[]. In most cases I prefer that syntax to produce an
array of true ints. In the uncommon situations when I want an array of uints I
can ask it with a syntax like array(iota(0U, 10U)). If this specification is
not possible then I prefer iota to always yield signed values, because they are
much *safer* in D.

I'd like iota(100) to be the same as iota(0, 100), as in the Python range().

To improve a *lot* my debugging in code like this I'd like this line of code:
writeln(tuple(['x': 1.0, 'y': 2.0], "hello", [[1, 2], [3, 4]]));
To print (better):
tuple(['x': 1.0, 'y': 2.0], "hello", [[1, 2], [3, 4]])
Or even:
Tuple!(double[char], string, int[][])(['x': 1.0, 'y': 2.0], "hello", [[1, 2],
[3, 4]])
Tuple!(double[char],string,int[][])([x:1, y:2], hello, 1 2 3 4)

Note that the double 1.0 is printed on default with a leading zero to denote
it's a floating point, the string if inside a collection is printed with "" on
its sides, the char inside '' (just like the way you have to write them in the
D code), the arrays with [] and commas, and associative arrays have a bit more

From various D2 programs I have seen that I usually don't need the full type of
the tuple in the printout, they clutter the printing too much. For example if
you try to print the 'heap' variable inside the encode() function just before
the return you get the following text, this is too much noisy and unreadable
(notice a funny detail, strings are correctly printed inside "" if they are
tuple field names!):

BinaryHeap!(Tuple!(double,"freq",Tuple!(char,"c",string,"code")[],"pairs")[],"b
< a")(1, Tuple!(double,"freq",Tuple!(char,"c",string,"code")[],"pairs")(39,
Tuple!(char,"c",string,"code")(g, 00000) Tuple!(char,"c",string,"code")(l,
00001) Tuple!(char,"c",string,"code")(h, 0001)
Tuple!(char,"c",string,"code")(m, 0010) Tuple!(char,"c",string,"code")(o, 0011)
Tuple!(char,"c",string,"code")(n, 010) Tuple!(char,"c",string,"code")(p, 01100)
Tuple!(char,"c",string,"code")(r, 01101) Tuple!(char,"c",string,"code")(s,
0111) Tuple!(char,"c",string,"code")(t, 10000)
Tuple!(char,"c",string,"code")(u, 10001) Tuple!(char,"c",string,"code")(a,
1001) Tuple!(char,"c",string,"code")( , 101) Tuple!(char,"c",string,"code")(e,
1100) Tuple!(char,"c",string,"code")(f, 1101) Tuple!(char,"c",string,"code")(i,
1110) Tuple!(char,"c",string,"code")(x, 11110)
Tuple!(char,"c",string,"code")(c, 111110) Tuple!(char,"c",string,"code")(d,
111111)) Tuple!(double,"freq",Tuple!(char,"c",string,"code")[],"pairs")(16,
Tuple!(char,"c",string,"code")(g, 00000) Tuple!(char,"c",string,"code")(l,
00001) Tuple!(char,"c",string,"code")(h, 0001)
Tuple!(char,"c",string,"code")(m, 0010) Tuple!(char,"c",string,"code")(o, 0011)
Tuple!(char,"c",string,"code")(n, 010) Tuple!(char,"c",string,"code")(p, 01100)
Tuple!(char,"c",string,"code")(r, 01101) Tuple!(char,"c",string,"code")(s,
0111)) Tuple!(double,"freq",Tuple!(char,"c",string,"code")[],"pairs")(11,
Tuple!(char,"c",string,"code")(t, 0000) Tuple!(char,"c",string,"code")(u, 0001)
Tuple!(char,"c",string,"code")(a, 001) Tuple!(char,"c",string,"code")( , 01))
Tuple!(double,"freq",Tuple!(char,"c",string,"code")[],"pairs")(8,
Tuple!(char,"c",string,"code")(g, 0000) Tuple!(char,"c",string,"code")(l, 0001)
Tuple!(char,"c",string,"code")(h, 001) Tuple!(char,"c",string,"code")(m, 010)
Tuple!(char,"c",string,"code")(o, 011))
Tuple!(double,"freq",Tuple!(char,"c",string,"code")[],"pairs")(6,
Tuple!(char,"c",string,"code")(e, 00) Tuple!(char,"c",string,"code")(f, 01))
Tuple!(double,"freq",Tuple!(char,"c",string,"code")[],"pairs")(5,
Tuple!(char,"c",string,"code")(t, 000) Tuple!(char,"c",string,"code")(u, 001)
Tuple!(char,"c",string,"code")(a, 01))
Tuple!(double,"freq",Tuple!(char,"c",string,"code")[],"pairs")(4,
Tuple!(char,"c",string,"code")(n, 0))
Tuple!(double,"freq",Tuple!(char,"c",string,"code")[],"pairs")(4,
Tuple!(char,"c",string,"code")(g, 000) Tuple!(char,"c",string,"code")(l, 001)
Tuple!(char,"c",string,"code")(h, 01))
Tuple!(double,"freq",Tuple!(char,"c",string,"code")[],"pairs")(3,
Tuple!(char,"c",string,"code")(i, 0))
Tuple!(double,"freq",Tuple!(char,"c",string,"code")[],"pairs")(3,
Tuple!(char,"c",string,"code")(e, 0))
Tuple!(double,"freq",Tuple!(char,"c",string,"code")[],"pairs")(2,
Tuple!(char,"c",string,"code")(t, 00) Tuple!(char,"c",string,"code")(u, 01))
Tuple!(double,"freq",Tuple!(char,"c",string,"code")[],"pairs")(2,
Tuple!(char,"c",string,"code")(p, 00) Tuple!(char,"c",string,"code")(r, 01))
Tuple!(double,"freq",Tuple!(char,"c",string,"code")[],"pairs")(2,
Tuple!(char,"c",string,"code")(m, 0))
Tuple!(double,"freq",Tuple!(char,"c",string,"code")[],"pairs")(2,
Tuple!(char,"c",string,"code")(g, 00) Tuple!(char,"c",string,"code")(l, 01))
Tuple!(double,"freq",Tuple!(char,"c",string,"code")[],"pairs")(1,
Tuple!(char,"c",string,"code")(x, 0))
Tuple!(double,"freq",Tuple!(char,"c",string,"code")[],"pairs")(1,
Tuple!(char,"c",string,"code")(t, 0))
Tuple!(double,"freq",Tuple!(char,"c",string,"code")[],"pairs")(1,
Tuple!(char,"c",string,"code")(p, 0))
Tuple!(double,"freq",Tuple!(char,"c",string,"code")[],"pairs")(1,
Tuple!(char,"c",string,"code")(g, 0))
Tuple!(double,"freq",Tuple!(char,"c",string,"code")[],"pairs")(1,
Tuple!(char,"c",string,"code")(c, 0)))

This is what Python prints in the same situation, it's more readable for my
eyes (but this is not a fair comparison, in D the structures are Tuples with
named fields, and so on):

[[39.0, ['g', '00000'], ['l', '00001'], ['h', '0001'], ['m', '0010'], ['o',
'0011'], ['n', '010'], ['p', '01100'], ['r', '01101'], ['s', '0111'], ['t',
'10000'], ['u', '10001'], ['a', '1001'], [' ', '101'], ['e', '1100'], ['f',
'1101'], ['i', '1110'], ['x', '11110'], ['c', '111110'], ['d', '111111']]]

The purpose of this program was to be short and "elegant". To test the
performance I have replaced in both programs the input text with something that
contains one hundred thousand different symbols.

Python:
txt = range(10000) + range(10000) + range(100000)

D2:
auto txt = array(iota(0, 10000)) ~ array(iota(0, 10000)) ~ array(iota(0,
100000));

The timings, seconds:
Python:       2.98
Python+Psyco: 2.84
D2:           1.97

In this benchmark most of the running time is spent inside the encode(), the
creation of symb2freq takes 0.05-0.16 seconds.

Bye,
bearophile
```
May 28 2010
Leandro Lucarella <llucax gmail.com> writes:
```bearophile, el 28 de mayo a las 18:01 me escribiste:
For me for one thing the D program is better than the Python version:
the Python std lib doesn't define a mutable named tuple like that one in
D2 (there is only one immutable and dynamically typed one), this forces
the Python code to use all those [0] and [1:]. Anonymous structures
sometimes make Python code shorter, but they can be less explicit too.
Of course it's easy to define in Python a function like Tuple of Phobos2
that accepts optional field names too.

Just for fun :)

def NamedTuple(*fields):
class T:
def __init__(self, *args):
for i in range(len(args)):
setattr(self, fields[i], args[i])
return T

Pair = NamedTuple("symb", "code")
Block = NamedTuple("freq", "pair")
p = Pair(1, 2)
b = Block(3, p)
print p.symb, p.code, b.freq, b.pair.symb, b.pair.code

I will keep missing array comprehensions in D. In the meantime other
languages have got some forms of them (but Python ones use the best
syntax still).

They are wonderful, and it's *very* hard to get used to live in a language
that doesn't support them once you start using it often.

PS: Sorry about the Python-love mail... =P

--
Leandro Lucarella (AKA luca)                     http://llucax.com.ar/
----------------------------------------------------------------------
GPG Key: 5F5A8D05 (F8CD F9A7 BF00 5431 4145  104C 949E BFB6 5F5A 8D05)
----------------------------------------------------------------------
"Lidiar" no es lo mismo que "holguear"; ya que "lidiar" es relativo a
"lidia" y "holguear" es relativo a "olga".
-- Ricardo Vaporeso
```
May 28 2010
bearophile <bearophileHUGS lycos.com> writes:
```Leandro Lucarella:

def NamedTuple(*fields):
class T:
def __init__(self, *args):
for i in range(len(args)):
setattr(self, fields[i], args[i])
return T

That's not enough, those tuples must support the cmp for the heap.

This barely works, but it's not good code yet:

def NamedTuple(*fields):
class Foo:
def __init__(self, *args):
for field, arg in zip(fields, args):
setattr(self, field, arg)
def __cmp__(self, other):
return cmp([getattr(self, f) for f in fields],
[getattr(other, f) for f in fields])
return Foo

Bye,
bearophile
```
May 28 2010
"Simen kjaeraas" <simen.kjaras gmail.com> writes:
```bearophile <bearophileHUGS lycos.com> wrote:

I will keep missing array comprehensions in D. In the meantime other
languages have got some forms of them (but Python ones use the best
syntax still).

I'm now so tired of hearing this, I started writing something that
does it:

auto r = list!"2 * a" | [1,2,3,4,5] & where!"a & 1" );

Takes any kind of range, and list and where are basically map and

Now, granted, I have little to no experience with list comprehension,
and as such this might not be what is needed. Still, it was fun to
play around with, and I kinda like what it turned out as.

import std.algorithm;
import std.range;
import std.array;

struct listImpl( alias pred ) {
auto opBinary( string op : "|", Range )( Range other ) {
return map!pred(other);
}
}

struct whereImpl( alias pred ) {
auto opBinaryRight( string op : "&", R )( R range ) {
return filter!pred(range);
}
}

property
whereImpl!pred where( alias pred )( ) {
whereImpl!pred result;
return result;
}

property
listImpl!pred list( alias pred )( ) {
listImpl!pred result;
return result;
}

unittest {
assert( equal( list!"2 * a" | [1,2,3,4,5] & where!"a & 1", [2,6,10] )
);
assert( equal( list!"2 * a" | [1,2,3], [2,4,6] ) );
}

--
Simen
```
May 28 2010
bearophile <bearophileHUGS lycos.com> writes:
```Simen kjaeraas:

I'm now so tired of hearing this, I started writing something that
does it:

Array comprehensions are syntax sugar. From what I have seen there is a very
narrow range of usable syntaxes for them. Outside that range, they get much
less useful or useless. Even Haskell has got them sub-quality.

At first sight they seem just able to allow you write one line of code instead
of three or four, so no big deal. In practice they allow the programmer to turn
those three lines of code into a single chunk. So the programmer can grasp and
think about more code at the same time. This improves programming.

The word 'chunk' comes from mind sciences, it's the thing referred to in the
famous "The Magical Number Seven, Plus or Minus Two", those are numbers of
chunks.
http://en.wikipedia.org/wiki/Chunking_%28psychology%29

Eventually Walter will understand that. Walter is sometimes slow in improving
his understanding of things, but he never stops moving forward: I think his
meta-learning capabilities are not high, but they are present and they are
higher than most of other people you find around (that often have near zero
meta-learning capabilities) :-)

Bye,
bearophile
```
May 28 2010
Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
```On 05/30/2010 10:27 AM, Simen kjaeraas wrote:
Philippe Sigaud <philippe.sigaud gmail.com> wrote:

That's fun to see, the syntax is cool. I never thought of using operator

I just had a look at Wikipedia's article on it, found that the syntax was
'hey, that's neat'. Just wish I could use curly brackets around it, but
parentheses work:

{ 2·x | x ∈ N, x² > 3 }
=>
( list!"2*a" | iota(1,int.max) * where!"x^^2 > 3" )

I did a range comprehension also, a few months ago. It's called comp in
http://svn.dsource.org/projects/dranges/trunk/dranges/docs/algorithm2.html

Like yours, it takes any range and is lazy, the main difference it
that it's
multirange: you can give it any number of range as input, it will
create the
combinations of elements (aka product of ranges), filter it with the
predicate and map the generative function on it.

auto pyth(int n)
{
return comp ! ("tuple(a,b,c)", "a*a+b*b==c*c && a<b")
(iota(1,n),iota(1,n), iota(1,n));
}

This reminded me that Phobos lacks a combinatorial range, taking two or
more (forward) ranges and giving all combinations thereof:

combine([0,1],[2,3])
=>
(0,2), (0,3), (1,2), (1,3)

Work has commenced on implementing just that.

Yah, that would be useful. If Philippe agrees to adapt his work, maybe
that would be the fastest route. And don't forget - the gates of Phobos
are open.

Andrei
```
May 30 2010
bearophile <bearophileHUGS lycos.com> writes:
```Andrei Alexandrescu:
And don't forget - the gates of Phobos are open.<

My original post contains numerous notes and annotations, I was about to send
it to you through email. You can think about reading it and thinking abut the
things I have written regarding Phobos2.

Bye,
bearophile
```
May 30 2010
Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
```On 05/30/2010 04:43 PM, Philippe Sigaud wrote:
On Sun, May 30, 2010 at 19:01, Simen kjaeraas <simen.kjaras gmail.com
<mailto:simen.kjaras gmail.com>> wrote:

Andrei Alexandrescu <SeeWebsiteForEmail erdani.org
<mailto:SeeWebsiteForEmail erdani.org>> wrote:

This reminded me that Phobos lacks a combinatorial range,
taking two or
more (forward) ranges and giving all combinations thereof:

combine([0,1],[2,3])
=>
(0,2), (0,3), (1,2), (1,3)

Work has commenced on implementing just that.

Yah, that would be useful. If Philippe agrees to adapt his work,
maybe that would be the fastest route. And don't forget - the
gates of Phobos are open.

Too late for that, as I've already written this. :p

Hey, cool, lots of static foreach. Man, it's like I'm reading my own
code. I'm happy to see convergent evolution: this must be the D way to
do this.

Current problems: back and popBack not implemented. I'm not sure they
even should be. Doing so would be a tremendous pain the region below the
spine.

Ow.
I *guess* it's doable, but I for sure don't want to do it.

May very well be there are other problems, I don't know. If anyone finds

Well, I like the way you dealt with popFront.  You length is more costly
than mine, but I cheated: I count the numbers of popFronts and substract
them from the original length.

Your empty use .length in the foreach loop. You should use .empty
instead, I think. And with an infinite range in the mix, the resulting
product is infinte also, so you can define your combine to be infinite.

Then I can give you something to munch over :-)

When one range is infinite, the resulting combination is infinite.
What's sad is that you'll never 'traverse' the infinite range:
auto c = combine([0,1,2], cycle([2,3,4]));
->
(0,2),(0,3),(0,4),(0,2),(0,3), ...

You never reach the (1,x) (2,x) parts, as it should be seeing how we
both defined combinations: iterating on the ranges as if they were
digits in a number.

But there is another way to iterate: diagonally, by cutting successive
diagonal slices:

c is:
(0,2),(0,3),(0,4),(0,2),...
(1,2),(1,3),(1,4),(1,2),...
(2,2),(2,3),(2,4),(2,2),...
->

(0,2),(0,3)(1,2),(0,4),(1,3),(2,2) ...

It's even better if all ranges are infinite.
I never coded this, but it seems doable for two ranges. Lot thougher for
any number of ranges... Pretty obscure, maybe?

btw, I think we should divert this discussion in another thread if you
wish to continue: this is bearophile's Huffman thread, after all.

Yah, there's no argument that infinite ranges must be allowed by a n-way
cross-product. It reminds one of Cantor's diagonalization, just in
several dimensions. Shouldn't be very difficult, but it only works if
all ranges except one are forward ranges (one can be an input range).

Andrei
```
May 30 2010
Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
```On 05/31/2010 08:07 PM, Simen kjaeraas wrote:
Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> wrote:

Yah, there's no argument that infinite ranges must be allowed by a
n-way cross-product. It reminds one of Cantor's diagonalization, just
in several dimensions. Shouldn't be very difficult, but it only works
if all ranges except one are forward ranges (one can be an input range).

Might I coerce you into indulging some more detail on this idea? I'm
afraid my knowledge of the diagonal method is sadly lacking, and some
reading on the subject did not give me satisfactory understanding of
its application in the discussed problem.

Way I thought of doing it is save the highest position this far of each
range, then in popFront see if we're past it. If we are, reset this
range, and pop from the next range up, recursively.

interesting than I thought.

Cantor enumerated rational numbers the following way: first come all
fractions that have numerator + denominator = 1. That's only one
rational number, 1/1. Then come all fractions that have num + denom = 2.
That gives 1/2 and 2/1. Then come all fractions that have num + denom =
3, and so on.

Using this enumeration method he proved that rational numbers are
countable so in some way they are not more "numerous" than natural
numbers, which was an important result.

With ranges, the trick should be similar: although individual ranges may
be infinite, they are composed in a simple, countable manner.

Generalizing Cantor's enumeration technique to n ranges, note that the
enumeration goes through elements such that the sum of their offsets
from the beginning of the ranges is constant.

So for two ranges, we first select pairs that have their offsets sum to
0. That is (0, 0). Then we select pairs of offsets summing to 1: (0, 1)
and (1, 0). Then same for 2: (0, 2), (1, 1), (2, 0). And so on.

The problem is that in order to make sure offsets are constant, forward
ranges are not enough. If all ranges involved had random access, the
problem would be trivially solvable. The trick is pushing that envelope;
for example, it's possible to make things work with one forward range
and one random-access range, and so on.

This is bound to be an interesting problem. Please discuss any potential
solutions here.

Andrei
```
May 31 2010
Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
```On 05/31/2010 08:54 PM, Andrei Alexandrescu wrote:
On 05/31/2010 08:07 PM, Simen kjaeraas wrote:
Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> wrote:

Yah, there's no argument that infinite ranges must be allowed by a
n-way cross-product. It reminds one of Cantor's diagonalization, just
in several dimensions. Shouldn't be very difficult, but it only works
if all ranges except one are forward ranges (one can be an input range).

Might I coerce you into indulging some more detail on this idea? I'm
afraid my knowledge of the diagonal method is sadly lacking, and some
reading on the subject did not give me satisfactory understanding of
its application in the discussed problem.

Way I thought of doing it is save the highest position this far of each
range, then in popFront see if we're past it. If we are, reset this
range, and pop from the next range up, recursively.

interesting than I thought.

Cantor enumerated rational numbers the following way: first come all
fractions that have numerator + denominator = 1. That's only one
rational number, 1/1. Then come all fractions that have num + denom = 2.
That gives 1/2 and 2/1. Then come all fractions that have num + denom =
3, and so on.

I'm off by one there, but you got the idea :o).

Andrei
```
May 31 2010
Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
```On 05/31/2010 10:51 PM, Simen kjaeraas wrote:
Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> wrote:

interesting than I thought.

Cantor enumerated rational numbers the following way: first come all
fractions that have numerator + denominator = 1. That's only one
rational number, 1/1. Then come all fractions that have num + denom =
2. That gives 1/2 and 2/1. Then come all fractions that have num +
denom = 3, and so on.

Using this enumeration method he proved that rational numbers are
countable so in some way they are not more "numerous" than natural
numbers, which was an important result.

With ranges, the trick should be similar: although individual ranges
may be infinite, they are composed in a simple, countable manner.

Generalizing Cantor's enumeration technique to n ranges, note that the
enumeration goes through elements such that the sum of their offsets
from the beginning of the ranges is constant.

So for two ranges, we first select pairs that have their offsets sum
to 0. That is (0, 0). Then we select pairs of offsets summing to 1:
(0, 1) and (1, 0). Then same for 2: (0, 2), (1, 1), (2, 0). And so on.

The problem is that in order to make sure offsets are constant,
forward ranges are not enough. If all ranges involved had random
access, the problem would be trivially solvable. The trick is pushing
that envelope; for example, it's possible to make things work with one
forward range and one random-access range, and so on.

This is bound to be an interesting problem. Please discuss any
potential solutions here.

All forward ranges should be doable, too.

How would the spanning strategy work for two forward infinite ranges?

Andrei
```
Jun 01 2010
Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
```On 06/01/2010 09:23 AM, Simen kjaeraas wrote:
Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> wrote:

All forward ranges should be doable, too.

How would the spanning strategy work for two forward infinite ranges?

In a complex, horrible way?

0. Save initial states (position = 0)
1. Pop first until past the position of the other
2. Restore other
3. Pop other until past the position of the first
4. Restore first
6. Goto 1.

Screw that, as you cannot save positions. Well, I guess a long should
be enough for most, but it might not be. As long as there is no way
to compare positions, 'tis unpossible.

If we accept saving the position (the number of pops), this approach
should be applicable to any number of ranges.

It's ok to store positions in ulong objects. Most uses of infinite range
combinations use only the first few elements; the computation will
anyway take a very, very long time when any of the ranges overflows a ulong.

That being said, I didn't understand the algorithm. What is its
complexity? From what I understand there's a lot of looping going on. We
need something that makes progress in O(1).

Andrei
```
Jun 01 2010
Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
```Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit

On 06/01/2010 11:34 AM, Simen kjaeraas wrote:
Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> wrote:

On 06/01/2010 09:23 AM, Simen kjaeraas wrote:
Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> wrote:

All forward ranges should be doable, too.

How would the spanning strategy work for two forward infinite ranges?

In a complex, horrible way?

0. Save initial states (position = 0)
1. Pop first until past the position of the other
2. Restore other
3. Pop other until past the position of the first
4. Restore first
6. Goto 1.

Screw that, as you cannot save positions. Well, I guess a long should
be enough for most, but it might not be. As long as there is no way
to compare positions, 'tis unpossible.

If we accept saving the position (the number of pops), this approach
should be applicable to any number of ranges.

It's ok to store positions in ulong objects. Most uses of infinite
range combinations use only the first few elements; the computation
will anyway take a very, very long time when any of the ranges
overflows a ulong.

With the algorithm (attempted) explained above, it's actually 2^128, which
is acceptably high, I think.

That being said, I didn't understand the algorithm. What is its
complexity? From what I understand there's a lot of looping going on.
We need something that makes progress in O(1).

Should be O(1). Each pop in the described algorithm is a call to popFront:

void popFront( ) {
ranges[active].popFront;
position[active]++;
if (position[active] > position[inactive]) {
active = !active;
position[active] = 0;
ranges[active] = savedRange[active];
}
}

I still haven't understood your explanation, but I think I figured a
different way to reach the same solution. The idea is to crawl the space
by adding layers on top of a hypercube of increasing side, starting from
the origin corner.

This is an absolutely awesome problem. I attach an implementation for
two ranges. It's quite a bit more messy than I'd hope, so generalization
to n ranges should be preceded by cleaning up the abstractions used. I

The output of the program is:

0	Tuple!(uint,uint)(0, 0)
1	Tuple!(uint,uint)(0, 1)
2	Tuple!(uint,uint)(1, 1)
3	Tuple!(uint,uint)(1, 0)
4	Tuple!(uint,uint)(0, 2)
5	Tuple!(uint,uint)(1, 2)
6	Tuple!(uint,uint)(2, 2)
7	Tuple!(uint,uint)(2, 0)
8	Tuple!(uint,uint)(2, 1)
9	Tuple!(uint,uint)(0, 3)
10	Tuple!(uint,uint)(1, 3)
11	Tuple!(uint,uint)(2, 3)
12	Tuple!(uint,uint)(0, 4)
13	Tuple!(uint,uint)(1, 4)
14	Tuple!(uint,uint)(2, 4)

Andrei
```
Jun 01 2010
Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
```On 06/01/2010 04:06 PM, Steven Schveighoffer wrote:
On Tue, 01 Jun 2010 13:54:01 -0400, Andrei Alexandrescu
<SeeWebsiteForEmail erdani.org> wrote:

The output of the program is:

0 Tuple!(uint,uint)(0, 0)
1 Tuple!(uint,uint)(0, 1)
2 Tuple!(uint,uint)(1, 1)
3 Tuple!(uint,uint)(1, 0)
4 Tuple!(uint,uint)(0, 2)
5 Tuple!(uint,uint)(1, 2)
6 Tuple!(uint,uint)(2, 2)
7 Tuple!(uint,uint)(2, 0)
8 Tuple!(uint,uint)(2, 1)
9 Tuple!(uint,uint)(0, 3)
10 Tuple!(uint,uint)(1, 3)
11 Tuple!(uint,uint)(2, 3)
12 Tuple!(uint,uint)(0, 4)
13 Tuple!(uint,uint)(1, 4)
14 Tuple!(uint,uint)(2, 4)

It looks like you're missing some iterations there.

-Steve

There should be 5 * 3 = 15 iterations.

Andrei
```
Jun 01 2010
Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
```On 06/01/2010 04:20 PM, Steven Schveighoffer wrote:
On Tue, 01 Jun 2010 17:12:29 -0400, Andrei Alexandrescu
<SeeWebsiteForEmail erdani.org> wrote:

On 06/01/2010 04:06 PM, Steven Schveighoffer wrote:
On Tue, 01 Jun 2010 13:54:01 -0400, Andrei Alexandrescu
<SeeWebsiteForEmail erdani.org> wrote:

The output of the program is:

0 Tuple!(uint,uint)(0, 0)
1 Tuple!(uint,uint)(0, 1)
2 Tuple!(uint,uint)(1, 1)
3 Tuple!(uint,uint)(1, 0)
4 Tuple!(uint,uint)(0, 2)
5 Tuple!(uint,uint)(1, 2)
6 Tuple!(uint,uint)(2, 2)
7 Tuple!(uint,uint)(2, 0)
8 Tuple!(uint,uint)(2, 1)
9 Tuple!(uint,uint)(0, 3)
10 Tuple!(uint,uint)(1, 3)
11 Tuple!(uint,uint)(2, 3)
12 Tuple!(uint,uint)(0, 4)
13 Tuple!(uint,uint)(1, 4)
14 Tuple!(uint,uint)(2, 4)

It looks like you're missing some iterations there.

-Steve

There should be 5 * 3 = 15 iterations.

Oh, I didn't realize the input was not two infinite ranges. I was
looking at this as the first 15 lines from the output of 2 infinite
ranges. I expected to see (3, 0), (3, 1), (3, 2), and (3, 3).

-Steve

Funniest thing is the infinite ranges code was _much_ easier to get
right. I got it rolling in a few minutes. It was the limit conditions
for the finite ranges that killed me.

Andrei
```
Jun 01 2010
Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
```On 06/01/2010 04:20 PM, Philippe Sigaud wrote:
On Tue, Jun 1, 2010 at 23:12, Andrei Alexandrescu
<SeeWebsiteForEmail erdani.org <mailto:SeeWebsiteForEmail erdani.org>>
wrote:

On 06/01/2010 04:06 PM, Steven Schveighoffer wrote:

It looks like you're missing some iterations there.

-Steve

There should be 5 * 3 = 15 iterations.

Andrei

The example is:

auto c = xproduct(iota(3), iota(5));

so the first index only goes from 0 to 2.

Philippe

And by the way, I added the feature that will ease bearophile's coding
by one order of magnitude: iota with one argument.

Andrei
```
Jun 01 2010
bearophile <bearophileHUGS lycos.com> writes:
```Andrei Alexandrescu:
And by the way, I added the feature that will ease bearophile's coding
by one order of magnitude: iota with one argument.

Thank you. There's a long way to go still :o)

Bye,
bearophile
```
Jun 01 2010
bearophile <bearophileHUGS lycos.com> writes:
```Philippe Sigaud:
What, do you also need the no-arg version of iota?

:-p

I'd like a generator (range) similar to the Python itertools.count, that yields
numbers starting from the given number (defaulting to zero) and just goes on
and on. You can use it in many situations:
http://docs.python.org/library/itertools.html#itertools.count

Bye,
bearophile
```
Jun 02 2010
Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
```On 06/02/2010 02:29 PM, Philippe Sigaud wrote:
On Wed, Jun 2, 2010 at 19:57, bearophile <bearophileHUGS lycos.com
<mailto:bearophileHUGS lycos.com>> wrote:

Philippe Sigaud:
> What, do you also need the no-arg version of iota?
>
> :-p

I'd like a generator (range) similar to the Python itertools.count,
that yields numbers starting from the given number (defaulting to
zero) and just goes on and on. You can use it in many situations:
http://docs.python.org/library/itertools.html#itertools.count

Yes, it's handy. It's one of the first range I made, a year ago.

iota(n, n.max) is close. Well, it's not infinite, but cycle(iota(n,
n.max)) is. Probably a version using BigInt would be most sensible.

Andrei
```
Jun 02 2010
bearophile <bearophileHUGS lycos.com> writes:
```Andrei Alexandrescu:
iota(n, n.max) is close. Well, it's not infinite, but cycle(iota(n,
n.max)) is. Probably a version using BigInt would be most sensible.

An enumerate() too can be useful (not much tested yet):

import std.range: isForwardRange, hasLength, isBidirectionalRange, ElementType;
import std.typecons: Tuple;
import std.array: front, back, empty, popFront, popBack;

/// ...
struct Enumerate(R) if (isForwardRange!R) {
alias Tuple!(size_t, "index", ElementType!R, "item") TPair;
R _range;
size_t _index;
static if (isBidirectionalRange!R && hasLength!R)
immutable size_t _originalEnd;

this(R input) {
_range = input;
static if (isBidirectionalRange!R && hasLength!R)
_originalEnd = _range.length - 1;

}

/// Range primitive implementations.
ref TPair front() {
return TPair(_index, _range.front());
}

/// Ditto
bool empty() {
return _range.empty();
}

/// Ditto
void popFront() {
_range.popFront();
_index++;
}

static if (isBidirectionalRange!R && hasLength!R) {
/// Ditto
ref TPair back() {
return TPair(_originalEnd + _index, _range.back());
}
}

static if (isBidirectionalRange!R && hasLength!R) {
/// Ditto
void popBack() {
_range.popBack();
_index--;
}
}

static if (hasLength!R) {
/// Ditto
property auto length() {
return _range.length;
}
}
}

/// Ditto
Enumerate!R enumerate(R)(R input) if (isForwardRange!R) {
return Enumerate!R(input);
}

import std.stdio: write, writeln;

void main() {
string[] arr = ["y", "n", "y", "n", "y"];

foreach (el; enumerate(arr))
write(el, " ");
writeln("\n");

foreach_reverse (el; enumerate(arr))
write(el, " ");
writeln("\n");
}

I don't know if a reverse iteration on an enumerate can be useful.

-----------------------

I have used that to try to implement in D2 this Python code:

arr = ["y", "n", "y", "n", "y"]
[i for i,el in enumerate(arr) if el == "y"]

This is a basic D version, Appender not used:

import std.stdio: writeln;

void main() {
// input data
string[] arr = ["y", "n", "y", "n", "y"];

//
int[] indexes;
foreach (i, item; arr)
if (item == "y")
indexes ~= i;
writeln(indexes);
writeln();
}

-----------------------

This is a more functional quite bad-looking D2 version, that doesn't work (see
http://d.puremagic.com/issues/show_bug.cgi?id=4264 ):

import std.stdio: writeln;
import std.algorithm: filter, array, map;

void main() {
// input data
string[] arr = ["y", "n", "y", "n", "y"];

auto r1 = filter!((p){ return p.item == "y"; })(enumerate(arr));
auto r2 = map!((p){ return p.index; })(r1);
writeln(array(r2));
}

Bye,
bearophile
```
Jun 02 2010
Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
```On 06/02/2010 07:24 PM, bearophile wrote:
Andrei Alexandrescu:
iota(n, n.max) is close. Well, it's not infinite, but cycle(iota(n,
n.max)) is. Probably a version using BigInt would be most sensible.

An enumerate() too can be useful (not much tested yet):

No need to write enumerate() - it's zip(iota(0, size_t.max), r).

Andrei
```
Jun 02 2010
bearophile <bearophileHUGS lycos.com> writes:
```Andrei Alexandrescu:
No need to write enumerate() - it's zip(iota(0, size_t.max), r).

What does it happen if someone gives you the sequence produced by:
zip(r, iota(0, size_t.max))
?
You have can require an adaptor because it's not the standard convention.
While enumerate() always gives you indexes at the first place. And the
index/item fields have a standard name that you remember in your code.

Finding the minimal number of pieces to do something is useful, but sometimes
if an operation is common enough it can be useful to give it a new name. It's
called chunking.

Inside an expression that can contain other stuff do you prefer to use:
zip(iota(0, size_t.max), items)
or
enumerate(items)
?
The second makes the expression shorter and more readable in its purpose.

Bye,
bearophile
```
Jun 02 2010
Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
```On 06/02/2010 08:04 PM, bearophile wrote:
Andrei Alexandrescu:
No need to write enumerate() - it's zip(iota(0, size_t.max), r).

What does it happen if someone gives you the sequence produced by:
zip(r, iota(0, size_t.max))
?
You have can require an adaptor because it's not the standard convention.
While enumerate() always gives you indexes at the first place. And the
index/item fields have a standard name that you remember in your code.

Finding the minimal number of pieces to do something is useful, but sometimes
if an operation is common enough it can be useful to give it a new name. It's
called chunking.

Inside an expression that can contain other stuff do you prefer to use:
zip(iota(0, size_t.max), items)
or
enumerate(items)
?
The second makes the expression shorter and more readable in its purpose.

Bye,
bearophile

My point was that there's no need to sit down and implement
functionality. Just write

auto enumerate(R)(R r) if (isInputRange!R)
{
return zip(iota(0, size_t.max), r);
}

Andrei
```
Jun 02 2010
bearophile <bearophileHUGS lycos.com> writes:
```Andrei Alexandrescu:

My point was that there's no need to sit down and implement
functionality. Just write

auto enumerate(R)(R r) if (isInputRange!R)
{
return zip(iota(0, size_t.max), r);
}

Right, thank you. A std lib can contain even small functions/HOFs (that are the
result of combination of few other things), if they are very commonly useful.

Bye,
bearophile
```
Jun 03 2010
Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
```On 06/03/2010 10:01 AM, Graham Fawcett wrote:
import std.range;

auto enumerate(R)(R r) if (isInputRange!R) {
return zip(iota(0, size_t.max), r);
}

void main() {
auto e = enumerate([10,20,30]);
}

I cry bug.

Andrei
```
Jun 03 2010
Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
```On 06/03/2010 10:25 AM, Graham Fawcett wrote:
On Thu, 03 Jun 2010 10:15:33 -0500, Andrei Alexandrescu wrote:

On 06/03/2010 10:01 AM, Graham Fawcett wrote:
import std.range;

auto enumerate(R)(R r) if (isInputRange!R) {
return zip(iota(0, size_t.max), r);
}

void main() {
auto e = enumerate([10,20,30]);
}

I cry bug.

LOL! Andrei, you are a very terse guy. :)

Do you cry a bug in my example, in std.range, or D 2.043?

My code sucks.

Andrei
```
Jun 03 2010
"Simen kjaeraas" <simen.kjaras gmail.com> writes:
```On Thu, 03 Jun 2010 17:25:47 +0200, Graham Fawcett <fawcett uwindsor.ca>
wrote:

On Thu, 03 Jun 2010 10:15:33 -0500, Andrei Alexandrescu wrote:

On 06/03/2010 10:01 AM, Graham Fawcett wrote:
import std.range;

auto enumerate(R)(R r) if (isInputRange!R) {
return zip(iota(0, size_t.max), r);
}

void main() {
auto e = enumerate([10,20,30]);
}

I cry bug.

LOL! Andrei, you are a very terse guy. :)

Do you cry a bug in my example, in std.range, or D 2.043?

This is Bugzilla 3123.
http://d.puremagic.com/issues/show_bug.cgi?id=3123

--
Simen
```
Jun 03 2010
Graham Fawcett <fawcett uwindsor.ca> writes:
```On Wed, 02 Jun 2010 20:21:49 -0500, Andrei Alexandrescu wrote:

My point was that there's no need to sit down and implement
functionality. Just write

auto enumerate(R)(R r) if (isInputRange!R) {
return zip(iota(0, size_t.max), r);
}

Should this work with v2.043? I get an error if I try to enumerate an
array, for example:

/* example.d */
import std.range;

auto enumerate(R)(R r) if (isInputRange!R) {
return zip(iota(0, size_t.max), r);
}

void main() {
auto e = enumerate([10,20,30]);
}

\$ dmd example.d
/usr/include/d/dmd/phobos/std/range.d(1773): Error: cannot implicitly
convert expression (&this.ranges._field_field_0.front) of type uint
delegate() to uint*

(The error message is unfortunate: it doesn't indicate the offending
expression in example.d.)

Thanks,
Graham
```
Jun 03 2010
Philippe Sigaud <philippe.sigaud gmail.com> writes:
```--0016367fae3de29c0a0487c09677
Content-Type: text/plain; charset=ISO-8859-1

On Sat, May 29, 2010 at 03:27, bearophile <bearophileHUGS lycos.com> wrote:

Now and then it's very useful to compare how to write in D2 a small

written in another language, the comparison can help find problems,

performance problems, and so on.

Time ago I have tried to convert to D2 a small Python program that finds

of a given string, but Phobos2 was not mature enough, and I didn't produce

I have tried again and this time things are good enough.

(snip)

Hey, cool. And you made it generic to boot. I'd vote that to be put in
std.algorithm.

Simen kjaeraas:
I'm now so tired of hearing this, I started writing something that
does it:

Now, granted, I have little to no experience with list comprehension,
and as such this might not be what is needed. Still, it was fun to
play around with, and I kinda like what it turned out as.

That's fun to see, the syntax is cool. I never thought of using operator

I did a range comprehension also, a few months ago. It's called comp in
http://svn.dsource.org/projects/dranges/trunk/dranges/docs/algorithm2.html

Like yours, it takes any range and is lazy, the main difference it that it's
multirange: you can give it any number of range as input, it will create the
combinations of elements (aka product of ranges), filter it with the
predicate and map the generative function on it.

Syntax is     comp!(mappingFunction, predicate)(ranges...)

The classical example for Haskell list comprehension is generating the
pythagorean triplets:

pyth n = [ ( a, b, c ) | a <- [1..n],          -- Pythagorean Triples
b <- [1..n],
c <- [1..n],
a + b + c <= n,
a^2 + b^2 == c^2 ]

In my case, it would be:

auto pyth(int n)
{
return comp ! ("tuple(a,b,c)", "a*a+b*b==c*c && a<b")
(iota(1,n),iota(1,n), iota(1,n));
}

pyth(11) -> (3,4,5), (6,8,10)

Philippe

--0016367fae3de29c0a0487c09677
Content-Type: text/html; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable

<br><br><div class=3D"gmail_quote">On Sat, May 29, 2010 at 03:27, bearophil=
e <span dir=3D"ltr">&lt;<a href=3D"mailto:bearophileHUGS lycos.com">bearoph=
ileHUGS lycos.com</a>&gt;</span> wrote:<br><br>&gt;Now and then it&#39;s ve=
ry useful to compare how to write in D2 a small=20
interesting program <br>&gt;written in another language, the comparison can=
help
find problems, possible improvements, <br>&gt;performance problems, and so=
on.<br>
&gt;<br>
&gt;Time ago I have tried to convert to D2 a small Python program that find=
s
the Huffman encoding<br>&gt; of a given string, but Phobos2 was not mature=
=20
enough, and I didn&#39;t produce a good enough D2 program. <br>&gt;I have t=
ried=20
again and this time things are good enough.<br>
<br>(snip)<br><br>Hey, cool. And you made it generic to boot. I&#39;d vote =
that to be put in std.algorithm.<br><br><br><blockquote class=3D"gmail_quot=
e" style=3D"margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204,=
Simen kjaeraas:<br>
<div class=3D"im"><br>
&gt; I&#39;m now so tired of hearing this, I started writing something that=
<br>
&gt; does it:</div></blockquote><div>&gt;Now, granted, I have little to no =
experience with list comprehension,<br>
&gt;and as such this might not be what is needed. Still, it was fun to<br>
&gt;play around with, and I kinda like what it turned out as.<br>=A0
<br>That&#39;s fun to see, the syntax is cool. I never thought of using ope=
lso, a few months ago. It&#39;s called comp in <br><a href=3D"http://svn.ds=
ource.org/projects/dranges/trunk/dranges/docs/algorithm2.html">http://svn.d=
source.org/projects/dranges/trunk/dranges/docs/algorithm2.html</a><br>
<br>Like yours, it takes any range and is lazy, the main difference it that=
it&#39;s multirange: you can give it any number of range as input, it will=
create the combinations of elements (aka product of ranges), filter it wit=
h the predicate and map the generative function on it.<br>
<br>Syntax is=A0=A0=A0=A0 comp!(mappingFunction, predicate)(ranges...)<br><=
br>The classical example for Haskell list comprehension is generating the p=
ythagorean triplets:<br><br><pre>pyth n =3D [ ( a, b, c ) | a &lt;- [1..n],=
=A0=A0=A0=A0=A0=A0=A0=A0=A0 -- Pythagorean Triples<br>
=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0 b =
&lt;- [1..n],=A0<br>=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=
=A0=A0=A0=A0=A0=A0 c &lt;- [1..n],=A0<br>=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=
=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0 a + b + c &lt;=3D n,<br>=A0=A0=A0=
=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0 a^2 + b^2 =
=3D=3D c^2 ]<br></pre><br>In my case, it would be:<br>
<br>auto pyth(int n) <br>{<br>=A0=A0=A0 return comp ! (&quot;tuple(a,b,c)&q=
uot;, &quot;a*a+b*b=3D=3Dc*c &amp;&amp; a&lt;b&quot;) (iota(1,n),iota(1,n),=
iota(1,n));<br>}<br><br>pyth(11) -&gt; (3,4,5), (6,8,10)<br><br><br>=A0=A0=
Philippe<br>
</div></div>

--0016367fae3de29c0a0487c09677--
```
May 29 2010
"Simen kjaeraas" <simen.kjaras gmail.com> writes:
```Philippe Sigaud <philippe.sigaud gmail.com> wrote:

That's fun to see, the syntax is cool. I never thought of using operat=

I just had a look at Wikipedia's article on it, found that the syntax wa=
s
'hey, that's neat'. Just wish I could use curly brackets around it, but
parentheses work:

{ 2=C2=B7x | x =E2=88=88 N, x=C2=B2 > 3 }
=3D>
( list!"2*a" | iota(1,int.max) * where!"x^^2 > 3" )

I did a range comprehension also, a few months ago. It's called comp i=

http://svn.dsource.org/projects/dranges/trunk/dranges/docs/algorithm2.=

Like yours, it takes any range and is lazy, the main difference it tha=

it's
multirange: you can give it any number of range as input, it will crea=

the
combinations of elements (aka product of ranges), filter it with the
predicate and map the generative function on it.

auto pyth(int n)
{
return comp ! ("tuple(a,b,c)", "a*a+b*b=3D=3Dc*c && a<b")
(iota(1,n),iota(1,n), iota(1,n));
}

This reminded me that Phobos lacks a combinatorial range, taking two or
more (forward) ranges and giving all combinations thereof:

combine([0,1],[2,3])
=3D>
(0,2), (0,3), (1,2), (1,3)

Work has commenced on implementing just that.

-- =

Simen
```
May 30 2010
"Simen kjaeraas" <simen.kjaras gmail.com> writes:
```------------u5f4rzlcDMXH0bXCF09X98
Content-Type: text/plain; charset=utf-8; format=flowed; delsp=yes
Content-Transfer-Encoding: 7bit

Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> wrote:
This reminded me that Phobos lacks a combinatorial range, taking two or
more (forward) ranges and giving all combinations thereof:

combine([0,1],[2,3])
=>
(0,2), (0,3), (1,2), (1,3)

Work has commenced on implementing just that.

Yah, that would be useful. If Philippe agrees to adapt his work, maybe
that would be the fastest route. And don't forget - the gates of Phobos
are open.

Too late for that, as I've already written this. :p

Current problems: back and popBack not implemented. I'm not sure they
even should be. Doing so would be a tremendous pain the region below the
spine.

May very well be there are other problems, I don't know. If anyone finds

--
Simen
------------u5f4rzlcDMXH0bXCF09X98
Content-Disposition: attachment; filename=combiner.d
Content-Type: application/octet-stream; name=combiner.d
Content-Transfer-Encoding: Base64

bW9kdWxlIGNvbWJpbmVyOw0KDQppbXBvcnQgc3RkLnJhbmdlOw0KaW1wb3J0IHN0
ZC50eXBlY29uczsNCmltcG9ydCBzdGQudHJhaXRzOw0KaW1wb3J0IHN0ZC5hbGdv
cml0aG07DQoNCi8qKg0KSXRlcmF0ZSB0aGUgY29tYmluYXRvcmlhbCByZXN1bHQg
b2Ygc2V2ZXJhbCByYW5nZXMuIFRoZSBlbGVtZW50IHR5cGUNCmlzIGEgZWxlbWVu
dFR1cGxlIHR1cGxlIHRoYXQgYWxsb3dzIGFjY2Vzc2luZyB0aGUgY3VycmVudCBl
bGVtZW50IGluIHRoZQ0KJChEIG4pdGggcmFuZ2UgYnkgdXNpbmcgJChEIGUuYXQh
KG4pKS4NCg0KRXhhbXBsZToNCi0tLS0NCmludFtdIGEgPSBbIDEsIDIgXTsNCnN0
cmluZ1tdIGIgPSBbICJhIiwgImIiIF07DQovLyBwcmludHMgMTphIDE6YiAyOmEg
MjpjDQpmb3JlYWNoIChlOyBjb21iaW5lKGEsIGIpKQ0Kew0KICAgIHdyaXRlKGUu
YXQhKDApLCAnOicsIGUuYXQhKDEpLCAnICcpOw0KfQ0KLS0tLQ0KDQokKEQgQ29t
YmluZSkgb2ZmZXJzIHRoZSBsb3dlc3QgcmFuZ2UgZmFjaWxpdGllcyBvZiBhbGwg
Y29tcG9uZW50cywgZS5nLg0KaXQgb2ZmZXJzIHJhbmRvbSBhY2Nlc3MgaWZmIGFs
bCByYW5nZXMgb2ZmZXIgcmFuZG9tIGFjY2VzcywgYW5kIGFsc28NCm9mZmVycyBt
dXRhdGlvbiBhbmQgc3dhcHBpbmcgaWYgYWxsIHJhbmdlcyBvZmZlciBpdC4NCiAq
Lw0Kc3RydWN0IENvbWJpbmUoUi4uLikNCnsNCnByaXZhdGU6DQoJVHVwbGUhUiBz
YXZlZFJhbmdlczsNCglhbGlhcyBUdXBsZSEoc3RhdGljTWFwIShFbGVtZW50VHlw
ZSwgUikpIGVsZW1lbnRUdXBsZTsNCnB1YmxpYzoNCglUdXBsZSFSIHJhbmdlczsN
Ci8qKg0KQnVpbGRzIGFuIG9iamVjdC4gVXN1YWxseSB0aGlzIGlzIGludm9rZWQg
aW5kaXJlY3RseSBieSB1c2luZyB0aGUNCiQoWFJFRiBjb21iaW5lcixjb21iaW5l
KSBmdW5jdGlvbi4NCiAqLw0KCXRoaXMoUiBhcmdzKQ0KCXsNCgkJZm9yZWFjaCAo
aSwgVW51c2VkOyBSKQ0KCQl7DQoJCQlyYW5nZXMuZmllbGRbaV0gPSBhcmdzW2ld
Ow0KCQkJc2F2ZWRSYW5nZXMuZmllbGRbaV0gPSBhcmdzW2ldOw0KCQl9DQoJfQ0K
LyoqDQpSZXR1cm5zICQoRCB0cnVlKSBpZiB0aGUgcmFuZ2UgaXMgYXQgZW5kLiAN
CiAqLw0KCWJvb2wgZW1wdHkoKQ0KCXsNCgkJZm9yZWFjaCAoIGksIFVudXNlZDsg
UiApIHsNCgkJCWlmICggc2F2ZWRSYW5nZXMuZmllbGRbaV0ubGVuZ3RoID09IDAg
KSB7DQoJCQkJcmV0dXJuIHRydWU7DQoJCQl9DQoJCX0NCgkJcmV0dXJuIHJhbmdl
cy5maWVsZFswXS5lbXB0eTsNCgl9DQovKioNClJldHVybnMgYSBlbGVtZW50VHVw
bGUgZm9yIHRoZSBjdXJyZW50IGl0ZXJhdGVkIGVsZW1lbnQuDQogKi8NCiAgICBl
bGVtZW50VHVwbGUgZnJvbnQoKQ0KCXsNCiAgICAgICAgZWxlbWVudFR1cGxlIHJl
c3VsdDsNCiAgICAgICAgZm9yZWFjaCAoaSwgVW51c2VkOyBSKQ0KCQl7DQoJCQly
ZXN1bHQuZmllbGRbaV0gPSByYW5nZXMuZmllbGRbaV0uZnJvbnQ7DQogICAgICAg
IH0NCiAgICAgICAgcmV0dXJuIHJlc3VsdDsNCiAgICB9DQovKioNCkFkdmFuY2Vz
IHRoZSBmcm9udCBvZiB0aGUgcmFuZ2UsIGxvb3BpbmcgYmFjayB0byB0aGUgc3Rh
cnQgZm9yIGFueQ0KcmFuZ2Ugd2hvc2UgbmV4dCByYW5nZSBpcyBlbXB0eS4NCiAq
Lw0KCXZvaWQgcG9wRnJvbnQoKQ0KCXsNCgkJdm9pZCBwb3BGcm9udEltcGwoIGlu
dCBpICkoIHJlZiB0eXBlb2YodGhpcykgdGhhdCApIC8vIFdlaXJkIGhhY2ssIEkg
a25vdy4NCgkJew0KCQkJdGhhdC5yYW5nZXMuZmllbGRbaV0ucG9wRnJvbnQ7DQoJ
CQlzdGF0aWMgaWYgKCBpID49IDEgKQ0KCQkJew0KCQkJCWlmICggdGhhdC5yYW5n
ZXMuZmllbGRbaV0uZW1wdHkgKQ0KCQkJCXsNCgkJCQkJdGhhdC5yYW5nZXMuZmll
bGRbaV0gPSB0aGF0LnNhdmVkUmFuZ2VzLmZpZWxkW2ldOw0KCQkJCQlwb3BGcm9u
dEltcGwhKCBpLTEgKSh0aGF0KTsNCgkJCQl9DQoJCQl9DQoJCX0NCgkJcG9wRnJv
bnRJbXBsIShSLmxlbmd0aC0xKSh0aGlzKTsNCgl9DQovKioNClJldHVybnMgdGhl
IGxlbmd0aCBvZiB0aGlzIHJhbmdlLiBEZWZpbmVkIG9ubHkgaWYgYWxsIHJhbmdl
cyBkZWZpbmUNCiQoRCBsZW5ndGgpLg0KICovDQpzdGF0aWMgaWYgKGFsbFNhdGlz
ZnkhKGhhc0xlbmd0aCwgUikpDQoJc2l6ZV90IGxlbmd0aCgpDQoJew0KCQlhdXRv
IHJlc3VsdCA9IHJhbmdlcy5maWVsZFswXS5sZW5ndGg7DQoJCWZvcmVhY2goIGks
IHVudXNlZDsgUlsxLi4kXSApDQoJCXsNCgkJCXJlc3VsdCAqPSBzYXZlZFJhbmdl
cy5maWVsZFtpKzFdLmxlbmd0aCAtIDE7DQoJCQlyZXN1bHQgKz0gcmFuZ2VzLmZp
ZWxkW2krMV0ubGVuZ3RoOw0KCQl9DQoJCXJldHVybiByZXN1bHQ7DQoJfQ0KfQ0K
DQovLy8gRGl0dG8NCkNvbWJpbmUhUiBjb21iaW5lKFIuLi4pKFIgcmFuZ2VzKQ0K
ew0KCXJldHVybiBDb21iaW5lIShSKShyYW5nZXMpOw0KfQ0KDQp1bml0dGVzdCB7
DQoJYXNzZXJ0KGVxdWFsKGNvbWJpbmUoWzEsMl0sWzMsNF0pLCBbdHVwbGUoMSwz
KSwgdHVwbGUoMSw0KSwgdHVwbGUoMiwzKSwgdHVwbGUoMiw0KV0pKTsNCglhc3Nl
cnQoZXF1YWwoY29tYmluZShbMSwyXSxbImEiLCJiIl0pLCBbdHVwbGUoMSwiYSIp
LCB0dXBsZSgxLCJiIiksIHR1cGxlKDIsImEiKSwgdHVwbGUoMiwiYiIpXSkpOw0K
CWFzc2VydCghZXF1YWwoY29tYmluZShbMV0sWyJhIiwiYiJdKSwgW3R1cGxlKDEs
ImEiKSwgdHVwbGUoMSwiYiIpLCB0dXBsZSgyLCJhIiksIHR1cGxlKDIsImIiKV0p
KTsNCn0=

------------u5f4rzlcDMXH0bXCF09X98--
```
May 30 2010
Philippe Sigaud <philippe.sigaud gmail.com> writes:
```--001636499fd1d048560487d281d4
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: quoted-printable

On Sun, May 30, 2010 at 18:00, Andrei Alexandrescu <
SeeWebsiteForEmail erdani.org> wrote:

On 05/30/2010 10:27 AM, Simen kjaeraas wrote:

{ 2=C2=B7x | x =E2=88=88 N, x=C2=B2 > 3 }
=3D>
( list!"2*a" | iota(1,int.max) * where!"x^^2 > 3" )
return comp ! ("tuple(a,b,c)", "a*a+b*b=3D=3Dc*c && a<b")

This reminded me that Phobos lacks a combinatorial range, taking two or
more (forward) ranges and giving all combinations thereof

http://www.dsource.org/projects/dranges/

Look at the algorithm and range sections, you'll find plenty of code that
try to tackle this.
In particular combinations() in algorithm2, and also tensorialProduct() in
rangeofranges

combinations is a higher-order range that takes any number of forward range=
s
and output their combinations as tuples.

tensorialProduct does the same, but creates 'topology' : the combination of
three ranges is a range, whereas the tensorial product of three (linear)
ranges is a range of ranges of ranges:

tensorialProduct([0,1],[2,3])
->
[[(0,2),(0,3)],
[(1,2),(1,3)]]

(where (x,y) indicates a tuple)

Yah, that would be useful. If Philippe agrees to adapt his work, maybe that
would be the fastest route. And don't forget - the gates of Phobos are op=

Andrei

possible. It's just that my job and formation are far from coding (I'm more
a physicist), so I'm not sure my code would be up to it without being
reviewed.

I'm OK with pretty much everything concerning licensing and adaptation. I'l=
l
begin by putting a Boost licence in my code, when dsource is up again. If
someone is interested by some of it, I'm quite ready to adapt it to conform
to D/Phobos evolutions. That's what I'm doing anyway.

Philippe

--001636499fd1d048560487d281d4
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable

<div class=3D"gmail_quote"><br>On Sun, May 30, 2010 at 18:00, Andrei Alexan=
drescu <span dir=3D"ltr">&lt;<a href=3D"mailto:SeeWebsiteForEmail erdani.or=
g">SeeWebsiteForEmail erdani.org</a>&gt;</span> wrote:<br><blockquote class=
=3D"gmail_quote" style=3D"margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid=
<div><div></div><div class=3D"h5">On 05/30/2010 10:27 AM, Simen kjaeraas wr=
ote:<br>
<blockquote class=3D"gmail_quote" style=3D"margin: 0pt 0pt 0pt 0.8ex; borde=
r-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;">
{ 2=C2=B7x | x =E2=88=88 N, x=C2=B2 &gt; 3 }<br>
=3D&gt;<br>
( list!&quot;2*a&quot; | iota(1,int.max) * where!&quot;x^^2 &gt; 3&quot; )<=
br>
return comp ! (&quot;tuple(a,b,c)&quot;, &quot;a*a+b*b=3D=3Dc*c &amp;&amp; =
a&lt;b&quot;)<br></blockquote></div></div></blockquote><div><br><br>=C2=A0<=
/div><blockquote class=3D"gmail_quote" style=3D"margin: 0pt 0pt 0pt 0.8ex; =
border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;">
<div><div class=3D"h5"><blockquote class=3D"gmail_quote" style=3D"margin: 0=
pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: =
1ex;">
This reminded me that Phobos lacks a combinatorial range, taking two or<br>
more (forward) ranges and giving all combinations thereof<br></blockquote><=
/div></div></blockquote><div><br>Simen, could you please have a look at my =
dranges project?<br><br><a href=3D"http://www.dsource.org/projects/dranges/=
">http://www.dsource.org/projects/dranges/</a><br>
<br>Look at the algorithm and range sections, you&#39;ll find plenty of cod=
e that try to tackle this.<br>In particular combinations() in algorithm2, a=
nd also tensorialProduct() in rangeofranges<br><br>combinations is a higher=
-order range that takes any number of forward ranges and output their combi=
nations as tuples.<br>
<br>tensorialProduct does the same, but creates &#39;topology&#39; : the co=
mbination of three ranges is a range, whereas the tensorial product of thre=
e (linear) ranges is a range of ranges of ranges:<br><br>tensorialProduct([=
0,1],[2,3])<br>
-&gt;<br>[[(0,2),(0,3)],<br>=C2=A0[(1,2),(1,3)]]<br><br>(where (x,y) indica=
tes a tuple)<br><br><br></div><blockquote class=3D"gmail_quote" style=3D"ma=
rgin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding=
-left: 1ex;">
<div><div class=3D"h5"><blockquote class=3D"gmail_quote" style=3D"margin: 0=
pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: =
1ex;"></blockquote></div></div>
Yah, that would be useful. If Philippe agrees to adapt his work, maybe that=
would be the fastest route. And don&#39;t forget - the gates of Phobos are=
open.<br><font color=3D"#888888">
<br>
Andrei<br>
<br></font></blockquote><div><br>Concerning helping Phobos, I&#39;d be deli=
ghted to if the Phobos team deems=20
it possible. It&#39;s just that my job and formation are far from coding=20
(I&#39;m more a physicist), so I&#39;m not sure my code would be up to it w=
ithout being reviewed.<br><br>I&#39;m OK with pretty much everything concer=
ning licensing and adaptation. I&#39;ll begin by putting a Boost licence in=
my code, when dsource is up again. If someone is interested by some of it,=
I&#39;m quite ready to adapt it to conform to D/Phobos evolutions. That&#3=
9;s what I&#39;m doing anyway.<br>
<br><br>=C2=A0=C2=A0=C2=A0 Philippe<br><br></div></div>

--001636499fd1d048560487d281d4--
```
May 30 2010
"Simen kjaeraas" <simen.kjaras gmail.com> writes:
```Philippe Sigaud <philippe.sigaud gmail.com> wrote:
Simen, could you please have a look at my dranges project?

http://www.dsource.org/projects/dranges/

Look at the algorithm and range sections, you'll find plenty of code that
try to tackle this.
In particular combinations() in algorithm2, and also tensorialProduct()
in
rangeofranges

combinations is a higher-order range that takes any number of forward
ranges
and output their combinations as tuples.

tensorialProduct does the same, but creates 'topology' : the combination
of
three ranges is a range, whereas the tensorial product of three (linear)
ranges is a range of ranges of ranges:

tensorialProduct([0,1],[2,3])
->
[[(0,2),(0,3)],
[(1,2),(1,3)]]

(where (x,y) indicates a tuple)

Indeed. I just had a quick look at the traits2 module last time you
linked it. This does seem to cover all bases. I have to say I'm impressed!

--
Simen
```
May 30 2010
Philippe Sigaud <philippe.sigaud gmail.com> writes:
```--0016e65b5e044a76410487d6a107
Content-Type: text/plain; charset=ISO-8859-1

On Sun, May 30, 2010 at 19:01, Simen kjaeraas <simen.kjaras gmail.com>wrote:

Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> wrote:

This reminded me that Phobos lacks a combinatorial range, taking two or
more (forward) ranges and giving all combinations thereof:

combine([0,1],[2,3])
=>
(0,2), (0,3), (1,2), (1,3)

Work has commenced on implementing just that.

Yah, that would be useful. If Philippe agrees to adapt his work, maybe
that would be the fastest route. And don't forget - the gates of Phobos are
open.

Too late for that, as I've already written this. :p

Hey, cool, lots of static foreach. Man, it's like I'm reading my own code.
I'm happy to see convergent evolution: this must be the D way to do this.

Current problems: back and popBack not implemented. I'm not sure they
even should be. Doing so would be a tremendous pain the region below the
spine.

I *guess* it's doable, but I for sure don't want to do it.

May very well be there are other problems, I don't know. If anyone finds

Well, I like the way you dealt with popFront.  You length is more costly
than mine, but I cheated: I count the numbers of popFronts and substract
them from the original length.

Your empty use .length in the foreach loop. You should use .empty instead, I
think. And with an infinite range in the mix, the resulting product is
infinte also, so you can define your combine to be infinite.

Then I can give you something to munch over :-)

When one range is infinite, the resulting combination is infinite. What's
sad is that you'll never 'traverse' the infinite range:
auto c = combine([0,1,2], cycle([2,3,4]));
->
(0,2),(0,3),(0,4),(0,2),(0,3), ...

You never reach the (1,x) (2,x) parts, as it should be seeing how we both
defined combinations: iterating on the ranges as if they were digits in a
number.

But there is another way to iterate: diagonally, by cutting successive
diagonal slices:

c is:
(0,2),(0,3),(0,4),(0,2),...
(1,2),(1,3),(1,4),(1,2),...
(2,2),(2,3),(2,4),(2,2),...
->

(0,2),(0,3)(1,2),(0,4),(1,3),(2,2) ...

It's even better if all ranges are infinite.
I never coded this, but it seems doable for two ranges. Lot thougher for any
number of ranges... Pretty obscure, maybe?

btw, I think we should divert this discussion in another thread if you wish
to continue: this is bearophile's Huffman thread, after all.

Philippe

--0016e65b5e044a76410487d6a107
Content-Type: text/html; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable

<div class=3D"gmail_quote">On Sun, May 30, 2010 at 19:01, Simen kjaeraas <s=
pan dir=3D"ltr">&lt;<a href=3D"mailto:simen.kjaras gmail.com">simen.kjaras =
gmail.com</a>&gt;</span> wrote:<br><blockquote class=3D"gmail_quote" style=
=3D"margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); p=
<div class=3D"im">Andrei Alexandrescu &lt;<a href=3D"mailto:SeeWebsiteForEm=
ail erdani.org" target=3D"_blank">SeeWebsiteForEmail erdani.org</a>&gt; wro=
te:<br>
</div><div class=3D"im"><blockquote class=3D"gmail_quote" style=3D"margin: =
0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left:=
1ex;"><blockquote class=3D"gmail_quote" style=3D"margin: 0pt 0pt 0pt 0.8ex=
; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;">

This reminded me that Phobos lacks a combinatorial range, taking two or<br>
more (forward) ranges and giving all combinations thereof:<br>
<br>
combine([0,1],[2,3])<br>
=3D&gt;<br>
(0,2), (0,3), (1,2), (1,3)<br>
<br>
Work has commenced on implementing just that.<br>
</blockquote>
<br>
Yah, that would be useful. If Philippe agrees to adapt his work, maybe that=
would be the fastest route. And don&#39;t forget - the gates of Phobos are=
open.<br>
</blockquote>
<br></div>
Too late for that, as I&#39;ve already written this. :p<br></blockquote><di=
v><br>Hey, cool, lots of static foreach. Man, it&#39;s like I&#39;m reading=
my own code. I&#39;m happy to see convergent evolution: this must be the D=
way to do this.<br>
<br>=A0</div><blockquote class=3D"gmail_quote" style=3D"margin: 0pt 0pt 0pt=
0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;">

Current problems: back and popBack not implemented. I&#39;m not sure they<b=
r>
even should be. Doing so would be a tremendous pain the region below the<br=

<br></blockquote><div><br>Ow.<br>I *guess* it&#39;s doable, but I for sure =
don&#39;t want to do it.<br>=A0</div><blockquote class=3D"gmail_quote" styl=
e=3D"margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); =

May very well be there are other problems, I don&#39;t know. If anyone find=
s<br>
any, please let me know.<font color=3D"#888888"></font></blockquote><div><b=
r>Well, I like the way you dealt with popFront.=A0 You length is more costl=
y than mine, but I cheated: I count the numbers of popFronts and substract =
them from the original length. <br>
<br>Your empty use .length in the foreach loop. You should use .empty inste=
ad, I think. And with an infinite range in the mix, the resulting product i=
s infinte also, so you can define your combine to be infinite.<br><br>Then =
I can give you something to munch over :-)<br>
<br>When one range is infinite, the resulting combination is infinite. What=
&#39;s sad is that you&#39;ll never &#39;traverse&#39; the infinite range:<=
br>auto c =3D combine([0,1,2], cycle([2,3,4]));<br>-&gt;<br>(0,2),(0,3),(0,=
4),(0,2),(0,3), ...<br>
<br>You never reach the (1,x) (2,x) parts, as it should be seeing how we bo=
th defined combinations: iterating on the ranges as if they were digits in =
a number.<br><br>But there is another way to iterate: diagonally, by cuttin=
g successive diagonal slices:<br>
<br>c is:<br>(0,2),(0,3),(0,4),(0,2),...<br>(1,2),(1,3),(1,4),(1,2),...<br>=
(2,2),(2,3),(2,4),(2,2),...<br>-&gt;<br><br>(0,2),(0,3)(1,2),(0,4),(1,3),(2=
,2) ... <br><br>It&#39;s even better if all ranges are infinite.<br>I never=
coded this, but it seems doable for two ranges. Lot thougher for any numbe=
r of ranges... Pretty obscure, maybe?<br>
<br>btw, I think we should divert this discussion in another thread if you =
wish to continue: this is bearophile&#39;s Huffman thread, after all.<br><b=
r>=A0 Philippe<br></div></div><br>

--0016e65b5e044a76410487d6a107--
```
May 30 2010
Philippe Sigaud <philippe.sigaud gmail.com> writes:
```--0016364178017962880487d6a8ff
Content-Type: text/plain; charset=ISO-8859-1

On Sun, May 30, 2010 at 19:29, Simen kjaeraas <simen.kjaras gmail.com>wrote:

Indeed. I just had a quick look at the traits2 module last time you
linked it. This does seem to cover all bases. I have to say I'm impressed!

Even though my todo list for this project has more than 200 entries left :-)

Philippe

--0016364178017962880487d6a8ff
Content-Type: text/html; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable

<div class=3D"gmail_quote">On Sun, May 30, 2010 at 19:29, Simen kjaeraas <s=
pan dir=3D"ltr">&lt;<a href=3D"mailto:simen.kjaras gmail.com">simen.kjaras =
gmail.com</a>&gt;</span> wrote:<br><blockquote class=3D"gmail_quote" style=
=3D"margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); p=
<br>
Indeed. I just had a quick look at the traits2 module last time you<br>
linked it. This does seem to cover all bases. I have to say I&#39;m impress=
ed!<br><br></blockquote><div><br>If you ever have time to look at it, I&#39=
;m always eager for comments/criticisms/new ideas.<br>Even though my todo l=
ist for this project has more than 200 entries left :-)<br>
<br><br>Philippe<br>=A0<br></div></div>

--0016364178017962880487d6a8ff--
```
May 30 2010
Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
```On 05/28/2010 05:01 PM, bearophile wrote:
[snip]
Some notes (later I can send them to Andrei):

Thanks for your notes. I removed those for which I have no notable answer.

The "std.typecons" module, that contains Tuple and tuple can be named
something simpler to remember as "std.tuples".

Phobos' general approach to naming modules is of coarse granularity. I
wanted to massage in std.typecons everything that constructs new,
generally useful types.

I will keep missing array comprehensions in D. In the meantime other
languages have got some forms of them (but Python ones use the best
syntax still).

Looks like we're having two proposals.

only bug I have found was caused by the different ordering of the
Python/Phobos2 heaps, so I have had to use "b<a" in D2. This is not a
bug, but I have to keep it in mind in future usages of heaps across
the two languages. I don't know why the two languages have chosen
different orderings here, if someone of you knows I'd like to know
it.

a < b is sort of the default comparison operator in D, so it would have
been surprising if I'd created a max heap.

Another small problem I have found was caused by BinaryHeap.pop().
I'd like it to pop and return a single item, instead of an array of
given length of items, because this is done quite more often than
popping many items. If the need to pop many items is important, then
a different method can be defined, as npop().

There exists a pop() function that only pops one element.

Maybe BinaryHeap can be moved to the collections module.

Agreed.

array(map(...)) is so common that an amap(...) can be considered.

I don't know.

A helper function like this one can be useful: auto binaryHeap(alias
less="a<  b", Range)(Range items) { return BinaryHeap!(Range,
less)(items); } Note that the 'less' is before the Range, so in that
program you can write: auto heap = binaryHeap!("b<  a")(s2w); Instead
of: auto heap = BinaryHeap!(Block[], "b<  a")(s2w); And in many cases
you just write: auto heap = binaryHeap(items);

Sounds good.

I have seen that this doesn't work, but something like this can be
useful (but I am not sure, I don't love strings used this way):
schwartzSort!("a.code.length")(r);

In Python there is both list.sort() and sorted(), the second creates
a new list. In my dlibs1 I have similar functions. They allow you to
write: return schwartzSorted!((x){ return x.code.length;
})(...items); Instead of: auto r = ...items; schwartzSort!((x){
return x.code.length; })(items); return items; So I'd like sorted and
schwartzSorted in Phobos2.

I'm not crazy about functions that return large arrays by value. I'd
have sorted() return a range (a heap!) that lazily spans the input in
sorted order.

While debugging this program I have found that array(iota(0, 10)) is
an uint[] instead of being an int[]. In most cases I prefer that
syntax to produce an array of true ints. In the uncommon situations
when I want an array of uints I can ask it with a syntax like
array(iota(0U, 10U)). If this specification is not possible then I
prefer iota to always yield signed values, because they are much
*safer* in D.

I'd like iota(100) to be the same as iota(0, 100), as in the Python
range().

Sounds good.

To improve a *lot* my debugging in code like this I'd like this line
of code: writeln(tuple(['x': 1.0, 'y': 2.0], "hello", [[1, 2], [3,
4]])); To print (better): tuple(['x': 1.0, 'y': 2.0], "hello", [[1,
2], [3, 4]]) Or even: Tuple!(double[char], string, int[][])(['x':
1.0, 'y': 2.0], "hello", [[1, 2], [3, 4]]) instead of:
Tuple!(double[char],string,int[][])([x:1, y:2], hello, 1 2 3 4)

I've never had a clear view on what the target audience for writeln()
is. You seem to want it to output debug strings; I'm not sure that's the
best way to purpose it.

Andrei
```
May 30 2010
bearophile <bearophileHUGS lycos.com> writes:
```Andrei:

My pleasure, if you like them I will try to do this thing some more times.
There are probably tens or hundreds of small details that can be improved in
Phobos. Some of such changes can improve the usage patterns. In past I have put
some of them in Bugzilla.
One good way to find such possible improvements is to use Phobos, to write
small programs, and keep eyes open.

Looks like we're having two proposals.<

I am sceptic that this can be done with no compiler/language support to offer
the good enough syntax sugar:
http://www.digitalmars.com/webnews/newsgroups.php?art_group=digitalmars.D&article_id=110613

In my dlibs1 (for D1) I have implemented and then later sometimes used an
expanded and improved an idea by Henning Hasemann shown in 2007, but this (you
are free to use it if you want, code shown in this newsgroup page is free to
use, I think):
- is not efficient
- you have to define the iteration variable types before this array comp
- the code that uses this array comp is not so easy to read
- this can't be done (in D1) for lazy comphrensions.

TA[] select(TA, TI, TC)(lazy TA mapper,
ref TI iter1, TC items1) {
static if(is( TC == void[0] )) {
return null;
} else {
auto aux1 = iter1; // save original iteration variable

static if (HasLength!(TC)) {
auto result = new TA[items1.length];

uint i;
static if (IsAA!(TC)) {
foreach (k, v; items1) {
iter1 = k;
result[i] = mapper();
i++;
}
} else {
// Then items1 is an iterable with attribute length
// (an array, xrange, etc)
// don't use foreach (i,el;items1), it's less general
foreach (el; items1) {
iter1 = el;
result[i] = mapper();
i++;
}
}

iter1 = aux1; // restore original iteration variable
return result;
} else {
// Then items1 is an iterable object
// when TA isn't an AA, geometric grow can be used to speed up
ArrayBuilder!(TA) result;
foreach (el; items1) {
iter1 = el;
result ~= mapper();
}
iter1 = aux1; // restore original iteration variable
return result.toarray;
}
}
}

TA[] select(TA, TI, TC, TP)(lazy TA mapper,
ref TI iter1, TC items1,
lazy TP where) {
...

TA[] select(TA, TI1, TC1, TI2, TC2)(lazy TA mapper,
ref TI1 iter1, TC1 items1,
ref TI2 iter2, lazy TC2 items2) {
...

TA[] select(TA, TI1, TC1, TI2, TC2, TP)(lazy TA mapper,
ref TI1 iter1, TC1 items1,
ref TI2 iter2, lazy TC2 items2,
lazy TP where) {
...

There exists a pop() function that only pops one element.<

This is how it is implemented:

/**
Pops the largest element (according to the predicate \$(D less)).
*/
void pop()
{
enforce(_length);
if (_length > 1)
swap(_store.front, _store[_length - 1]);
--_length;
percolateDown(_store[0 .. _length]);
}

I'd like it to also return the popped item, a ElementType!Range, is this
possible?
Popping one item out is one of the most common operations I have to perform on
an heap.

array(map(...)) is so common that an amap(...) can be considered.<<

I don't know.<

A too much long list of function (that is a too much large API) is bad, but I
have found that for the most common higher order functions (map and filter,
they are common because array comps aren't present) I like a short cut for the
eager version, amap/afilter. But they are not essential, we can survive without
them :-)

I'm not crazy about functions that return large arrays by value. I'd have
sorted() return a range (a heap!) that lazily spans the input in sorted order.<

When I need only the few items in sorted order I can use just pop(n), or many
pop().
Functional languages return data copies, but they are sometimes lazy (Haskell)
or thy try to avoid using arrays and use more functional-friendly data
structures that reduce the need for copying lot of data.

sorted() and schwartzSorted() can be handy because they can be used as
expressions in a functional style. You can write:

foreach (x; sorted(items)) {...

auto sortedItems = items.dup;
sortedItems.sorted();
foreach (x; sortedItems) {...

If items is long then sorted() is not the top efficiency in both memory and
time, but in many situations you don't have many items. Most arrays are short.
If you have a 5 items long array and the items are small (like numbers) then
using sorted() is not so bad unless it's in the middle of a critical piece of
code. And in this case using a standard sort is probably wrong anyway.

So sorted/schwartzSorted are not for every situation, they are more for
situations where you prefer handy and short code, and you don't need max
performance. You don't have to abuse them, as most other things.

I've never had a clear view on what the target audience for writeln() is. You
seem to want it to output debug strings; I'm not sure that's the best way to
purpose it.<

Usages of the printing functions:
- To debug code. For this purpose the text shown has to be human-readable, the
writeln has to be as automatic as possible (to reduce time needed to add the
printing statements), and the text shown has to be "nice" to show the data
types but not too much noisy, otherwise the text can become useless. There are
more modern ways to show data structures, even GUI-based, but having a
fall-back strategy with a good writeln is good.
- To show output in small script-like programs or medium command line programs.
I think this is the same case as the debug code one.
- To print a lot of numbers or simple symbols, for later processing with other
programs. In this case printf() is better because it's faster than writeln.
- To print many strings. In this case in D printf()/puts() can be suboptimal or
unfit. Some very simple, very fast and not templated function similar to puts()
but designed for D strings.
- For (textual) serialization? In this case it's better to use functions more
specialized for this purpose, and to avoid the writeln.

So I don't see why it's better for this command:
writeln(tuple(['x': 1.0, 'y': 2.0], "hello", [[1, 2], [3, 4]]));

To print:
Tuple!(double[char],string,int[][])([x:1, y:2], hello, 1 2 3 4)

Instead of something more fitter for humans, that can show the things well, as:
tuple(['x': 1.0, 'y': 2.0], "hello", [[1, 2], [3, 4]])
Or:
Tuple!(double[char], string, int[][])(['x': 1.0, 'y': 2.0], "hello", [[1, 2],
[3, 4]])

Bye,
bearophile
```
May 31 2010
bearophile <bearophileHUGS lycos.com> writes:
``` I'd like it to also return the popped item, a ElementType!Range, is this
possible?
Popping one item out is one of the most common operations I have to perform on
an heap.

I have read some pages, trying to understand why your pop doesn't return the
item.

In a page I have read:
Pop returns void for the sake of speed: SGI FAQ, and to prevent exceptions that
may be thrown by the objects copy constructor.<

http://www.sgi.com/tech/stl/FAQ.html
Why do the pop member functions return void? All of the STL's pop member
functions (pop_back in vector, list, and deque; pop_front in list, slist, and
deque; pop in stack, queue, and priority_queue) return void, rather than
returning the element that was removed. This is for the sake of efficiency. If
the pop member functions were to return the element that was removed then they
would have to return it by value rather than by reference. (The element is
being removed, so there wouldn't be anything for a reference to point to.)
Return by value, however, would be inefficient; it would involve at least one
unnecessary copy constructor invocation. The pop member functions return
nothing because it is impossible for them to return a value in a way that is
both correct and efficient.<

Time ago I have suggested about a possible enum boolean value defined inside
nonvoid functions, that is true/false if the function result is used or not:
http://www.digitalmars.com/webnews/newsgroups.php?art_group=digitalmars.D&article_id=97424
So this value can be used with a static if to compute the result. So such
functions are like templates, they get copied in two (generic function pointers
have to refer to the nornal version of the function that computes and returns
the result).

A simpler solution is to use two different names for two functions. The most
common operation is to pop an item from a heap and then to use it. So the pop()
can return the popped item. And then the heap can define another method that
just pops the top item and doesn't return it, it can be named for example
"drop", something similar to this (I don't know if this is right):

/**
Pops the largest element (according to the predicate \$(D less))
and returns it.
*/
ElementType!Range pop()
{
enforce(_length);
auto tmp = _store.front;
enforce(_length);
if (_length > 1)
swap(_store.front, _store[_length - 1]);
--_length;
percolateDown(_store[0 .. _length]);
return tmp;
}

/**
Drops the largest element (according to the predicate \$(D less)).
*/
void drop()
{
enforce(_length);
if (_length > 1)
swap(_store.front, _store[_length - 1]);
--_length;
percolateDown(_store[0 .. _length]);
}

Bye,
bearophile
```
May 31 2010
"Simen kjaeraas" <simen.kjaras gmail.com> writes:
```Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> wrote:

Yah, there's no argument that infinite ranges must be allowed by a n-way
cross-product. It reminds one of Cantor's diagonalization, just in
several dimensions. Shouldn't be very difficult, but it only works if
all ranges except one are forward ranges (one can be an input range).

Might I coerce you into indulging some more detail on this idea? I'm
afraid my knowledge of the diagonal method is sadly lacking, and some
reading on the subject did not give me satisfactory understanding of
its application in the discussed problem.

Way I thought of doing it is save the highest position this far of each
range, then in popFront see if we're past it. If we are, reset this
range, and pop from the next range up, recursively.

--
Simen
```
May 31 2010
"Simen kjaeraas" <simen.kjaras gmail.com> writes:
```Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> wrote:

interesting than I thought.

Cantor enumerated rational numbers the following way: first come all
fractions that have numerator + denominator = 1. That's only one
rational number, 1/1. Then come all fractions that have num + denom = 2.
That gives 1/2 and 2/1. Then come all fractions that have num + denom =
3, and so on.

Using this enumeration method he proved that rational numbers are
countable so in some way they are not more "numerous" than natural
numbers, which was an important result.

With ranges, the trick should be similar: although individual ranges may
be infinite, they are composed in a simple, countable manner.

Generalizing Cantor's enumeration technique to n ranges, note that the
enumeration goes through elements such that the sum of their offsets
from the beginning of the ranges is constant.

So for two ranges, we first select pairs that have their offsets sum to
0. That is (0, 0). Then we select pairs of offsets summing to 1: (0, 1)
and (1, 0). Then same for 2: (0, 2), (1, 1), (2, 0). And so on.

The problem is that in order to make sure offsets are constant, forward
ranges are not enough. If all ranges involved had random access, the
problem would be trivially solvable. The trick is pushing that envelope;
for example, it's possible to make things work with one forward range
and one random-access range, and so on.

This is bound to be an interesting problem. Please discuss any potential
solutions here.

All forward ranges should be doable, too. One input range also, as long
as no other range is infinite. In the case of all forward ranges, elements
of each should be visited in order, though. I believe this to be possible,
but not at all easy.

I had to abandon my original idea, as it proved fundamentally flawed.

I believe that for the case of 0 or 1 infinite ranges, the approach used
in the already supplied version is good enough. It also works if one range
is an (optionally infinite) input range. Well, except that it does not
without some rewrites...

For more than one infinite range, Cantor's diagonalization approach
should work, but only if all ranges or all except one are random-access.

--
Simen
```
May 31 2010
"Simen kjaeraas" <simen.kjaras gmail.com> writes:
```Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> wrote:

All forward ranges should be doable, too.

How would the spanning strategy work for two forward infinite ranges?

In a complex, horrible way?

0. Save initial states (position = 0)
1. Pop first until past the position of the other
2. Restore other
3. Pop other until past the position of the first
4. Restore first
6. Goto 1.

Screw that, as you cannot save positions. Well, I guess a long should
be enough for most, but it might not be. As long as there is no way
to compare positions, 'tis unpossible.

If we accept saving the position (the number of pops), this approach
should be applicable to any number of ranges.

--
Simen
```
Jun 01 2010
"Simen kjaeraas" <simen.kjaras gmail.com> writes:
```Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> wrote:

On 06/01/2010 09:23 AM, Simen kjaeraas wrote:
Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> wrote:

All forward ranges should be doable, too.

How would the spanning strategy work for two forward infinite ranges?

In a complex, horrible way?

0. Save initial states (position = 0)
1. Pop first until past the position of the other
2. Restore other
3. Pop other until past the position of the first
4. Restore first
6. Goto 1.

Screw that, as you cannot save positions. Well, I guess a long should
be enough for most, but it might not be. As long as there is no way
to compare positions, 'tis unpossible.

If we accept saving the position (the number of pops), this approach
should be applicable to any number of ranges.

It's ok to store positions in ulong objects. Most uses of infinite range
combinations use only the first few elements; the computation will
anyway take a very, very long time when any of the ranges overflows a
ulong.

With the algorithm (attempted) explained above, it's actually 2^128, which
is acceptably high, I think.

That being said, I didn't understand the algorithm. What is its
complexity? From what I understand there's a lot of looping going on. We
need something that makes progress in O(1).

Should be O(1). Each pop in the described algorithm is a call to popFront:

void popFront( ) {
ranges[active].popFront;
position[active]++;
if (position[active] > position[inactive]) {
active = !active;
position[active] = 0;
ranges[active] = savedRange[active];
}
}

--
Simen
```
Jun 01 2010
Philippe Sigaud <philippe.sigaud gmail.com> writes:
```--0016e6db2aa9f4a39c0487fe2d81
Content-Type: text/plain; charset=ISO-8859-1

On Tue, Jun 1, 2010 at 19:54, Andrei Alexandrescu <
SeeWebsiteForEmail erdani.org> wrote:

Yeah, that's why I proposed it as a challenge.  You guys sure seem to like
this :)
What's interesting, is that it may even be useful :)

It's ok to store positions in ulong objects. Most uses of infinite

range combinations use only the first few elements; the computation
will anyway take a very, very long time when any of the ranges
overflows a ulong.

I still haven't understood your explanation, but I think I figured a
different way to reach the same solution. The idea is to crawl the space by
adding layers on top of a hypercube of increasing side, starting from the
origin corner.

Like this?

01234
11234
22234
33334
44444

where you have layer #0, #1, ...

In fact, any method to iterate on a finite but growing space without going
onto the already produced values is OK. You could iterate on an hypercube,
then duplicate it to make it n times bigger and recurse:

01 22 3333
11 22 3333
22 22 3333
22 22 3333
3333
3333 ...
3333
3333

I think your solution is viable, because you always iterate on 'square'
shapes, that's a good idea. Its only drawback is that the elements are
produced in a less natural order, but really, who cares: you just want to
take a finite part of an infinite range without closing any door while doing
so.
Going full diagonal is more difficult: you must find a way to peel of the
slices.

ranges, but the only implentation I know of for diagonals is here:

Related to this, I've something that takes 'hyperslices' from ranges of
ranges of ... (of whatever rank), but only
'vertical' or 'horizontal' (perpendicular to the normal basis of ranges of
ranges...)

I also have a n-dim generalization of take: take(rangeOfRanges, 2,3,4, ...)
and for drop and slice.
I think it's doable to preduce something akin to your layers than way, or
maybe my suggestion on blocks. A combination of takes and drops should
produce
finite cubic shapes that can then be iterated.

This is an absolutely awesome problem.

Man, don't you have some boring stuff to do instead?

I also found the (simple?) problem to enumerate a range of ranges to be more
interesting than I thought.
Given a range of ranges ... of ranges, of whatever rank, recursively
enumerate it:

[[a,b,c],[d,e,f],[g,h,i]]

produce:

(a,0,0),(b,0,1), (c,0,2),(d,1,0), ...

the coordinates of each element, if you will. I have a working version now,
but it sure taught me that my vision of recursion was flawed.

I attach an implementation for two ranges. It's quite a bit more messy than
I'd hope, so generalization to n ranges should be preceded by cleaning up

It's good if you can make it to more than two ranges, but I think 2 is

The output of the program is:

0       Tuple!(uint,uint)(0, 0)
1       Tuple!(uint,uint)(0, 1)
2       Tuple!(uint,uint)(1, 1)
3       Tuple!(uint,uint)(1, 0)
4       Tuple!(uint,uint)(0, 2)
5       Tuple!(uint,uint)(1, 2)
6       Tuple!(uint,uint)(2, 2)
7       Tuple!(uint,uint)(2, 0)
8       Tuple!(uint,uint)(2, 1)
9       Tuple!(uint,uint)(0, 3)
10      Tuple!(uint,uint)(1, 3)
11      Tuple!(uint,uint)(2, 3)
12      Tuple!(uint,uint)(0, 4)
13      Tuple!(uint,uint)(1, 4)
14      Tuple!(uint,uint)(2, 4)

Seems good to me. I see the layers, like in the Matrix.

standard combination, or use a policy to let the user dicide to iterate
along layers. Most of the time, you just want the standard 'digit-like' way
to iterate on n ranges.

I'll have a look at your code.

Philippe

--0016e6db2aa9f4a39c0487fe2d81
Content-Type: text/html; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable

<div class=3D"gmail_quote">On Tue, Jun 1, 2010 at 19:54, Andrei Alexandresc=
u <span dir=3D"ltr">&lt;<a href=3D"mailto:SeeWebsiteForEmail erdani.org">Se=
eWebsiteForEmail erdani.org</a>&gt;</span> wrote:<br><br>&gt; I thought abo=
ut this some more, and it&#39;s more difficult and more=20
interesting than I thought.<br><br>Yeah, that&#39;s why I proposed it as a =
challenge.=A0 You guys sure seem to like this :)<br>What&#39;s interesting,=
is that it may even be useful :)<br><br><br>It&#39;s ok to store positions=
in ulong objects. Most uses of infinite<br>
<blockquote class=3D"gmail_quote" style=3D"margin: 0pt 0pt 0pt 0.8ex; borde=
r-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;"><div><div class=
=3D"h5"><blockquote class=3D"gmail_quote" style=3D"margin: 0pt 0pt 0pt 0.8e=
x; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;">
<blockquote class=3D"gmail_quote" style=3D"margin: 0pt 0pt 0pt 0.8ex; borde=
r-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;">
range combinations use only the first few elements; the computation<br>
will anyway take a very, very long time when any of the ranges<br>
overflows a ulong.<br></blockquote></blockquote></div></div></blockquote><d=
iv><br>Quite... <br>=A0</div><blockquote class=3D"gmail_quote" style=3D"mar=
gin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-=
left: 1ex;">
<div><div class=3D"h5">
<br></div></div>
I still haven&#39;t understood your explanation, but I think I figured a di=
fferent way to reach the same solution. The idea is to crawl the space by a=
dding layers on top of a hypercube of increasing side, starting from the or=
igin corner.<br>
</blockquote><div><br>Like this?<br><br>01234<br>11234<br>22234<br>33334<br=
44444<br><br>where you have layer #0, #1, ...<br><br>In fact, any method t=

uced values is OK. You could iterate on an hypercube, then duplicate it to =
make it n times bigger and recurse:<br>
<br>01 22 3333<br>11 22 3333<br>22 22 3333<br>22 22 3333<br>3333<br>3333 ..=
.<br>3333<br>3333<br><br>I think your solution is viable, because you alway=
s iterate on &#39;square&#39; shapes, that&#39;s a good idea. Its only draw=
back is that the elements are produced in a less natural order, but really,=
who cares: you just want to take a finite part of an infinite range withou=
t closing any door while doing so. <br>
Going full diagonal is more difficult: you must find a way to peel of the s=
ing infinite ranges, but the only implentation I know of for diagonals is h=
ere:<br>
to this, I&#39;ve something that takes &#39;hyperslices&#39; from ranges of=
=20
ranges of ... (of whatever rank), but only<br>
&#39;vertical&#39; or &#39;horizontal&#39; (perpendicular to the normal bas=
is of ranges of ranges...)<br><br>I also have a n-dim generalization of tak=
e: take(rangeOfRanges, 2,3,4, ...) and for drop and slice.<br>I think it&#3=
9;s doable to preduce something akin to your layers than way, or maybe my s=
uggestion on blocks. A combination of takes and drops should produce<br>
finite cubic shapes that can then be iterated.<br><br><br></div><blockquote=
class=3D"gmail_quote" style=3D"margin: 0pt 0pt 0pt 0.8ex; border-left: 1px=
solid rgb(204, 204, 204); padding-left: 1ex;">
<br>
This is an absolutely awesome problem. </blockquote><div><br>Man, don&#39;t=
you have some boring stuff to do instead?<br><br>I also found the (simple?=
) problem to enumerate a range of ranges to be more interesting than I thou=
ght.<br>
Given a range of ranges ... of ranges, of whatever rank, recursively enumer=
ate it:<br><br>[[a,b,c],[d,e,f],[g,h,i]]<br><br>produce:<br><br>(a,0,0),(b,=
0,1), (c,0,2),(d,1,0), ...<br><br>the coordinates of each element, if you w=
ill. I have a working version now, but it sure taught me that my vision of =
recursion was flawed.<br>
<br><br><br></div><blockquote class=3D"gmail_quote" style=3D"margin: 0pt 0p=
t 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;"=
I attach an implementation for two ranges. It&#39;s quite a bit more messy=

aning up the abstractions used. I think your solution already has said clea=
nups!<br>
</blockquote><div><br>It&#39;s good if you can make it to more than two ran=
ges, but I think 2 is already quite useful.<br>=A0<br></div><blockquote cla=
ss=3D"gmail_quote" style=3D"margin: 0pt 0pt 0pt 0.8ex; border-left: 1px sol=
id rgb(204, 204, 204); padding-left: 1ex;">

The output of the program is:<br>
<br>
0 =A0 =A0 =A0 Tuple!(uint,uint)(0, 0)<br>
1 =A0 =A0 =A0 Tuple!(uint,uint)(0, 1)<br>
2 =A0 =A0 =A0 Tuple!(uint,uint)(1, 1)<br>
3 =A0 =A0 =A0 Tuple!(uint,uint)(1, 0)<br>
4 =A0 =A0 =A0 Tuple!(uint,uint)(0, 2)<br>
5 =A0 =A0 =A0 Tuple!(uint,uint)(1, 2)<br>
6 =A0 =A0 =A0 Tuple!(uint,uint)(2, 2)<br>
7 =A0 =A0 =A0 Tuple!(uint,uint)(2, 0)<br>
8 =A0 =A0 =A0 Tuple!(uint,uint)(2, 1)<br>
9 =A0 =A0 =A0 Tuple!(uint,uint)(0, 3)<br>
10 =A0 =A0 =A0Tuple!(uint,uint)(1, 3)<br>
11 =A0 =A0 =A0Tuple!(uint,uint)(2, 3)<br>
12 =A0 =A0 =A0Tuple!(uint,uint)(0, 4)<br>
13 =A0 =A0 =A0Tuple!(uint,uint)(1, 4)<br>
14 =A0 =A0 =A0Tuple!(uint,uint)(2, 4)<br><font color=3D"#888888">
<br>
<br>
</font></blockquote><div>Seems good to me. I see the layers, like in the Ma=
trix.<br>If you ever put that in Phobos, make it a secondary function compa=
red to a standard combination, or use a policy to let the user dicide to it=
erate along layers. Most of the time, you just want the standard &#39;digit=
-like&#39; way to iterate on n ranges.<br>
<br>I&#39;ll have a look at your code.<br><br>Philippe<br><br></div></div>

--0016e6db2aa9f4a39c0487fe2d81--
```
Jun 01 2010
"Steven Schveighoffer" <schveiguy yahoo.com> writes:
```On Tue, 01 Jun 2010 13:54:01 -0400, Andrei Alexandrescu
<SeeWebsiteForEmail erdani.org> wrote:

The output of the program is:

0	Tuple!(uint,uint)(0, 0)
1	Tuple!(uint,uint)(0, 1)
2	Tuple!(uint,uint)(1, 1)
3	Tuple!(uint,uint)(1, 0)
4	Tuple!(uint,uint)(0, 2)
5	Tuple!(uint,uint)(1, 2)
6	Tuple!(uint,uint)(2, 2)
7	Tuple!(uint,uint)(2, 0)
8	Tuple!(uint,uint)(2, 1)
9	Tuple!(uint,uint)(0, 3)
10	Tuple!(uint,uint)(1, 3)
11	Tuple!(uint,uint)(2, 3)
12	Tuple!(uint,uint)(0, 4)
13	Tuple!(uint,uint)(1, 4)
14	Tuple!(uint,uint)(2, 4)

It looks like you're missing some iterations there.

-Steve
```
Jun 01 2010
Philippe Sigaud <philippe.sigaud gmail.com> writes:
```--0016e6dd8bb71c93200487fe8293
Content-Type: text/plain; charset=ISO-8859-1

On Tue, Jun 1, 2010 at 22:54, Philippe Sigaud <philippe.sigaud gmail.com>wrote:

I also found the (simple?) problem to enumerate a range of ranges to be
more interesting than I thought.
Given a range of ranges ... of ranges, of whatever rank, recursively
enumerate it:

[[a,b,c],[d,e,f],[g,h,i]]

produce:

(a,0,0),(b,0,1), (c,0,2),(d,1,0), ...

the coordinates of each element, if you will. I have a working version now,
but it sure taught me that my vision of recursion was flawed.

[[(a,0,0),(b,0,1),(c,0,2)],
[(d,1,0), (e,1,1),(f,1,2)],
[(g,2,0), (h,2,1),(i,2,2)]]

Lazily, of course.
I wanted the to conserve the rank because

1- that was the goal of the module: map, produce, etc range of ranges
2- it allowed me to iterate to a 'line' and then descend into this
particular line.
3- the original idea was to generate an infinite n-dim grid of coordinates

Philippe

--0016e6dd8bb71c93200487fe8293
Content-Type: text/html; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable

<br><br><div class=3D"gmail_quote">On Tue, Jun 1, 2010 at 22:54, Philippe S=
igaud <span dir=3D"ltr">&lt;<a href=3D"mailto:philippe.sigaud gmail.com">ph=
ilippe.sigaud gmail.com</a>&gt;</span> wrote:<br><blockquote class=3D"gmail=
_quote" style=3D"margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204,=
<div class=3D"gmail_quote">I also found the (simple?) problem to enumerate =
a range of ranges to be more interesting than I thought.<br><div>
Given a range of ranges ... of ranges, of whatever rank, recursively enumer=
ate it:<br><br>[[a,b,c],[d,e,f],[g,h,i]]<br><br>produce:<br><br>(a,0,0),(b,=
0,1), (c,0,2),(d,1,0), ...<br><br>the coordinates of each element, if you w=
ill. I have a working version now, but it sure taught me that my vision of =
recursion was flawed.<br>
<br></div></div></blockquote><div><br>Ow, I meant, while conserving the ori=
ginal topology, not as a flat range:<br><br>[[(a,0,0),(b,0,1),(c,0,2)],<br>=
=A0[(d,1,0), (e,1,1),(f,1,2)],<br>=A0[(g,2,0), (h,2,1),(i,2,2)]]<br><br>Laz=
ily, of course.<br>
I wanted the to conserve the rank because<br><br>1- that was the goal of th=
e module: map, produce, etc range of ranges<br>2- it allowed me to iterate =
to a &#39;line&#39; and then descend into this particular line.<br>3- the o=
riginal idea was to generate an infinite n-dim grid of coordinates<br>
<br>Philippe<br><br></div></div>

--0016e6dd8bb71c93200487fe8293--
```
Jun 01 2010
"Steven Schveighoffer" <schveiguy yahoo.com> writes:
```On Tue, 01 Jun 2010 17:12:29 -0400, Andrei Alexandrescu
<SeeWebsiteForEmail erdani.org> wrote:

On 06/01/2010 04:06 PM, Steven Schveighoffer wrote:
On Tue, 01 Jun 2010 13:54:01 -0400, Andrei Alexandrescu
<SeeWebsiteForEmail erdani.org> wrote:

The output of the program is:

0 Tuple!(uint,uint)(0, 0)
1 Tuple!(uint,uint)(0, 1)
2 Tuple!(uint,uint)(1, 1)
3 Tuple!(uint,uint)(1, 0)
4 Tuple!(uint,uint)(0, 2)
5 Tuple!(uint,uint)(1, 2)
6 Tuple!(uint,uint)(2, 2)
7 Tuple!(uint,uint)(2, 0)
8 Tuple!(uint,uint)(2, 1)
9 Tuple!(uint,uint)(0, 3)
10 Tuple!(uint,uint)(1, 3)
11 Tuple!(uint,uint)(2, 3)
12 Tuple!(uint,uint)(0, 4)
13 Tuple!(uint,uint)(1, 4)
14 Tuple!(uint,uint)(2, 4)

It looks like you're missing some iterations there.

-Steve

There should be 5 * 3 = 15 iterations.

Oh, I didn't realize the input was not two infinite ranges.  I was looking
at this as the first 15 lines from the output of 2 infinite ranges.  I
expected to see (3, 0), (3, 1), (3, 2), and (3, 3).

-Steve
```
Jun 01 2010
Philippe Sigaud <philippe.sigaud gmail.com> writes:
```--0015174c345e4dc9370487fe8c1e
Content-Type: text/plain; charset=ISO-8859-1

On Tue, Jun 1, 2010 at 23:12, Andrei Alexandrescu <
SeeWebsiteForEmail erdani.org> wrote:

On 06/01/2010 04:06 PM, Steven Schveighoffer wrote:

It looks like you're missing some iterations there.

-Steve

There should be 5 * 3 = 15 iterations.

Andrei

The example is:

auto c = xproduct(iota(3), iota(5));

so the first index only goes from 0 to 2.

Philippe

--0015174c345e4dc9370487fe8c1e
Content-Type: text/html; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable

<div class=3D"gmail_quote">On Tue, Jun 1, 2010 at 23:12, Andrei Alexandresc=
u <span dir=3D"ltr">&lt;<a href=3D"mailto:SeeWebsiteForEmail erdani.org">Se=
eWebsiteForEmail erdani.org</a>&gt;</span> wrote:<br><blockquote class=3D"g=
mail_quote" style=3D"margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(=
<div><div></div><div class=3D"h5">On 06/01/2010 04:06 PM, Steven Schveighof=
fer wrote:<br>
<blockquote class=3D"gmail_quote" style=3D"margin: 0pt 0pt 0pt 0.8ex; borde=
r-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;">
It looks like you&#39;re missing some iterations there.<br>
<br>
-Steve<br>
</blockquote>
<br></div></div>
There should be 5 * 3 =3D 15 iterations.<br><font color=3D"#888888">
<br>
Andrei<br>
</font></blockquote></div><br>The example is:<br><br>=A0auto c =3D xproduct=
(iota(3), iota(5));<br><br>so the first index only goes from 0 to 2.<br><br=
<br>Philippe<br><br>

--0015174c345e4dc9370487fe8c1e--
```
Jun 01 2010
Philippe Sigaud <philippe.sigaud gmail.com> writes:
```--0015175cda12cbeaea04880f7b9f
Content-Type: text/plain; charset=ISO-8859-1

On Tue, Jun 1, 2010 at 23:45, bearophile <bearophileHUGS lycos.com> wrote:

Andrei Alexandrescu:
And by the way, I added the feature that will ease bearophile's coding
by one order of magnitude: iota with one argument.

Thank you. There's a long way to go still :o)

Bye,
bearophile

What, do you also need the no-arg version of iota?

:-p

--0015175cda12cbeaea04880f7b9f
Content-Type: text/html; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable

<br><br><div class=3D"gmail_quote">On Tue, Jun 1, 2010 at 23:45, bearophile=
<span dir=3D"ltr">&lt;<a href=3D"mailto:bearophileHUGS lycos.com">bearophi=
leHUGS lycos.com</a>&gt;</span> wrote:<br><blockquote class=3D"gmail_quote"=
style=3D"margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 2=
Andrei Alexandrescu:<br>
<div class=3D"im">&gt; And by the way, I added the feature that will ease b=
earophile&#39;s coding<br>
&gt; by one order of magnitude: iota with one argument.<br>
<br>
</div>Thank you. There&#39;s a long way to go still :o)<br>
<br>
Bye,<br>
<font color=3D"#888888">bearophile<br>
</font></blockquote></div><br>What, do you also need the no-arg version of =
iota?<br><br>:-p<br><br>

--0015175cda12cbeaea04880f7b9f--
```
Jun 02 2010
Philippe Sigaud <philippe.sigaud gmail.com> writes:
```--00032555afb6954c0e0488111c54
Content-Type: text/plain; charset=ISO-8859-1

On Wed, Jun 2, 2010 at 19:57, bearophile <bearophileHUGS lycos.com> wrote:

Philippe Sigaud:
What, do you also need the no-arg version of iota?

:-p

I'd like a generator (range) similar to the Python itertools.count, that
yields numbers starting from the given number (defaulting to zero) and just
goes on and on. You can use it in many situations:
http://docs.python.org/library/itertools.html#itertools.count

--00032555afb6954c0e0488111c54
Content-Type: text/html; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable

<br><br><div class=3D"gmail_quote">On Wed, Jun 2, 2010 at 19:57, bearophile=
<span dir=3D"ltr">&lt;<a href=3D"mailto:bearophileHUGS lycos.com">bearophi=
leHUGS lycos.com</a>&gt;</span> wrote:<br><blockquote class=3D"gmail_quote"=
style=3D"margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 2=
Philippe Sigaud:<br>
<div class=3D"im">&gt; What, do you also need the no-arg version of iota?<b=
r>
&gt;<br>
&gt; :-p<br>
<br>
</div>I&#39;d like a generator (range) similar to the Python itertools.coun=
t, that yields numbers starting from the given number (defaulting to zero) =
and just goes on and on. You can use it in many situations:<br>
<a href=3D"http://docs.python.org/library/itertools.html#itertools.count" t=
arget=3D"_blank">http://docs.python.org/library/itertools.html#itertools.co=
unt</a><br><br></blockquote><div><br>Yes, it&#39;s handy. It&#39;s one of t=
he first range I made, a year ago. <br>
<br>=A0<br></div></div>

--00032555afb6954c0e0488111c54--
```
Jun 02 2010
Philippe Sigaud <philippe.sigaud gmail.com> writes:
```--0016e6db2aa9d3ec80048811cc29
Content-Type: text/plain; charset=ISO-8859-1

On Wed, Jun 2, 2010 at 21:41, Andrei Alexandrescu <
SeeWebsiteForEmail erdani.org> wrote:

On 06/02/2010 02:29 PM, Philippe Sigaud wrote:

On Wed, Jun 2, 2010 at 19:57, bearophile <bearophileHUGS lycos.com
<mailto:bearophileHUGS lycos.com>> wrote:

Philippe Sigaud:
> What, do you also need the no-arg version of iota?
>
> :-p

I'd like a generator (range) similar to the Python itertools.count,
that yields numbers starting from the given number (defaulting to
zero) and just goes on and on. You can use it in many situations:
http://docs.python.org/library/itertools.html#itertools.count

Yes, it's handy. It's one of the first range I made, a year ago.

iota(n, n.max) is close. Well, it's not infinite, but cycle(iota(n, n.max))
is. Probably a version using BigInt would be most sensible.

As it's mostly used to enumerate/index ranges or generate some simple
numbers, iota(n,n.max) is largely good enough, except, as you said it's not
infinite. I never used iota much, it regularly crashed on me in the
beginning. I can't remember why.

I don't know if your suggestion of BigInt is a joke or not, but the truth
is, I have a version using any numerical type, I called it numberz. numbers
is the standard version, numberz!T the templated. It uses T for indexing
also (it's a random-access range), which allowed me to do

auto r = numberz(BigInt("1000000000"),  BigInt("10000000000"));
auto n = r[BigInt("3000000000")];

Hmm, this doesn't work:
auto i = iota(BigInt("0"),BigInt("10"), BigInt("1"));

But honestly, I just used it to learn ranges and D, and never had a real use
for it. It's just the kind of things that's useful to try, to break out of
some preconceptions (using a size_t to index..., 1u as a step).
As you said, it already takes loooots of iterations to exhaust a long.

Philippe

--0016e6db2aa9d3ec80048811cc29
Content-Type: text/html; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable

<br><div class=3D"gmail_quote">On Wed, Jun 2, 2010 at 21:41, Andrei Alexand=
rescu <span dir=3D"ltr">&lt;<a href=3D"mailto:SeeWebsiteForEmail erdani.org=
">SeeWebsiteForEmail erdani.org</a>&gt;</span> wrote:<br><blockquote class=
=3D"gmail_quote" style=3D"margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid=
<div class=3D"im">On 06/02/2010 02:29 PM, Philippe Sigaud wrote:<br>
</div><blockquote class=3D"gmail_quote" style=3D"margin: 0pt 0pt 0pt 0.8ex;=
border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;"><div class=
=3D"im">
<br>
<br>
On Wed, Jun 2, 2010 at 19:57, bearophile &lt;<a href=3D"mailto:bearophileHU=
GS lycos.com" target=3D"_blank">bearophileHUGS lycos.com</a><br></div><div>=
<div></div><div class=3D"h5">
&lt;mailto:<a href=3D"mailto:bearophileHUGS lycos.com" target=3D"_blank">be=
arophileHUGS lycos.com</a>&gt;&gt; wrote:<br>
<br>
=A0 =A0Philippe Sigaud:<br>
=A0 =A0 &gt; What, do you also need the no-arg version of iota?<br>
=A0 =A0 &gt;<br>
=A0 =A0 &gt; :-p<br>
<br>
=A0 =A0I&#39;d like a generator (range) similar to the Python itertools.co=
unt,<br>
=A0 =A0that yields numbers starting from the given number (defaulting to<b=
r>
=A0 =A0zero) and just goes on and on. You can use it in many situations:<b=
r>
=A0 =A0<a href=3D"http://docs.python.org/library/itertools.html#itertools.=
count" target=3D"_blank">http://docs.python.org/library/itertools.html#iter=
tools.count</a><br>
<br>
<br></div></div><div class=3D"im">
Yes, it&#39;s handy. It&#39;s one of the first range I made, a year ago.<br=

<br>
iota(n, n.max) is close. Well, it&#39;s not infinite, but cycle(iota(n, n.m=
ax)) is. Probably a version using BigInt would be most sensible.<font color=
=3D"#888888"><br></font></blockquote><div><br><br></div><div><br>As it&#39;=
s mostly used to enumerate/index ranges or generate some simple numbers, io=
ta(n,n.max) is largely good enough, except, as you said it&#39;s not infini=
te. I never used iota much, it regularly crashed on me in the beginning. I =
can&#39;t remember why.<br>
<br>I don&#39;t know if your suggestion of BigInt is a joke or not, but the=
truth is, I have a version using any numerical type, I called it numberz. =
numbers is the standard version, numberz!T the templated. It uses T for ind=
exing also (it&#39;s a random-access range), which allowed me to do<br>
<br>auto r =3D numberz(BigInt(&quot;1000000000&quot;),=A0 BigInt(&quot;1000=
0000000&quot;));<br>auto n =3D r[BigInt(&quot;3000000000&quot;)];<br><br><b=
r>Hmm, this doesn&#39;t work:<br>auto i =3D iota(BigInt(&quot;0&quot;),BigI=
nt(&quot;10&quot;), BigInt(&quot;1&quot;));<br>
<br>But honestly, I just used it to learn ranges and D, and never had a rea=
l use for it. It&#39;s just the kind of things that&#39;s useful to try, to=
break out of some preconceptions (using a size_t to index..., 1u as a step=
).<br>
As you said, it already takes loooots of iterations to exhaust a long.<br><=
br><br>=A0Philippe<br></div></div>

--0016e6db2aa9d3ec80048811cc29--
```
Jun 02 2010
Graham Fawcett <fawcett uwindsor.ca> writes:
```On Thu, 03 Jun 2010 10:15:33 -0500, Andrei Alexandrescu wrote:

On 06/03/2010 10:01 AM, Graham Fawcett wrote:
import std.range;

auto enumerate(R)(R r) if (isInputRange!R) {
return zip(iota(0, size_t.max), r);
}

void main() {
auto e = enumerate([10,20,30]);
}

I cry bug.

LOL! Andrei, you are a very terse guy. :)

Do you cry a bug in my example, in std.range, or D 2.043?

Graham
```
Jun 03 2010