[phobos] More tuple algorithms with std.meta

[Shin Fujishiro]

Philippe Sigaud <philippe.sigaud at gmail.com> wrote:
> As a general note, I find it quite elegant, even though I found your
> constant use of a subdivide-and-recurse scheme a bit strange.
> It makes for some clean implementations, but also complicates matters
> in some cases. I'll indicate when I think a standard, linear
> implementation might be more readable.

Forgive me, but I'll omit answering to your individual comments against
the subdivision.  I had the following thing in mind.

I implemented most templates with linear recursion at first.  But it hit
compiler's limit (= 500) of recursive template instantiation when
testing combinatorial algorithms.  The limitation makes sense because
the compiler actually recurses without tail-recursion optimization.

I think a library should hide such kind of defects from user code.
That's why I implemented most templates with the subdivision
scheme, which reduced recursion depth to log(n).

That said, I must agree that it complicates things.  I'm sorry for
having you read such a weird code.  If needed, I'll make them revert
to adopt straightforward linear recursion.


> Also, maybe it'd be best if you introduced helper templates first. I
> believe Phobos does this.

If you are saying about private templates such as _staticReplace,
okay, I'll follow the convention.


> l. 8: Why redefining TypeTuple as StaticTuple? I agree the name is a
> bit of a misnomer,
> but I'd prefer your module to use already defined templates if possible.

I'm happy with TypeTuple personally.  But now is the chance to fix the
misnomer, isn't it?  I'll post another topic on the messy situation
around the tuple nomenclature.


> l. 21-40: staticMap : instead of testing for seq.length<2 and then
> have a special case for == 0, I'd write
> test for == 0
> else test for == 1
> else (the rest)

Isn't it a matter of taste?


> I grok Instantiate!template.With!arguments, but really in this case
> and many other, you just use a subcase.
> Why not do directly map!(seq[0])?

That's for allowing staticMap!(q{a.sizeof }, ...).  It's indeed ugly and
I'll fix as follows.

template staticMap(alias map, seq...);
template staticMap(string map, seq...);


> l. 55: why seq and not seq[0]? Because you want the result to always
> be a tuple?

Yes.  staticFilter should consistently return a tuple.


> l.93 (staticReduce).Ideally, there should be a 2-args version that
> takes seq[0] as a seed.

Oh, it's your StaticScan.  Could you contribute your templates?
(SegmentTypes too.)


> l. 143: what is m? Is that the predicate's arity? That can be
> determined, given a template's symbol.
> So that could be done automatically here.

Yes, m is the arity.  I know dranges has a template that parses arity
out of a stringof property.  But is it reliable to parse stringof?  Its
content is unspecified and it sometimes lies.

Also, consider this:
----------
import dranges.templates;

template isStaticArray(T : T[N], size_t N)
{
    enum isStaticArray = true;
}
static assert(TemplateArity!isStaticArray == 2);
----------
TemplateArity reports isStaticArray as a binary template, but it's
effectively a unary one.  I suspect that template arity can't be
determined due to argument deduction and default arguments.


> l. 156: I suggest: enum size_t index = 0;

Yeah.


> l. 210: maybe you should test for pred being a binary template (arity == 2)

The same problem about template's arity arises.


> l. 302 (staticCountIf): another example of recursing being strange to my eye.
> Cannot it just be staticFilter!(pred, seq).length?

I didn't use staticFilter to avoid unnecessary tuple allocation inside
the compiler.  Maybe I'm too much worrying such kind of things.


> l. 352 (_staticReplace(tr...): what if tr.length is not 2?

It's an internal stuff and tr.length must be always 2.

> Why not just do _staticReplace(from,to)?

It doesn't work with symbols or constants if declared so.  I used
template tuple parameters as wildcard parameters.


> l. 354-355: what's the usefulness of Identity in this case? Cannot
> just "alias tr[0] from;" work?

No, it can't work when tr[0] is a literal constant.  For instance:
----------
template A(tr...)
{
    alias tr[0] from;
    // Error: alias test.A!("x","y").from cannot alias an expression "x"
}
alias A!("x", "y") a;
----------
It errors because tr[0] is a literal.  Indeed, this should not work:

    alias "x" from;

Identity gives a symbol to the literal constant and makes it work.


> l. 377 (staticMost): it's a kind of fold, so it's implementable with
> staticReduce. Maybe staticReduce!(selectWith!comp, seq)

It's for reducing recursion depth.  staticMost can be computed with
log(n) recursions, whereas staticReduce can't.


> l. 384 & 388: why Identity?

It doesn't work if a tuple contains literal constants as I noted above.


> l. 422 & 430, 432 & 437: Does the compiler know what template to
> instantiate for an empty tuple? I thought that was considered
> ambiguous?

No ambiguity.  It's specifically stated in the document (template.html):

  If both a template with a tuple parameter and a template without a
  tuple parameter exactly match a template instantiation, the template
  without a TemplateTupleParameter is selected.

You can expect pattern-match semantics here. :-)


