benji6/imlazy

😴 Functional programming with lazy immutable iterables

imlazy

Functional programming with lazy immutable iterables

Introduction

imlazy let's you harness the power of the ES2015 iteration protocols. With it you can create infinite or circular iterables which are lazy, immutable and performant. For instance:

const { filter, range } = require("imlazy");

const isEven = (x) => x % 2 === 0;

const positiveIntegers = range(1, Infinity); // => (1 2 3 4 5 6 7 8 9 10...)
const positiveEvenIntegers = filter(isEven, positiveIntegers); // => (2 4 6 8 10 12 14 16 18 20...)

All functions are auto-curried and iterable-last (like in lodash/fp and ramda) which allows developers to build up reusable functions with partial application like so:

const { take } = require("imlazy");

const takeThree = take(3);

const oneTwoThree = takeThree(positiveIntegers); // => (1 2 3)
const twoFourSix = takeThree(positiveEvenIntegers); // => (2 4 6)

Putting iterables into an array, or set, or using them as arguments to a function call is simple (be careful with anything infinite or circular though!):

[...twoFourSix]; // => [2, 4, 6]
Array.from(twoFourSix); // => [2, 4, 6]
new Set(twoFourSix); // => Set { 2, 4, 6 }
Math.max(...twoFourSix); // => 6

Because imlazy uses the ES2015 iteration protocols it is compatible with all native iterables (including the Generator, String, Array, TypedArray, Map and Set types) and many libraries (including Immutable.js):

const { sum } = require("imlazy");
const Immutable = require("immutable");

sum(twoFourSix); // => 12
sum([2, 4, 6]); // => 12
sum(new Set(twoFourSix)); // => 12
sum(Immutable.List.of(2, 4, 6)); // => 12

const fibonacciGenerator = function* () {
  let [a, b] = [0, 1];
  while (true) yield ([a, b] = [b, a + b])[0];
};

take(8, fibonacciGenerator()); // => (1 1 2 3 5 8 13 21)

All iterables created by imlazy are frozen with Object.freeze so, not only are they lazy, they're also immutable.

If you want to find out more about the ES2015 iteration protocols this MDN article is a good place to start.

Getting Started

Installation

npm i imlazy

API Documentation

API docs are here.

Support

imlazy is written in ES2015 and will run in any environment that supports that specification. If using in Node.js use version 6 or greater.

Debugging

imlazy implements a custom toString method for the iterables it returns. Just invoke String on an iterable returned by one of imlazy's functions to see what's inside it:

String(range(1, 8)); // => (1 2 3 4 5 6 7 8)
String(range(1, Infinity)); // => (1 2 3 4 5 6 7 8 9 10...)

The custom toString method can handle nested and infinite iterables (in which case it lists the first 10 elements followed by ellipsis) and uses a LISP-like notation to differentiate iterables from arrays and other JS data structures

Static Land

This library implements the following Static Land algebraic types:

• Functor
  • Apply
    • Applicative
    • Chain
      • Monad
• Foldable
  • Traversable
• Filterable
• Semigroup
  • Monoid
• Setoid

Performance

There is a benchmarks dir in the root of this repo. Here are the results on my machine running node 8.9.3:

benchmarks/filter.js

imlazy - filter 1x over array x 3,762 ops/sec ±0.27% (98 runs sampled)
imlazy - filter 2x over array x 3,104 ops/sec ±0.37% (96 runs sampled)
imlazy - filter 3x over array x 3,022 ops/sec ±0.18% (100 runs sampled)
native - filter 1x over array x 42,003 ops/sec ±15.10% (90 runs sampled)
native - filter 2x over array x 21,413 ops/sec ±13.20% (98 runs sampled)
native - filter 3x over array x 18,075 ops/sec ±13.47% (95 runs sampled)

benchmarks/map.js

