Compile map and filter to just one loop (transducer like)

Is this possible/desirable? Rescript does have a goal of optimized compiled code.

So this:

let result1 = [1, 2, 3]
  -> => a + 1)
  -> => a + 2)

could compile to this

var result1 = [1, 2, 3].map(function (a) {
    var a1 = a + 1 | 0;
    return a1 + 2 | 0;    

Or event to a regular loop, or a reduce in case of filter + map for instance.

1 Like

The only optimisation I know of in ReScript so far is filterMap. And AFIAK, that’s about it for OCaml too. Nothing fancy unlike, say, Haskell.

As for transducers you mentioned, this obviously can be done in userland. No idea if they’re going to be popular with ReScript crowd though. There must me a reason why they’re not mainstream.

Why not compose each steps into a single function?

Yeah, I usually go for filterMap if I’m in need of speed. In userland, there are babel plugins that “sort of” does that.

I wonder why it’s not mainstream. Even if not by default, just as an option.

You mean this? (pseudo codish)

let fn1 = => a + 1);
let fn2 = => a + 2);

let result1 = [1, 2, 3]
  -> fn1
  -> fn2

Or having just one map? That would be more efficient. But depending on the user writing efficient code, usually trading for readability, is what the compiling should help with. Google “transducers” for some more use cases.

This is an interesting question. I think the main reason transducers aren’t used as much in javascript (and so rescript too) is that they are super slow (at least in my experience). Now what you show don’t look like transducers, but rather you wanting some sort of iter/gen/stream fusion thing.

A couple of months ago I benchmarked some of the ways of doing this in rescript/javascript. (Unfortunately the code is not available publicly right now, as I’m a bit busy to clean it up, but at some point I would like to.)

Here is a quick summary of what I tested:

  • cognitect’s transducers-js
    • If you’re asking about transducers, I’m guessing you probably know clojure (or maybe haskell?) so you may have seen this library before
    • for those that haven’t seen it, transducers are like this: (whatever, input -> whatever) -> (whatever, input -> whatever) (docs)
  • jmagaram’s seq library
    • at the time I did the benchmark it was in his extras library, so it may have changed since then
    • this one is a generator (lazy/pull-based/thunk), eg:
type rec t<'a> = (. unit) => node<'a>
and node<'a> =
  | End
  | Next('a, t<'a>)
  • a quick port of c-cube’s OCaml iter library to rescript that I did
    • this one is a push-based iterator: type t<+'a> = ('a => unit) => unit
    • in OCaml it is very fast and with the certain compiler options can basically compile down to for loop
  • different levels of “chaining” Array map/reduce vs “in-lining” the steps into a single fold function

The last point I mean something like this:

// All inlined
ary->Array.filterMap(x => {
  let y = x->f1->f2->f3
  if predicate(y) {
  } else {

// Sort of inlined, sort of broken up
ary->map(x => x->f1->f2->f3)->filter(predicate)->map(x => x->f4->f5)

// All broken up

The overall results in terms of speed were (fastest to slowest)

  • array ops all inlined
  • array ops sort of inlined
  • array ops broken up
  • transducer
  • iterator
  • generator

Anyway, maybe that will be interesting for you.

Edit: It really is sort of a shame that the chaining methods aren’t more efficient in javascript, as I do think it helps with readability. I wonder if there is a way to do them efficiently, as it is a nice style I think.

A bit off topic, but OCaml has a lot of different ways of doing this sort of thing. You might find this benchmark interesting.


Yeah, I’m not after a real transducer, as they are very slow for small arrays. Here are my WIP tests:

      name         mean(ns)   median(ns)     op/s      slower   slower
----------------- ---------- ------------ ----------- -------- --------
 imperative          154.96       154.39   6,453,263    1.00x    0.00% FASTEST
 declarative         456.21       456.00   2,191,972    2.94x   66.03%
 nativePipe          398.10       397.58   2,511,902    2.57x   61.08%
 belt                365.36       361.59   2,737,035    2.36x   57.59%
 iterOps            6536.78      6440.12     152,981   42.18x   97.63%
 lazy               7584.46      7394.84     131,849   48.94x   97.96% SLOWEST
 transducersJs      1770.48      1757.49     564,819   11.43x   91.25%
 ppipe              1139.07      1140.20     877,906    7.35x   86.40%
 ramda               403.58       399.30   2,477,799    2.60x   61.60%
 @arrows             426.57       427.96   2,344,283    2.75x   63.67%
 lodash/fp           402.54       400.84   2,484,224    2.60x   61.50%

The problem of “filter().map()” instead of a “reduce” is the O(n) vs O(1) complexity. The more steps you have, the slower it gets.

So this 3 operations

    chain: input => input
        .filter(x => x % 2 !== 0)
        .map(x => x * 3)
        .reduce((a, b) => a + b, 0),

are ~3x slower than

    reduce: input => input.reduce((total, x) => {
        return x % 2 !== 0 ? total + x * 3 : total;
    }, 0),

Thank you for sharing your results.


I have always thought this was a big gain for FP to be able to do this without writing it explicitly. Though maybe the compilers under Rescript do it just as well?

Nice, thanks for posting. Just an FYI, that link is broken for me. …not that I can complain, as I didn’t even post my code :sweat_smile:

I saw a similar behavior as well. I guess it’s just something the javascript engine doesn’t optimize well…

Btw, were you running your benchmarks on node, in the browser? I saw ops/sec differences up to three orders of magnitude between the generator and the “everything in one fold function” way. …I should really post my code, but it was actually pretty similar to that example I gave above: map a couple functions, filter, then map a couple more (all pretty simple math functions), with the array size of 1,000 items and 10,000 items.

It was private, sorry. It’s public now

1 Like

Node 20.3.1, local. There is a nice benchmark lib for multiple browsers, but I haven’t used it yet.

Also interesting: The Declarative Cost in Javascript. The guy ran the benchmark for ~17hours, with array of many sizes.


The main purpose of transducer is to abstract away input/output types of the collection, and they only get performance gain where lazy evaluation is by default like Haskell and Clojure, because transducers behave as eager.

I’m dubious that transducers will be used well in ReScript.