関数型プログラミング言語Haskell Part30 [無断転載禁止]©2ch.net

**デフォルトの名無しさん** · 2017/01/15(日) 23:43:54.28

関数型プログラミング言語 Haskell について語るスレです。

haskell.org (公式サイト)
http://www.haskell.org/

前スレ
関数型プログラミング言語Haskell Part28
http://echo.2ch.net/test/read.cgi/tech/1428597032/

**デフォルトの名無しさん** · 2017/06/19(月) 05:32:16.99

そういう関数ってすでにある？って質問なのにオレオレ実装載せてく人たち…

**デフォルトの名無しさん** · 2017/06/19(月) 06:40:21.02

しかも、質問者の実装が一番素直で分かりやすい

**デフォルトの名無しさん** · 2017/06/19(月) 07:45:05.62

隙あらば実装

いや、プログラム板ではそれでいいんじゃないか。

**デフォルトの名無しさん** · 2017/06/19(月) 10:22:09.65

組み込みの関数でラムダ式を隠蔽してしまうことには意味があるんじゃないか

ところで質問者の例だと結果が可換なのでそうじゃない例の方が良かったのでは
f (+) [1, 2, 3] [1, 3, 5] -> [[2,4,6],[3,5,7],[4,6,8]]
f (+) [1, 3, 5] [1, 2, 3] -> [[2,3,4],[4,5,6],[6,7,8]]
とか

**デフォルトの名無しさん** · 2017/06/19(月) 10:46:07.27

>>702
それならば、あなたはどのような意味を見いだしたのかまでちゃんと言わないと。
何にどのような意味を見いだすかは人それぞれですし。

私は、ソースは人間が読みやすい事に最大の意味を見いだします。
なので、計算結果を容易に想像できるという点で、
>>692 や >> 696 の下の定義は好きですね。

**デフォルトの名無しさん** · 2017/07/01(土) 02:37:46.49

IOモナドは命令書という喩えが一番しっくり来た

**デフォルトの名無しさん** · 2017/07/01(土) 08:12:10.07

IOモナドっつーか、モナドは難しく考えんで良いだろと。
IO String >>= String
IO String >> は結果を捨てる。>>= ¥_ -> の略記。
return String ってしたらIOなString返るから、return使えばモナドの途中で純粋な関数で加工出来る。

それがIOモナドにも具体的な型にも依存しない汎用的な表現が

m a >>= a

ってだけ。

これだけ覚えれば使うにゃ十分だし、使ってるうちにただの型クラスやってわかる。
結局型クラスも型を受け取れる型ってだけで、ただの型でもあるから、純粋関数の結果としてString返すと、IO StringとStringは型が違うよって怒られる。

だからIO Stringにする為にIO Stringな関数か、return使いましょうってだけ。

具体的な型を考えれば何のことはない。
returnはそう考えればまあ自然なんだが、リターンってよりレシーブって印象。

**デフォルトの名無しさん** · 2017/07/01(土) 09:35:49.67

main = getLine >>= return.tail >>= putStrLn

getLine
一行入力でIO String生成。

>>=
getLineに生成されたIO StringをStringとして右辺に渡す。

return.tail
tailは受け取ったStringの先頭を省く。
そのままだとStringのままで、IO Stringを受け取る次の>>=に渡せないので、returnでStringをIO Stringにして返す。

>>=(2番目)
最終出力のputStrLnに向けてIO StringをStringにして渡す。

putStrLn
受け取ったStringを改行付き出力。

説明のために長く書いたけど、型を揃えれば良いって分かればこうも書ける。

main = getLine >>= putStrLn.tail

何もないところからIOを生成するmain = 直後の関数以降は基本的に純粋な型を受け取ってIOな型を返せばコンパイラ通るので、何の役にも立たないけどこれもコンパイル通る。

main = getLine >>= return.tail

putStrLnも関数である以上、何らかの値を返してるので見ようと思えば見れる。

main >>= putStrLn.tail >>= print

()にIOを付けたIO ()が返ってると分かる。

**デフォルトの名無しさん** · 2017/07/01(土) 10:27:56.55

IOと純粋関数の関係がどうしても理解できなかったけどwiki読んだらやっとわかったからオススメ
https://wiki.haskell.org/IO_inside

**デフォルトの名無しさん** · 2017/07/03(月) 20:20:17.13

