First pass illustrating the basic data layout:

http://dpaste.dzfl.pl/0d4a589ad6f5

Code is obviously barebones but passes tests and works with allocators.

Notes:

* I managed to not store one allocator per node, but there's one allocator per range. That's needed if we want "orphan ranges" to work, i.e. ranges that survive the list they came from. This is a clasic convenience vs. efficiency thing.

* There's a refcount per node because any given node may belong to multiple lists.

* Refcounting is interesting because many nodes are only used by the previous node. So destroying a list is... funny. Never saw or wrote code like this previously. See nukeTransitively.

All in all things seem convex. Please destroy appropriately.


Thanks,

Andrei

On Thursday, 18 June 2015 at 23:32:03 UTC, Andrei Alexandrescu wrote:
> First pass illustrating the basic data layout:
>
> http://dpaste.dzfl.pl/0d4a589ad6f5
>
> Code is obviously barebones but passes tests and works with allocators.
>
> Notes:
>
> * I managed to not store one allocator per node, but there's one allocator per range. That's needed if we want "orphan ranges" to work, i.e. ranges that survive the list they came from. This is a clasic convenience vs. efficiency thing.
>
> * There's a refcount per node because any given node may belong to multiple lists.
>
> * Refcounting is interesting because many nodes are only used by the previous node. So destroying a list is... funny. Never saw or wrote code like this previously. See nukeTransitively.
>
> All in all things seem convex. Please destroy appropriately.
>
>
> Thanks,
>
> Andrei

Before being able to compile your code i have some very basic questions:

1. Where can I find 'std/experimental/allocator.d'? The compiler seems to want it and i cannot find it in either https://github.com/andralex/phobos/tree/allocator/std/experimental/allocator or https://github.com/D-Programming-Language/phobos/tree/master/std/experimental

2. What is the rationale behind a singly linked list? Or is it just to experiment with collections and allocators?

"JDemler" <jakob.demler@stud-mail.uni-wuerzburg.de> wrote:
> On Thursday, 18 June 2015 at 23:32:03 UTC, Andrei Alexandrescu wrote:
>> First pass illustrating the basic data layout:
>> 
>> http://dpaste.dzfl.pl/0d4a589ad6f5
>> 
>> Code is obviously barebones but passes tests and works with > allocators.
>> 
>> Notes:
>> 
>> * I managed to not store one allocator per node, but there's > one allocator per range. That's needed if we want "orphan > ranges" to work, i.e. ranges that survive the list they came > from. This is a clasic convenience vs. efficiency thing.
>> 
>> * There's a refcount per node because any given node may belong > to multiple lists.
>> 
>> * Refcounting is interesting because many nodes are only used > by the previous node. So destroying a list is... funny. Never > saw or wrote code like this previously. See nukeTransitively.
>> 
>> All in all things seem convex. Please destroy appropriately.
>> 
>> 
>> Thanks,
>> 
>> Andrei
> 
> Before being able to compile your code i have some very basic questions:
> 
> 1. Where can I find 'std/experimental/allocator.d'? The compiler seems to
> want it and i cannot find it in either
> https://github.com/andralex/phobos/tree/allocator/std/experimental/allocator or
> https://github.com/D-Programming-Language/phobos/tree/master/std/experimental

Should be around there, I'm on the phone now so can't check. It's std/experimental/allocator/package.d

> 2. What is the rationale behind a singly linked list? Or is it just to experiment with collections and allocators?

It's the simplest collection that's meaningful. So I chose it as proof of concept.

On Thursday, 18 June 2015 at 23:32:03 UTC, Andrei Alexandrescu wrote:
> First pass illustrating the basic data layout:
>
> http://dpaste.dzfl.pl/0d4a589ad6f5
>
> Code is obviously barebones but passes tests and works with allocators.
>
> Notes:
>
> * I managed to not store one allocator per node, but there's one allocator per range. That's needed if we want "orphan ranges" to work, i.e. ranges that survive the list they came from. This is a clasic convenience vs. efficiency thing.
>
> * There's a refcount per node because any given node may belong to multiple lists.
>
> * Refcounting is interesting because many nodes are only used by the previous node. So destroying a list is... funny. Never saw or wrote code like this previously. See nukeTransitively.
>
> All in all things seem convex. Please destroy appropriately.
>
>
> Thanks,
>
> Andrei

It's a nice start and I like in general how easy it is to integrate an allocator to the design. The node ref-counting and disposal make this almost a classic text-book example - it's that easy :)

I have some comments/questions:
* I don't know if it's because this is WIP, but it also strange that the range has empty and popFront primitives, but the Slist doesn't have them.
* More over, the distinction between the SList collection and it's range is a bit blurry. They even have the same members. You have named your module
std.[..]functional.[..], which makes me wonder if you actually need a collection to operate with such lists. This idea reminds of programming lisp where operations with lists are fluid and everything is floating around and it just works without having to call collection<T>.push_back(elem); a single-time. The difference being that this is GC-free and with more deterministic behavior, but it still resembles this productivity of "just get stuff done and don't bother me with management".

* It's strange that the copy-constructor `this(this)` has reference semantics (it adds reference to the list) and the assign-operator (opAssign) has move semantics (it steals the contents of the victim on assignment).
Edit: actually because Slist is a struct this line doesn't do anything to the moved from list: http://dpaste.dzfl.pl/06e24fecd2da#line-93 , though to the comment in the function is a bit disorienting.

* In a couple of places like this: http://dpaste.dzfl.pl/06e24fecd2da#line-181
you assert that the list is non-empty. Why don't you instead use in contracts?

On Friday, 19 June 2015 at 01:07:10 UTC, ZombineDev wrote:
> On Thursday, 18 June 2015 at 23:32:03 UTC, Andrei Alexandrescu wrote:
>
> [...]

