transducerを実装したjsコードを書いてみましたが、合っているか分かりません

Question

調べた事

Js

• Transducers: Efficient Data Processing Pipelines in JavaScript@Eric Elliott -Medium
• Understanding Transducers in JavaScript@Roman Liutikov -Medium

半分位から、特によく分からなくなった記事

• What's a Transducer?
• Simpler Transducers for JavaScript
• How to make your data transformations more efficient using transducers

Clojure

• TRANSDUCERS ARE COMING by Rich Hickey -cognitect
• Transducers -Clojure.org

Clojureは公式ページのチュートリアル2ページほど読み、基礎構文初歩は理解しました(CommonLispの基礎部分を以前少しやっており理解できました)。transducerの例に出てくるライブラリの関数等は、逐次調べ、例題コードの理解率は75%ほどです、多分。。

質問

以下の理解・jsコードが合っている・間違っている のかを知りたいです。ご教授宜しくお願い致します<(_ _)>????

Transducerとは

1. compose()して返却された関数構成群がtransducerである。
2. transducerを実行するには、❶transduce()に渡す以外にも、❷transducer()に配列を渡す事でも実行できる。
3. ❷の内部処理において、中間値が生成されるような処理ではなく、下画像のような効率的な処理がなされる。

via:画像ソース元 Understanding Transducers in JavaScript@Roman Liutikov -Medium

自分で書いたコード

"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

Comments

[1T2R3M4]

https://stackoverflow.com/questions/56507025/is-my-understanding-and-js-code-about-transducer-correct

Multipost???

[退会済みユーザー]

yes. the question in different language and different services is illegal?At that time, I stronglly want to undersnad teansducer, so I post the question about tenasducer in Stackoverflow.en and teratail.

[1T2R3M4]

You should read the following link carefully.
https://teratail.com/help#posted-otherservice

I think teratail does NOT recommend to post the question to multi site regardless language and country.

[1T2R3M4]

Oh, I remembered you are a multi accounter in teratail.
So, this is like a talking to the wall for immoralist like you.
Sorry for bother you.
Please forget about it.

[退会済みユーザー]

Thank. But..., those help page mentioned that it is not RECOMMENDED to multiposting, but not stated that it is prohibited. In addition, the help page is not stated about different language.

In my opitnion, the reason why multiposting is bad practice is that it makes web viewer confused and ruin web resources. So, I think multiposting in different language is not a problem.

yeah, I understand that this is my personal opinion. So I will send inquiry to the dev team of teratail and take action following these response.

Grateful to comment to know me for those information. I haven't read those page.
Sincerely.

[退会済みユーザー]

Please give me a chance short time! That action is testing purpose to answering the quiestion and not abusing pupose. So, I suddenly delete that account. If you doubt me, please search that account(azumax) in serach form in teratail's navigation bar.

https://teratail.com/questions/194413#reply-289205

Answer 1

(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 を生成するような意味はありません。

1. transducerを実行するには、❶transduce()に渡す以外にも、❷transducer()に配列を渡す事でも実行できる。

transducer は配列を取る関数ではないです。reducer を受け取って reducer を返す関数なので、transducer に (acc, a) => acc を渡して、返ってきた (acc, a) => acc を Array.reduce に渡すことで初めて実行されます。
transduce は、ソースと transducer と reducer と initValue をまとめて取るだけの単なる糖衣関数です。

1. ❷の内部処理において、中間値が生成されるような処理ではなく、下画像のような効率的な処理がなされる。

これは正しいです。transducer は全ての処理が合成された1つの reducer を生成するため、reduce 処理の実行時に各要素毎に処理され、中間データは生成されません。

Comments

[退会済みユーザー]

至らない質問に、お時間を割いていただきありがとうございます。

でも、言い方がひどいです…???? 今後質問はもう控えようかと今は感じております…????

> 課題でもなんでもない
課題でなくてはダメでしょうか???? 純粋に関数型プログミングが好きで、理解したいのです。ただ、私のコード・理解が、理解と呼べる代物ではありませんでした。。今なら少し分かります。質問する前に
- 再度記事を読み直す
- 関数型言語を基礎から学習する

べきでした…すみません、よく読み直します????

もう少し優しく教えて頂けると嬉しかったです???? 貴重なお時間を割いて頂けた事、教えて頂けた事には非常に感謝しております。ありがとうございました。

[tamoto]

すみません、不用意に強い言葉を使ってしまったことを謝罪します。
質問についてですが、本質問は「合っていますでしょうか」という、はい/いいえ。と書いてしまえば回答として成立してしまう、「課題」が含まれていないと認識されうるタイプに該当します。
いわゆる「このコードを添削してください」系の質問と同系統かと思います。そのため、しばらく回答が付かなかったりします。
「何を不安に思っているのか」「どの視点からの回答を得たいのか」という「課題の焦点」を意識して質問するのが良かったかと思います。
これは後出しですが、関数型言語に対する学習を深めたい、という道程であったそうで、その背景が分かっていればこのような強い否定は使わなかっただろうと思います。そこが見えない状態では、どのような態度で質問をしているのかを誤解してしまいました。
回答の方、後ほど修正致します。
-> 修正しました。よろしければご確認ください。

[oikashinoa]

人間ですもん、間違えることもや機嫌悪いことも有りますよね？
凄くいい質問の仕方してると思いますよ。
言葉尻なんで流して知りたいことを吸収しましょうよ。

[退会済みユーザー]

Re: > oikashinoaさん
取り持って頂いてありがとうございます。確かにそうですね。僕も引っかかり過ぎた気がします。今後はoikashinoaさんの気概を胸に邁進して参ります!

> tamotoさん
色々合点がいきました。私自身、焦点が不明確であり、良くない誤解を招く質問の仕方であったこと、反省します。また、その他も反省する点があります。すみませんでした> <;

直して頂いた上に、更に分かりやすい説明を沢山加えて頂き、本当にありがとうございます。多くのお時間を注いで頂き、感謝で一杯です。

transducerに関して漠然としていた部分が明確に分かりました!

- 何をtransducerと呼ぶのか
- なぜtransducerだと中間値が作成されないのか
- transducer(reducer) => reducerが返され arr.reduce()に渡して実行できる事

上記リンク2番目の記事をメインに、他の記事も再読し、更にtransducerや関数型プログラミングの理解を深めたいと思います。
今後も関数型プログラミングに邁進して参ります。ありがとうございました!

Answer 2

add1, even に入ってくる配列の値をコンソールに表示してみてはいかがでしょうか？
ご自身で書かれたコードにコンソール出力を追加

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)

すると、コンソールには

1
2
3
2
3
4

と表示されます（Medium の記事にあるもう一つの画像の方に対応します）。

望ましい出力（質問に貼られている画像での流れ）は、

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])

で得られる

1
2
2
3
3
4

ではないでしょうか。

Comments

[退会済みユーザー]

回答ありがとうございます。なるほど! 実際にためしてみましたが、こうしてみると処理が歴然ですね。
compose()のreducerRight()の部分も、理解しました。
コードも書いて頂き、ありがとうございました。色々試させて頂きます!