Hello

[paldepind]

Hello @emmanueltouzery. Congratulations on a very nice looking library! :+1: I recently stumbled upon it and found it to be very interesting.

As you're aware I've created a library with an immutable list. I saw the really clever type you have for partition. I've just implemented it here. Thanks a lot for sharing the idea in your blog post!

I see that you've added List to your benchmarks :smile: I had already done so myself to see how the libraries compare. I'm going to work on improving performance in the cases where List is not as fast as your Vector.

I can see that you have "Non-empty vector?" on the "Wishlist/upcoming features". I have been thinking about adding such a feature to List. But, I'm now sure if it's worth it. What do you think? When does the feature help?

[emmanueltouzery]

Hi, thank you for the feedback, I love this cross-pollination! I'm busy now optimizing prelude's vector in some cases where your list bests it too :-) especially map & concat, maybe others and also it causes me to reconsider how to iterate over items in the vector. Anyway, super interesting and tons of fun, a shame time is so limited.

Regarding the non-empty vector. Actually in the blog post I mention prelude already has a non-empty linked list, ConsLinkedList and give that example:

if (!myLinkedList.isEmpty()) {
    return myLinkedList.last().get();
}

where Vector can only achieve:

if (!myVector.isEmpty()) {
    return myVector.last().getOrThrow();
}

With the if statement, you prove to the compiler that the linked list is not empty (that it's a ConsLinkedList), and therefore last returns a Some -- we know there is a last item. Prelude is actually not taking full advantage of this for now, because I'm a bit reluctant to change the return type of some methods from Option to Some (and of some others from LinkedList to ConsLinkedList), as it would require a new major release. And there's an annoyance too, I'll explain just a little later. Anyway prelude for now uses this only for head and last. But we could use it also at least for minOn, maxOn, reduce. And LinkedList.append could return a ConsLinkedList and so on.

Now, the annoyance... If you have three options... [option1, option2, option3]. This is Option[]. No problem. But now if the first one is somehow a Some. And the other two are only Option... Then you get a compile error... Can't put an Option in a Some array. For that reason I added on Option a method toOption(). Meant to transform Some & None to Option. Same on linkedlist and stream. That's really a weakness of typescript's type inference (it really should unify to Option) but in the end that creates some inconvenience of being provided these more precise types even if you don't really need them, and the question is, do you get enough reward for these annoyances?

It can make sense to have this ability as a programmer to say "this function only accepts non-empty lists", depending on the function, also as a documentation feature. But I'm not taking advantage of this much in prelude because I want to support javascript users.

Many libraries and languages offer a non-empty list/vector, it certainly cannot hurt, and if a team is diligent about using them, I'm sure they can be a real plus, but I'm not sure they're so important as to invest lots of energy into them for typescript which is still a little weak in its type-system. I actually stumbled almost without trying on a way to get them almost for free for linkedlist (and stream), because that's just the way linkedlist works... (a node is cons.. or empty...) So my current way of thinking is... If you care about that as a prelude user, you can use LinkedList. If you don't care much about that, you'll get better performance with Vector.

I didn't come up with a way to get non-empty vectors in prelude in a low-overhead and not-complicating way for now, but I'm keeping an open mind on the issue. But I have no plans on implementing them for now.

[emmanueltouzery]

since the title of the issue is "hello" maybe I'm not off-topic here by asking this now. I've been looking at the implementations of prepend & append in your list library. Very very neat trick with comparing the prefix & suffix length with a value stored in the vector to allow for concurrent append/prepend without eagerly duplicating the prefix & suffix! I think I'll steal this from you ;-)

however to give credit, i'm wondering, did you come up with that idea (together with the idea of storing these lengths with the depth in a single number, pretty cool as well), or if this from some paper or something like that?

[paldepind]

Slow response here :sweat: I've been busy with my exams and catching up afterward.

Hi, thank you for the feedback, I love this cross-pollination!

Me too :smile:

Thank you for sharing your thoughts with regards to non-empty structures. The way I have considered adding non-empty list is to do it completely at the type-level with no differences at run-time. To see what I mean look at this internal type MutableList. Values of type MutableList doesn't actually exist at run-time. When I create it I have to cast like here. The solution I had in mind is somewhat similar. A non-empty list would be defined like this:

type NonEmptyList<A> = List<A> & { "nonEmpty": true };

The nonEmpty property would never exist at run-time. It would only be there so that the type system could keep track of non-empty lists. Then all functions that always returns a list with elements would return a NonEmptyList (prepend, append, etc.). Additionally, all functions that benefit from this knowledge would be overloaded to take advantage of it. last would have this type:

function last<A>(l: NonEmptyList<A>): A;
function last<A>(l: List<A>): A | undefined;

What do you think about that? It seems to me that it would add extra type safe-type and isEmpty could be made into a type guard. On the other hand, it would add a lot of extra overloads and complicate the types.

Now, the annoyance... If you have three options... [option1, option2, option3]. This is Option[]. No problem. But now if the first one is somehow a Some. And the other two are only Option... Then you get a compile error... Can't put an Option in a Some array. For that reason I added on Option a method toOption(). Meant to transform Some & None to Option. Same on linkedlist and stream. That's really a weakness of typescript's type inference (it really should unify to Option) but in the end that creates some inconvenience of being provided these more precise types even if you don't really need them, and the question is, do you get enough reward for these annoyances?

That sounds weird to me. I think that TypeScript should be able to handle that correctly as long as Some is a subtype of Option. At least in some cases it inferes it correctly.

since the title of the issue is "hello" maybe I'm not off-topic here by asking this now.

Not at all :smile:

however to give credit, i'm wondering, did you come up with that idea (together with the idea of storing these lengths with the depth in a single number, pretty cool as well), or if this from some paper or something like that?

The idea of storing some elements in both ends (what I call prefix and suffix) is not my own. It's described here for instance. The trick where List stores the length of the affixes separately and use it to avoid duplicating them it is my own idea :blush: I'm happy to hear that you like it. It does make prepend and append noticeably faster. But, since the affixes are mutated and since the array lengths are not necessarily right one has to be a bit careful in the rest of the implementation. I've had a few bugs where I accidentally used the array length instead of the stored length.

The trick where several integers are stored in a single bit field is not my own. I read about it at some point in this article by the author of Bluebird. I'm sure the idea proceeds that article though. It's supposed to reduce the allocation cost and memory usage. From my benchmarks, it did make a difference but definitely not a huge one.