stack使ってるのですが、openFileでカレントディレクトリ以外のファイルを指定って出来ないんですかね？

**デフォルトの名無しさん** · 2017/07/03(月) 20:31:50.76

stack関係あったっけ？
何となく¥を¥¥ってしてないだけじゃないかと予想。

**デフォルトの名無しさん** · 2017/07/08(土) 21:56:26.43

タプル作ろうと思ってHoogleで
f :: a -> b -> (a, b)
f a b = (a, b)
となるような関数探したら見つからないんだけどもしかしてない？
割と使いそうなイメージなんだけど

**デフォルトの名無しさん** · 2017/07/08(土) 22:11:48.22

どういうときに使いたいのさ
curry/uncurry ならたまに使うけど

**デフォルトの名無しさん** · 2017/07/08(土) 22:18:49.21

これで
https://wandbox.org/permlink/bSFTBbmr9cQGguSw

**デフォルトの名無しさん** · 2017/07/08(土) 22:48:00.26

>>710
タプルコンストラクタ

$ ghci
GHCi, version 8.0.2: http://www.haskell.org/ghc/ :? for help
Prelude> :t ((,))
((,)) :: a -> b -> (a, b)

**デフォルトの名無しさん** · 2017/07/08(土) 22:53:26.22

>>713
おお、まさにこれです
ありがとうございます

**デフォルトの名無しさん** · 2017/07/10(月) 01:15:03.97

すみません traceデバッグについてですが
ある変数に色とかで印を付けて
IOとは別の専用簡易コンソールに出力表示とか
簡単に出来ない物でしょうか。

**デフォルトの名無しさん** · 2017/07/15(土) 19:13:14.12

GHC 8.2 で実装予定の backpack なるものが一体
現在のどのような問題をどのように解決することを目指したものか、
分かる方いますか？

どうも、モジュールシステムの拡張みたいですが...

**デフォルトの名無しさん** · 2017/07/17(月) 23:01:46.61

ご冥福

**デフォルトの名無しさん** · 2017/07/18(火) 03:45:58.72

すぐりって読むのだと思ってました

**デフォルトの名無しさん** · 2017/07/19(水) 22:41:31.74

https://twitter.com/tanakh/status/886624071005294592

これ？

**デフォルトの名無しさん** · 2017/07/21(金) 21:39:30.54

文字列のリストがあって、それぞれの要素を順番にputStrLnするだけならmapM_よりtraverse_の方がいいですか？

**デフォルトの名無しさん** · 2017/07/22(土) 10:13:22.40

Haskellerなんですぐ死んでしまうん

**デフォルトの名無しさん** · 2017/07/22(土) 11:57:08.36

えぇ・・・

**デフォルトの名無しさん** · 2017/07/22(土) 14:53:16.39

必要以上に多相にしたり制約を弱めるのは典型的な bad practice
concat のかわりに join 使ったりしないでしょ

**デフォルトの名無しさん** · 2017/07/22(土) 14:54:33.27

ライブラリコード書くときには可能な限り型クラス制約を弱めて多相に
利用するコードではむしろ反対に

**デフォルトの名無しさん** · 2017/07/22(土) 17:58:06.65

>>723
つまりtraverse_の方がいいって認識でいいですか？

**デフォルトの名無しさん** · 2017/07/22(土) 19:58:53.32

Haskellerはマジでメンヘラが多い

**デフォルトの名無しさん** · 2017/07/22(土) 22:29:16.45

パフォーマンスモニターを提供する ekg というライブラリがあるんだが、
これ、なかなか凄いな。

統計情報がHTTPプロトコルでリアルタイムに提供されるから、
モニタリング専用のアプリを使わずとも普通のブラウザで見れる。
カウントするものをプログラムの中で定義することもできるみたいだし、
けっこう本格的だ。
パフォーマンスチューニングが捗りそう。

ちなみに、俺はこのライブラリの存在をここで知った。
http://www.stephendiehl.com/posts/production.html
このブログポストに商業アプリ制作にHaskellを使う際の心得みたいなことが書かれていて、
Performance and Monitoring の項で ekg が紹介されている。
このブログの他のポストもなかなか面白いから暇人は読んでみるといいよ。

**デフォルトの名無しさん** · 2017/07/23(日) 00:17:34.21

>>725
ちょい待ち　>>723 や >>724 のアドバイスに従うなら、そこは mapM_ でしょ