imlazy - map 1x over array x 2,726 ops/sec ±0.24% (99 runs sampled)
imlazy - map 2x over array x 1,584 ops/sec ±0.28% (98 runs sampled)
imlazy - map 3x over array x 999 ops/sec ±0.44% (97 runs sampled)
native - map 1x over array x 60,221 ops/sec ±17.07% (96 runs sampled)
native - map 2x over array x 9,820 ops/sec ±10.96% (97 runs sampled)
native - map 3x over array x 3,899 ops/sec ±0.16% (100 runs sampled)

Influences

• Ramda
• Haskell
• Clojure

imlazy's Issues

increase performance splitEvery

I'm reading about splitEvery and I've seen that maybe #22 is the reason to do slice eager. However I think that maybe yo can optimize splitEvery without doing slice eager.

function* splitEvery(n, iterable) {
    const iterator = iterable[Symbol.iterator]()
    const chunk = []
    let state = iterator.next()
    let i = 0
    while(!state.done) {
        if (i < n) {
            chunk.push(state.value)
        } else {
            yield chunk
            chunk = [state.value]
            i = 0
        }
    }
    if (chunk.length > 0) {
        yield chunk
    } 
}

It has a little caveat: if n === Infinity, splitEvery could potentially use infinite cached data.

prevent cycle of empty iterable

Hi,

Implementation of cycle:

module.exports.cycle = xs => genToIter(function * () {
  while (true) yield * xs
})

produces infinite loop that could be avoided:

[...cycle([])] // could be [] but produces and infinite loop.

equals is not enough lazy

It is obvious that is imposible to avoid this infinite loop

const list1 = drop(1, range(0, Infinity))
const list2 = drop(1, range(0, Infinity))
equals(list1, list2) // infinite loop

But what about that?

const naturals = range(0, Infinity)
equals(naturals, assoc(2, 42, naturals)) // It should return false

I think that it could return false using finite time.

Cheers!

Can reduce make lazy sequence?

Current implementation of reduce:

let reduce = curry((reduceFn, init, iter) => {
  let acc = init;
  for (let x of iter) {
    acc = reduceFn(acc, x);
  }
  return acc;
});

Question: can it be updated somehow in a way that given a lazy sequence it would return a lazy sequence. Can it be done in an effective way?

It is not only a good theoretical question, the answer implies consequences. If the answer is yes than transducers can run over lazy sequences (generators). Then they should be seen as a fundamental building block for collection processing instead of generators (in dynamically typed language like JS). If the answer is no than transducers and generators kinda overlap and library API will suffer from expression problem (different code branches, reproducing the same behavior for lazy and eager sequences).

An attempt to address this question: https://github.com/Gozala/reducers

`partition` is caching values.

Hi @benji6

I was reading partition implementation and it is implemented breaking your idea about not caching values.

I propose use filter for the implementation:

module.exports.partition = curry((f, xs) => genToIter(function * () {
    yield filter(f, xs)
    yield filter(x => !f(x), xs)
}))

Cheers!

repeat does not follow the specs

Hi,

I look that repeat method does not follow the specs. It has the correct signature: repeat a -> [a] but description and examples is not consistent with the signature:

Returns a new iterable where every value is the given value and there are as many values as the given count

const repeat42 = repeat(42)
repeat42(3)) // => (42 42 42)
repeat42(Infinity)) // => (42 42 42 42 42 42 42 42 42 42...)

Cheers!

Benchmarks compared to ramda and native

Hi @benji6

I've read benchmarks about transducers-and-native.js file and I think that the benchmarks related to ramda are a little bit unfair. The function consumeIterable takes an iterable and transforms it to array. Then the test is about applying some filters and maps to an iterable and then transform to array. However, ramda performs it using the function R.into([]). For that, taking the array that returns R.into and iterating it over is a little tricky because the iterable is traversed twice.

I mean, I think that the ramda tests could be simplified to:

const ramdaTransducerArrayBenchmark = xs => R.into([], R.compose(
  R.map(add10),
  R.map(triple),
  R.filter(divisibleBy5),
  R.filter(isEven)
), xs)

