Spread the love: transduce + chain

[Izhaki]

The secretive laziness

As some of you know, some of us are using Ramda to compose lazy sequences. Although the library supports it, it isn't advertised anywhere, which means people like me have used lazy.js along side Ramda, although the latter alone would do.

Serendipity

Now if you're lazy, the way to surf the docs would be to search for "transducer" or "transformer".

I've been looking for months for a way to do something. But the Ramda docs said "No can do" (or more precisely, it didn't say "can do"). So I have spent 3 weeks writing an original lazy tree traversal implementation.

Then one day, by sheer accident, my eyes landed on chain. Not a single hint it would work, but I had to give it a go. And guess what?

[REPL]

const tapLog = R.tap( (what) => console.log(what) )

const suits = ['♠', '♥', '♦', '♣']
const ranks = ['1', '2', '3', '4', '5', '6', '7', '8', '9', 'J', 'Q', 'K', 'A']

const addSuit = ( rank ) => R.xprod( [rank], suits)

var transducer = R.compose(
  R.chain(addSuit),
  tapLog,
  R.take(2)
);

R.into([], transducer, ranks);

Outputs:

["1","♠"] // console.log
["1","♥"] // console.log

// => [["1", "♠"], ["1", "♥"]]

So it turns out chain works with transducers.

Why is it such a big deal?

Because it allows one-to-many lazy traversal, which enables the colossal ability to lazily traverse trees and graphs, not just lists.

Here's an example, showing both breadth- and depth- first lazy graph traversal, albeit naïve.

The issue

There is no mentioning of this in the docs.

If chain plays nicely with transduce, please let it be known.

[kedashoe]

Would you like to submit a PR to update the docs to match other functions which mention transducer support?

[Izhaki]

Sure.

I guess that will simply involve adding:

Acts as a transducer if a transformer is given in list position.

?

[kedashoe]

👍

[Izhaki]

Seems like it has been done already:

6377838

Hmmm... by you @kedashoe

[kedashoe]

whelp, glad we got that cleared up :|

[buzzdecafe]

nonetheless, thanks for the excellent example!

[Izhaki]

@kedashoe @buzzdecafe and @CrossEye

Forgive me for this is more of a question, but one too long for gitter and one that others landing on this issue may benefit from.

Chain branch isn't lazy.

If you look at this revised example:

const tapLog = R.tap( (what) => console.log(what) )

const suits = ['♠', '♥', '♦', '♣']
const ranks = ['1', '2', '3', '4', '5', '6', '7', '8', '9', 'J', 'Q', 'K', 'A']

const addRank = (suit) => R.map(concat(suit),ranks)

var transducer = R.compose(
  R.chain(addRank),
  tapLog,
  R.take(2)
);

R.into([], transducer, suits);

Then you probably know that R.map(concat(suit),ranks) will not be lazily evaluated - all the ranks will be mapped (creating intermediate array), and only then chain will 'pipe' them one by one down the transducer sequence.

This is not an issue, unless you are mapping 680k graph nodes.

Can this be achieved?

Now I've looked at the implementation of chain, and I believe that the _makeFlat branch makes this impossible to achieve?

However, both the tests for reduce and the source show examples of 'Iterable' (either symIterator or .next()). Intuitively, I thought it would be possible to return something like this from the mapper function given to the chain function; but like many other intuitions, this one was as good as John Lennon's decision to write songs whilst sober.

Yet I have a feeling that if you wire things right, you can get it done. But for the life of me I can't figure out how.

Goal

Essentially what I'm after is in addition to the laziness on the tranducer sequence, laziness on the chain branch (which can do one to many).

By laziness I mean - one array item at a time. Like so:

[polytypic]

I'm pretty sure it can be achieved with transducers, but you will need to replace the chain implementation. Here is a simple stream implementation that achieves the desired one-at-a-time processing.

[Izhaki]

@scott-christopher has answered my question on SO. I share the solution here:

const combineWith = (fn, xs) => xf => ({
  // proxy both `init` and `result` straight through
  // see internal/_xfBase.js
  '@@transducer/init': xf['@@transducer/init'].bind(xf),
  '@@transducer/result': xf['@@transducer/result'].bind(xf),

  // combine the item at each step with every element from `xs`
  // using `fn`, returning early if `reduced` is ever encountered
  '@@transducer/step': (acc, item) => {
    for (let i = 0; i < xs.length; i++) {
      acc = xf['@@transducer/step'](acc, fn(item, xs[i]))
      if (acc['@@transducer/reduced']) return acc
    }
    return acc
  }
})

const suits = ['♠', '♥', '♦', '♣']
const ranks = ['1', '2', '3', '4', '5', '6', '7', '8', '9', 'J', 'Q', 'K', 'A']

const tapLog = R.tap(console.log.bind(console, 'tapLog'))

const transducer = R.compose(
  combineWith(R.concat, ranks),
  tapLog,
  R.take(2)
)

console.log('result', R.into([], transducer, suits))