reasonml-old / bs-containers

[ABANDONED] Containers for Bucklescript application
https://buckletypes.github.io/bs-containers/
Other
27 stars 6 forks source link

Make the Sequence type functional #26

Open bordoley opened 7 years ago

bordoley commented 7 years ago

The definition of Sequence requires the use of side effects and provides no way to abandon iteration. At the surface, Sequence appears to provide similar functionality to Immutable.re's Iterable type, with less flexibility. I would suggest either changing to Sequence to implement an ocaml compatible monadic sequence, or an api similar to Immutable.re's Iterable, which is implemented using a reduceWhile function, taking advantage of a GADT to avoid allocations for empty Iterables. See: https://github.com/facebookincubator/immutable-re/blob/master/src/core/Iterable.re

bordoley commented 7 years ago

Another option would be to implement Immutable.re's Iterator module instead.

c-cube commented 7 years ago

Just curious, why is Sequence less flexible? Side effects are not exposed to the user anyway…

ghost commented 7 years ago

@c-cube on a not so related note, could you enlighten me on some use cases of iterators other than say populating a binary tree with a list without knowing their internal structure? I find most the time I can just use List.map etc to iterate over a some structure? Thanks.

bordoley commented 7 years ago

@c-cube: I meant that Immutable.re's Iterable module is more flexible and to a degree more pure (even though some operators use side effects internally) as it is implemented using a reduction function that supports early termination via a while check. This allow implementation of more operators such as take(). The monadic iterator's main benefits are that it supports zipping and eager seeking (Immutable.re's Sequence). The reduce/while approach is faster, since most operators can be implemented allocation free.

@dorafmon: In general, whenever chaining operators you should prefer the iterator/sequence approach. In the stdlib, functions such as List.map, etc. constantly allocate memory, since they are eager. List.map is actually particularly bad because the default implementation is not even tail recursive.

c-cube commented 7 years ago

@dorafmon I use them a lot for various purpose (sequence is very very low overhead):

the debate as to which iterator type is the best has been going on for a while, without clear agreement. I'll just say that Sequence is very efficient for most uses (as can be shown in benchmarks, especially with flambda), that it is structural (can define it in several libraries in a compatible way, unlike a fold approach that requires a nominal record for the quantification) and that it works with stdlib structures, such as Queue.t or Hashtbl.t.

For reference, slides of a talk I gave on sequence.