関数型プログラミング言語Haskell Part30

1 名前：デフォルトの名無しさん mailto:sage [2017/01/15(日) 23:43:54.28 ID:Vh4eztBk.net] 関数型プログラミング言語 Haskell について語るスレです。 haskell.org (公式サイト) www.haskell.org/ 前スレ 関数型プログラミング言語Haskell Part28 echo.2ch.net/test/read.cgi/tech/1428597032/ 741 名前：デフォルトの名無しさん mailto:sage [2017/07/24(月) 21:27:21.43 ID:jM5xaigZ.net] 大リーグ養成ギブスはめられてるような気持ち 742 名前：デフォルトの名無しさん mailto:sage [2017/07/24(月) 21:56:08.66 ID:RBhDn3mI.net] >>731 　　　　 /: : : : : __: :/: : ::/: : :／/: : :/l::|: : :i: :l: : :ヽ: : :丶: : 丶ヾ　　　　＿＿＿ 　　 　 /;,, : : : //::/: : 7l,;:≠-::/: : / .l::|: : :l: :|;,,;!: : :!l: : :i: : : :|: : ::､　 ／　　　　 ヽ 　　　 /ヽヽ: ://: :!:,X~::|: /;,,;,/: :／　 ﾘ!: ::/ﾉ　 l｀ヽl !: : |: : : :l: :l: ﾘ /　そ　そ　お　＼ 　　　/: : ヽヾ/: : l/::l |／|||llllヾ,､　　/ |: :/ , -==､　l＼:::|: : : :|i: |　/ 　 う　う　 前　　| .　　 /: : : //ヾ ; :|!: ｲ､||ll|||||::||　　　 ﾉノ　 ｲ|||||||ヾ､ |: ::|!: : ｲ: ::|/　 　な　思　が 　　 /: : ://: : :ヽｿ::ヽl |{ i||ll"ﾝ　　　 ´　　　i| l|||l"l　｀|: /|: : /'!/l 　 　 ん　う 　∠: : : ~: : : : : : : :丶ゝ-―-　　　　　 , 　ｰ=z_ｿ　　 |/ ﾊﾒ;, :: ::|.　　　だ　ん 　　 i|::ﾊ: : : : : : : : : : : ､ﾍﾍﾍﾍ　　　　 ､　　ﾍﾍﾍﾍﾍ /: : : : : ＼,|.　　　ろ　な 　　 |!l　|: : : : : : : : :､: ::＼　　　　､-―-,　　　　　　/ : : :丶;,,;,:ミヽ　　 う　 ら 　　　　　丶: :ﾊ､lヽ: :ヽ: : ::＼__　　｀~　"　　　　　 /: : ﾄ; lヽ）　　　ゝ 　　　　　　 ﾚ　｀|　｀､l｀､＞=ﾆ´　　　　　　　 ,　　_´ : :}　｀　　　／ 　　　　　　　　 ,,､r"^~´"''''"t-｀r､ _　　-､　´ヽノ　＼ﾉ　　　／　　　　お ・ 　　　　　　　,;'~　　_r-- ､__　　　　　~f､_>'､_　　　　　　　　 |　　で　　前 ・ 　　　　　　f~　　,;"　　　　　~"t___　　　　ﾐ､ ^'t　 　 　 　 　|　　は　　ん ・ 　　　　　 ,"　　,~　　　　　　　　　ヾ~'-､__　ﾐ_ξ丶　　　　　|　　な　　中 ・ 　　　　　;'　　,ｲ　.. 　　　　　　　　　ヽ_　　 ヾ､0ヽ丶　　　　l　　　　　　　　　/ 　　　　 （　;":: |:　:: ..　　　　　　　　　 .｀,　　 ヾ　丶 !　　　　＼＿＿＿＿／ 　　　　　;;;; :: 入:: :: :: 　 　　　l｀ｰ-､　　 ）l　　 ヾ　丶 　　　　　"~､ｿ:: :い:: :　　　　　＼_　　ノ　,　　　 ヾ　丶 743 名前：デフォルトの名無しさん mailto:sage [2017/07/24(月) 22:18:09.60 ID:Dtg+FNV7.net] 俺は大幅に改善されたので満足です 744 名前：デフォルトの名無しさん mailto:sage [2017/07/24(月) 22:30:09.86 ID:DrMH5w+T.net] はすける始めたら彼女とセフレが出来ました！ 745 名前：デフォルトの名無しさん mailto:sage [2017/07/25(火) 00:51:32.66 ID:oURyYS1P.net] デザインパターンのようなものが自然に学べる(要出典) >>732 IOモナドを学んでしまうとvoidとかなんやねん！て気持ちになる 746 名前：デフォルトの名無しさん mailto:sage [2017/07/25(火) 02:18:19.45 ID:kRJD7bjt.net] IO () ← なんやねん！ 747 名前：デフォルトの名無しさん mailto:sage [2017/07/25(火) 11:48:16.84 ID:QpQhPQ2k.net] 空のタプルやね 引数にタプル使わないけど戻り値には使う 他の言語では最も書きにくいパターンを敢えて書く 748 名前：デフォルトの名無しさん mailto:sage [2017/07/27(木) 03:54:31.04 ID:iGcNC8dh.net] 空のタポゥってvoidに相当するんでないのって訊いてんの！ 749 名前：デフォルトの名無しさん mailto:sage [2017/07/27(木) 07:51:05.82 ID:y/+6hAIl.net] 例えばIO ()なら空のタプル自体は要らなくとも「IOという文脈に包まれている」という情報は欲しい 遅延評価がデフォのHaskellで実行順序 を保証するためにはそれらのIOを繋げる必要がある voidは何も返さないからそれができない こんな感じで値そのものに意味はなくとも「それとセットになっている何か」が欲しいとき空のタプルを使うことが多い 750 名前：デフォルトの名無しさん mailto:sage [2017/07/27(木) 08:18:47.17 ID:iGcNC8dh.net] 空タプルはvoidなんじゃないかっていってるの！ voidが無いなんて嘘っぱちだろっていってるの！ 実質 IO void やろってゆってんの！ 751 名前：デフォルトの名無しさん mailto:sage [2017/07/27(木) 08:24:32.65 ID:UvZuKEGA.net] 物狂いか 752 名前：デフォルトの名無しさん mailto:sage [2017/07/27(木) 11:08:02.42 ID:BU4hr0QJ.net] IO () はIOモナドの中にしか現れられないが 他言語のvoidはその辺の関数に普通に紛れ込めてしまう もちろん通常は規約とかデザインパターンなどで読みやすく気をつけるわけだけど IOモナドならそういう意図しない副作用が無いことを 型レベルで保証してくれてありがたい 753 名前：デフォルトの名無しさん mailto:sage [2017/07/27(木) 11:45:48.74 ID:tePeK+XY.net] 集合論でいうと()型の値の集合は空集合ではない デザインパターンでいうとSingleton だがvoidはSingletonではない そもそもvoidはオブジェクトか？ 754 名前：デフォルトの名無しさん mailto:sage [2017/07/27(木) 13:52:35.44 ID:cb3Opfj1.net] Haskellにおいてユニット型の値は () とボトムの2つ。 755 名前：デフォルトの名無しさん mailto:sage [2017/07/27(木) 15:38:01.66 ID:tePeK+XY.net] ボトムは正規形になっていない式ではないのか 途中の式のことを値といっていいのか 756 名前：デフォルトの名無しさん mailto:sage [2017/07/27(木) 16:36:16.86 ID:cb3Opfj1.net] >>747 https://wiki.haskell.org/Bottom > Bottom is a member of any type, even the trivial type () or the equivalent simple type: > > data Unary = Unary 757 名前：デフォルトの名無しさん mailto:sage [2017/07/27(木) 18:13:58.43 ID:tePeK+XY.net] value of any typeとは言っていない 758 名前：デフォルトの名無しさん [2017/07/27(木) 18:57:57.46 ID:TN85Uszo.net] >>747 関数を返す関数もShowのインスタンスじゃ無いから表示出来ないだけで値として扱われてるし、途中の式も値として扱われるなら扱って良いんじゃ無い？ 759 名前：デフォルトの名無しさん [2017/07/27(木) 19:03:38.43 ID:TN85Uszo.net] >>742 IO ()は出力関数の(どうせ捨てられる)値として便宜上付けてるだけだしなぁ。。。 別にIO Stringで毎回"Hello"とか返したっていいのをIO ()にしてるだけ。 受け取る意味はないけど、受け取って表示だって出来る。 そう言う意味じゃvoidとは言い難いな。 760 名前：デフォルトの名無しさん mailto:sage [2017/07/27(木) 19:18:08.33 ID:20Yx27ly.net] 一体彼は何を躍起になってるんだろうか 761 名前：デフォルトの名無しさん mailto:sage [2017/07/27(木) 20:05:00.63 ID:egT7olKo.net] >>749 型を集合とみなしたときの元(member)をずっと型が取り得る値(value)だと思い込んでた。 違うのか。 それは済まなかった。 私のレスは無視してくれ。 762 名前：デフォルトの名無しさん mailto:sage [2017/07/27(木) 22:06:59.31 ID:vZOWG5O9.net] まあ確かに⊥を値と認めない流儀はあるからなあ 763 名前：デフォルトの名無しさん mailto:sage [2017/07/27(木) 22:15:49.20 ID:vZOWG5O9.net] 任意の型aに対して、()型の値（≠⊥）を返す関数 :: a -> () はただひとつ f _ = () つまり const () しかないので、「void型を返す関数」が（パラメータ多相を除いて） 一意に決まるということを受け入れるという自殺的蛮勇がないなら void 型と ()型を同視することはできない 764 名前：デフォルトの名無しさん mailto:sage [2017/07/29(土) 00:23:19.35 ID:4ZTKGS6D.net] ゲーム作りてえなあ 765 名前：デフォルトの名無しさん mailto:sage [2017/07/29(土) 01:03:41.38 ID:e8mE+qrd.net] raincatは全ステージクリアした スペランカー並みに弱い猫だなあれ 766 名前：デフォルトの名無しさん mailto:sage [2017/07/29(土) 11:39:03.53 ID:kqaT8BL8.net] 遅延評価でグラフィック描画して何か嬉しいことあるん？ 767 名前：デフォルトの名無しさん mailto:sage [2017/07/29(土) 12:15:52.61 ID:SWzA4YZp.net] deleteを遅延するガベコレだけで邪魔臭いんだが 毒食わば皿までとnewも遅延するみたいな感じ 768 名前：デフォルトの名無しさん mailto:sage [2017/07/29(土) 20:11:41.20 ID:bMHI66Oo.net] GHCランタイムシステムのガベコレって、人間が操作するなら必ずここで一瞬停まるから、この瞬間にちょっとだけガベコレしといてねっていう細かい調整はできないの？ とにかく食い尽くしてもうなくなったら、解放可能な記憶域ないか、ようやく探し始めるしか能がないの？ 769 名前：デフォルトの名無しさん mailto:sage [2017/07/29(土) 21:04:34.50 ID:Txodz0Ts.net] >>760 標準ライブラリにGCを促す関数がある 770 名前：デフォルトの名無しさん mailto:sage [2017/07/29(土) 21:13:59.96 ID:GuKX0EtE.net] メモリー管理が陽に出てこないGC言語でGCについて語るAPIが存在するのも美しくないな 待機型処理の内部に組み入れられないんだろうか 771 名前：_ [2017/07/29(土) 21:43:41.58 ID:z3bKXBTm.net] ghc 8.2.1リリース age 772 名前：デフォルトの名無しさん mailto:sage [2017/07/29(土) 22:00:35.21 ID:ezVHy3/u.net] 実行頻度不明なのに強制GCしたらGCのオーバーヘッドに食い尽くされる可能性あるやろ 人力か機械学習でGCポイント探すしかないわ 線形型はよ 773 名前：デフォルトの名無しさん mailto:sage [2017/07/29(土) 22:05:39.73 ID:EGnuLLJd.net] Numeric Prelude標準モードできねえかな 774 名前：デフォルトの名無しさん mailto:sage [2017/07/30(日) 18:38:08.27 ID:Qtbkg44k.net] いつになったらGHCのコードに型を記述するんだよ あんなコードじゃ常に参加してる奴しか解読出来ないだろ 775 名前：デフォルトの名無しさん mailto:sage [2017/08/02(水) 14:19:58.09 ID:nRMWmSFr.net] デバッグで行単位で進める、 変数の値を都度観察できる、みたいなエディタというかIDEってありますかね？ 776 名前：デフォルトの名無しさん mailto:sage [2017/08/02(水) 15:25:19.26 ID:D+JhlBxR.net] デバッグで苦しんだことがないから分からないが 観察するべき実行時エラーが出るものなのか 必死に型を記述した結果がこれか 777 名前：デフォルトの名無しさん mailto:sage [2017/08/02(水) 15:33:23.39 ID:W2G2gcC4.net] >>767 ghciのデバッガじゃいかんの？ 778 名前：デフォルトの名無しさん mailto:sage [2017/08/02(水) 23:16:44.52 ID:Fofa317S.net] >>768 >>769 いや、型は合ってんだけど画像いじってて行列の合計数が合わんとか、出来映えがおかしいとかそういうの。途中でどうなってるのか観察したい。 emacsのREPLでちまちま動かして確認してんだけど面倒いなって。 途中でブレークポイント設定とかGHCにあるっぽいのは見たけど、そちらをもう少し当たるのが正解ですかね。 779 名前：デフォルトの名無しさん mailto:sage [2017/08/03(木) 00:12:26.54 ID:Ip+Lj8Tk.net] 純粋関数のprintデバッグができるDebug.Traceとかどうですか 780 名前：デフォルトの名無しさん mailto:sage [2017/08/03(木) 07:59:11.85 ID:d2xIcHkQ.net] プログラミング初心者だけど将来Haskell用のデバッガを作るのが夢です 781 名前：デフォルトの名無しさん mailto:sage [2017/08/03(木) 08:47:54.62 ID:jTGWEJQg.net] ジーニアス英和辞典 第五版にぴったりの例文があった Passion without action is�merely�a dream. 782 名前：デフォルトの名無しさん mailto:sage [2017/08/03(木) 08:53:44.89 ID:z5sKoHNx.net] デバッガよりVisual Studio並みの最強IDEがほしいわ 783 名前：デフォルトの名無しさん mailto:sage [2017/08/03(木) 22:43:53.87 ID:PWpQLJ0B.net] Bounded クラスと Enum クラスのインスタンスである型 T について、 n 個の要素を持つリスト型 [T] の値を全て要素として持つリストを生成する関数を enumerate とします。 たとえば型 T の値が A と B の2つだとし、n=3 だとすると、 (enumerate 3 :: [T]) = [[A, A, A], [A, A, B], [A, B, A], [A, B, B], [B, A, A], [B, A, B], [B, B, A], [B, B, B]] となります。 ただし、生成されるリストの要素の順番は問いません。 私は下記のように定義しました。 enumerate :: (Bounded a, Enum a) => Int -> [[a]] enumerate 1 = map (:[]) [minBound .. maxBound] enumerate n = concatMap (\x -> map (x:) (enumerate (n-1))) [minBound .. maxBound] n-1個の既に作られたリストの各要素 (リスト) に新たに型 T のそれぞれの値を接頭する作り方です。 シンプルで分かりやすいのですが、問題が1つあります。 この関数が生成したリストの全要素を順に別の計算に消費するようなプログラムを作っているのですが、 上記の定義ですと、リストの全要素が消費し尽くされるまでほぼ全要素分のメモリが必要になります。 x : x : x : ... と積み上がった cons がメモリに残るような作りのためです。 消費は順に一つずつ行うので、理想的にはメモリも要素一つ分で足ります。 現実はそうもいかないと思いますが、全要素分のメモリを保持し続ける必要はないはずです。 メモリ消費量をもっと抑える良い方法はないでしょうか。 784 名前：デフォルトの名無しさん mailto:sage [2017/08/04(金) 03:26:35.06 ID:F7/4gW8S.net] >>775 ちゃんとプロファイル取ってないから確証はないけど enumerateの定義が悪くてメモリ食いすぎてるような気がする Control.Monad のreplicateMをリストモナドに対して使うと 同様に重複順列を作れるからそれならどうだろうか replicateM 3 [0, 1] -- > [[0,0,0],[0,0,1],[0,1,0],[0,1,1],[1,0,0],[1,0,1],[1,1,0],[1,1,1]] あとリストを順に消費していくような計算ならfoldl'が使えるはず あるいは、「EnumなT型の有限個の直積」をうまく新たにEnumのインスタンスにして、 succ: Enum a => a -> a で例えば succ [A, A, A] = [A, A, B] みたいに計算できるようにしておいて、 STRefを利用してsuccで更新しながら消費していく、とか 785 名前：デフォルトの名無しさん mailto:sage [2017/08/04(金) 06:02:27.89 ID:dl0ZTbjy.net] https://wandbox.org/permlink/jdlx4FhKT80IWQKN data T = A | B deriving Show hoge 0 = A hoge 1 = B fuga _ 0 _ = [] fuga k x n = let (d,m) = divMod n k in hoge m : fuga k (x-1) d piyo x = map (fuga 2 x) [0..2^x-1] main = print $ piyo 3 786 名前：デフォルトの名無しさん mailto:sage [2017/08/04(金) 07:58:50.98 ID:QkUZB/64.net] >>775 import Data.List enumerate 1 = map (:[]) [1..] enumerate n = concatMap (\x -> map (x:) (enumerate (n-1))) [1..] main = print $ foldl' (+) 0 $ map (foldl' (+) 0) $ enumerate 10000 これ(最適化無し)でメモリリークしないあたり 普通に深さ優先で要らなくなった枝はGCされてると思うけど 787 名前：デフォルトの名無しさん [2017/08/04(金) 08:14:23.88 ID:QkUZB/64.net] あー>>778だと最後の一個が変わり続けるだけだから例としてはダメか 一応enumerateの引数やEnumリストの長さを変えてみても大丈夫だったけど 788 名前：デフォルトの名無しさん [2017/08/04(金) 22:00:01.39 ID:dl0ZTbjy.net] そんなことより8月4日21時から72時間のICFPのプログラミングコンテストがあるよ！ HaskellerならICFPくらい知ってるよね！ events.inf.ed.ac.uk/icfpcontest2017/ https://twitter.com/ICFPContest2017 789 名前：デフォルトの名無しさん mailto:sage [2017/08/04(金) 22:13:55.04 ID:hukhoKmj.net] みなさん、ありがとうございます。 >>776 前半の replicateM を使う方法は、プロファイリングしてみましたが、私のものとほとんど同じ結果でした。 メモリ消費の傾向もピークも同じ形です。 enumerate 14 で試したところ、最初にピークの 100MB ほどまでぐんぐんメモリを消費し、 その後 90MB 近くまで落ちてから一定です。 後半の方法はこれから試してみます。 >>777 挙げていただいたコードを Bounded と Enum を使って一般化して試してみました。 同様に enumerate 14 で実行してみると、メモリ消費傾向は全体的にほぼまっすぐな長方形に近い台形で、 ピークも 40kB と桁違いに少ないです。 >>778 メモリリークが起きていないことはどのようにして確認されました? 私は実行する時に RTS オプションの hc を付けてプロファイルを取って確認しました。 確かに深さ優先で一度ずつ探索する処理なのに、メモリが 100MB も消費されていて、 これは明らかにメモリリークしていると思ったのですが、どうでしょう? これから、私や >>776 の前半のやり方と >>777 のやり方の違いについて研究してみます。 790 名前：デフォルトの名無しさん [2017/08/05(土) 02:29:47.95 ID:B0WoWMTx.net] >>775 これの話に似てる？ kanae.2ch.net/test/read.cgi/prog/1431362559/667-670n これみたいなメモ化を使えばいいような気もする echo.2ch.net/test/read.cgi/tech/1428597032/873 https://wiki.haskell.org/The_Fibonacci_sequence 791 名前：デフォルトの名無しさん mailto:sage [2017/08/05(土) 03:50:29.84 ID:pRMdXxul.net] >>781 40KBはありえないので一般化に失敗してると思われる 792 名前：デフォルトの名無しさん mailto:sage [2017/08/05(土) 04:37:17.71 ID:2UARNcsu.net] >>782 メモ化は空間計算量と引き換えに高速化する話だからむしろ逆のような フィボナッチで言うならInteger 3個分のメモリがあればn番目が計算できるでしょって話だから タプリングの方が解決策としては近いと思う 結局リストで定義しちゃうと(そして評価しちゃうと) そのイミュータブル性のために各要素はまた参照されるかもしれないから GHCは捨てられないんだと思ってる 793 名前：デフォルトの名無しさん mailto:sage [2017/08/05(土) 05:35:09.29 ID:pRMdXxul.net] /usr/bin/time -f "sec: %e\tmem: %M" で n=13 >>775の sec: 0.36 mem: 89032 https://paiza.io/projects/EvT2VA9nWlsu95GfM7llhA >>776の replicateM は sec: 0.38 mem: 89016 と確かにメモリそう変わらない https://paiza.io/projects/-jBpd8K5u3IcfeqromaImg >>777の変な奴は sec: 0.86 mem: 3856 と確かにメモリ少ないけど時間かかりすぎ https://paiza.io/projects/k_jsvUVfq54JyTaA691CaQ >>782の iterate は sec: 0.36 mem: 77668 と少しメモリ小さい https://paiza.io/projects/rb9bWzNuI410te_SxtMqMw 794 名前：デフォルトの名無しさん mailto:sage [2017/08/05(土) 11:12:37.24 ID:xs6w3tHN.net] iterateは良いよね iterateはメモリを無限に使うとか予想したやつを退場させてから冷静な議論ができる 795 名前：デフォルトの名無しさん mailto:sage [2017/08/05(土) 11:39:14.63 ID:ZbIs+TkB.net] 好戦的 796 名前：デフォルトの名無しさん mailto:sage [2017/08/05(土) 13:37:30.60 ID:xs6w3tHN.net] 人間を退場させそうな勢いのAIに同じことが言えるのかね 好戦的AIの開発を禁止できるのか 797 名前：デフォルトの名無しさん mailto:sage [2017/08/05(土) 20:09:57.57 ID:O1n7JOVS.net] Windowsでjupyterできませんか？ 798 名前：デフォルトの名無しさん mailto:sage [2017/08/06(日) 00:35:09.20 ID:Q0UOjaQj.net] >>785 haskell初心者の私が頑張ってみました sec: 0.18 mem: 4024 https://paiza.io/projects/WzVPNUUH0xYOfCR99rLSVw 799 名前：デフォルトの名無しさん mailto:sage [2017/08/06(日) 14:15:08.49 ID:PBiILbDw.net] 私 (>>775) のや replicateM を使う方法は仮想的なツリーを深さ優先でたどります。 なので列挙したい型や、リストの要素数の影響をもろに受けるのですね。 (リストの要素ではなく、それを計算するためのサンクが大きい?) 一方で >>777 は10進数の値を一つずつn桁のk進数に変換しており、 また >>790 はn桁のk進数の値を0から順に1ずつ足しています (>>776 の後半のアイデア)。 共に理論上は1要素分のメモリしか必要ない方法なので、かなり省メモリなんですね。 理屈が分かってスッキリ� 800 名前：ｵました。 みなさん、ありがとうございました。 [] [ここ壊れてます] 801 名前：デフォルトの名無しさん mailto:sage [2017/08/07(月) 02:20:55.75 ID:LndoSP5N.net] 未評価のサンクじゃなくて最終的にn-1以下の評価済み結果を全て保持することになるからメモリを食うのでは？ 802 名前：デフォルトの名無しさん mailto:sage [2017/08/07(月) 09:52:01.96 ID:/JDQv1Xc.net] 自由な長さのビットは標準ライブラリに無いのですか？ 803 名前：デフォルトの名無しさん mailto:sage [2017/08/07(月) 11:32:36.95 ID:EbDwvOe5.net] >>792 全てとは何個ですか 有限個なら定量的に書いてください 無限なら書かなくていいです 804 名前：デフォルトの名無しさん mailto:sage [2017/08/07(月) 20:00:07.36 ID:Nk2fFjGd.net] >>789 dockerでihaskellだったら使ってる 805 名前：デフォルトの名無しさん mailto:sage [2017/08/07(月) 21:16:35.72 ID:AGrOxn5I.net] >>792 そうでしょうか? 私の方法 (>>775) で data T = A|B|C の時に print $ enumerate 3 としてみると [[A,A,A], [A,A,B], [A,A,C], [A,B,A], [A,B,B], ...] の順で評価されます。 外側リストの第1要素 [A,A,A] を評価し終えて次に第2要素 [A,A,B] を評価しようとする時、 [A,A,A] の第3要素の A はもう要らないので捨てて構わないはずです。 [A,A,B] の評価にまだ必要なのは第1要素と第2要素それぞれの A のみのはず。 さらに [B,A,A] まで評価が進めば、[A,A,A] から [A,C,C] まで評価した分はもう必要ありません。 そう考えると、enumerate n に常に必要なのは理論的には T 型の値 n 個分のみ。 評価済みの値の保持に必要なメモリ量は >>777 や >>790 の方法と同じです。 なので、評価済み結果の保持によってメモリが大きく消費されるのであれば、 >>777 や >>790 でも同様に大きなメモリを消費しているはずだと私は思うのですが、 どうでしょうか? 806 名前：デフォルトの名無しさん mailto:sage [2017/08/07(月) 21:17:23.45 ID:AGrOxn5I.net] >>792 私が原因はサンクにあるのではと思ったのは次のことからです。 私の方法 (>>775) で enumerate 3 :: [[T]] の第1要素を評価しようとする時、 まず concatMap の引数である [minBound .. maxBound] の第1要素だけが評価され、 残りは未評価のまま残ります (正確には enumFromTo の結果の弱頭部正規化ですね)。 次に map (x:) enumerate (n-1) があるので enumerate 2 の第1要素を評価する必要があります。 enumerate 2 でも同様のことが起こります。 これ、全部評価されつくされるまで、深さ分だけずっと残りますよね。 enumerate 自身が深さ方向にたどるごとに毎回呼ばれ、評価し切る前にまた呼ばれるので、 未評価で残るのは [minBound .. maxBound] の部分だけではないと思います。 このようなことが積み重なって、大量のメモリ消費に繋がっていると私は考えました。 リストを消費して何かを計算する関数に使うリストそのものを再帰的に作ると、 たぶん似たような事(無駄なメモリ消費)が起こるのではないかと思います。 807 名前：デフォルトの名無しさん mailto:sage [2017/08/08(火) 00:32:40.42 ID:ix2x2634.net] sumじゃなくlenghtで計算すると>>790のでもメモリ使うんだね >>775のsec: 0.19 mem: 89068 https://paiza.io/projects/CqJoDIkGAnH7qGSCKEAiyQ >>790のsec: 0.09 mem: 49084 https://paiza.io/projects/L4gRQ7RM5z3XFGf_Wu1YvQ 808 名前：デフォルトの名無しさん mailto:sage [2017/08/08(火) 03:20:35.89 ID:fUnlTWTU.net] 副作用の無い関数は同じ引数で毎回同じ戻り値になることが保証されてます n=2のとき enumerate 2 = concatMap (\x -> map (x:) (enumerate 1)) [A,B,C] となります [A,A]..[A,C]まで評価が終わったとき enumerate 1 = [[A],[B],[C]] が評価済みとなり再利用が可能となり enumerate 2 = [A,A] : [A,B] : [A,C] : concatMap (\x -> map (x:) [[A],[B],[C]]) [B,C] となり n-1 すなわち n=1 のときの結果が保持されることが分かります 同様にn=3のとき同じことが生じ enumerate 3 = [A,A,A] : ... : [A,C,C] : concatMap (\x -> map (x:) [[A,A], ... ,[C,C]]) [B,C] のようになり n-1 すなわち n=2 のときの結果が保持されることが分かります また n=3 のとき n=1 の結果の [[A],[B],[C]] の各要素は n=2 の結果から参照されてます すなわちGC可能な対象は 中身の[A] [B] [C]ではなく[,,,]の外側の部分だけです (もちろんまだ enumerate 1 をどこか呼び出される可能性があるならGCはされませんが…) ここまで言えば>>792の意味がわかりますね？ はい 809 名前：デフォルトの名無しさん mailto:sage [2017/08/08(火) 03:28:04.28 ID:fUnlTWTU.net] なおサンクを気にされてたようですが サンクを気おつけるべきは>>790のようなコードだと私は考えますが lastを取れば分かります https://paiza.io/projects/lmYXW-sssdTlAIGrju4u9g 810 名前：デフォルトの名無しさん mailto:sage [2017/08/08(火) 03:45:42.60 ID:aoRcppZr.net] >>796 >外側リストの第1要素 [A,A,A] を評価し終えて次に第2要素 [A,A,B] を評価しようとする時、 >[A,A,A] の第3要素の A はもう要らない 後ろ二つ [A,A]は、[A,A,A],[B,A,A],[C,A,A]で共有されるから そこで捨てるわけにはいかないんじゃないかな 811 名前：デフォルトの名無しさん mailto:sage [2017/08/08(火) 04:31:27.11 ID:shTh0A51.net] 詳しい情報サンクス 812 名前：デフォルトの名無しさん mailto:sage [2017/08/08(火) 21:31:40.60 ID:OEct+pCd.net] >>799 すいません、まだ良く理解できていません。 2点確認させてください。 まず、1行目でおっしゃっているのは参照透過性のことですよね。 次に、3行目以降でおっしゃっていることですが、それは本当ですか? それだと勝手にメモ化が行われているように私には見えるのですが。 例えば f x = x*2 という関数が定義されているとします。 その時に、別の関数 g の定義の中で、 let a = f 1; b = f 1 in ... とやっても、1度目の g の呼び出しで 1*2 の計算結果は再利用されませんよね。 a の束縛時と b の束縛時で、計 2 回同じ計算がされると思います。 1度目の g の呼び出しで a や b が 2 と評価された後、再び g が呼ばれた時は、 a や b はもう関数 f ではなく値 2 を指していますから、 これを以て「保存される」「再利用される」と言うのは理解できます。 以上のことから、enumerate 1 = [[A], [B], [C]] のリストも、 このままでは再利用されないと思うのですが。 再利用するには、計算結果を変数に束縛する必要がありませんか。 変なことを言っていたらすいません。 813 名前：デフォルトの名無しさん mailto:sage [2017/08/08(火) 21:58:17.33 ID:aoRcppZr.net] >>803 >再利用するには、計算結果を変数に束縛する必要がありませんか。 mapの引数として束縛されるんじゃないの? >>775 814 名前：デフォルトの名無しさん mailto:sage [2017/08/08(火) 22:23:03.19 ID:OEct+pCd.net] >>804 仮引数が束縛しているのはそのスコープ内だけだと思っていましたが、 違うのでしょうか。 let a = map id (enumerate 1); b = map id (enumerate 1) これは2度同じ計算 (enumerate 1 の評価) がされませんか? 815 名前：デフォルトの名無しさん mailto:sage [2017/08/08(火) 22:33:15.60 ID:aoRcppZr.net] 実際に起こっているのはこういうことなんだろうな let a = map id (enumerate 1); b = a; c=a 816 名前：デフォルトの名無しさん [2017/08/09(水) 00:17:08.56 ID:VTzajaTq.net] >>799-800 嘘乙 817 名前：デフォルトの名無しさん [2017/08/09(水) 02:22:31.31 ID:mQsXelmt.net] Glasgow Haskell Compiler上の遅延オブジェクト再利用手法の設計と実装 https://www.jstage.jst.go.jp/article/jssst/32/1/32_1_253/_pdf 818 名前：デフォルトの名無しさん mailto:sage [2017/08/09(水) 05:51:36.85 ID:L1lV7cdZ.net] ・愚直にパラメーターマシマシの関数 ・そのごちゃごちゃしたパラメーターをデータ構造にまとめてコードの視認性と一目理解可能性を向上したコード 後者が前者より２倍近く時間かかって悲しい データ構造の更新に思いの外時間がかかってるのだろうか データ構造の一部だけ更新って、変える部分だけ新しく作って、後のパラメーターは元のデータのそれへポインタコピーするだけだと思うんですけど それでもオーバーヘッド嵩むもんなんすかね ごちゃごちゃ版の、一つパラメーター更新して再帰で関数呼び出すだけなのと、 データ構造にまとめた版の（データ構造の）一つパラメーター更新して再帰で関数呼び出すのとは 何が処理の手間的に違うんですかね いいからパラメーター全部そのまま関数に並べ立てた方が速いんだよって言われてるようで悲しい 性能を犠牲にせずにメンテ力アップしたい 819 名前：デフォルトの名無しさん mailto:sage [2017/08/09(水) 05:57:53.35 ID:L1lV7cdZ.net] 多くの場合を受け取って、後でcaseなどで引数の場合分けをするより トップレベルで最初に引数のパターンマッチで場合分けしてから始める書き方の方が速いんですかね 後者はなんか何度も関数名書かなきゃいけなくて汚い感じするんですが。同じlet式もボイラープレートのようにまた書かなきゃならないし でも後者の方が高速動作する（経験則）みたいで悔しい 820 名前：デフォルトの名無しさん mailto:sage [2017/08/09(水) 07:31:58.59 ID:azQJOuJj.net] vectorパッケージ使ってて、ベンチマークとるとVector.Fusion.UtilとVector.Fusion.Stream.Monadicにリソースが割かれてるんだけど、 stream fusionてコンパイル時に効いてて、ランタイム時には出てこないと思ってたのだが、違うんかね？ 821 名前：デフォルトの名無しさん [2017/08/10(木) 00:20:12.66 ID:joXozDrb.net] 本物のプログラマはHaskellを使う - 第31回 itpro.nikkeibp.co.jp/article/COLUMN/20090512/329783/ > これは，GHCの最適化機能の一つである「共通部分式の削除（CSE：Common Subexpression Elimination）」によって，共通する式「unsafeVal 10」がメモ化されたためです。これにより「unsafeVal 10」は1回しか評価・実行されなくなってしまいます。 822 名前：デフォルトの名無しさん [2017/08/10(木) 00:21:53.72 ID:joXozDrb.net] > Haskellには第8回で説明した「メモ化」という機能があるため，同じ式が複数回，評価・実行されることはありません。 823 名前：デフォルトの名無しさん mailto:sage [2017/08/10(木) 01:41:50.38 ID:wtM226NM.net] >>809 パラメータごちゃごちゃってのが多引数関数なら、Haskellの関数はカリー化されてるので 変更するパラメータの箇所によっては関数定義が使いまわせて効率がよくなってる、かも 末尾再帰化で局所関数作ってやるみたいに、 外からは定義したデータ構造で受け取って、 関数内で再帰回すときはばらした局所関数を使うとかはどうか 824 名前：デフォルトの名無しさん mailto:sage [2017/08/10(木) 06:48:00.63 ID:Gy6ZNt2K.net] メモ化じゃなくてグラフ簡約では？ 825 名前：デフォルトの名無しさん mailto:sage [2017/08/10(木) 07:14:52.40 ID:7mVrofJh.net] itpro.nikkeibp.co.jp/article/COLUMN/20070305/263828/ >本物のプログラマはHaskellを使う >第8回　遅延評価の仕組み >この問題を解決するのが必要呼び出しです。必要呼び出しでは， >同じ変数から束縛された項はポインタによって共有され， >一度簡約された項をもう一度使用する場合には最初の計算によってキャッシュされた解を利用します。 >項を共有することにより，構文はもはや通常の木構造ではなくグラフ（graph）構造を取ることになります。 >そのため，このような簡約方法を「グラフ簡約（あるいはグラフ簡約法，graph reduction）」と呼びます。 >また，同じ式の評価のために，キャッシュされた解を使う手法のことを「メモ化（memoization）」といいます。 826 名前：デフォルトの名無しさん mailto:sage [2017/08/10(木) 11:53:35.98 ID:Mbfm9qrf.net] 共通部分式削除か もしバグの原因が最適化だったら簡単だな 最適化を無効にするだけでわかる 827 名前：デフォルトの名無しさん mailto:sage [2017/08/10(木) 15:16:55.85 ID:7Zrve9l8.net] 共通部分式削除ではないしバグでもない 828 名前：デフォルトの名無しさん mailto:sage [2017/08/10(木) 16:49:36.71 ID:R2w5AQk8.net] ぼく、グラフ簡約がいつされていつされないのかよく解ってない(｀･ェ･´) 829 名前：デフォルトの名無しさん [2017/08/10(木) 22:16:48.24 ID:fh9/jf6h.net] 基本的なこと www.kotha.net/hperf/basics.html > 関数の自動メモ化はない > Haskellの関数は同じ引数で呼ぶと同じ結果を返すので透過的にメモ化が可能だが、GHCはそれを行わない。 > 局所的な最適化によってメモ化と同じ結果になることはあるが、一般には期待できない。 > メモ化が必要なら「引数->結果」の対応を保存するデータ構造(Map、Arrayなど)を明示的に用意する必要がある。 830 名前：デフォルトの名無しさん [2017/08/10(木) 22:27:51.24 ID:fh9/jf6h.net] GHCのこと www.kotha.net/hperf/ghc.html > プログラムの低水準の振る舞い(たとえば、「このループでメモリ確保は発生する？」「この式はどのタイミングで評価される？」)を理解したり、GHCの最適化の結果を見たりするのには、Core言語形式の中間出力を読むと良い。 > 特に、小さいループを可能な限り高速化したい場合など、最適化後のCore出力を比較しながらコードをいじるのが有効なことがある。 > Core形式の最終形(最適化された後、STG言語に変換される直前)は-ddump-prepで読める。 831 名前：デフォルトの名無しさん mailto:sage [2017/08/10(木) 23:42:17.05 ID:7Zrve9l8.net] >>820 www.kotha.net/hperf/basics.html Haskellの言語仕様(ja)は式の評価順序を定めていないが、 GHCを始めとする有名な処理系は全て「必要呼び(call by need)」という評価戦略を基本にしている。 必要呼び戦略のもう一つの特徴は引数の自動メモ化である。 ある関数の仮引数が、その関数の本体に複数回出現したとしても、対応する実引数の評価は高々一回しか発生しない。 832 名前：デフォルトの名無しさん mailto:sage [2017/08/11(金) 00:45:37.86 ID:Ze2QVHug.net] 困ったときはhaskell-masterことtanakhに助けを求める 833 名前：デフォルトの名無しさん mailto:sage [2017/08/11(金) 03:54:12.02 ID:7orZPIZ6.net] フィボナッチ数を漸化式で単に実装したとき、そのままだと深い部分で同じ引数による呼び出しが無数に発生してると思うんですが 自動メモ化してくれないんすね 834 名前：デフォルトの名無しさん mailto:sage [2017/08/11(金) 04:15:27.98 ID:L7AEIGon.net] >>824 それは>>820のほうで >>775で起こる「メモ化」は>>816だろ 835 名前：デフォルトの名無しさん mailto:sage [2017/08/11(金) 05:49:13.91 ID:ZqUin61F.net] 言語別平均年収ランキング 1位Scala 626万円 2位Python 601万円 3位Kotlin 577万円 4位Swift, Ruby 562万円 6位Java 552万円 7位Perl 551万円 8位 C言語 538万円 9位JavaScript 536万円 10位PHP 522万円 11位COBOL 509万円 以下は求人が少ないためランキングから除外 Groovy 680万円 Haskell 670万円 Erlang 604万円 LISP 581万円 尚、C++, C#は調査対象外とする 836 名前：デフォルトの名無しさん mailto:sage [2017/08/11(金) 10:48:20.88 ID:Ca8C76qb.net] >>826 ＞尚、C++, C#は調査対象外とする なぜなんだ？それこそ興味深いんだが？ 837 名前：デフォルトの名無しさん mailto:sage [2017/08/11(金) 10:55:08.08 ID:mLIKyCPo.net] 難しすぎて習得者が少なすぎて調査不能なんだろう 838 名前：デフォルトの名無しさん [2017/08/11(金) 11:06:36.65 ID:QQDjRimB.net] 求人数が少ないから除外？ どうしてもその言語じゃなきゃだけど、その言語使える人が少ないって方が給料良いんだが。 (あと金出す側の資金力にもよる) Fortranとか意外と良いぞ。 金融系なら関数型言語。 839 名前：デフォルトの名無しさん [2017/08/11(金) 11:07:39.31 ID:QQDjRimB.net] あ、Fortranは大学がスパコンで使うとかの場合ね。 840 名前：デフォルトの名無しさん mailto:sage [2017/08/11(金) 11:15:12.10 ID:07jWFZnC.net] いやC++C#は� 841 名前：ｽいだろうよ [] [ここ壊れてます]

---

---

[ 続きを読む ] / [ 携帯版 ]

read.cgi ver5.27 [feat.BBS2 +1.6] / e.0.2 (02/09/03) / eucaly.net products.
担当:undef