**デフォルトの名無しさん** · 2017/07/24(月) 20:13:14.08

他の言語の書き方が良くなると聞いて始めてみたが、難しい・・・
というか今のとこ恩恵が分かんない^^;

**デフォルトの名無しさん** · 2017/07/24(月) 20:20:07.13

他言語の書き方は俺は良くなったな

**デフォルトの名無しさん** · 2017/07/24(月) 21:03:53.98

過去何度か似たような質問や意見が出てるが、
今までこういう書き方だったのがHaskellのお陰でこう改善された、
という具体例が挙がった試しがない。
改善例が載っているブログなどの紹介すらない。

俺の中では、前後の違いを明確に説明できないものは改善とは認められない。
原因がはっきりしない事はあるだろうが、改善したと言うからには
少なくとも違いははっきりと説明してほしい。

それができないと言う事は、きっと違いが説明できないほど微妙で曖昧な変化を
改善と言っているのだろう。

**デフォルトの名無しさん** · 2017/07/24(月) 21:22:17.61

いやそんなの最初からちゃんとやれよと思うかもしれんが非関数型の言語を触っているときに比べて入出力をはっきりと意識するようにはなった
特に動的型付けだと何も考えなくても動くだけのものは作れてしまうからな

**デフォルトの名無しさん** · 2017/07/24(月) 21:27:21.43

大リーグ養成ギブスはめられてるような気持ち

**デフォルトの名無しさん** · 2017/07/24(月) 21:56:08.66

>>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　　ヾ　丶
　　　　　"~､ｿ:: :い:: :　　　　　＼_　　ノ　,　　　ヾ　丶

**デフォルトの名無しさん** · 2017/07/24(月) 22:18:09.60

俺は大幅に改善されたので満足です

**デフォルトの名無しさん** · 2017/07/24(月) 22:30:09.86

はすける始めたら彼女とセフレが出来ました！

**デフォルトの名無しさん** · 2017/07/25(火) 00:51:32.66

デザインパターンのようなものが自然に学べる(要出典)

>>732
IOモナドを学んでしまうとvoidとかなんやねん！て気持ちになる

**デフォルトの名無しさん** · 2017/07/25(火) 02:18:19.45

IO () ← なんやねん！

**デフォルトの名無しさん** · 2017/07/25(火) 11:48:16.84

空のタプルやね
引数にタプル使わないけど戻り値には使う
他の言語では最も書きにくいパターンを敢えて書く

**デフォルトの名無しさん** · 2017/07/27(木) 03:54:31.04

空のタポゥってvoidに相当するんでないのって訊いてんの！

**デフォルトの名無しさん** · 2017/07/27(木) 07:51:05.82

例えばIO ()なら空のタプル自体は要らなくとも「IOという文脈に包まれている」という情報は欲しい
遅延評価がデフォのHaskellで実行順序
を保証するためにはそれらのIOを繋げる必要がある
voidは何も返さないからそれができない
こんな感じで値そのものに意味はなくとも「それとセットになっている何か」が欲しいとき空のタプルを使うことが多い

**デフォルトの名無しさん** · 2017/07/27(木) 08:18:47.17

空タプルはvoidなんじゃないかっていってるの！
voidが無いなんて嘘っぱちだろっていってるの！

実質 IO void やろってゆってんの！

**デフォルトの名無しさん** · 2017/07/27(木) 08:24:32.65

物狂いか

**デフォルトの名無しさん** · 2017/07/27(木) 11:08:02.42

IO () はIOモナドの中にしか現れられないが
他言語のvoidはその辺の関数に普通に紛れ込めてしまう
もちろん通常は規約とかデザインパターンなどで読みやすく気をつけるわけだけど
IOモナドならそういう意図しない副作用が無いことを
型レベルで保証してくれてありがたい

**デフォルトの名無しさん** · 2017/07/27(木) 11:45:48.74

集合論でいうと()型の値の集合は空集合ではない
デザインパターンでいうとSingleton

だがvoidはSingletonではない
そもそもvoidはオブジェクトか？

**デフォルトの名無しさん** · 2017/07/27(木) 13:52:35.44

Haskellにおいてユニット型の値は () とボトムの2つ。

**デフォルトの名無しさん** · 2017/07/27(木) 15:38:01.66

ボトムは正規形になっていない式ではないのか
途中の式のことを値といっていいのか

