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