www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - looking for a D3 stl project

reply monkyyy <crazymonkyyy gmail.com> writes:
I want to *help* with an stl-like data structures and algorithms 
project, I'm under no delusions I should be in charge of such a 
thing, but I am not seeing movement even with openD

I take the following things as given:

1. data structures + algorithms = programs
2. with templates you can make your algorithms somewhat data 
structure agonistic
3. M data structures and N algorithms with templates roughly make 
N*M solutions for N+M code
4. there are more than 2 useful data structures, and d is 
***massively*** wasting its potential
5. This will be a template hell project that is just hard, where 
minor issues make for 10 template error messages, and you need 
the same people in charge of both data structures and algorithms 
so you dont have the easy answer "other guys fault"

I have the following requirements for any such project:

1. feature-based and not hierarchy-based. Filter will break 
length, map will break a ref front, if you declare length is 
higher on the hierarchy than ref front, or vice versa you're 
necessarily limiting your flexibility and users will find hacks 
like adding `.array` to move up back up the hierarchy
2. one of those feature sets has indexing, so searching isn't so 
badly designed and named
3. permissive merging until it has enough code to be usable
4. the goal is to be an std candidate or a first-party lib
5. "composite algorithms" where you reuse smaller pieces are 
encouraged and not blocked for "you made an extra allocation","to 
trivail" `auto sumWhere(alias F,R)(R 
r)=>r.filter!F.reduce((a,b)=>a+b)`
Jan 15
parent reply "H. S. Teoh" <hsteoh qfbox.info> writes:
On Mon, Jan 15, 2024 at 05:40:20PM +0000, monkyyy via Digitalmars-d wrote:

 I want to *help* with an stl-like data structures and algorithms
 project, I'm under no delusions I should be in charge of such a thing,
 but I am not seeing movement even with openD


Adam's pretty good about merging stuff that makes sense. If you make
something that works well, I'm pretty sure Adam will have no problems
about merging it.



 I take the following things as given:


[...]

 2. with templates you can make your algorithms somewhat data structure
 agonistic


My personal goal is to make my algorithms *completely* data structure
agnostic.


[...]

 I have the following requirements for any such project:
 
 1. feature-based and not hierarchy-based.


This is a good idea. DbI FTW!!



 Filter will break length, map will break a ref front, if you declare
 length is higher on the hierarchy than ref front, or vice versa you're
 necessarily limiting your flexibility and users will find hacks like
 adding `.array` to move up back up the hierarchy


I'm confused. You just said "feature-based and not hierarchy-based" and
then you start talking about moving back up the hierarchy.  Which do you
mean?



 2. one of those feature sets has indexing, so searching isn't so badly
 designed and named


Don't understand what exactly you mean here. What does has indexing have
to do with "searching isn't so badly designed"?

Also, a name is just an identifier; as long as it's not ridiculous I
don't really care how things are named.



 3. permissive merging until it has enough code to be usable


Just create a project on github and invite contributors.



 4. the goal is to be an std candidate or a first-party lib
 5. "composite algorithms" where you reuse smaller pieces are
 encouraged and not blocked for "you made an extra allocation","to
 trivail" `auto sumWhere(alias F,R)(R
 r)=>r.filter!F.reduce((a,b)=>a+b)`


Why should there be an exponential number of functions when you could
just provide the log(n) number of primitives which the user could
compose himself to build an exponential variety of algorithms?


T

-- 
Без труда не выловишь и рыбку из пруда.
Jan 15
next sibling parent reply monkyyy <crazymonkyyy gmail.com> writes:
On Monday, 15 January 2024 at 19:48:30 UTC, H. S. Teoh wrote:

 Adam's pretty good about merging stuff that makes sense.



 Just create a project on github and invite contributors.


I can't imagine *myself* writing the 100 useful algorithms, the 
glue code, the 20 or so data structures alone


 My personal goal is to make my algorithms *completely* data 
 structure agnostic.


I find that unlikely unless you stick to purely functional 
algorithms
in-place sorting and finding indexs/slices in my mind are 
imperative


 Filter will break length, map will break a ref front, if you 
 declare length is higher on the hierarchy than ref front, or 
 vice versa you're necessarily limiting your flexibility and 
 users will find hacks like adding `.array` to move up back up 
 the hierarchy


 I'm confused. You just said "feature-based and not 
 hierarchy-based" and then you start talking about moving back 
 up the hierarchy.  Which do you mean?


Im arguing why hierarchy-based suck and how users(me) respond
if I type out 5 chained functions and it says "you don't have a 
bidirectional range", I will throw .array in each spot before 
thinking about why I'm lacking anything.


 2. one of those feature sets has indexing, so searching isn't 
 so badly designed and named


 Don't understand what exactly you mean here. What does has 
 indexing have to do with "searching isn't so badly designed"?

 Also, a name is just an identifier; as long as it's not 
 ridiculous I don't really care how things are named.


The theory of "finding" when your imagining ranges are "views of 
data", is you "countUntil" the right element or you return a 
range in a "state" that's useful in some way

I view data as having a place where it actually exists, and would 
like filter/chunks/slide to fundamentally leave ".index" alone

copy and pasted from my libs:

```d
enum isIter(R)=is(typeof(
	(R r){
		if(r.empty)return r.front;
		r.pop;
		return r.front;
	}));