**デフォルトの名無しさん** · 2017/07/27(木) 16:36:16.86

>>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

**デフォルトの名無しさん** · 2017/07/27(木) 18:13:58.43

value of any typeとは言っていない

**デフォルトの名無しさん** · 2017/07/27(木) 18:57:57.46

>>747
関数を返す関数もShowのインスタンスじゃ無いから表示出来ないだけで値として扱われてるし、途中の式も値として扱われるなら扱って良いんじゃ無い？

**デフォルトの名無しさん** · 2017/07/27(木) 19:03:38.43

>>742
IO ()は出力関数の(どうせ捨てられる)値として便宜上付けてるだけだしなぁ。。。
別にIO Stringで毎回"Hello"とか返したっていいのをIO ()にしてるだけ。
受け取る意味はないけど、受け取って表示だって出来る。
そう言う意味じゃvoidとは言い難いな。

**デフォルトの名無しさん** · 2017/07/27(木) 19:18:08.33

一体彼は何を躍起になってるんだろうか

**デフォルトの名無しさん** · 2017/07/27(木) 20:05:00.63

>>749
型を集合とみなしたときの元(member)をずっと型が取り得る値(value)だと思い込んでた。

違うのか。
それは済まなかった。

私のレスは無視してくれ。

**デフォルトの名無しさん** · 2017/07/27(木) 22:06:59.31

まあ確かに⊥を値と認めない流儀はあるからなあ

**デフォルトの名無しさん** · 2017/07/27(木) 22:15:49.20

任意の型aに対して、()型の値（≠⊥）を返す関数 :: a -> () はただひとつ

f _ = ()
つまり const ()

しかないので、「void型を返す関数」が（パラメータ多相を除いて）
一意に決まるということを受け入れるという自殺的蛮勇がないなら
void 型と ()型を同視することはできない

**デフォルトの名無しさん** · 2017/07/29(土) 00:23:19.35

ゲーム作りてえなあ

**デフォルトの名無しさん** · 2017/07/29(土) 01:03:41.38

raincatは全ステージクリアした
スペランカー並みに弱い猫だなあれ

**デフォルトの名無しさん** · 2017/07/29(土) 11:39:03.53

遅延評価でグラフィック描画して何か嬉しいことあるん？

**デフォルトの名無しさん** · 2017/07/29(土) 12:15:52.61

deleteを遅延するガベコレだけで邪魔臭いんだが
毒食わば皿までとnewも遅延するみたいな感じ

**デフォルトの名無しさん** · 2017/07/29(土) 20:11:41.20

GHCランタイムシステムのガベコレって、人間が操作するなら必ずここで一瞬停まるから、この瞬間にちょっとだけガベコレしといてねっていう細かい調整はできないの？

とにかく食い尽くしてもうなくなったら、解放可能な記憶域ないか、ようやく探し始めるしか能がないの？

**デフォルトの名無しさん** · 2017/07/29(土) 21:04:34.50

>>760
標準ライブラリにGCを促す関数がある

**デフォルトの名無しさん** · 2017/07/29(土) 21:13:59.96

メモリー管理が陽に出てこないGC言語でGCについて語るAPIが存在するのも美しくないな
待機型処理の内部に組み入れられないんだろうか

_ · 2017/07/29(土) 21:43:41.58

ghc 8.2.1リリース
age

**デフォルトの名無しさん** · 2017/07/29(土) 22:00:35.21

実行頻度不明なのに強制GCしたらGCのオーバーヘッドに食い尽くされる可能性あるやろ
人力か機械学習でGCポイント探すしかないわ
線形型はよ

**デフォルトの名無しさん** · 2017/07/29(土) 22:05:39.73

Numeric Prelude標準モードできねえかな

**デフォルトの名無しさん** · 2017/07/30(日) 18:38:08.27

いつになったらGHCのコードに型を記述するんだよ
あんなコードじゃ常に参加してる奴しか解読出来ないだろ

**デフォルトの名無しさん** · 2017/08/02(水) 14:19:58.09

デバッグで行単位で進める、
変数の値を都度観察できる、みたいなエディタというかIDEってありますかね？

**デフォルトの名無しさん** · 2017/08/02(水) 15:25:19.26

デバッグで苦しんだことがないから分からないが
観察するべき実行時エラーが出るものなのか
必死に型を記述した結果がこれか

