Immutable list for Sanctuary

[paldepind]

Hi all,

I've been working on a fast immutable list for JavaScript with a functional API. The library is designed to be used together with other functional libraries and replace the usage of arrays. Currently, the
library includes a wrapper that makes the it work seamlessly with Ramda. I would like to do something similar for Sanctuary. I've opened this issue to hear if there's any interest in that and get feedback on how best to do it.

The two primary reasons for using List together with Sanctuary would be:

• Safety. JavaScript arrays are inherently mutable. When using arrays in functional code the only thing that prevents us from mutating them is our own self-discipline. In my experience, this is sometimes not good enough and can be a source of bugs, especially on teams. Immutable data structures, on the other hand, guarantees that mutations don't happen.

• Performance. Immutable data structures can give better performance. For instance, S.init on arrays take O(n) time, L.init on List takes constant time. S.concat on arrays takes O(n + m) time but L.concat on List takes O(log(n)) time. Furthermore, List has been carefully optimized such that the constants are also low.

To make List work smoothly with Sanctuary I think the following could be done in a Sanctuary specific export:

• Export all List function wrapped with sanctuary-def. This would give Sanctuary currying and run-time type checking.
• All List functions that can return undefined (at, head, etc.) should instead return a Sanctuary Maybe.
• Maybe provide Sanctuary aliases. For instance, List has includes which is elem in Sanctuary.

I'd love to hear what you all think about the idea and if there's any interest in this? Is there anything that could be done in addition to the above?

[CrossEye]

Creating something like this has been on my personal TODO list for a long time. I'm glad that someone has actually done it. It looks very nice, @paldepind!

[paldepind]

@CrossEye Thank's a lot Scott. It's great to hear that you feel that way. Let me know how your experience is if/when you get a chance to try the library.

[davidchambers]

This is very exciting, Simon!

Export all List function wrapped with sanctuary-def. This would give Sanctuary currying and run-time type checking.

👍

All List functions that can return undefined (at, head, etc.) should instead return a Sanctuary Maybe.

👍

Maybe provide Sanctuary aliases. For instance, List has includes which is elem in Sanctuary.

S.elem operates on any Foldable, so the Sanctuary wrapper need not even expose a List-specific elem function.

One thing that would be interesting to consider is whether S.head and friends could be generalized to operate on List values as well as Array values. I believe you have given this matter some thought, Simon. Have you defined an interface which list-like structures can implement?

[paldepind]

@davidchambers

This is very exciting, Simon!

😄

One thing that would be interesting to consider is whether S.head and friends could be generalized to operate on List values as well as Array values. I believe you have given this matter some thought, Simon. Have you defined an interface which list-like structures can implement?

One can implement head on any Foldable. But one probably doesn't want to do that as it will run in O(n) time even on data structures that support head in constant time.

Foldable has a bit of a dilemma. In theory, you can derive a lot of useful things from just foldr: elem, head, nth, length, find, indexOf, and much more. But in practice these functions will perform very poorly when derived from foldr\ foldl. For instance elem should stop iterating as soon as a match is found. But, S.elem wont do that so on average it will be twice as slow as it should be. For me personally that is a deal-breaker.

Haskell has a decent solution to the dilemma. Their Foldable type class includes a lot of derivable methods. Thanks to Haskell's support for default method implementations implementors of Foldable can optionally override these with performant versions for their data structure. Thus Haskell's Foldable can be used for additional things without being prohibitively expensive. This stands in contrast to the Foldable in Fantasy Land and Purescript (PureScript doesn't support default methods implementations so they can't use the Haskell solution) which is essentially only good for reduce/foldr/foldl.

Haskell's solution could be mimicked in JavaScript by defining a Foldable with a bunch of methods and then offering a mixin function that installs default method implementations. The problem is that how many methods to include in such a Foldable becomes arbitrary (there are methods that could've been included in Haskell's Foldable but which are not). A second downside is that it makes the Foldable definition a lot bulkier. I suspect that due to these issues proposing such a thing for Fantasy Land would be controversial. fantasyland/fantasy-land#224 would have made it possible to define elem and more on Fantasy Land Filterables with acceptable performance. But the PR didn't gather much interest so I'm guessing that Fantasy Land users are fine with Filterable giving them only reduce. And maybe it's best that way.

By taking the same approach as what I've done for Ramda using List and Sanctuary together would mean that people would be able to do

import * as S from "sanctuary";
import * as L from "list/sanctuary";

And then rely on the fact that for every S.foo that operates on arrays there is a matching L.foo that operates on immutable lists. This has the advantages:

• The API is immediately familiar
• Moving code between lists and arrays is easy
• It is explicit in the code if it is operating on immutable lists or plain arrays

IMO this is quite nice but the downside is, of course, that it isn't actualy polymorphism so one can't write code that works for both lists and arrays at the same time.

[davidchambers]

Your proposal sounds good to me, Simon.

How would you like to proceed? Would you like the project to live in the @funkia account, the @sanctuary-js account, or some other account? I don't mind. If it's to live in the @sanctuary-js account I would like it to be written in ES5 in accordance with the conventions adopted for other Sanctuary projects. ;)

