mapと再帰で木構造を扱う

SICP楽しすぎるな。 第２章の途中、mapを使って木構造のデータ処理を紹介していて、えらく感動した。

題材は以下のとおり、木構造の中の全要素に対して任意のfactorを掛ける関数scale-treeを作ること。

(def ttree (list 1 (list 2 (list 3 4) 5) (list 6 7)))
(scale-tree ttree 10)
;-> (10 (20 (30 40) 50) (60 70))

再帰を使うのは分かりやすい。

(defn scale-tree [tree factor]
  (cond (not (coll? tree)) (* tree factor)
        (empty? tree) nil
        :else (cons (scale-tree (first tree) factor)
                    (scale-tree (rest tree) factor))))

一回分解して組み立て直しているコストはかかるが、木構造と再帰は実に相性がよい。

処理の流れは以下のとおりで、データの先頭と残り取り出して、ツリー階層を下っている。 （カッコがあるとデータが分かりにくいので、関数呼び出しは簡略的に記す。）

1: scale-tree (1 (2 (3 4) 5) (6 7)), 10
2: cons scale-tree 1, 10
        scale-tree ((2 (3 4) 5) (6 7)), 10
3: cons 10
        scale-tree ((2 (3 4) 5) (6 7)), 10
4: cons 10
        cons scale-tree (2 (3 4) 5)), 10
             scale-tree (6 7), 10
5: cons 10
        cons cons 2, 10
                  ((3 4) 5), 10
             scale-tree (6 7), 10
...

これをmapを使うと以下のように書ける。

(defn scale-tree [tree factor]
  (map (fn [sub-tree]
         (if (coll? sub-tree)
           (scale-tree sub-tree factor)
           (* sub-tree factor)))
       tree))

処理の流れは下記のとおり。

1: scale-tree (1 (2 (3 4) 5) (6 7)), 10
2: map処理
      fn 1
      fn (2 (3 4) 5)
      fn (6 7)
3: map処理
      10
      scale-tree (2 (3 4) 5)
      fn (6 7)
4: map処理
      10
      map処理
         fn 2
         fn (3 4)
         fn 5
      fn (6 7)
...

これの何がすごいかって？ 実際には木構造を再構築しているのにconsをまったく使用していないところだ。 （表に見えるところでは）

map関数はシーケンス（データ列）をインプットに、各要素に処理を施したあとのシーケンスを返す。 しかし、これが単純なデータ列だけではなく、木構造にも応用できるとは思ってもみなかった。

それも、概念を整理するとシンプルで、シーケンスの構成要素が、たまたま別のシーケンスだった場合は そこを再帰的にたどっていけばよいだけ、だ。

同じデータ構造に対して、別の視点を持つことで、プログラミングの仕方が変わってくる。 SICPを読んでいると、こういうパラダイムの転換が頻繁に出てくるから実に面白い。