const ramdaTransducerInfiniteBenchmark = xs => R.into([], R.compose(
  R.map(add10),
  R.map(triple),
  R.filter(divisibleBy5),
  R.filter(isEven),
  R.take(length)
), xs)

The same happens with native test.

Cheers!

Performance

It's awesome that in node 8 performance is exceeding that of the native array methods, but can we do better? In particular it would be amazing to gain some sort of parity with transducers. It seems that the extra work being done by imlazy consists in creating intermediate iterables rather than composing transformations directly over a single iterable. This makes imlazy much nicer to use in many ways - intermediate iterables can massively help with code readability and understandability. Transducers are not so easy to understand or use. But maybe there is a way to reduce this extra work while still keeping the iterable interface at each transformation step?

slice & infinite loops

Hi!

Implementing lazy groupBy method on iterum I noticed that I have some problems with slice method with infinite iterables.

I checked that in imlazy library there are the same problems. For example:

Given this iterables:

const naturals = range(0)(Infinity)
const naturalsOneTwo = map(e => [...e])([naturals, [1], [2]])
const oneTwoNaturals = map(e => [...e])([[1], [2], naturals])

• slice(Infinity)(Infinity)(naturals) produces infinite loop but Infinity is not less than Infinity. Then, we can infer that returns empty iterable.

• The same case is [...slice(5)(2)(naturalsOneTwo)]. It produces an infinite loop but 5 is greater than 2. Then, we can infer that returns empty iterable.

• [...slice(0)(2)(oneTwoNaturals)] produces an infinite loop but if third element of iterable is not computed the method should return [[1], [2]]. It seems that slice computes one more element that requires.

Here my first attempt to solve these problems. Maybe you can find a implementation less verbose.

Merge function that given two sorted lists produces a sorted list containing the union of each list’s elements.

Inspiration from here

Add sum function

slice(-10, -2) === slice(0, 8)

I analyzed the code for slice implementation and it seems that slice(-10, -2) behaves equal than slice(0, 8). Is the expected behaviour?

The automated release is failing 🚨

🚨 The automated release from the master branch failed. 🚨

I recommend you give this issue a high priority, so other packages depending on you could benefit from your bug fixes and new features.

You can find below the list of errors reported by semantic-release. Each one of them has to be resolved in order to automatically publish your package. I’m sure you can resolve this 💪.

Errors are usually caused by a misconfiguration or an authentication problem. With each error reported below you will find explanation and guidance to help you to resolve it.

Once all the errors are resolved, semantic-release will release your package the next time you push a commit to the master branch. You can also manually restart the failed CI job that runs semantic-release.

If you are not sure how to resolve this, here is some links that can help you:

• Usage documentation
• Frequently Asked Questions
• Support channels

If those don’t help, or if this issue is reporting something you think isn’t right, you can always ask the humans behind semantic-release.

---

Invalid npm token.

The npm token configured in the NPM_TOKEN environment variable must be a valid token allowing to publish to the registry https://registry.npmjs.org/.

If you are using Two-Factor Authentication, make configure the auth-only level is supported. semantic-release cannot publish with the default auth-and-writes level.

Please make sure to set the NPM_TOKEN environment variable in your CI with the exact value of the npm token.

---

Good luck with your project ✨

Your semantic-release bot 📦🚀

Implement traversable

Hi there. Many thanks for the useful library. I see that the library implements transpose, but this can be generalized to an implementation of Traversable (your pick of traverse or sequence), which will let you transpose (Applicative f) => Iterable (f a)s into f (Iterable a)s.

The degenerate case of transpose is then just sequence-ing an Iterable (Iterable a).

Random considerations

Cool library, Ben 👍

I've reviewed your API and it seems very close to Ramda.

My random questionmarked considerations:

1. Rename makeCircular to cycle just as it is in Haskell and Clojure?
   http://hackage.haskell.org/package/base-4.8.1.0/docs/Prelude.html#v:cycle
   https://clojuredocs.org/clojure.core/cycle
