Clojure の Transducer を勉強する

はじめに

Clojure を触り始めて半年ほどが経ちました。

とはいっても、私の所属はインフラチームなので、他のソフトウェアエンジニアの方々と比べると Clojure に触れる機会は少し少なめです。会社で使用しているメイン言語は Clojure ですが、インフラエンジニアは多種多様な知識やツールを使うので、相対的に Clojure でバリバリコーディングするタスクは少なくなるのです。

そんなこんなで、放っておくとせっかく覚えた Clojure のことをいつの間にか忘れてしまいそうなので、時々自分から学びに行かなくてはと思っていたところ、会社の Clojure つよつよエンジニアの方から Transducer について教えていただく機会がありました。

せっかくなので、そこでお聞きした話をベースに、自分でも改めて Transducer について調べてまとめてみることにしました。あくまで Transducer 初心者の私が頭を整理するために書いているものなので、すでに知っている方にとってはかなりまどろこしい記事になっていると思います。

Transducer 入門

実はまだ、私自身、自分で書くコードの中で積極的に Transducer を使ってその恩恵を実感したことはあまりありません......。普通に動くアプリを作る上では、あまり知らなくてもやっていけてしまうものではあるのですが、巨大なシーケンスの処理を高速に実行したい、といった場面でその威力を発揮してくれるらしいです。

Transducer が Clojure に追加された当時の公式ブログはこちら
2014/08 の記事です。
Transducers are Coming

Transducer の作り方

Transducer の中身に踏み込む前に、まずはユーザー視点での使い方を見てみます。

Transducer を私の言葉で平易に説明すると「シーケンス関数から変換命令だけを抜き出したもの」といったイメージです(自信はない)。

公式リファレンスの記事 の冒頭の一文によると、

Transducers are composable algorithmic transformations.
(トランスデューサーは合成可能な、演算的変換である)

らしいです(むずかしい......)

具体例を見た方が早いのでコードを見てみます。

(filter odd? (range 10)) ;; => (1 3 5 7 9)

(filter odd?) ;; => Transducer になる

こんな感じで、map や filter といったシーケンス関数を、シーケンスを渡さずに引数1つだけで呼び出すと Transducer が返ってきます。実際にシーケンスを変換するのではなく、「こんな変換をしてね」という命令だけを取り出した、というイメージです。

さて、この「変換」は合成することができます。
複数の変換を合成する時には comp を使用することが推奨されています。

(def xform
  (comp (filter odd?)
        (map inc)))

Clojure では、xform と書いて「トランスフォーム」と読むことが多いらしいです。
xf と略すこともあります。

この Transducer xform は「奇数の要素を取り出してから各要素をインクリメントするという変換命令」です。

処理の順番に注意です。

comp に渡した関数は右から左に実行されますが

((comp (partial + 5) (partial * 2)) 10) ; => 25
((comp (partial * 2) (partial + 5)) 10) ; => 30

comp を使って合成された Transducer は左から右にシーケンスへ適用されます。
以下の二つがシーケンスに対して行う変換処理は同じです。

(comp (filter odd?)
      (map inc))

(->> (range 5)
     (filter odd?)
     (map inc))

Transducer の使い方

このようにして変換処理だけを抜き出した Tansducer を実際に使う方法を見てみます。
公式リファレンスの記事では以下のようなパターンが紹介されています。

sequence

Transduecer として定義した変換をあるシーケンスに適用した新しいシーケンスが欲しい場合。

(def xform
  (comp (filter odd?)
        (map inc)))

(sequence xform (range 10)) ;; => (2 4 6 8 10)

(= (sequence xform (range 10))
   (->> (range 10)
        (filter odd?)
        (map inc))) ;; => true

変換処理が、map のように複数のシーケンスを取れるものの場合は、複数のシーケンスを渡すことができます。

(sequence (map vector) [1 2 3] [:a :b :c]) ;; => ([1 :a] [2 :b] [3 :c])

into

into 関数も引数として Transducer を取ることができます。

into のドキュメントをみると、into の呼び出し方は以下の4通りがあります。

• (into)
• (into to)
• (into to from)
• (into to xform from)

このうち4番目にある xform が Transducer のことです。
シーケンス from を xform によって変換した結果を、シーケンス to に結合するという処理になります。

(def xform
  (comp (filter odd?)
        (map inc)))

(into [] xform (range 10)) ;; => [2 4 6 8 10]
(into [100 200 300] xform (range 10)) ;; => [100 200 300 2 4 6 8 10]

transduce

transduce というズバリそのものな名前の関数があります。
この関数の役割は以下のように整理するとわかりやすいです。

1. シーケンスを Transducer によって変換する
2. 変換後のシーケンスを使って reduce 処理を行う

たとえば以下の2つの式の結果は同じになります。

(def xform
  (comp (filter odd?)
        (map inc)))
; A
(transduce xform + 0 (range 10)) ; => 30

; B 
(->> (range 10)
     (filter odd?)
     (map inc)
     (reduce + 0)) ;; => 30

では、この二つで何が変わるのかというと、実行速度です。
B の式では、シーケンス (range 10) に　(filter odd?) を適用した中間シーケンスを生成し、その中間シーケンスに次は map inc を適用し、といった具合に順番に処理が進みます。
一方、A の式は (filter odd?) と (map inc) という変換命令が一つの Transducer に合成されているので、中間シーケンスを生成することなく一気に計算結果を得ることができます。中間シーケンスの生成コストが省ける分、A の式の方が高速に処理できます。

