Hatena::ブログ(Diary)

すにぺっと

2011-04-15

clojureプログラミング入門-24 カリー化とか

| 21:45 | clojureプログラミング入門-24 カリー化とかを含むブックマーク

もっと怠け者のススメ

遅延シーケンスは言語レベルで遅延評価を表現するが、

PGが明示的なシーケンス処理をかかずにすむことでもっと楽になる。

書籍では例としてコイントスの処理を実装。

表を:h裏を:tで表現したデータを使用する。

[:h :t :t :h :h :h]

ここで2回続けて表が出たケースは何回あるかを調べる。

今回の問題は1つの要素でなく、隣り合う2つの要素を見る。

上記ベクタは、このようにして考えてみる。

:h :t] [:t :t ] [:t :h] [:h :h] [:h :h] ]

そして遅延シーケンスを使用して作る。

user=> (defn by-pairs [coll] 
  (let [take-pair (fn [c]
					  (when (next c) (take 2 c)))]
	(lazy-seq
	 (when-let [pair (seq (take-pair coll))]
			   (cons pair (by-pairs (rest coll)))))))
#'user/by-pairs
user=> (by-pairs [:h :t :t :h :h :h])
((:h :t) (:t :t) (:t :h) (:h :h) (:h :h))

これでコイントスの結果をペアのシーケンスとして扱えるようになった。

次に要素が両方とも表であるペアの数を数える。

