回答編集履歴
2
微修正
answer
CHANGED
|
@@ -62,9 +62,10 @@
|
|
|
62
62
|
|
|
63
63
|
型シグネチャとして見ると、標準の射影関数と同等となっていることが分かると思います。つまり、Array に対してそれぞれが射影を行っているため、実行される度に全要素が処理された中間データが生成されています。
|
|
64
64
|
Transducers の理解 3. の内容自体は正しいですが、コードでは全くそうなっていないのです。
|
|
65
|
-
質問のコードを展開すると、動いているのはただの `arr.map(add1).filter(even)` となってい
|
|
65
|
+
質問のコードを展開すると、動いているのはただの `arr.map(add1).filter(even)` となっています。
|
|
66
|
-
transducer を用いて生成された reducer は、ただ1回の reduce 際に、1要素毎に合成した各関数を実行する (質問に引用している画像の通りです) からこそ、中間データを生成しないのです。
|
|
67
66
|
|
|
67
|
+
transducer を用いて生成される reducer は、ただ1回の reduce を実行する際に、1要素毎に合成した各関数を実行する (質問に引用している画像の通りです) からこそ、中間データを生成しないのです。
|
|
68
|
+
|
|
68
69
|
---
|
|
69
70
|
|
|
70
71
|
まとめると、
|
1
内容の更新
answer
CHANGED
|
@@ -1,20 +1,29 @@
|
|
|
1
|
+
(2019/06/11 追記: 全体修正しました)
|
|
2
|
+
|
|
1
3
|
こんにちは。
|
|
2
4
|
|
|
3
|
-
回答
|
|
5
|
+
本回答は「Transducers という概念がどのようなものか」という質問に対するものとします。
|
|
4
6
|
|
|
5
|
-
Transducers については今さっき質問に記載のリンク先を読んで理解した程度ですが、
|
|
6
|
-
|
|
7
|
+
まず簡単に説明すると、質問内参照の記事が言っている Transducers の概念とは、
|
|
7
8
|
|
|
8
9
|
「reduce が使う関数 `(acc, a) => acc` を composable にする」
|
|
9
10
|
|
|
10
11
|
というものです。
|
|
11
|
-
|
|
12
|
+
上から2番目のリンクの記事のコードが最も理解しやすいと思うので、書かれているコードを順番に一つずつ追いかけてみると理解につながると思います。
|
|
12
13
|
|
|
14
|
+
以下、Transducders の概念の解説です。
|
|
15
|
+
|
|
13
16
|
---
|
|
14
17
|
|
|
18
|
+
関数型言語における中心的な概念を表した一つに、map/reduce というものがあるのは質問者さんも知っていると思います。
|
|
19
|
+
この map というのは射影変換、特定のデータ構造 (例えば集合、Array) に対して、要素を変換する関数を Array から Array への変換関数に格上げするものです。既に使っている Array.map はまさに配列の要素に対して一括変換するものですね。
|
|
20
|
+
そして reduce というのは、Array などのデータ構造を「処理」する関数によって「集計」「押し潰し」を行う関数と言えます。
|
|
15
|
-
|
|
21
|
+
Transducers はこの reduce に着目した概念です。
|
|
22
|
+
|
|
16
|
-
まずは前提として、reduce に渡す関数 `(acc, a) => acc` に `reducer` という別名を付けておきます。
|
|
23
|
+
まずは前提として、reduce に渡す関数 `(acc, a) => acc` に `reducer` という別名を付けておきます。つまり、Array.reduce は reducer を使ってデータ構造を集計する関数、という意味になります。
|
|
24
|
+
|
|
17
25
|
ここで、任意の reducer を渡すとそれを用いて新たな reducer を生成する関数 `reducer => reducer` を想定します。これに `transducer` という名前を付けます。
|
|
26
|
+
|
|
18
27
|
このとき、`compose` の型は、
|
|
19
28
|
|
|
20
29
|
```
|
|
@@ -24,18 +33,21 @@
|
|
|
24
33
|
|
|
25
34
|
となります。
|
|
26
35
|
複数の transducer を合成して一つの transducer にする関数であることを意味します。
|
|
27
|
-
となると、`map` や `filter` が返すべきものは `transducer`、つまり `reducer => reducer` である必要があります。
|
|
36
|
+
となると、Transducers における `map` や `filter` が返すべきものは `transducer`、つまり `reducer => reducer` である必要があります。
|
|
28
37
|
|
|
29
38
|
```
|
|
30
39
|
map : (a => b) => transducer
|
|
31
40
|
map : (a => b) => reducer => reducer
|
|
41
|
+
map : (a => b) => ((acc, b) => acc) => ((acc, a) => acc)
|
|
42
|
+
|
|
32
43
|
filter : (a => Bool) => transducer
|
|
33
44
|
filter : (a => Bool) => reducer => reducer
|
|
45
|
+
filter : (a => Bool) => ((acc, a) => acc) => ((acc, a) => acc)
|
|
34
46
|
```
|
|
35
47
|
|
|
36
|
-
|
|
48
|
+
型として表すとこうなります。
|
|
37
49
|
|
|
38
|
-
|
|
50
|
+
これらの transducer を compose で合成し、出来上がった transducer に最終結果を得るための `reducer : (acc, a) => acc` を渡すことで `(acc, a) => acc` が得られます。これを reduce で利用するのが Transducers の仕組みです。
|
|
39
51
|
|
|
40
52
|
あなたのコードでは、
|
|
41
53
|
|
|
@@ -46,13 +58,12 @@
|
|
|
46
58
|
transducer : Array => Array
|
|
47
59
|
```
|
|
48
60
|
|
|
49
|
-
となっており、根本的に
|
|
61
|
+
となっており、これでは根本的に別物となっています。
|
|
50
62
|
|
|
51
|
-
transducer を用いて生成された reducer は、reduce の1ステップ毎に合成した各関数を実行する (質問に引用している画像の通りです) のに対し、
|
|
52
|
-
|
|
63
|
+
型シグネチャとして見ると、標準の射影関数と同等となっていることが分かると思います。つまり、Array に対してそれぞれが射影を行っているため、実行される度に全要素が処理された中間データが生成されています。
|
|
53
|
-
|
|
64
|
+
Transducers の理解 3. の内容自体は正しいですが、コードでは全くそうなっていないのです。
|
|
54
|
-
|
|
65
|
+
質問のコードを展開すると、動いているのはただの `arr.map(add1).filter(even)` となっているのです。
|
|
55
|
-
|
|
66
|
+
transducer を用いて生成された reducer は、ただ1回の reduce 際に、1要素毎に合成した各関数を実行する (質問に引用している画像の通りです) からこそ、中間データを生成しないのです。
|
|
56
67
|
|
|
57
68
|
---
|
|
58
69
|
|
|
@@ -60,4 +71,21 @@
|
|
|
60
71
|
|
|
61
72
|
* Transducers は、reduce に渡す関数 `(acc, a) => acc` を合成可能にする概念
|
|
62
73
|
* map や filter、その他 Transducers の関数群は、それぞれ任意の関数や値を引数に取って transducer を返す関数である
|
|
63
|
-
* 合成した transducer に任意の reducer を渡すことで reducer が得られ、それを `arr.reduce()` で使用することで動作する
|
|
74
|
+
* 合成した transducer に任意の reducer を渡すことで reducer が得られ、それを `arr.reduce()` で使用することで動作する
|
|
75
|
+
|
|
76
|
+
---
|
|
77
|
+
|
|
78
|
+
以上の説明の元で、質問にある定義について注釈を入れると、
|
|
79
|
+
|
|
80
|
+
> 1. compose()して返却された関数構成群がtransducerである。
|
|
81
|
+
|
|
82
|
+
compose に「渡すもの」こそが transducer で、だからこそ合成されたものも transducer なのです。compose はその名の通り「合成」だけを意味しており、transducer を生成するような意味はありません。
|
|
83
|
+
|
|
84
|
+
> 2. transducerを実行するには、❶transduce()に渡す以外にも、❷transducer()に配列を渡す事でも実行できる。
|
|
85
|
+
|
|
86
|
+
transducer は配列を取る関数ではないです。reducer を受け取って reducer を返す関数なので、transducer に (acc, a) => acc を渡して、返ってきた (acc, a) => acc を Array.reduce に渡すことで初めて実行されます。
|
|
87
|
+
transduce は、ソースと transducer と reducer と initValue をまとめて取るだけの単なる糖衣関数です。
|
|
88
|
+
|
|
89
|
+
> 3. ❷の内部処理において、中間値が生成されるような処理ではなく、下画像のような効率的な処理がなされる。
|
|
90
|
+
|
|
91
|
+
これは正しいです。transducer は全ての処理が合成された1つの reducer を生成するため、reduce 処理の実行時に各要素毎に処理され、中間データは生成されません。
|