LoginSignup
21
19

More than 5 years have passed since last update.

LivesenseAdvent Calendar 2015Day 7
@xorphitus

ある日moriの中Transducersに出会ったけどこれは何者か

Posted at

JavaScriptで使うTransducers

前置きなしで乱暴に話を始めます。

JavaScriptでTransducersというとまず、本家(?)っぽいCognitectのtransducers-jsというのもあるのですが
https://github.com/cognitect-labs/transducers-js
今回はJavaScriptのイミュータブル界でじわじわと勢力を伸ばしているという噂のある、mori を使ってみたいと思います。
https://github.com/swannodette/mori

とりあえず試してみた

本家のREADMEにあるコードを、個人的に好みにしたがって修正して実行してみました。

const _ = require('lodash');
const m = require('mori');

const arr = _.range(1000000);
const vec = m.into(m.vector(), arr);

console.time('mori / transducers');
const xf = m.comp(m.map(m.inc), m.map(m.inc), m.map(m.inc));
m.transduce(xf, m.completing(m.sum), 0, vec);
console.timeEnd('mori / transducers');

console.time('native / method chain');
arr.map(m.inc).map(m.inc).map(m.inc).reduce((a, b) => { return a + b; }, 0);
console.timeEnd('native / method chain');

console.time('lodash / flow');
arr.map(_.flow(m.inc, m.inc, m.inc)).reduce((a, b) => { return a + b; }, 0);
console.timeEnd('lodash / flow');

実行した環境は以下です。

  • Arch Linux
  • Intel(R) Core(TM) i7-4770K CPU @ 3.50GHz
  • Node.js v5.1.1

結果は次の通り。

mori / transducers: 85.069ms
native / method chain: 275.670ms
lodash / flow: 167.297ms

Transducers速えー。

関数合成したら適用が一回だけになるわけで、そりゃメソッドチェーンよりは速いよねという話が出そうだったので、lodashでの関数合成とも比較をしています。

ところでmoriって何なの?

まず、公式のロゴがこれです。

mori

forest感にあふれます。

こちらは、Immutable.jsと同じくJavaScriptで不変データ構造を利用できるようにするライブラリです。
この不変データ構造はClojureScriptのものなのですが、Valilla JSからも(たぶん)気軽に使えます。
Immutable.jsとの違いは以下です。

  • 各データ構造はpublicメソッドを持たない (メソッド呼び出しでなく、関数呼び出しになる)
  • 速い
  • ファイルサイズがでかい (gzipした場合Immutable.jsよりも6KB重い)

まとめ

  • moriによってJavaScriptで不変データ構造と共にTransducersが使える
  • Transducersは速らしい

以上、メインテーマ終了です。

:

というわけにもいかないので、Transducersとは一体何なのかを追ってみたいと思います。

Transducersとは

そもそもTransducersとは何なのでしょうか。

元々はClojureに1.7から導入された概念です。
(他の言語では…自分の把握している範囲では確認されていません。ご存知の方がいたらコメントください)

ふわっとイメージを捉える

パっと見は、カリー化・部分適用に似ています。

例えば「全ての要素に1を足す」処理を作って再利用しようと思った時、Transducersを使うと次のようになります。

;; mapを素朴に使うと
(map inc [1 2 3])            ; => (2 3 4)
(reduce + (map inc [4 5 6])) ; => 18

;; で、Transducers
;; sequence, transduce関数については後述
(def xf (map inc))       ; この xf がTransducers
(sequence xf [1 2 3])    ; => (2 3 4)
(transduce xf + [4 5 6]) ; => 18

;; ちなみに部分適用で書くと
(def p (partial map inc))
(p [1 2 3])            ; => (2 3 4)
(reduce + (p [4 5 6])) ; => 18

ちなみに関数sequence、transduceのアバウトな意味はだいたいこんな感じです。

  • sequenceは各要素にxfを適用
  • transduceは各要素にxfを適用してreduce

これだけ見ると「なーんだ、Transducersってただの部分適用した関数じゃね?」という感じですね。
第二引数を省略すると部分適用になる的な。
これはHaskellのように関数がカリー化されている言語からすると何だか冗長に感じます。
Haskellで書いた場合はこんな感じでしょうか??

let f = map (+1)
f [1, 2, 3]
foldl (+) 0 (f [4, 5, 6])

アリティが不足したら部分適用された関数が返ってくるので、ずいぶんと美しく感じます。

まあ、ひとまず先へ進みましょう。

Transducersは通常の関数と同じく合成することもできます。

(def xf (comp (filter odd?)
              (map inc)
              (take 5)))

(transduce xf + (range 1000))
(transduce xf * (range 200))

合成の順序が、通常の関数と異なり右からではなく左からになるので注意です。
これも部分適用で云々と言われそうですね。

しかしRich Hickeyはこう言っています。
https://twitter.com/richhickey/status/497098126709506049
「Transducers are not currying or partial!」と。

Transducersは部分適用ではない

そろそろ関数型ガチ勢からマサカリが飛んできそうな気がしていて、手汗をかき始めていますが虎穴に入らずんば何とやら。

