www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Some combinatorics?

reply bearophile <bearophileHUGS lycos.com> writes:
I'd like to write combinations, permutations, etc ranges (generators), for
std.algorithm or for a small std.combinatorics Phobos module. (I have written
this code time ago for dlibs1 in D1).

I have found some small performance problems in converting the opApply
combinatorics code to the Range protocol.

Are you interested in this module (or in just those few generators for
std.algorithm)? I find them often useful.

Bye,
bearophile
Apr 02 2011
next sibling parent dsimcha <dsimcha yahoo.com> writes:
== Quote from bearophile (bearophileHUGS lycos.com)'s article

 I'd like to write combinations, permutations, etc ranges (generators), for


std.algorithm or for a small std.combinatorics Phobos module. (I have written
this
code time ago for dlibs1 in D1).

 I have found some small performance problems in converting the opApply


combinatorics code to the Range protocol.

 Are you interested in this module (or in just those few generators for


std.algorithm)? I find them often useful.

 Bye,
 bearophile


I've included these in my dstats lib, but my implementations admittedly aren't
very well thought out.  (I wrote these in 2008 before ranges and shoehorned them
into ranges.  I never fixed them because I kept thinking I or someone else was
going to rewrite them and that hasn't happened so far.)  I need this often
enough
that I'd be interested in having them in Phobos.

Some code by Philippe Sigaud does it better than my implementations
(http://svn.dsource.org/projects/dranges/trunk/dranges/docs/algorithm.html) and
is
Boost licensed.  He was thinking of getting parts of this lib into Phobos, but I
don't know what the status of that is.  If this project is abandoned and you
like
it, you could take it over, or you could just write your own.

One important issue is whether the number of elements for a combination should
be
specified at compile time (more efficient), runtime (more flexible) or both
(possibly bloated).

As far as where these should go, I'd say either std.range or a module publicly
imported by std.range.  They deal with range topology.
Apr 02 2011
prev sibling parent reply bearophile <bearophileHUGS lycos.com> writes:
dsimcha:


 I need this often enough
 that I'd be interested in having them in Phobos.


Good.



 Some code by Philippe Sigaud does it better than my implementations
 (http://svn.dsource.org/projects/dranges/trunk/dranges/docs/algorithm.html)
and is
 Boost licensed.  He was thinking of getting parts of this lib into Phobos, but
I
 don't know what the status of that is.  If this project is abandoned and you
like
 it, you could take it over, or you could just write your own.


I will take a look at the code. In the meantime some comments:
- frequency, scan, flatMap, subranges, separate: good;
- tmap: this is the default semantics map should have, in my opinion;
- unfold: nice, but maybe a bit too much hard to understand for nonfunctional
programmers;
- comp, setComp: I'd like a built in syntax instead of this. In my dlibs1 I
have select() that has a different syntax;
- select: I am not sure, maybe this is this better in the array module;
- first, second: maybe good, but I suggest to add a leading "s" to their names;
- combinations: good, but the name has to change;
- permutations: I prefer my version;
- choose: good, but with name change;
- consumer: too much complex to use;

This stuff is good to have in Phobos. But I was thinking about some more
combinatorics.



 One important issue is whether the number of elements for a combination should
be
 specified at compile time (more efficient), runtime (more flexible) or both
 (possibly bloated).


The runtime version is needed. The compile time is surely a different version,
and it's probably less needed. So I suggest to add the runtime version only,
and then add the compile time version later if needed.



 As far as where these should go, I'd say either std.range or a module publicly
 imported by std.range.  They deal with range topology.


Most of those things from dranges are fit in std.range (or std.algorithm?), or
a little module that they publicly import, as you say. But if enough
combinatorics stuff is added, then maybe a std.combinatorics module will be
better.

If Andrei is OK with this then I will probably create a patch for std.range.

See you later,
bearophile
Apr 03 2011
parent reply Philippe Sigaud <philippe.sigaud gmail.com> writes:
David:


 Some code by Philippe Sigaud does it better than my implementations
 (http://svn.dsource.org/projects/dranges/trunk/dranges/docs/algorithm.html)
and is
 Boost licensed.  He was thinking of getting parts of this lib into Phobos, but
I
 don't know what the status of that is.  If this project is abandoned and you
like
 it, you could take it over, or you could just write your own.


Hi there,

I was even invited into Phobos by Andrei in August (so, before the Git
migration). I
intended to cut the more 'Phobos-y' parts of dranges and present them for
inclusion.
It's just, I was then propelled two levels upwards hierarchically and things
have been a
bit hectic since then. I don't have any time right now to participate in
Phobos. If I
ever get some rest, I'll formally knock on the door again.

I still read the D mailing lists with interest (even more so when I see the
rate at
which bugs are corrected). dranges is Boost licensed specifically to be
compatible with
Phobos. If anyone is interested in using it in any way (even proposing it for
Phobos
inclusion), you have my permission.


Philippe
Apr 03 2011
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 4/3/11 8:31 AM, Philippe Sigaud wrote:

 David:


 Some code by Philippe Sigaud does it better than my implementations
 (http://svn.dsource.org/projects/dranges/trunk/dranges/docs/algorithm.html)
and is
 Boost licensed. �He was thinking of getting parts of this lib into Phobos,
but I
 don't know what the status of that is. �If this project is abandoned and you
like
 it, you could take it over, or you could just write your own.


 Hi there,

 I was even invited into Phobos by Andrei in August (so, before the Git
migration). I
 intended to cut the more 'Phobos-y' parts of dranges and present them for
inclusion.
 It's just, I was then propelled two levels upwards hierarchically and things
have been a
 bit hectic since then. I don't have any time right now to participate in
Phobos. If I
 ever get some rest, I'll formally knock on the door again.

 I still read the D mailing lists with interest (even more so when I see the
rate at
 which bugs are corrected). dranges is Boost licensed specifically to be
compatible with
 Phobos. If anyone is interested in using it in any way (even proposing it for
Phobos
 inclusion), you have my permission.


 Philippe


Congrats. Were you the one working on a simple JSON replacement?

Andrei
Apr 03 2011
next sibling parent Philippe Sigaud <philippe.sigaud gmail.com> writes:
On Sun, Apr 3, 2011 at 15:55, Andrei Alexandrescu
<SeeWebsiteForEmail erdani.org> wrote:

 Congrats. Were you the one working on a simple JSON replacement?


Hmm, no. My interests were in ranges, algorithms and template stuff.
Apr 03 2011
prev sibling parent reply "Robert Jacques" <sandford jhu.edu> writes:
On Sun, 03 Apr 2011 09:55:54 -0400, Andrei Alexandrescu  
<SeeWebsiteForEmail erdani.org> wrote:


 On 4/3/11 8:31 AM, Philippe Sigaud wrote:

 David:


 Some code by Philippe Sigaud does it better than my implementations
 (http://svn.dsource.org/projects/dranges/trunk/dranges/docs/algorithm.html)  
 and is
 Boost licensed. �He was thinking of getting parts of this lib into  
 Phobos, but I
 don't know what the status of that is. �If this project is abandoned  
 and you like
 it, you could take it over, or you could just write your own.


 Hi there,

 I was even invited into Phobos by Andrei in August (so, before the Git  
 migration). I
 intended to cut the more 'Phobos-y' parts of dranges and present them  
 for inclusion.
 It's just, I was then propelled two levels upwards hierarchically and  
 things have been a
 bit hectic since then. I don't have any time right now to participate  
 in Phobos. If I
 ever get some rest, I'll formally knock on the door again.

 I still read the D mailing lists with interest (even more so when I see  
 the rate at
 which bugs are corrected). dranges is Boost licensed specifically to be  
 compatible with
 Phobos. If anyone is interested in using it in any way (even proposing  
 it for Phobos
 inclusion), you have my permission.


 Philippe


 Congrats. Were you the one working on a simple JSON replacement?

 Andrei


I've been working on a JSON replacement.
Apr 03 2011
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 4/3/11 10:50 AM, Robert Jacques wrote:

 On Sun, 03 Apr 2011 09:55:54 -0400, Andrei Alexandrescu
 <SeeWebsiteForEmail erdani.org> wrote:


 On 4/3/11 8:31 AM, Philippe Sigaud wrote:

 David:


 Some code by Philippe Sigaud does it better than my implementations
 (http://svn.dsource.org/projects/dranges/trunk/dranges/docs/algorithm.html)
 and is
 Boost licensed. �He was thinking of getting parts of this lib into
 Phobos, but I
 don't know what the status of that is. �If this project is abandoned
 and you like
 it, you could take it over, or you could just write your own.


 Hi there,

 I was even invited into Phobos by Andrei in August (so, before the
 Git migration). I
 intended to cut the more 'Phobos-y' parts of dranges and present them
 for inclusion.
 It's just, I was then propelled two levels upwards hierarchically and
 things have been a
 bit hectic since then. I don't have any time right now to participate
 in Phobos. If I
 ever get some rest, I'll formally knock on the door again.

 I still read the D mailing lists with interest (even more so when I
 see the rate at
 which bugs are corrected). dranges is Boost licensed specifically to
 be compatible with
 Phobos. If anyone is interested in using it in any way (even
 proposing it for Phobos
 inclusion), you have my permission.


 Philippe


 Congrats. Were you the one working on a simple JSON replacement?

 Andrei


 I've been working on a JSON replacement.


Apologies, I had the names mangled.

What is the status of that? Do you think you could use a student's help 
for completing and expanding that work?


Thanks,

Andrei
Apr 03 2011
parent "Robert Jacques" <sandford jhu.edu> writes:
On Sun, 03 Apr 2011 12:22:24 -0400, Andrei Alexandrescu  
<SeeWebsiteForEmail erdani.org> wrote:


 On 4/3/11 10:50 AM, Robert Jacques wrote:

 On Sun, 03 Apr 2011 09:55:54 -0400, Andrei Alexandrescu
 <SeeWebsiteForEmail erdani.org> wrote:


 On 4/3/11 8:31 AM, Philippe Sigaud wrote:

 David:


 Some code by Philippe Sigaud does it better than my implementations
 (http://svn.dsource.org/projects/dranges/trunk/dranges/docs/algorithm.html)
 and is
 Boost licensed. �He was thinking of getting parts of this lib into
 Phobos, but I
 don't know what the status of that is. �If this project is abandoned
 and you like
 it, you could take it over, or you could just write your own.


 Hi there,

 I was even invited into Phobos by Andrei in August (so, before the
 Git migration). I
 intended to cut the more 'Phobos-y' parts of dranges and present them
 for inclusion.
 It's just, I was then propelled two levels upwards hierarchically and
 things have been a
 bit hectic since then. I don't have any time right now to participate
 in Phobos. If I
 ever get some rest, I'll formally knock on the door again.

 I still read the D mailing lists with interest (even more so when I
 see the rate at
 which bugs are corrected). dranges is Boost licensed specifically to
 be compatible with
 Phobos. If anyone is interested in using it in any way (even
 proposing it for Phobos
 inclusion), you have my permission.


 Philippe


 Congrats. Were you the one working on a simple JSON replacement?

 Andrei


 I've been working on a JSON replacement.


 Apologies, I had the names mangled.

 What is the status of that? Do you think you could use a student's help  
 for completing and expanding that work?


 Thanks,

 Andrei


No problem. I'd say JSON is now basically ready for review. However, it is  
dependent on my improvement to std.variant. Variant core code is close to  
being ready for a rough review; I'm doing a code cleanup and documentation  
pass right now. But I feel a need to do a thorough review / update the  
unit tests, particularly for Algebraic and Prototype, in part because of  
alias this issues, new functionality, etc.

As for completing and expanding the work, there are a couple of issues  
that might be of interest:
- Currently, Json is an Algebraic type, which means that methods that act  
on Json values, like toStringHR or isValid, must be called as  
JSON.isValid(json). This isn't terrible, but it would be nice to be able  
to add functions to an algebraic type. I've been thinking of ways this  
might be done, i.e. detecting template parameters of the form  
function(Algebraic, args), but I haven't gotten around to trying it yet.
- Serialization: Currently, Json supports a simple form of serialization,  
which currently requires first constructing a json value before/after  
writing/parseing can occur. So methods to provide direct  
serialization/de-serialization would be a good extension. Also, there is  
the general question of serialization with polymorphism support, etc. ala  
Orange.
- Reflection: I've added some basic compile-time to runtime reflection  
capabilities to Variant, but I don't know (from a design perspective)  
where to go beyond var.x == 10 or foo.bar(10,20). And good runtime  
reflection folds into serialization.
- Prototype: I've added a proof-of concept Prototype class, which  
uses/tests some of variant's reflection capabilities. But some good use  
cases/unit tests would really flesh this out.
Apr 03 2011