user=> (defn count-heads-pairs [coll]
  (count (filter (fn [pair] (every? #(= :h %) pair))
				 (by-pairs coll))))
#'user/count-heads-pairs
user=> (count-heads-pairs [:h :t :t :h :h :h])
2

これはうまくいくが、

partition関数を使えばもっと簡単に書くことができる。

(partition size step? coll)


partitionはコレクションをsize個ずつの塊に切り出す。

user=> (partition 2 1 [:h :t :t :h :h :h])
((:h :t) (:t :t) (:t :h) (:h :h) (:h :h))

次はcountとfilterの組み合わせをリファクタリングする。

user=> (defvar count-if (comp count filter) "Count items matching a filter.")
#'user/count-if
user=> (count-if odd? [1 2 3 4 5]) ;1
3

defvarはdef の便利なラッパーで、

varにドキュメントを付属させることができる。

他に


・defonce

(defonce symbol initioal-value?)

varに初期値が設定されていなければ設定


・defhinted

(defhinted symbol initioal-value?)

varをつくり、初期値に応じた型情報をvarにつける


・defn-

(defn- name & args-as-for-defn)

defnと同じように動作するが、それが定義された

名前空間だけで参照できる束縛を作る。


などがある。

ほかにもいろいろあるらしい。あとでドキュメントみよう。


defvar以外に、comp関数を使っている。

これは 2つ以上の関数を合成する。

compは渡された関数のうち一番右の関数引数適用し、

その結果に次の関数適用し・・・という動作をする新たな関数

作って返す。

なので、count-ifはfilterを行い、結果をcountに渡す、という動作を行う。

→1


では完成版の関数を。

user=> (defn count-runs 
  "Count runs of length n where pred is true in coll."
  [n pred coll]
  (count-if #(every? pred %) (partition n 1 coll)))
#'user/count-runs
user=> (count-runs 2 #(= % :h) [:h :t :t :h :h :h]) ;1
2
user=> (count-runs 3 #(= % :h) [:h :t :t :h :h :h]) ;2
1

1.2連続表の数をカウント。

2.3連続表の数も簡単にわかるようになった。


ここで、3連続表の数を数える専用の関数がほしいとする。

partial関数を使って部分適用すれば専用の関数が作れる。

user=> (defvar count-three (partial count-runs 3 #(= % :h))
  "count three that are both heads.")
#'user/count-three
user=> (count-three [:h :t :t :h :h :h])
1

(partial f & partial-args)

partialには関数fと引数リストの一部を与える。

部分適用はカリー化と似ているが、同じではない。


カリー化と部分適用

カリー化とは1つの引数をうけとり、

元の関数を呼び出しにおいてその引数が固定されたような新しい関数

つくること。

カリー化は部分適用のために行われることが度々ある。

本物のカリー化はclojureにはないが、それほど大きな問題ではないとのこと。

その前提は、

・多くのプログラマがカリー化と部分適用を同じ意味で使っていること

・部分適用するにはpartial関数が使えること

なので。


もう一度、clojureにおける部分適用

user=> (defn add[ x y] ( + x y ))
#'user/add
user=> (add 8 9)
17
user=> (def add-10 (partial add 10))
#'user/add-10
user=> (add-10 4)
14

問題を解く関数を0から考えて書くより、

まずシーケンスライブラリの既存関数の組み合わせを

考えるようにするべし。

clojureプログラミング入門-23 関数型プログラミングと再帰その2

| 16:34 | clojureプログラミング入門-23 関数型プログラミングと再帰その2を含むブックマーク

今回は、フィボナッチ数列を求める関数

ちゃんとした再帰関数で書く。


recurをつかった自己再帰

自己再帰は、JVM最適化できるかもしれない手法のひとつ。

clojureでは自分自身を末尾で呼び出している関数をrecurを使った自己再帰として

書き直せる。

user=> (defn recur-fib [n]
  (letfn [(fib
            [current next n]
			(if (zero? n)
				current
			    (recur next (+ current next) (dec n))))]
		 (fib 0 1 n)))
#'user/recur-fib
user=> (recur-fib 9)
34
user=> (recur-fib 100000000)
;とても巨大な数

 recurがfibへの呼び出しの代わりに使われている。

とても時間がかかるが、いちおう結果はとることができる。

だが、できれば値の範囲を気にしなくてすむAPI

提供したい。

呼び出し側がtakeとdropをつかって、取り出せるようにする。

そのために遅延シーケンスを使用する。


遅延シーケンス

遅延シーケンスはlazy-seqマクロで作られる。

(lazy-seq & body)

これは直接または関節にseqが呼ばれたときにbodyを実行。

そして後によばれたときのために値をキャッシュする。

lazy-seqをつかってフィボナッチ数列を求める。

user=> (defn lazy-fib
  ([]
     (concat [0 1] (lazy-fib 0 1 )))
  ([a b]
     (let [n (+ a b)]
	   (lazy-seq ;1
		(cons n (lazy-fib b n))))))
#'user/lazy-fib
user=> (take 10 (lazy-fib))
(0 1 1 2 3 5 8 13 21 34)
user=> (rem (nth (lazy-fib) 100000) 1000)
875

1.ここで本体の実行を遅延評価している。

 これによって再帰遅延評価で置換える。


上記関数は、無限シーケンスに遅延評価を使うというルールに従っている。

しかし、lazy-seqを呼ばない方法もある。

シーケンスライブラリ関数を使った見ると。。

(take 5 (iterate (fn [[a b]] [b ( + a b)]) [ 0 1 ] ))

iterateは最初の2つのフィボナッチ数[0 1]からスタートし、

常に先頭のフィボナッチ数2つを保持しながら次のフィボナッチ数を計算し続ける。

フィボナッチ数を得るには、

各ペアの最初の値をとればよいということで、

map firstをシーケンス全体に対して適用すればOK。

(defn fib[]
 (map first (iterate (fn [[a b]] [b ( + a b)]) [ 0 1 ] )))

fibが返すのは遅延シーケンス。

遅延シーケンスもスタックやヒープを消費しないわけではない。

肝心なのは、シーケンス全体の長さに比例したリソース

消費することはないという点。

どのくらいリソースを使うかは、リソースを使う側が決めること。

必要な箇所だけfibから取り出せばOK.

clojureプログラムを書いているとき、

大きいor要素数がわからないシーケンスを作る

必要があったら、loop/recurより遅延シーケンスを作るべし。


シーケンスの現実化

遅延シーケンスが現実化されるときに、

実際にメモリ上にインスタンス化される部分がリソースを消費する。

clojureはそのあたりを非常にがんばっているらしい。

takeは遅延シーケンスを返すので、自身は現実化を行わない。

user=> (def lots-fib (take 1000000000 (fib)))
#'user/lots-fib

関数を呼び出したときにはじめて関数内部が実行されるので

定義結果はすぐにかえってくる。

また、呼び出した際も必要な値しか計算しない。

user=> (nth lots-fib 100)
354224848179261915075

これは100番目にフィボナッチ数を取り出しているが、

残りの値は計算されない。


ほとんどのシーケンス関数は遅延シーケンスを返すという。

ドキュメントをみれば遅延シーケンスを返すかどうかわかる。

ただ、REPL遅延評価をしないので注意。

遅延シーケンスをREPLでいろいろ試すには、

(set! *print-length* 10)

としておく。

こうすればREPLの出力する要素数に制限をかけられる。

もう一点注意。

遅延シーケンスを使うに当たり、シーケンスのユーザーやAPI

シーケンス中のもう使わない要素への参照を持たないようにすること。

典型的なケースとして、シーケンスの先頭の参照をもってしまうことが

多いという。

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

これはトップレベルのvarである

head-fibがコレクションの頭を抱えているため、

大きい数をとろうとするとoutofmemoryエラーとなる。


遅延シーケンスを作るときは、それを直接varに束縛せず、

作られたシーケンスを返す関数としてユーザーに見せるべき。



・・・難しい。

なんか数学的な考え方がいつも以上に必要な気がする。

中学高校の数学の復習でもやるか。。。



プログラミングClojure
プログラミングClojure
posted with amazlet at 11.04.14
Stuart Halloway
オーム社
売り上げランキング: 90335

Connection: close