[paldepind]

Good question. I think there are a few options:

1. The code lives inside the current npm package and git repository
2. It gets a seperate npm package but still lives in the main list git repository
3. It gets its own npm package and git repository

Number 1 is what I've currently done for Ramda. There is a file for Ramda that users can import by doing require("list/ramda"). The benefit is that there only is a single npm package to manage. But there are some downsides as well so maybe that is not the best way to do it?

I'm thinking number 2 may be the best option. Having it in a single repository makes it easy to keep things in synchrony. For instance I have a test in place that ensures that the curried Ramda file has all the functions that the main file has. This ensures that I don't add a new function and forget to add it in the Ramda file.

What do you think?

[davidchambers]

It makes sense to me for the Sanctuary wrapper to be handled in the same way as the Ramda wrapper. The peer dependency ({"ramda": "*"}) concerns me. Shouldn't this be more specific to make it clear which particular version of the Ramda API the wrapper mirrors? Functions are occasionally renamed, as you know.

I'm thinking number 2 may be the best option.

I agree. Would you do the same for the Ramda wrapper, or do you see significant differences between the two wrappers which warrant different treatment?

[paldepind]

The peer dependency ({"ramda": "*"}) concerns me. Shouldn't this be more specific to make it clear which particular version of the Ramda API the wrapper mirrors? Functions are occasionally renamed, as you know.

You're right, * isn't optimal. But, only equals and curry are used from Ramda and they're fairly stable I think. Would it be better to specify >=0.15.0? 0.15.0 is the version in which equals was added. That range doesn't have to change whenever a new Ramda version is released but on the other hand it assumes that equals and curry won't change.

Would you do the same for the Ramda wrapper, or do you see significant differences between the two wrappers which warrant different treatment?

I agree with you that it makes sense to do the same thing for both Ramda and Sanctuary.

I've looked at a tool call Lerna which looks like it would make it possible to manage option number 2 with very little overhead. The core list, the Ramda wrapper and the Sanctuary rapper would each live in a directory in the same repo. Lerna would make it easy to run tests for them all at once and to publish new package versions in sync.

I would like it to be written in ES5 in accordance with the conventions adopted for other Sanctuary projects. ;)

That is fine for me 😄 Are the conventions documented or should I just look at the existing code?

[davidchambers]

I was thinking of the peer dependency from the perspective of one of your users. You claim that the API of your wrapper matches that of Ramda, but you must qualify this claim. If R.contains becomes R.includes, for example, your API will need to change accordingly. If someone then uses the latest version of your library with an older version or Ramda, there will be a mismatch between L.includes and R.contains. You could provide an alias to handle this particular case, but making the wrapper mirror every version of Ramda at once seems fraught with difficulty. ;)

The core list, the Ramda wrapper and the Sanctuary rapper would each live in a directory in the same repo.

👍

Are the conventions documented or should I just look at the existing code?

@sanctuary-js projects all use sanctuary-style, but since this project will live in the @funkia account it should follow Funkia conventions rather than Sanctuary conventions. :)

[Avaq]

Would it be better to specify >=0.15.0?

I usually use >=minimum_feature_complete_version <next_major_version. So in your case >=0.15.0 <0.26.0. This gives you the chance to evaluate whether any breaking changes introduced in a major version release impact your library, before expanding the range to the next major version and publishing a patch.

[paldepind]

@davidchambers You're right that there need to be some sort of documentation about which version of List goes with which version of Ramda. But I'm not sure if the peerDependency property is the right place to do it? I think of the peer dependency as saying "I need this version of this library in order to work". But in order to just work the List Ramda wrapper only needs curry and equals.

@Avaq Good suggestion! That's definitely better than my idea 😄

[paldepind]

Thanks a lot for the feedback in this thread 😄 I'll probably start working on this in a week or so. I'll let you know when I've got something to share.

[paldepind]

I've realized that I'd like to offer a curried variant of List that doesn't depend on Ramda for people who want currying but doesn't want the dependency on Ramda. I've then decided that it's not worth it to maintain two near-identical curried variants. Ramda users can easily use the dependency-free one.

Therefore the Ramda integration no longer has to be a separate package and then using Lerna doesn't seem like it's worth the additional complexity. I was, therefore, thinking that a separate sanctuary-list repository in @sanctuary-js would be the best option. The approach also has the benefit that people can make contributions to list without having to know implement the sanctuary-list part as well (for instance if they implement a function that function should be included wrapped in a def in sanctuary-list).

What do you think?

[davidchambers]

Sounds good to me, Simon. I have created sanctuary-list and granted you write access. Please create a branch named paldepind/everything or similar and do your work there. Once you're ready to share your work you can open a pull request. I look forward to seeing it. :)

[RichardForrester]

Is this still happening?

@paldepind

[davidchambers]

I have needed List a in various test suites, and have defined it in several places. I will add documentation, then make the code available on GitHub and npm. At a later point it should be possible to replace my straightforward implementation with @paldepind's efficient one. :)