関数型プログラミング言語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/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の意味がわかりますね？

はい

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

なおサンクを気にされてたようですが
サンクを気おつけるべきは>>790のようなコードだと私は考えますが
lastを取れば分かります
https://paiza.io/projects/lmYXW-sssdTlAIGrju4u9g

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

>>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]で共有されるから
そこで捨てるわけにはいかないんじゃないかな

**デフォルトの名無しさん** · 2017/08/08(火) 04:31:27.11

詳しい情報サンクス

**デフォルトの名無しさん** · 2017/08/08(火) 21:31:40.60

>>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]] のリストも、
このままでは再利用されないと思うのですが。
再利用するには、計算結果を変数に束縛する必要がありませんか。

変なことを言っていたらすいません。

**デフォルトの名無しさん** · 2017/08/08(火) 21:58:17.33

>>803
>再利用するには、計算結果を変数に束縛する必要がありませんか。

mapの引数として束縛されるんじゃないの? >>775

**デフォルトの名無しさん** · 2017/08/08(火) 22:23:03.19

>>804
仮引数が束縛しているのはそのスコープ内だけだと思っていましたが、
違うのでしょうか。

let a = map id (enumerate 1); b = map id (enumerate 1)

これは2度同じ計算 (enumerate 1 の評価) がされませんか?

**デフォルトの名無しさん** · 2017/08/08(火) 22:33:15.60

実際に起こっているのはこういうことなんだろうな

let a = map id (enumerate 1); b = a; c=a

**デフォルトの名無しさん** · 2017/08/09(水) 00:17:08.56

>>799-800
嘘乙

**デフォルトの名無しさん** · 2017/08/09(水) 02:22:31.31

Glasgow Haskell Compiler上の遅延オブジェクト再利用手法の設計と実装
https://www.jstage.jst.go.jp/article/jssst/32/1/32_1_253/_pdf

**デフォルトの名無しさん** · 2017/08/09(水) 05:51:36.85

・愚直にパラメーターマシマシの関数
・そのごちゃごちゃしたパラメーターをデータ構造にまとめてコードの視認性と一目理解可能性を向上したコード

後者が前者より２倍近く時間かかって悲しい
データ構造の更新に思いの外時間がかかってるのだろうか

データ構造の一部だけ更新って、変える部分だけ新しく作って、後のパラメーターは元のデータのそれへポインタコピーするだけだと思うんですけど
それでもオーバーヘッド嵩むもんなんすかね

ごちゃごちゃ版の、一つパラメーター更新して再帰で関数呼び出すだけなのと、
データ構造にまとめた版の（データ構造の）一つパラメーター更新して再帰で関数呼び出すのとは
何が処理の手間的に違うんですかね

いいからパラメーター全部そのまま関数に並べ立てた方が速いんだよって言われてるようで悲しい

性能を犠牲にせずにメンテ力アップしたい

**デフォルトの名無しさん** · 2017/08/09(水) 05:57:53.35

多くの場合を受け取って、後でcaseなどで引数の場合分けをするより
トップレベルで最初に引数のパターンマッチで場合分けしてから始める書き方の方が速いんですかね

後者はなんか何度も関数名書かなきゃいけなくて汚い感じするんですが。同じlet式もボイラープレートのようにまた書かなきゃならないし

でも後者の方が高速動作する（経験則）みたいで悔しい

**デフォルトの名無しさん** · 2017/08/09(水) 07:31:58.59

vectorパッケージ使ってて、ベンチマークとるとVector.Fusion.UtilとVector.Fusion.Stream.Monadicにリソースが割かれてるんだけど、
stream fusionてコンパイル時に効いてて、ランタイム時には出てこないと思ってたのだが、違うんかね？

**デフォルトの名無しさん** · 2017/08/10(木) 00:20:12.66

本物のプログラマはHaskellを使う - 第31回
http://itpro.nikkeibp.co.jp/article/COLUMN/20090512/329783/
> これは，GHCの最適化機能の一つである「共通部分式の削除（CSE：Common Subexpression Elimination）」によって，共通する式「unsafeVal 10」がメモ化されたためです。これにより「unsafeVal 10」は1回しか評価・実行されなくなってしまいます。

**デフォルトの名無しさん** · 2017/08/10(木) 00:21:53.72

> Haskellには第8回で説明した「メモ化」という機能があるため，同じ式が複数回，評価・実行されることはありません。

**デフォルトの名無しさん** · 2017/08/10(木) 01:41:50.38

>>809
パラメータごちゃごちゃってのが多引数関数なら、Haskellの関数はカリー化されてるので
変更するパラメータの箇所によっては関数定義が使いまわせて効率がよくなってる、かも

末尾再帰化で局所関数作ってやるみたいに、
外からは定義したデータ構造で受け取って、
関数内で再帰回すときはばらした局所関数を使うとかはどうか

**デフォルトの名無しさん** · 2017/08/10(木) 06:48:00.63

メモ化じゃなくてグラフ簡約では？