**デフォルトの名無しさん** · 2017/08/02(水) 15:33:23.39

>>767
ghciのデバッガじゃいかんの？

**デフォルトの名無しさん** · 2017/08/02(水) 23:16:44.52

>>768
>>769
いや、型は合ってんだけど画像いじってて行列の合計数が合わんとか、出来映えがおかしいとかそういうの。途中でどうなってるのか観察したい。
emacsのREPLでちまちま動かして確認してんだけど面倒いなって。

途中でブレークポイント設定とかGHCにあるっぽいのは見たけど、そちらをもう少し当たるのが正解ですかね。

**デフォルトの名無しさん** · 2017/08/03(木) 00:12:26.54

純粋関数のprintデバッグができるDebug.Traceとかどうですか

**デフォルトの名無しさん** · 2017/08/03(木) 07:59:11.85

プログラミング初心者だけど将来Haskell用のデバッガを作るのが夢です

**デフォルトの名無しさん** · 2017/08/03(木) 08:47:54.62

ジーニアス英和辞典第五版にぴったりの例文があった
Passion without action is??merely??a dream.

**デフォルトの名無しさん** · 2017/08/03(木) 08:53:44.89

デバッガよりVisual Studio並みの最強IDEがほしいわ

**デフォルトの名無しさん** · 2017/08/03(木) 22:43:53.87

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 がメモリに残るような作りのためです。

消費は順に一つずつ行うので、理想的にはメモリも要素一つ分で足ります。
現実はそうもいかないと思いますが、全要素分のメモリを保持し続ける必要はないはずです。

メモリ消費量をもっと抑える良い方法はないでしょうか。

**デフォルトの名無しさん** · 2017/08/04(金) 03:26:35.06

>>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で更新しながら消費していく、とか

**デフォルトの名無しさん** · 2017/08/04(金) 06:02:27.89

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

**デフォルトの名無しさん** · 2017/08/04(金) 07:58:50.98

>>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されてると思うけど

**デフォルトの名無しさん** · 2017/08/04(金) 08:14:23.88

あー>>778だと最後の一個が変わり続けるだけだから例としてはダメか
一応enumerateの引数やEnumリストの長さを変えてみても大丈夫だったけど

**デフォルトの名無しさん** · 2017/08/04(金) 22:00:01.39

そんなことより8月4日21時から72時間のICFPのプログラミングコンテストがあるよ！
HaskellerならICFPくらい知ってるよね！

http://events.inf.ed.ac.uk/icfpcontest2017/
https://twitter.com/ICFPContest2017

**デフォルトの名無しさん** · 2017/08/04(金) 22:13:55.04

みなさん、ありがとうございます。

>>776
前半の replicateM を使う方法は、プロファイリングしてみましたが、私のものとほとんど同じ結果でした。
メモリ消費の傾向もピークも同じ形です。

enumerate 14 で試したところ、最初にピークの 100MB ほどまでぐんぐんメモリを消費し、
その後 90MB 近くまで落ちてから一定です。

後半の方法はこれから試してみます。

>>777
挙げていただいたコードを Bounded と Enum を使って一般化して試してみました。
同様に enumerate 14 で実行してみると、メモリ消費傾向は全体的にほぼまっすぐな長方形に近い台形で、
ピークも 40kB と桁違いに少ないです。

>>778
メモリリークが起きていないことはどのようにして確認されました?
私は実行する時に RTS オプションの hc を付けてプロファイルを取って確認しました。
確かに深さ優先で一度ずつ探索する処理なのに、メモリが 100MB も消費されていて、
これは明らかにメモリリークしていると思ったのですが、どうでしょう?

これから、私や >>776 の前半のやり方と >>777 のやり方の違いについて研究してみます。

**デフォルトの名無しさん** · 2017/08/05(土) 02:29:47.95

>>775
これの話に似てる？
http://kanae.2ch.net/test/read.cgi/prog/1431362559/667-670n

これみたいなメモ化を使えばいいような気もする
http://echo.2ch.net/test/read.cgi/tech/1428597032/873
https://wiki.haskell.org/The_Fibonacci_sequence

**デフォルトの名無しさん** · 2017/08/05(土) 03:50:29.84

>>781
40KBはありえないので一般化に失敗してると思われる

**デフォルトの名無しさん** · 2017/08/05(土) 04:37:17.71