BTW, for those who want to review this, you actually don't need to download the forthcoming allocator modules. You can just replace the missing imports with this:

class IAllocator
{
	T* make(T, Args...)(Args args) { return new T(args); }
	void dispose(T)(T* toDelete) { }
}

static IAllocator theAllocator;

static this() { theAllocator = new IAllocator(); }

On Friday, 19 June 2015 at 01:07:10 UTC, ZombineDev wrote:
> On Thursday, 18 June 2015 at 23:32:03 UTC, Andrei Alexandrescu wrote:
> [..]

I also noticed that the `front` primitive returns only `const ref` (instead of `inout ref`). Is this because the user should regard the SList as immutable - i.e. if you want to change an element, you have to make the modification in a copy of the list, instead of doing it inplace?

On 6/18/15 6:07 PM, ZombineDev wrote:
> It's a nice start and I like in general how easy it is to integrate an
> allocator to the design. The node ref-counting and disposal make this
> almost a classic text-book example - it's that easy :)

Thanks for taking a look! Yah, I, too, was a tad surprised about the seamless dovetailing of things.

> I have some comments/questions:
> * I don't know if it's because this is WIP, but it also strange that the
> range has empty and popFront primitives, but the Slist doesn't have them.

functional.SList should have empty but not popFront. The latter is mutating.

> * More over, the distinction between the SList collection and it's range
> is a bit blurry. They even have the same members. You have named your
> module
> std.[..]functional.[..], which makes me wonder if you actually need a
> collection to operate with such lists. This idea reminds of programming
> lisp where operations with lists are fluid and everything is floating
> around and it just works without having to call
> collection<T>.push_back(elem); a single-time. The difference being that
> this is GC-free and with more deterministic behavior, but it still
> resembles this productivity of "just get stuff done and don't bother me
> with management".

Years ago when I chose the range primitives there was a choice between:

for (auto r = x[]; !r.empty; r.popFront) {
  ... use r.front ...
}

and

for (auto r = x[]; !r.empty; r = r.tail) {
  ... use r.front ...
}

The first won, partly because it's easier to implement efficiently. So now we have this one mutating operation that we need to mind. Because of it, we'll need functional containers to be distinct from their ranges.

> * It's strange that the copy-constructor `this(this)` has reference
> semantics (it adds reference to the list) and the assign-operator
> (opAssign) has move semantics (it steals the contents of the victim on
> assignment).
> Edit: actually because Slist is a struct this line doesn't do anything
> to the moved from list: http://dpaste.dzfl.pl/06e24fecd2da#line-93 ,
> though to the comment in the function is a bit disorienting.

Yah, there's a little trick there that deserves an explanation - opAssign takes a SList by value, so the reference counting has already occurred at the caller side. So there's no extra need to do that, just move from it and leave it empty.

> * In a couple of places like this:
> http://dpaste.dzfl.pl/06e24fecd2da#line-181
> you assert that the list is non-empty. Why don't you instead use in
> contracts?

Well, it's briefer...


Andrei

On 6/18/15 6:26 PM, ZombineDev wrote:
> On Friday, 19 June 2015 at 01:07:10 UTC, ZombineDev wrote:
>> On Thursday, 18 June 2015 at 23:32:03 UTC, Andrei Alexandrescu wrote:
>> [..]
>
> I also noticed that the `front` primitive returns only `const ref`
> (instead of `inout ref`). Is this because the user should regard the
> SList as immutable - i.e. if you want to change an element, you have to
> make the modification in a copy of the list, instead of doing it inplace?

Yah, traditionally functional data structures don't allow their clients to mutate the data AND the topology of the container. So front() returns a non-mutable ref.

It might be interesting to explore containers that allow mutation of data but not of topology. We may collectively think of a few applications of that. For now I went the traditional route.


Andrei

On Friday, 19 June 2015 at 02:24:35 UTC, Andrei Alexandrescu wrote:
> On 6/18/15 6:26 PM, ZombineDev wrote:
>> On Friday, 19 June 2015 at 01:07:10 UTC, ZombineDev wrote:
>>> On Thursday, 18 June 2015 at 23:32:03 UTC, Andrei Alexandrescu wrote:
>>> [..]
>
> Yah, traditionally functional data structures don't allow their clients to mutate the data AND the topology of the container. So front() returns a non-mutable ref.
>
> It might be interesting to explore containers that allow mutation of data but not of topology. We may collectively think of a few applications of that. For now I went the traditional route.
>
>
> Andrei

I just realized that my idea of something in between collections and ranges obviously comes from D's own slices/dynamic arrays :D (I really shouldn't be allowed to talk so late in the night :D)

So here's an idea - can we make the new functional SList (and probably DList) the logic counter-part of slices?

const SList!int;    // <- `const int[]` You can't mutate the elements,
                    // nor the topology

SList!(const(int)); // <- `const(int)[]` You can mutate the topology,
                    //but not the elements

ConstSList!(int);   // <- `missing head const array` You can mutate the elements,
                    // but not the topology

SList!(int);        // <- `int[]` Unlimited power

SList!(int) mutable_list;
mutable_list ~= 3; //change the topology in-place

const SList!(int) const_list;
const_list ~= 42; //error - can't mutate const SList
const SList!(int) concat_result = const_list ~ 42; //functional-style "modification"
foreach (elem; concat_result) {..} //error need mutable range, because of popFront()

SList!(const(int)) range = concat_result; // implicitly convertable
                                          // like const(int)[] <- const(int[])
foreach (elem; range) {..} // works


So instead of limiting the user by making `front` return const refs, we allow him to choose.

On Friday, 19 June 2015 at 03:10:36 UTC, ZombineDev wrote:
> [...]

In short, make SList both a range and a collection, just like the way arrays/slices are.