Project Euler Problem 2 #mitori_clj

problem_2.clj

(defn fib
  "Returns the nth Fibonacci number."
  ^long
  [n]
  (-> (* 0.5 (inc (Math/sqrt 5)))       ; golden ratio
      (Math/pow n)
      (/ (Math/sqrt 5))
      (+ 0.5)
      Math/floor
      long))

(loop [n 0 sum 0]
  (let [x (fib n)]
    (if (< x 4000000)
      (recur (+ n 3) (+ sum x))
      sum)))

フィボナッチ数列の一般項 を使って解を求めてみました．私は数式を組み立てるときに -> や ->> をよく使うのですが，みなさんはどのようにしていますか? 数式の組み立てに関しては，演算子に結合強度がある分 Java のほうが書き易いかなと感じています．

一般項かっこいいですね.

無限数列を使って, 元の漸化式に近い表現をする場合はこんな感じでしょうか.

(defn fibs [a b] (cons a (lazy-seq (fibs b (+ a b)))))
(apply + (take-while #(<= % 4000000) (filter even? (fibs 1 2))))

-> や ->> についてはいつも悩みます.
処理内容を考えている最中は, 使わないで

(qux
  (baz
     (bar foo)))

みたいに書いていき, ある程度固まったら,

(->> foo
  (bar)
  (baz)
  (qux))

なんて書いて, 「あーインデントが綺麗になった」と思うですが, やっぱり途中を直したりしてると,
「S式中では前置の方が把握しやすい」と思って戻してみたり.

• 一般項かっこいいですね、なんてさらっと言えない(数学わかってないorz)。
• 自分は最近 -> とか ->> とか多用するようになってきました。慣れるまでは大変でした(どっちをつかったらいいのかわからんかったり...)。慣れてしまえば ))))) みたいなコードが減って、流れが読みやすいように感じます。単に個人の好みのような気がしますね。

コンセプトはlazy-seqバージョンと同じですが、シーケンスでやってみました。

(defn my-fibo [seed]
  (map first (iterate (fn [[a b]] [b (+ a b)]) seed)))