enum hasIndex(R)=is(typeof((R r)=>r.index));
auto filter(alias F,R)(R r){
	static assert(isIter!R);
	struct filter_{
		R r;
		auto front()=>r.front;
		void pop(){
			r.pop;
			while( (!r.empty) && (!F(r.front)) ){
				r.pop;
			}
		}
		bool empty()=>r.empty;
		static if(hasIndex!R){
			auto index()=>r.index;
		}
	}
	auto temp=filter_(r);
	if(temp.empty){return temp;}
	if(!F(temp.front)){temp.pop;}
	return temp;
}
auto swapkeyvalue(R)(R r){
	struct swap{
		R r;
		auto front()=>r.index;
		auto index()=>r.front;
		auto pop()=>r.pop;
		auto empty()=>r.empty;
	}
	return swap(r);
}
```

`filter.swapkeyvalue`, should let you take any filter and get a 
lazy list of indexs under such a scheme.


 5. "composite algorithms" where you reuse smaller pieces are
 encouraged and not blocked for "you made an extra 
 allocation","to
 trivail" `auto sumWhere(alias F,R)(R
 r)=>r.filter!F.reduce((a,b)=>a+b)`


 Why should there be an exponential number of functions when you 
 could just provide the log(n) number of primitives which the 
 user could compose himself to build an exponential variety of 
 algorithms?


Map filter and reduce, have to be template hell, but template 
hell should be minimized.

I'm not so convinced about all algorithms, and Id like to see a 
collection of small algorithms written with base algorithms end 
users could try first, if it fails copy and paste and edit.
Jan 15
parent reply Nickolay Bukreyev <buknik95 ya.ru> writes:
On Monday, 15 January 2024 at 21:01:54 UTC, monkyyy wrote:

 I view data as having a place where it actually exists, and 
 would like filter/chunks/slide to fundamentally leave ".index" 
 alone


I’d argue that having an index is not a must-have requirement for 
a data structure.

1. Singly and doubly linked lists contain data that actually 
exists.
2. (Imperative) concatenation of two doubly linked lists is 
(should be) an `O(1)` operation.
3.  It invalidates indices of the right-hand side list in the 
process.

Therefore, if a list stores its indices, it cannot implement 
concatenation in `O(1)` time. That is, without invalidating its 
ranges/iterators created prior to concatenation.
Jan 15
parent reply monkyyy <crazymonkyyy gmail.com> writes:
On Monday, 15 January 2024 at 21:48:38 UTC, Nickolay Bukreyev 
wrote:

 On Monday, 15 January 2024 at 21:01:54 UTC, monkyyy wrote:

 I view data as having a place where it actually exists, and 
 would like filter/chunks/slide to fundamentally leave ".index" 
 alone


 I’d argue that having an index is not a must-have requirement 
 for a data structure.

 1. Singly and doubly linked lists contain data that actually 
 exists.
 2. (Imperative) concatenation of two doubly linked lists is 
 (should be) an `O(1)` operation.
 3.  It invalidates indices of the right-hand side list in the 
 process.

 Therefore, if a list stores its indices, it cannot implement 
 concatenation in `O(1)` time. That is, without invalidating its 
 ranges/iterators created prior to concatenation.


Its an optional feature even in my example code.

If you're getting a list of indexes from a linked list you picked 
the wrong data structure, and if you "countUntil" a string you 
will have a bad time once its unicode.

It would be only correct for hash maps(and other key indexed 
data) and array-based data structures to implement a .index 
iterator in my view.
Jan 15
parent reply Nickolay Bukreyev <buknik95 ya.ru> writes:
On Monday, 15 January 2024 at 22:08:30 UTC, monkyyy wrote:

 Its an optional feature even in my example code.


Sorry, I misunderstood you. So you suggest that `.index` should 
be a primitive operation of an iterator. But then every iterator 
transformer (`map`, `filter`, `retro`, `take`, hundreds of them) 
would have to implement it if the underlying iterator implements 
it. This makes construction of new iterator transformers harder 
than it ought to be.

In Phobos, on the other hand, the index feature is decoupled from 
ranges’ implementation: if you need an index, you do 
`.enumerate`, and no other range cares about indices.

Of course, it’s up to you how you design it. I just presented a 
different point of view on that.
Jan 15
parent monkyyy <crazymonkyyy gmail.com> writes:
On Monday, 15 January 2024 at 22:43:33 UTC, Nickolay Bukreyev 
wrote:

 On Monday, 15 January 2024 at 22:08:30 UTC, monkyyy wrote:

 Its an optional feature even in my example code.


 Sorry, I misunderstood you. So you suggest that `.index` should 
 be a primitive operation of an iterator. But then every 
 iterator transformer (`map`, `filter`, `retro`, `take`, 
 hundreds of them) would have to implement it if the underlying 
 iterator implements it. This makes construction of new iterator 
 transformers harder than it ought to be.

 In Phobos, on the other hand, the index feature is decoupled 
 from ranges’ implementation: if you need an index, you do 
 `.enumerate`, and no other range cares about indices.

 Of course, it’s up to you how you design it. I just presented a 
 different point of view on that.


right now they implement 20 ish functions to support "random 
access ranges" and can have drastic differences if you dont met 
something like "bidirectional" which is why some of the range 
functions are like 300 lines long

yes, template hell is part of this

I would hope to make it simpler then 20 functions, but I dont 
know.
Jan 15
prev sibling parent reply Alexandru Ermicioi <alexandru.ermicioi gmail.com> writes:
On Monday, 15 January 2024 at 19:48:30 UTC, H. S. Teoh wrote:

 My personal goal is to make my algorithms *completely* data 
 structure agnostic.


Just wondering how can this be achieved? Per my understanding any 
algorithm would require some set of functionality from any data 
structure it accepts, so that it could properly work.
Jan 15
parent "H. S. Teoh" <hsteoh qfbox.info> writes:
On Mon, Jan 15, 2024 at 10:01:04PM +0000, Alexandru Ermicioi via Digitalmars-d
wrote:

 On Monday, 15 January 2024 at 19:48:30 UTC, H. S. Teoh wrote:

 My personal goal is to make my algorithms *completely* data
 structure agnostic.


 
 Just wondering how can this be achieved? Per my understanding any
 algorithm would require some set of functionality from any data
 structure it accepts, so that it could properly work.


Well yes, but one could use DbI to discover the capabilities of an input
structure, and adapt accordingly.  Of course, the algorithm would need
*some* minimum functionality to work, but this minimal functionality may
change depending on the structure, and there may not be a common core of
minimum functionality. For example, there could be two algorithms, or
two implementations of an algorithm, with the same interface, that could
perform some operation, and they would be chosen depending on which
capabilities are presented by the structure.


T

-- 
"You are a very disagreeable person." "NO."
Jan 16