transducerを実装したjsコードを書いてみましたが、合っているか分かりません
退会済みユーザー
総合スコア0

Question

## 調べた事
#### Js
- [Transducers: Efficient Data Processing Pipelines in JavaScript@Eric Elliott -Medium](https://medium.com/javascript-scene/transducers-efficient-data-processing-pipelines-in-javascript-7985330fe73d)
- [Understanding Transducers in JavaScript@Roman Liutikov -Medium](https://medium.com/@roman01la/understanding-transducers-in-javascript-3500d3bd9624)

半分位から、特によく分からなくなった記事
- [What's a Transducer?](https://raganwald.com/2017/04/30/transducers.html)
- [Simpler Transducers for JavaScript](https://codeburst.io/simpler-transducers-for-javascript-4d02a0926648)
- [How to make your data transformations more efficient using transducers](https://www.freecodecamp.org/news/efficient-data-transformations-using-transducers-c779043ba655/)


#### Clojure
- [TRANSDUCERS ARE COMING by Rich Hickey -cognitect](http://blog.cognitect.com/blog/2014/8/6/transducers-are-coming)
- [Transducers -Clojure.org](https://clojure.org/reference/transducers)

Clojureは公式ページのチュートリアル2ページほど読み、基礎構文初歩は理解しました(CommonLispの基礎部分を以前少しやっており理解できました)。transducerの例に出てくるライブラリの関数等は、逐次調べ、例題コードの理解率は75%ほどです、多分。。


## 質問
以下の理解・jsコードが合っている・間違っている のかを知りたいです。ご教授宜しくお願い致します<(_ _)>????


### Transducerとは
1. `compose()`して返却された関数構成群がtransducerである。
2. transducerを実行するには、❶`transduce()`に渡す以外にも、❷`transducer()`に配列を渡す事でも実行できる。
5. ❷の内部処理において、中間値が生成されるような処理ではなく、下画像のような効率的な処理がなされる。

![process_transducer](43564333e9c5a14398892222cb344936.gif)
via:画像ソース元 [Understanding Transducers in JavaScript@Roman Liutikov -Medium](https://medium.com/@roman01la/understanding-transducers-in-javascript-3500d3bd9624#6a68)



**自分で書いたコード**

```js
"use strict";

const map = fn => arr => arr.map(fn),
filter = fn => arr => arr.filter(fn),
addReducer = arr => arr.reduce((acc, num) => acc + num, 0),
add1 = n => n + 1,
even = n => n % 2 === 0,

compose = (...fns) => initVal => fns.reduce((acc, fn) => fn(acc), initVal),
transduce = (xform, reducer, arr ) => reducer( xform(arr) );



const arr = [1,2,3],
transducer = compose( // transducer もしくは xform と呼ぶ
   map( add1 ), // 2,3,4
   filter( even ), // 2,4
);

console.log( transducer(arr) ) // 2,4
console.log( transduce(transducer, addReducer, arr) ) // 6
```

Accepted Answer

(2019/06/11 追記: 全体修正しました)

こんにちは。

本回答は「Transducers という概念がどのようなものか」という質問に対するものとします。

まず簡単に説明すると、質問内参照の記事が言っている Transducers の概念とは、

「reduce が使う関数 `(acc, a) => acc` を composable にする」

というものです。
上から2番目のリンクの記事のコードが最も理解しやすいと思うので、書かれているコードを順番に一つずつ追いかけてみると理解につながると思います。

以下、Transducders の概念の解説です。

---

関数型言語における中心的な概念を表した一つに、map/reduce というものがあるのは質問者さんも知っていると思います。
この map というのは射影変換、特定のデータ構造 (例えば集合、Array) に対して、要素を変換する関数を Array から Array への変換関数に格上げするものです。既に使っている Array.map はまさに配列の要素に対して一括変換するものですね。
そして reduce というのは、Array などのデータ構造を「処理」する関数によって「集計」「押し潰し」を行う関数と言えます。
Transducers はこの reduce に着目した概念です。

まずは前提として、reduce に渡す関数 `(acc, a) => acc` に `reducer` という別名を付けておきます。つまり、Array.reduce は reducer を使ってデータ構造を集計する関数、という意味になります。

ここで、任意の reducer を渡すとそれを用いて新たな reducer を生成する関数 `reducer => reducer` を想定します。これに `transducer` という名前を付けます。

このとき、`compose` の型は、

```
compose : transducer => transducer => transducer
compose : (reducer => reducer) => (reducer => reducer) => (reducer => reducer)
```

となります。
複数の transducer を合成して一つの transducer にする関数であることを意味します。
となると、Transducers における `map` や `filter` が返すべきものは `transducer`、つまり `reducer => reducer` である必要があります。

```
map : (a => b) => transducer
map : (a => b) => reducer => reducer
map : (a => b) => ((acc, b) => acc) => ((acc, a) => acc)

filter : (a => Bool) => transducer
filter : (a => Bool) => reducer => reducer
filter : (a => Bool) => ((acc, a) => acc) => ((acc, a) => acc)
```

型として表すとこうなります。

これらの transducer を compose で合成し、出来上がった transducer に最終結果を得るための `reducer : (acc, a) => acc` を渡すことで `(acc, a) => acc` が得られます。これを reduce で利用するのが Transducers の仕組みです。

あなたのコードでは、

```
filter : (a => Bool) => Array => Array
map : (a => b) => Array => Array

transducer : Array => Array
```

となっており、これでは根本的に別物となっています。

型シグネチャとして見ると、標準の射影関数と同等となっていることが分かると思います。つまり、Array に対してそれぞれが射影を行っているため、実行される度に全要素が処理された中間データが生成されています。
Transducers の理解 3. の内容自体は正しいですが、コードでは全くそうなっていないのです。
質問のコードを展開すると、動いているのはただの `arr.map(add1).filter(even)` となっています。

transducer を用いて生成される reducer は、ただ1回の reduce を実行する際に、1要素毎に合成した各関数を実行する (質問に引用している画像の通りです) からこそ、中間データを生成しないのです。

---

まとめると、

* Transducers は、reduce に渡す関数 `(acc, a) => acc` を合成可能にする概念
* map や filter、その他 Transducers の関数群は、それぞれ任意の関数や値を引数に取って transducer を返す関数である
* 合成した transducer に任意の reducer を渡すことで reducer が得られ、それを `arr.reduce()` で使用することで動作する

---

以上の説明の元で、質問にある定義について注釈を入れると、

> 1. compose()して返却された関数構成群がtransducerである。

compose に「渡すもの」こそが transducer で、だからこそ合成されたものも transducer なのです。compose はその名の通り「合成」だけを意味しており、transducer を生成するような意味はありません。

> 2. transducerを実行するには、❶transduce()に渡す以外にも、❷transducer()に配列を渡す事でも実行できる。

transducer は配列を取る関数ではないです。reducer を受け取って reducer を返す関数なので、transducer に (acc, a) => acc を渡して、返ってきた (acc, a) => acc を Array.reduce に渡すことで初めて実行されます。
transduce は、ソースと transducer と reducer と initValue をまとめて取るだけの単なる糖衣関数です。

> 3. ❷の内部処理において、中間値が生成されるような処理ではなく、下画像のような効率的な処理がなされる。

これは正しいです。transducer は全ての処理が合成された1つの reducer を生成するため、reduce 処理の実行時に各要素毎に処理され、中間データは生成されません。

Answer

`add1`, `even` に入ってくる配列の値をコンソールに表示してみてはいかがでしょうか？
ご自身で書かれたコードにコンソール出力を追加

```js
const map = fn => arr => arr.map(fn),
filter = fn => arr => arr.filter(fn),
addReducer = arr => arr.reduce((acc, num) => acc + num, 0),
add1 = n => {
  console.log(n)
  return n + 1
},
even = n => {
  console.log(n)
  return n % 2 === 0
},

compose = (...fns) => initVal => fns.reduce((acc, fn) => fn(acc), initVal),
transduce = (xform, reducer, arr ) => reducer( xform(arr) );

const arr = [1,2,3],
transducer = compose( // transducer もしくは xform と呼ぶ
   map( add1 ), // 2,3,4
   filter( even ) // 2,4
);

transducer(arr)
```

すると、コンソールには

```console
1
2
3
2
3
4
```

と表示されます（[Medium の記事](https://medium.com/@roman01la/understanding-transducers-in-javascript-3500d3bd9624)にあるもう一つの画像の方に対応します）。

望ましい出力（質問に貼られている画像での流れ）は、

```js
const concat = (a, c) => a.concat([c])
const map = f => (a, c) => (acc, cur) => a(acc, f(cur))
const filter = f => (a, c) => (acc, cur) => f(cur) ? a(acc, cur) : acc
const compose = (...fns) => x => fns.reduceRight((y, f) => f(y), x)
const transduce = (xform, reducing, initial, input) => input.reduce(xform(reducing), initial)

const isEven = n => {
    console.log(n)
    return n % 2 === 0
}
const add1 = n => {
    console.log(n)
    return n + 1
}

const xform = compose(map(add1), filter(isEven))

transduce(xform, concat, [], [1, 2, 3])
```

で得られる

```console
1
2
2
3
3
4
```

ではないでしょうか。

調べた事

Js

Clojure

質問

Transducerとは

関連した質問