2. API lacks exact "typed" signatures. Unfortunately we're far from having common conventions for JS type notation. I like how Ramda adapts Haskell(-ish) notation, though.
3. Difference bettween assoc and insert? Second one mimics Ramda while first one contradicts it.
4. Both Haskell and Ramda use all name for every. Clojure uses every though.
   Which one is better?
5. Implement sortBy equivalent?
6. Use freeze only on production for better performance? Example.

Everything else seems predictable. Great. My appreciation!

slice is not lazy now

Hi @benji6,

I'm doing some benchmarking comparing to your package and I've noticed that slice performance decrease when increase the first parameter of slice. I reviewed your code and I found the problem

module.exports.slice = curry((n, m, xs) => {
  if (n >= m) return module.exports.empty()
  let iterator
  if (n > 0) {
    iterator = xs[Symbol.iterator](noValueSymbol)
    let i = n
    while (i--) iterator.next(noValueSymbol)
  } else {
    iterator = xs[Symbol.iterator]()
  }
  const generatorFactory = iterToGenFactory(iterator)
  return genToIter(function * (msg) {
    let j = m - n
    const iterator = generatorFactory(msg)
    while (j--) {
      const {done, value} = iterator.next(msg)
      if (done) return; yield value
    }
  })
})

This part:

    iterator = xs[Symbol.iterator](noValueSymbol)
    let i = n
    while (i--) iterator.next(noValueSymbol)

is executed eagerly and produces bad performance when n is big.

The automated release is failing 🚨

🚨 The automated release from the master branch failed. 🚨

I recommend you give this issue a high priority, so other packages depending on you could benefit from your bug fixes and new features.

You can find below the list of errors reported by semantic-release. Each one of them has to be resolved in order to automatically publish your package. I’m sure you can resolve this 💪.

Errors are usually caused by a misconfiguration or an authentication problem. With each error reported below you will find explanation and guidance to help you to resolve it.

Once all the errors are resolved, semantic-release will release your package the next time you push a commit to the master branch. You can also manually restart the failed CI job that runs semantic-release.

If you are not sure how to resolve this, here is some links that can help you:

• Usage documentation
• Frequently Asked Questions
• Support channels

If those don’t help, or if this issue is reporting something you think isn’t right, you can always ask the humans behind semantic-release.

---

Invalid npm token.

The npm token configured in the NPM_TOKEN environment variable must be a valid token allowing to publish to the registry https://registry.npmjs.org/.

If you are using Two-Factor Authentication, make configure the auth-only level is supported. semantic-release cannot publish with the default auth-and-writes level.

Please make sure to set the NPM_TOKEN environment variable in your CI with the exact value of the npm token.

---

Good luck with your project ✨

Your semantic-release bot 📦🚀

filter benchmarks: divisibleBy{X} variables does not correspond to the real operations that do

Hi @benji6

I was reading the benchmarks implementation and I found in benchmarks/filter.js:

const divisibleBy2 = x => x + 1
const divisibleBy3 = x => x / 2
const divisibleBy5 = x => 3 * x

It seems a copy past of benchmarks/map.js

Cheers!

Iterables vs arrays for tuples in zip function

zip most common usage is to combine values with their indexes

Now we have to deal with generators, inside newly created kinda-tuples.

Generators are still broken in Node6. Take console.log:

// nope
console.log(zip(["a", "b", "c"], range(1, Infinity))) // {}

// nope
console.log(Array.from(zip(["a", "b", "c"], range(1, Infinity)))) // [{}, {}, {}]

// yep
console.log(Array.from(zip(["a", "b", "c"], range(1, Infinity))).map((x) => Array.from(x))) // [["a", 0]...]

Too much pain for a normal workflow IMO.

So I think it would be practical to use basic arrays for those tuples.
At least until some serious tech update will change the status quo.

For a sidenote: perfect console.log should output, say, first 10 items of an iterable printing ... if there are more.