先のRich Hickeyのツイートを引用します。

Clojure's (map f) returns a transducer, (x->b->x)->(x->a->x),
not [a]->[b].
No lists involved.

型が全然違いますね。もし部分適用であるならば、[a] -> [b]になるはずです。
さらに「No lists involved」とわざわざ一言添えているので、リストが型に入っていないことが重要そうな予感がします。

続きの話をするにあたり、 reducing function という概念を導入します。
これは一言で言うと、reduceの第一引数として渡せる、二引数関数のことです。
型はx -> a -> xとなります。

以下、話を簡単にするため(map f)に絞ります。

Transducersとは、型だけ見れば reducing function をx -> a -> xからx -> b -> xに置き換える関数ということになります。
reduceの第一引数の関数において、「次の入力」の型がaだったものを、bで取り扱えるようになります。

何のこっちゃ。

部分適用でないのなら何なのか

Richのブログポスト
http://blog.cognitect.com/blog/2014/8/6/transducers-are-coming
によると、一番の利点は「以下の3つから分離された処理が作れること」だそうです。

  1. reducing function が行う仕事
  2. どんなコンテキストで使われるか (x -> a -> xのxが何であるか)
  3. どんな入力がされるか

どうやら、モジュール(曖昧な言葉で濁します)を様々なしがらみから解き放ち、汎用的に再利用できるようにするようです。

しかしこれだけでは話が抽象的すぎてよく分からないので、もう少し踏み込んでみます。

以下、k2nr様の「Clojure1.7のtransducersとはなにか」をかなり参考にさせていただいています。
http://k2nr.me/blog/2014/08/10/transducers.html
全く同じ例を取り上げますがご容赦ください。

;; Transducer
(def xf (map str))
;; conj は reducing function であり xf で変換している
(def rf (xf conj))

(rf [] 1)    ; => ["1"]
(rf ["1"] 2) ; => ["1" "2"]

;; 比較用: 素の conj
;; 他の言語で言うと append や push_back 等です
(conj [] 1)  ; => [1]
(conj [1] 2) ; => [1 2]

これ、部分適用だと思って眺めると不思議なのでは。

mapは元々シーケンスを受けとる関数なのですが、rfは1や2といったスカラ値を受け取っています。
どうもTransdusersというのは、「対象がシーケンスかどうかに関わらず適用できる、変換の本質部分だけを抜き出したもの」と言えそうです。

なお、ここにおける「変換の本質部分」は、「対象をstrする」です。
これがconjに持ち込まれたと見ることができます。

だとすれば、それは確かに前述した以下を分離していると言えるのではないでしょうか。

  1. reducing function が行う仕事
  2. どんなコンテキストで使われるか (x -> a -> xのxが何であるか)
  3. どんな入力がされるか

前述のRichのツイートを思い出しますと、なるほど「No lists involved」。たしかにList(ここの例はVectorですが)かどうかに依存していないということになります。

型から見るTransdusers

先ほどの例を再掲します。

(def xf (map str))
(def rf (xf conj))
(rf [] 1)    ; => ["1"]

ここでmapのTransdusersの型が(x -> b -> x) -> (x -> a -> x)であったことを思い出しつつ
strの型をa -> Stringとすると、(map str)の型は(x -> String -> x) -> (x -> a -> x)となります。

次にconjの型を[y] -> y -> [y]と考えると、(xf conj)は[String] -> a -> [String]となります。
(yがStringになるので、x = [y] = [String]です)

※ちなみに[x]はHaskellと異なりListではなくVectorの意味で使っています

これはconjという reducing function に対して「Stringに変換する」という処理の本質が持ち込まれ、「何か来たら[y]に放り込む」だったものが「何か来たら[String]となるよう放り込む」になったと見ることができるのではないでしょうか。

そろそろ身近なHaskellerの力に頼りたい領域に差し掛かったので、型の解釈はこれで終えます。撤退。

map以外のTransducers

mapのTransducersの型は(x -> b -> x) -> (x -> a -> x)だったわけですが他も同様です。
例えばfilterはこの特殊系で、a = bであるケースです。

なおmap、filterをTransducersを生成する関数として見た時、これらの型は次のようになります。

  • map f: (a -> b) -> (x -> b -> x) -> (x -> a -> x)
  • filter pred: (a -> bool) -> (x -> a -> x) -> (x -> a -> x)

この次の話

さて大まかなところは見てきましたが、より理解を深めるためには以下の2点に踏み込む必要がありそうです。

  • core.asyncにおけるTransducers
  • moriのTransducersは何故_.flowより高速だったのか

前者については、Transducersの解説記事でちょいちょい見かけるものです。
切り出された「処理の本質」は channel に対しても用いることができるということでしょう。
Transducersの応用例とも言えそうです。

後者は、Transducersの内部で何が起きているかを追いかける必要があると見ています。

これらを冬休みの宿題とし、いったん〆めたいと思います。

もし理解の至っていない点がございましたら、コメントいただけると幸いです。

参考文献

21
19
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
21
19