(reduce + (filter even? (take-while #(< % 4000000) (my-fibo [1 2]))))

慣れるまでは、-> とか ->> はあまり使っていませんでしたが、最近、よく使うようになりました。でも、連鎖の場所が固定されてしまっているので使いにくいことがよくありますね。マクロ文字みたいなので、挿入場所を指定できるようなマクロを作ってみるのがいいかも。

-> と ->> は処理の流れを視覚的・感覚的に理解しやすいと感じています。(加工元データが一直線にフィルタを通っていくようなイメージ)
使用する時の判断基準としては、3つ以上の S式 を 1つの ->, ->> 形式に直せる場合は積極的に使用しています。

一般項、プログラムでこんなに簡単に扱えるんですね。
私には、この例の->はすごくシンプルなのに、なぜかそれほど読みやすく思えないです。数式のイメージがあまり頭に持ててないから? でしょうか。
emanon001さんのコメントにもありますが、データ変換のパイプラインの「入り口」に入力のnが来るような先入観があるのかもしれません。

kohyamaさんとypsilon-takaiさんの例で lazy-seq とiterateが何するものなのかやっと飲み込めてきました。

あと、私のも晒してみます。繰り返しの基本の部品はfoldが扱いやすいとの思い込みで書いた解です。泣き言コメントつきです。
https://gist.github.com/d34487ab2ba5a3f375f3

横から解説

数値計算では,

long fib(long n) {
  retuern (long)floor(pow(0.5 * (1 + sqrt(5.0)), n) / sqrt(5.0) + 0.5);
}

と書くところを, 計算のパーツを分離したいけど, 変数は沢山使いたくないので,

long fib(long n) {
  double v;

  v = 0.5 * (1 + sqrt(5.0));
  v = pow(v, n); 
  v /= sqrt(5.0);
  v += 0.5;
  v = floor(v);
  return (long)v;
}

と書きたいような場面が割とあるんですね.

この場面を何度か見たことがあると, tnoda さんの -> を見て,「なるほどこりゃ便利」となる訳です.

@kohyama

lazy-seq のお手本のような使い方だと思いました．今まで lazy-seq を使った遅延シーケンスの作り方を説明するときの例に困っていたのですが，今後，このコードを有り難く使わせてもらいます．正直言うと，この問題で lazy-seq を使って解いてくるパターンは想定していませんでした．

重箱の隅をつつくと，私は，

(defn fibs [a b] (cons a (lazy-seq (fibs b (+ a b)))))

よりも，

(defn fibs' [a b] (lazy-seq (cons a (fibs b (+ a b)))))

と，lazy-seq を cons の前に出す形のほうをよく書きます．というのも，

user> (type (fibs 0 1))
clojure.lang.Cons

user> (type (fibs' 0 1))
clojure.lang.LazySeq

のように，cons を前に出すと遅延シーケンスなのに type が clojure.lang.Cons になってしまうからです．

---

もう一つ，「数値計算あるある」もありがとうございます．数値計算していると本当によくありますよね > 一つの変数を更新していくスタイル．

実をいうと，数式で -> を使うのは，自分では何となく読み易いと思っていたのですが，なぜ，-> が読み易いのか，よく分かっていないところがありました．言われてみれば自分も @kohyama が例示している書き方を何度も見たり書いたりしたことがあり，それで -> に違和感が無いんだと納得できました．とても参考になりました．

@ypsilon-takai iterate を使った別解ありがとうございます．この解答が初学者向けおすすめ解答になると思うのですがいかがでしょうか > みなさま

ところで，シーケンスを使えば immutable な値に対してプログラミングする Clojure でも状態を表現でき，iterate はその状態遷移を表現するのにとても便利です．そういう意味で，初学者に iterate の最初の例として (iterate inc 1) を見せるのは誤解のもとだと考えており，どうせなら，@ypsilon-takai の解答のほうが良いと思います．

https://gist.github.com/4239310 で議論のあった効率化をこの問題でもやってみます．実は (fib n) が偶数になるのは n が 3 の倍数のときだけなので，(fib n) < 4000000 なる全ての n について (fib n) を計算する必要はありません．

というわけで解答を更新してみました．even? も不要になりました．

一般項で解を求めることのメリットとデメリット

• メリット
  • オブジェクトを作らない = GC 走らない
  • 数列の全てを計算しなくてもよい（この問題の場合は 1/3）
• デメリット
  • コードが長くなる
  • 大学の課題で使うと点数をもらえない

大学の課題、フィボナッチ数求めるプログラムで一般項使ったら点数もらえなかった。

— ねこはる (@halcat0x15a) October 29, 2012

<script src="//platform.twitter.com/widgets.js" charset="utf-8"></script>

(fn f [...] (cons ... (lazy-seq (f ... と (fn f [...] (lazy-seq (cons ... (f ... でどちらを使うかは, 自分の中で特に判断基準がなく, 若干多くみかける気がする前者を使ってましたが, 外から見て LazySeq であることが分かるからというのは, なるほど後者を選ぶ理由になりますね.

(fib n) が偶数になるのは n が 3 の倍数のときだけ

！？
Wikipedia/フィボナッチ数 を読んでみたら「性質」のところに載ってた. おどろき.
ちなみに, 5 の倍数になるのは 5 の倍数番目の項だけらしい...

一般項使ったら点数もらえなかった

その先生に「不可」をあげたい.

この解答が初学者向けおすすめ解答になると思うのですがいかがでしょうか > みなさま
初学者をどの辺と定義するかにもよりますが、「フィボナッチ数列を作る」の回答としていきなりこれを提示するのは、厳しいんじゃないでしょうか。 繰り返しで作る->再帰で作る->シーケンスで作るという流れで行き着くのが妥当かと。

lazy-seqの場所について考えてみたんですが、(cons x (lazy-seq ...)) がいいと思います。
この形であれば、「すでにxの値は確定してるけど、続きは必要だったら計算するよ」というのを明確に表現していると思うからです。 結果についても、 全体でなく、 next部がLazySeqになっているはず(未確認)なので、その情報が必要な場合はそのように捉えるべきかと。
逆に、(lazy-seq (cons ...)) のパターンだと、結果のfirst を取るのにコストがかかる可能性を考えなくてはいけないのでは？

@ypsilon-takai の書いた iterate 版は Programming Clojure の中でも紹介されている方法で、シンプルで Clojure らしいコードになっているので、すごく好きです。

Programming Clojure では、末尾再帰なし版、末尾再帰(loop recur)版、lazy-seq 版と紹介され、最後が iterate による遅延シーケンスを返す版だったと思います。