> l. 439-448: I suggest to invert B and A in the test. Mostly, you want
> to do comp!(A[0],B[0]).
> And then do the then branch with A, the else branch with B. Looks more
> natural to me.

It breaks stability of the sorting algorithm.  Comparison must be in
that order, or you'll get wrong results:

staticSort!(q{ a.sizeof < b.sizeof }, int, byte, char)
  = (char, byte, int)  // no

In this case, the expected result is (byte, char, int).


> l. 593: What's the difference with staticUniq?

staticUniq only eliminates consecutive duplicates with O(n) comparisons,
while staticRemoveDuplicates eliminates all duplicates with O(n^2).


> l. 595 here also, choose <=1 or <2, but stick with it for the entire module.

Okay, I'll stick with < 2.


> l. 664: why do you have staticStride return 1-element tuples instead
> of directly the elements?

You mean l. 674?  I think staticStride should consistently return
a tuple, not forcing user to handle the special case of 1-element.

  staticStride!(3, int, double, string, bool) = (int, bool)
  staticStride!(3, int, double) = int  // why?
  staticStride!(3) = ()

Do you really want the second case to be special: a bare int?


> l. 699: you should test for .Expand being legal. Or maybe introduce a
> isTupleOfTuples template.
> Maybe implement staticTransverse with staticMap.

Agreed.


> l. 732: staticZip: good idea! I never had the energy to code this.
> staticZipWith would be cool.

Could you elaborate what staticZipWith is?


> l. 763: staticPermutations: do you have a use case in mind?

I regard the combinatorial algorithms as helpers for systematic tests.


> l. 765: (5 is the limit). Really? 120 5-tuplets is the limit?

It's too slow to list 6! permutations with that implementation.  An
iterative algorithm might reduce the time cost, but it would instead
hit the limit of recursion depth and eventually limited up to 5!


> l. 781 & 787: I believe metaArray is not defined in the module.

My bad, I forgot to replace it with Wrap.  For your curiosity, here's a
simplified metaArray:

  metaArray
  http://gist.github.com/610238

I abandoned it because of compiler bugs and maybe-specs.


> l. 1000. Wrap is good, but I'd prefer not to introduce another
> Tuple-like template.
> I'd suggest using std.typecons.Tuple and extend it when possible. When
> that's not possible (as Tuple is a type and not a 'pure' template), use
> a free template.
> For example template insertFront(A, Tuple)

Wait, std.typecons.Tuple can't hold constants.  This doesn't work:
Tuple!("foo", "bar", "baz").  I really want to wrap types and constants
with a consistent manner.

Consider parsing template parameters (int, "x", 100, double, "y", 200)
which represents  "int x = 100;"  and  "double y = 200;".

You may want to use staticSegment!(3, ...) and get a tuple of tuples
(Wrap!(int, "x", 100) , Wrap!(double, "y", 200)).  Now it's very easy
to handle each group in the segmented form.  That's a use case.


> l. 1113: Very clever, forcing the compiler to generates the two inner
> templates to compare the arguments.
> That's for being able to test aliases too, right?

Yes.  It could be "is(Wrap!A == Wrap!B)" if Wrap were a type.

I wanted to make Wrap a type, but the optlink bug 4904 worries me
about type information generated for every Wrap instantiation... ugh!

  http://d.puremagic.com/issues/show_bug.cgi?id=4904


> l. 1271 & 1280 (templateAnd, templateOr): These are quite useful, good
> idea to add them.

Thanks.  Since we don't have template literals, this kind of composers
would be vital.  Maybe we'll eventually need more.

> I have the basis of a 'type pattern' module, to look for patterns in
> tuples, like for regexes. Maybe that could interest someone.

Cool, it would vastly reduce ad-hoc tuple parsing code.  I want to
eliminate ones in std.typecons.Tuple and std.bitmanip.bitfields!


> Btw, I tested Robert's suggestion to put things in a struct called
> meta, and it worked:
> 
> ...snip...
> 
> I find meta.* much cleaner than static* and such.

I agree.  It's a reasonable solution at this point.


Shin