遅延 × 再帰 × フィボナッチ

12 11月 2009

長らく連載がストップしている某マンガ風なタイトルで。

Clojureのドキュメントやチュートリアルでよく見かけるフィボナッチ数列を求める関数定義：

(def fibs (lazy-cat [0 1]
     (map + fibs (rest fibs))))

一見しただけでは えっ？これで動くの？ と感じてしまうのだが紙の上で動かしてみるとなるほど納得できた。

2行目の map関数での処理部分はつまることろ

       fibs: 0  1  1  2  3  5 ...
(rest fibs): 1  1  2  3  5  8 ...
;----------------------------------
   0  1   +: 1  2  3  5  8 13 ...

と、まさにフィボナッチ数の定義そのままをコードにしたもの。
動作も順を追っていくと理解できる。

[0 1]                             ; -> [0 1]
[0 1] + (map + [0 1] [1])         ; -> [0 1 1]
[0 1] + (map + [0 1 1] [1 1])     ; -> [0 1 1 2]
[0 1] + (map + [0 1 1 2] [1 1 2]) ; -> [0 1 1 2 3]

再帰と遅延評価はそれぞれ理解していたつもりだけどこうやって組み合わされると一瞬「ん？これで動くの？」と考えてしまう。
まだ思考がこっち側になれていないみたい。

知識だけではすんなり頭に入っていかないこの感覚はまさに数学のそれに似てるな。おもしろい。

Tags: Clojure

研究所大佐: コメントありがとうございます。エントリ拝見しました。>この� [...]

MATSUOKA Hiroshi: 初めまして。こんな解き方をやってみました。良ければ参考まで。 [...]

Lisp風のインデントは見やすいと思う。 - マンジラボ: [...] たとえば先の記事のコードを例にとると [...] [...]

WordTwitが正常に動かないので修正してみる。 - マンジラボ: [...] 参考エントリ： WordTwitがさっそく対応してくれました。 Tags: WordTwit [...]

Clojureコーディング規約・訳 - マンジラボ: [...] ではGoogle Groupsでまとめられたこちらの規約の方が詳しいです。 &rArr [...]

マンジラボ

遅延 × 再帰 × フィボナッチ

About this blog

Photostream

Categories

Archives