>>782
メモ化は空間計算量と引き換えに高速化する話だからむしろ逆のような
フィボナッチで言うならInteger 3個分のメモリがあればn番目が計算できるでしょって話だから
タプリングの方が解決策としては近いと思う

結局リストで定義しちゃうと(そして評価しちゃうと)
そのイミュータブル性のために各要素はまた参照されるかもしれないから
GHCは捨てられないんだと思ってる

**デフォルトの名無しさん** · 2017/08/05(土) 05:35:09.29

/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

**デフォルトの名無しさん** · 2017/08/05(土) 11:12:37.24

iterateは良いよね
iterateはメモリを無限に使うとか予想したやつを退場させてから冷静な議論ができる

**デフォルトの名無しさん** · 2017/08/05(土) 11:39:14.63

好戦的

**デフォルトの名無しさん** · 2017/08/05(土) 13:37:30.60

人間を退場させそうな勢いのAIに同じことが言えるのかね
好戦的AIの開発を禁止できるのか

**デフォルトの名無しさん** · 2017/08/05(土) 20:09:57.57

Windowsでjupyterできませんか？

**デフォルトの名無しさん** · 2017/08/06(日) 00:35:09.20

>>785
haskell初心者の私が頑張ってみました

sec: 0.18 mem: 4024
https://paiza.io/projects/WzVPNUUH0xYOfCR99rLSVw

**デフォルトの名無しさん** · 2017/08/06(日) 14:15:08.49

私 (>>775) のや replicateM を使う方法は仮想的なツリーを深さ優先でたどります。
なので列挙したい型や、リストの要素数の影響をもろに受けるのですね。
(リストの要素ではなく、それを計算するためのサンクが大きい?)

一方で >>777 は10進数の値を一つずつn桁のk進数に変換しており、
また >>790 はn桁のk進数の値を0から順に1ずつ足しています (>>776 の後半のアイデア)。
共に理論上は1要素分のメモリしか必要ない方法なので、かなり省メモリなんですね。

理屈が分かってスッキリしました。
みなさん、ありがとうございました。

**デフォルトの名無しさん** · 2017/08/07(月) 02:20:55.75

未評価のサンクじゃなくて最終的にn-1以下の評価済み結果を全て保持することになるからメモリを食うのでは？

**デフォルトの名無しさん** · 2017/08/07(月) 09:52:01.96

自由な長さのビットは標準ライブラリに無いのですか？

**デフォルトの名無しさん** · 2017/08/07(月) 11:32:36.95

>>792
全てとは何個ですか
有限個なら定量的に書いてください
無限なら書かなくていいです

**デフォルトの名無しさん** · 2017/08/07(月) 20:00:07.36

>>789
dockerでihaskellだったら使ってる

**デフォルトの名無しさん** · 2017/08/07(月) 21:16:35.72

>>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 でも同様に大きなメモリを消費しているはずだと私は思うのですが、
どうでしょうか?

**デフォルトの名無しさん** · 2017/08/07(月) 21:17:23.45

>>792
私が原因はサンクにあるのではと思ったのは次のことからです。

私の方法 (>>775) で enumerate 3 :: [[T]] の第1要素を評価しようとする時、
まず concatMap の引数である [minBound .. maxBound] の第1要素だけが評価され、
残りは未評価のまま残ります (正確には enumFromTo の結果の弱頭部正規化ですね)。
次に map (x:) enumerate (n-1) があるので enumerate 2 の第1要素を評価する必要があります。
enumerate 2 でも同様のことが起こります。
これ、全部評価されつくされるまで、深さ分だけずっと残りますよね。

enumerate 自身が深さ方向にたどるごとに毎回呼ばれ、評価し切る前にまた呼ばれるので、
未評価で残るのは [minBound .. maxBound] の部分だけではないと思います。

このようなことが積み重なって、大量のメモリ消費に繋がっていると私は考えました。
リストを消費して何かを計算する関数に使うリストそのものを再帰的に作ると、
たぶん似たような事(無駄なメモリ消費)が起こるのではないかと思います。

**デフォルトの名無しさん** · 2017/08/08(火) 00:32:40.42

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

**デフォルトの名無しさん** · 2017/08/08(火) 03:20:35.89

副作用の無い関数は同じ引数で毎回同じ戻り値になることが保証されてます

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の意味がわかりますね？

はい