実際に試してみます。

(time (transduce xform + 0 (range 1000000))) ;; => "Elapsed time: 34.775834 msecs"

(time (->> (range 1000000)
           (filter odd?)
           (map inc)
           (reduce + 0))) ;; => "Elapsed time: 44.9005 msecs"

確かに Transducer の方が速くなってますね!
性能が重要な局面では積極的にこちらを使っていくと良さそうです。

eduction

公式リファレンスの記事　では Transducer を使うユースケースとして eduction という関数も紹介されています。ただ、解説などを読んでもこれがなんなのか分かりづらく、このタイミングで深入りすると逆に混乱しそうなのでこれは一旦スキップします。

eduction 関数をどのような場合に使うと良いのかについては以下の議論が参考になりそうです。
Transducers: sequence versus eduction

Transducer の中を見る

Transducer とは

Transducer とは実際のところなんなのか。
公式リファレンスの記事 では以下のように用語が説明されています。

reduce 関数に渡す関数のことを reducing function と呼ぶ。
具体的には、計算結果と入力という2つの値を受け取り、それらを使って計算した新しい計算結果を返す関数のこと

(fn rf [result input] new-input)

Transducer とは reducing function を別の reducing function に変換するもの

reducing function とは

reduce は関数 f と初期値 i、シーケンス X(x_0, x_1, ..., x_n) を受け取って次のような計算をします。この関数 f が reducing function です。

(f i x_0)   ;; => r_1
(f r_1 x_1) ;; => r_2
(f r_2 x_2) ;; => r_3
...
(f r_n x_n) ;; => output

reduce を使って 0 から 10 までの整数を足し合わせる例は次のようになります。

(reduce + 0 (range 10)) ;; => 45

ここで利用されている reducing function をより具体的に書き下すとこんな感じになります。

(defn rf [result input]
  (+ result input))

(reduce rf 0 (range 10)) ;; => 45

Transducer の実装

reducing function を別の reducing function に変換するのが Transducer なので、その見た目は次のような感じになるはずです。

(defn incomplete-xform [rf]
  (fn [result input] 
    (rf result input)))

これは rf を　rf に変換する (つまり何もしない)関数です。試しにこれを Transducer として使ってみるとエラーが出ます。

(sequence xform (range 10)) ;; => Wrong number of args (1) passed to: xxx.core2/incomplete-xform/fn--yyyy

実は、Transducer として利用するためには、incomplete-xform で定義した一般的な変換処理のほかに「初期化処理」と「終端処理」のための arity が必要です。(arity というのは関数定義の中での引数の数のこと)

まずは「初期化処理」について、transduce 関数のドキュメント には次のように書かれています。

(transduce xform f coll) (transduce xform f init coll)
reduce with a transformation of f (xf).
If init is not supplied, (f) will be called to produce it.

reduce 処理を行うためには初期値が必要です。これは引数として明示的に与えることもできますが、初期値が引数として与えられなかった場合には (rf) を実行した結果を初期値として使います。

初期化処理を追加した Transducer(仮)の見た目は次のようになります。

(defn init-and-xform [rf]
  (fn
    ([] (rf))
    ([result input]
     (rf result input))))

Transducer が引数なしで呼ばれた場合 (reduce 処理の一番最初に初期値が与えられなかった場合)、reducing function を引数なしで実行した結果を初期値として利用する、というのがここで定義されている内容です。

次に「終端処理」についてですが、これは reduce 処理でシーケンスの末尾まで辿り着いて最終的な結果を出力する arity です。直前のイテレーションの result のみが渡されて次の input がなかった場合に何を返すかを定義します。

これらを加えると、一番単純な「何もしない」 Transducer の実装は次のようになります。Transducer の実装はこのように3つの arity で1セットになります。

(defn xform [rf]
  (fn
    ([] (rf))
    ([result] (rf result))
    ([result input]
     (rf result input))))

cf. Creating Transducers

実際に使われている Transducer をみてみる

実際に Clojure のソースコードをみてみると、上記の Transducer と同じような形の Transducer の姿を見ることができます。filter と map のソースのうち Transducer に該当する箇所を抜き出すとこんな感じです。

(defn filter
  ([pred]
   (fn [rf]
     (fn
       ([] (rf))
       ([result] (rf result))
       ([result input]
        (if (pred input)
          (rf result input)
          result))))))

(defn map
  ([f]
   (fn [rf]
     (fn
       ([] (rf))
       ([result] (rf result))
       ([result input]
        (rf result (f input)))
       ([result input & inputs]
        (rf result (apply f input inputs)))))))

まとめ

Transducer とは何者で、どのように使うのか、これを使うことでどんな利点があるのかについて簡単に調べてまとめてみました。

Clojure を書き始めたばかりの頃は、シーケンスの変換処理は threading macro でスマートにかければ合格なのだと思っていました。ただ、実際には変換処理の過程で生成される中間生成物としての lazy seq もコストであり、Transducer を使うことで処理をより高速にできるということでした。

正直、まだ私の中でも理解として整理しきれていない部分が多々あるように感じます。
そもそもなぜ reducing function や Transducer という概念に特別に名前がつけられて開発されるに至ったのかという思考の過程が追えていません。また、lazy seq も万能ではなく、場面によっては高コストな場合もあるようで、lazy seq が中で何をしているのかもよく知らないままだなと思ったりしました。eduction の話もこの辺りと絡めてまた後で振り返ってみると学びがありそうです。