maths
maths copied to clipboard
gleam-community
Make functions in the combinatoric/sequences modules iterator-based instead of list-based
The functions in the combinatorics and sequences modules could be improved by making them return an iterator instead of a list, which will be prohibitively expensive to do for larger inputs. See related comments and info by DanielSherlock:
No worries, I'm not in any rush (and I hope you aren't too)!
Actually, I thought after posting this pull request: Oh before I start writing tests and docs I should go and look at the standard (or standard-ish) libraries of other languages to see how they handle this case. Then I got distracted. And now it is now.
As far as I can tell, it's like this:
| Language | Behaviour A | Behaviour B | Iterator |
|---|---|---|---|
| Javascript (Deno) | permutations |
||
| Ruby | permutation |
✅ | |
| Scala | permutations |
✅ | |
| Swift | permutations |
uniquePermutations |
✅ (Sequence) |
| Julia | permutations |
multiset_permutations |
✅ |
| Rust | permutations |
✅ | |
| Nim | nextPermutation |
✅ (mutating) | |
| C++ | next_permutation |
✅ (mutating) | |
| Haskell | permutations |
✅ (everything is lazy) | |
| Python | permutations |
✅ | |
| Clojure | permutations |
✅ (lazy-seq) |
(I had hoped to find a list-permuting function in the standard (or standard-ish) libraries of Erlang or Elixir, and prioritise similarity to that. But no luck, not even Elixir's Math library has this. Other languages that seem to have nothing (semi-)official include Java, Elm, and Lobster. Though perhaps I wasn't looking hard enough.)
Personally, I like the way Swift handles it. Plus, their documentation is clear (with examples) and also has some hints for possible efficient implementations. The Clojure implementation seem nice and clean too, and might be easy to port. Not all other documentation was similarly clear...
Another thing to note: Almost all of the languages I surveyed returned an iterator (or equivalent thing in that language), even when given a list/array/etc. If we are going to be worried about performance, we might consider doing the same. This after all exactly the sort of function where iterators make a lot of sense:
- It does not take a particularly large input list for the output list to be very very large indeed.
- The state needed to generate the next permutation is small.
Originally posted by @DanielSherlock in https://github.com/gleam-community/maths/issues/9#issuecomment-1811371118
