[過去ﾛｸﾞ] 関数型プログラミング言語Haskell Part7 (1001ﾚｽ)

関数型プログラミング言語Haskell Part7 http://echo.5ch.net/test/read.cgi/tech/1174211797/

上下前次1-新
通常表示 512ﾊﾞｲﾄ分割 ﾚｽ栞
抽出解除 ﾚｽ栞

---

このｽﾚｯﾄﾞは過去ﾛｸﾞ倉庫に格納されています｡
次ｽﾚ検索 歴削→次ｽﾚ 栞削→次ｽﾚ 過去ﾛｸﾞﾒﾆｭｰ

---

895: デフォルトの名無しさん [sage] 2007/09/21(金) 20:23:16 >>885 このコードが理解できない初心者のために、教えてください。 seqは遅延評価をしないための関数のようですが、lengthは何のためにあるのでしょうか。 あとseqは２項演算子として使うのが普通なのですか。 qsort [] = [] qsort (x:xs) = seq (length elts_lt_x) (seq (length elts_greq_x) (qsort elts_lt_x ++ [x] ++ qsort elts_greq_x)) 　where 　　elts_lt_x = [y | y <- xs, y < x] 　　elts_greq_x = [y | y <- xs, y >= x] と買いても間違いではない？ >>886 >数字はtotal allocにqsortの%allocをかけたもの total alloc と %alloc が何か分からないので、それらをかけて何が求まるのか分かりません。 total alloc は全体のメモリ消費量で単位はバイトでしょうか。 http://echo.5ch.net/test/read.cgi/tech/1174211797/895

897: デフォルトの名無しさん [sage] 2007/09/21(金) 21:07:44 >>895 それで合ってる。seqを中置で使うのは良く見かける気がする。 seqを使っているのは再帰に入る前にelts_lt_xとelts_greq_xを完全に評価するため。 未評価のelts_greq_xのサンクはxsを参照しているけど、 完全に評価してしまえばただのリストなので、xsへの参照がなくなって、 GCがxsを回収できるようになる。 seq A Bの値はBと同じだけど、この式を評価する時はまずAを評価して、 その結果を捨て、改めてBを評価する。 length elts_lt_x `seq` 本体 を評価するときは、まずelts_lt_xの長さを求めることになるが、 リストの長さを求めるにはリスト全体を評価する必要がある。 結局、本体が評価される前にelts_lt_xが完全に評価される。 lengthが必要な理由には、seqの仕様が関わってくる。 seq A Bが評価されるとき、Aは弱冠頭正規形(weak head normal form, WHNF)まで簡約される。 WHNFというのは、最も外側のデータ構築子が確定した形。 例えば1+2や[1,2]++[3,4]はWHNFじゃないけど、3や1:([2]++[3,4])はWHNF。 だから、lengthを使わずに elts_lt_x `seq` 本体 のように定義すると、例えば elts_lt_x = [y | y <- [1, 2, 3, 4], y < 5] のとき、これを elts_lt_x = 1 : [y | y <- [2, 3, 4], y < 5] と簡約したら、この段階でWHNFに達したことになり、評価が終わってしまう。 これだと、xs(ここでは[2, 3, 4])への参照が残っていて、GCがxsを回収できない。 http://echo.5ch.net/test/read.cgi/tech/1174211797/897

904: 886 [sage] 2007/09/21(金) 23:41:03 >>895 -prof付きでコンパイルしてから+RTS -p付きで実行するとプロファイルがとれて、 Fri Sep 21 23:19 2007 Time and Allocation Profiling Report (Final) main.exe +RTS -p -RTS total time = 0.05 secs (1 ticks @ 50 ms) total alloc = 9,079,028 bytes (excludes profiling overheads) COST CENTRE MODULE %time %alloc main Main 100.0 0.3 qsort Main 0.0 99.1 というようなログが出力される。 total allocとか%allocはこれのこと。 total allocはアロケートされたメモリの累計で、%allocは各関数ごとの割合。 とまあそういうことなんだけど、ここでの議論は、GCでメモリが再利用されて O(n)になるという話なので、無意味と言うか、的外れと言うか、 >>886-887は無かったことにしてください。 メモリ使用量を正しく知る方法は>>888。 http://echo.5ch.net/test/read.cgi/tech/1174211797/904

---

ﾒﾓ帳

(0/65535文字)

---

上下前次1-新書関写板覧索設栞歴

---

ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ

---

Google検索

Wikipedia

---

ぬこの手 ぬこTOP 0.060s