関数型プログラミング言語Haskell Part9
■ このスレッドは過去ログ倉庫に格納されています
0001デフォルトの名無しさん
2008/05/17(土) 16:41:29http://www.haskell.org/
日本語サイト
http://www.sampou.org/cgi-bin/haskell.cgi
http://www.shido.info/hs/
過去ログ
関数型プログラミング言語Haskell
Part1 http://pc.2ch.net/tech/kako/996/996131288.html
Part2 http://pc2.2ch.net/test/read.cgi/tech/1013846140/
Part3 http://pc8.2ch.net/test/read.cgi/tech/1076418993/
Part4 http://pc8.2ch.net/test/read.cgi/tech/1140717775/
Part5 http://pc8.2ch.net/test/read.cgi/tech/1149263630/
Part6 http://pc11.2ch.net/test/read.cgi/tech/1162902266/
Part7 http://pc11.2ch.net/test/read.cgi/tech/1174211797/
Part8 http://pc11.2ch.net/test/read.cgi/tech/1193743693/
・2chの仕様により、行頭の半角スペースは表示されません。
コードをインデントしたいときは、代わりに または全角スペースを使うことができます。
0655デフォルトの名無しさん
2008/08/29(金) 14:13:46記述上は包まれた形になってるけど、実装では包みが外れた形になる。
参照: http://haskell.g.hatena.ne.jp/jmk/20061203/1165141002
Pは直接的にはうまく束ねることができないから、一旦仮想的なReadPで束ねてるって感じ？
0656デフォルトの名無しさん
2008/08/29(金) 15:53:54どうもありがとうございます。
実際にはReadPの所はR Get やR Lookなどが渡されることになりますよね。
そのあとすぐにrunで即Rはずしてますし。
＞Pは直接的にはうまく束ねることができないから
これってどういう意味で仰ったんですか？
P を束ねてパーサとして使うことも、実際できる（>>654のget'など）のでわざわざどうしてReadPにするのか、
Pの>>=が左結合的に作用するのが問題らしいんですけどそれが問題になる具体的なケースについて
私にはｻｯﾊﾟﾘ思い付かなかったので先人たる皆様にお聞きしたかった次第です。
0657デフォルトの名無しさん
2008/08/29(金) 17:28:28ReadP の計算で左結合になってる >>= がある場合でも、
内側の P の >>= をすべて右結合にすることで、
P の >>= の再帰が無くなって効率が良くなる。
9節の第1パラグラフに書いてある通りなんだけど。
左結合を右結合にってのは、>>= の結合則
(m >>= f) >>= g == m >>= (\a -> f a >>= g)
の左辺を右辺にするってな話。
例えば、string s >>= f でも string s の中で
>>= を使ってるので、左結合になってる。
つまりほとんど全ての場合に当てはまる。
0658デフォルトの名無しさん
2008/08/29(金) 17:29:19リストの ++ は左引数に関して再帰する。
[] ++ ys = ys
(x:xs) ++ ys = x : (xs ++ ys)
そのため (xs ++ ys) ++ zs は xs に関して二重に再帰することになる。
foldr (++) [] (map show [1..10000])
foldl (++) [] (map show [1..10000])
実際これらを実行してみると前者はすぐ終わるけど、後者は "1" を10000回結合、
"2" を9999回結合、... "10000" を1回結合、みたいになって遅い。加速してくけど。
遅いだけじゃなく、中間リストを生成するので無駄にメモリを使うことにもなる。
foldl は極端な例だけど、foldr も極端で、いつも無駄が無いようにはいかない。
0659デフォルトの名無しさん
2008/08/29(金) 17:30:18xs ++ ys は、xs の最後の [] を ys に置き換える。
それを効率よくやるには、最初っから [] なんか使わないで、
1:2:3:[] を \nil -> 1:2:3:nil みたいにしとけばいいじゃんという発想。
つまり [a] を [a] -> [a] に、xs を xs ++ に、++ を (.) にする。
こうしておくと、[] を与えてリストに戻すときには、
(.) が右結合になってなくても ++ は右結合になる。
(((xs ++) . (ys ++)) . (zs ++)) []
= ((xs ++) . (ys ++)) (zs ++ [])
= (xs ++) (ys ++ (zs ++ []))
= xs ++ (ys ++ (zs ++ []))
実際 String の ++ を頻繁に使う class Show あたりでは、
できるだけ type ShowS = String -> String を使うことになってる。
shows :: Show a => a -> ShowS を使ってさっきの
foldl (.) id (map shows [1..10000]) []
をやってみると、今度は問題無く速い。
0660デフォルトの名無しさん
2008/08/29(金) 17:31:29m >>= f (P の >>=)は、m の最後の return a を f a に置き換える。
それを効率よくやるには、最初っから return なんか使わないで、
Get (\c1 -> Get (\c2 -> return [c1,c2])) を
\k -> Get (\c1 -> Get (\c2 -> k [c1,c2])) みたいにしとけばいいじゃんという発想。
つまり P a を forall b. (a -> P b) -> P b に、
m を m >>= に、>>= を \m f k -> m (\a -> f a k) にする。
以下略。
0661デフォルトの名無しさん
2008/08/29(金) 17:32:22foldr c n xs は、xs の : を c に、[] を n に置き換える。
それを効率よくやるには、最初っから : や [] なんか使わないで、
1:2:3:[] を \c n -> 1 `c` 2 `c` 3 `c` n みたいにしとけばいいじゃんという発想。
つまり [a] を forall b. (a -> b -> b) -> b -> b にする。
リストに戻すときは build xs = xs (:) [] を使う。
すると foldr c n (build xs) ==> xs c n と変換できる。
map f xs <==> build (\c n -> foldr (c . f) n xs)
例えばこういう変換を定義すれば、
(map f . map g) xs = map f (map g xs)
==> build (\c n -> foldr (c . f) n (build (\c n -> foldr (c . g) n xs)))
==> build (\c n -> (\c n -> foldr (c . g) n xs) (c . f) n)
==> build (\c n -> foldr (c . f . g) n xs)
==> map (f . g) xs
のように map f . map g ==> map (f . g) という変換ができる。
map f . map g 以外にも、他のいろいろなリスト関数の
foldr/build を使った形への変換を定義しておけば、いろいろな変換ができる。
foldr/build による融合変換ってやつ。今の GHC もこれを使ってる。
詳しくは GHC User's Guide の 8.13. Rewrite rules あたりを見てくれ。
0662デフォルトの名無しさん
2008/08/29(金) 18:19:15とても分かりやすい解説どうもありがとうございます！
ちょっと解決の糸口がつかめた感じがします、これからじっくり考えてみたいと思います。
とてもご丁寧にありがとうございました。
流石だ。。。
0663デフォルトの名無しさん
2008/08/30(土) 18:34:320664デフォルトの名無しさん
2008/08/30(土) 18:44:45ごく自然発生的なものだと思うが？
0665デフォルトの名無しさん
2008/08/31(日) 00:07:29手続き型言語 = how（どうやるか）を記述
クロージャをいかに早めに潰すかに苦心するHaskellは後者ですな
0666デフォルトの名無しさん
2008/08/31(日) 00:38:36宣言型言語＝述語論理を記述
と思ったらHaskellも述語論理の仕様記述言語に非常に近い特徴を持っていることに気づく。
0667デフォルトの名無しさん
2008/08/31(日) 03:38:00> クロージャをいかに早めに潰すかに苦心
ってどういうこと？
0668デフォルトの名無しさん
2008/08/31(日) 09:45:13関数のインライン展開のようなものじゃないか
よく分からんが
関数リテラルなら展開しやすいが高階関数の戻り値のクロージャは展開しにくい気がする
だからどう書くか (how) を工夫する
人間が問題を「宣言」するだけでコンパイラが問題を解いてくれる
というのは
素朴な解決策は簡単に見つかるのだが最適化が難しい (が機械的にできる) 問題に限定されるはず
0669デフォルトの名無しさん
2008/08/31(日) 15:47:120670デフォルトの名無しさん
2008/08/31(日) 15:59:09最適化は手続き型でもやってるから、非手続き型の人はwhatの部分を強調してみたりC/C++より速くなると言ってみたり。
LLの人は最適化にあまり拘らないし、テストさえ通ればhowを直接書いてもいいやって感じだけど。
0671デフォルトの名無しさん
2008/08/31(日) 17:18:22>>600前後の流れ参照
要するに未評価の式(これはクロージャで実装されてる)を溜め込まないように注意する必要がある
0672デフォルトの名無しさん
2008/08/31(日) 20:51:420673デフォルトの名無しさん
2008/08/31(日) 21:42:38人間の性格はA型B型O型AB型の4種類に分けることができる
とか思ってそうだよな。
0674デフォルトの名無しさん
2008/08/31(日) 23:36:24血液型と性格をろくな検証なしに簡単に結びつけてしまう短絡さ
どっちをさしてるのか紛らわしいので例としては不適
0675デフォルトの名無しさん
2008/09/01(月) 01:06:10おもしろおかしい
0676デフォルトの名無しさん
2008/09/01(月) 07:57:32書き終わったって。
0677デフォルトの名無しさん
2008/09/01(月) 15:40:490678デフォルトの名無しさん
2008/09/02(火) 14:15:50試しにZあたりの実行系でもつくってみればw
0679デフォルトの名無しさん
2008/09/02(火) 17:56:25何が言いたいのははっきり言え。
小馬鹿にするだけでは情報価値ゼロだぞ。
0680デフォルトの名無しさん
2008/09/03(水) 08:50:51せめてホーン論理に限定するとかじゃないと話にならんだろ。
0681デフォルトの名無しさん
2008/09/03(水) 23:53:100682デフォルトの名無しさん
2008/09/04(木) 00:04:13おお！でも英語疲れる。訳書出版の予定はないの？
0683デフォルトの名無しさん
2008/09/04(木) 01:25:52死滅しそうなのはHaskellだが、新しいHaskellのライブラリはほとんどArrowベースだよ。
0684デフォルトの名無しさん
2008/09/04(木) 11:41:240685デフォルトの名無しさん
2008/09/04(木) 12:00:02ってレス多いよな。
0686デフォルトの名無しさん
2008/09/04(木) 15:00:58東大 誰も吸っていない
京大 誰も吸っていない
同志社大 ちらほら
関西大 校舎内で吸っているやつがいる（！！！）
ありえないです、低ランク大・・・
やっぱりランクの低い大学出身のやつは信用できない・・・
0687デフォルトの名無しさん
2008/09/04(木) 15:19:000688デフォルトの名無しさん
2008/09/04(木) 15:20:04素人なのでどの変がうそなのか教えてください
0689デフォルトの名無しさん
2008/09/04(木) 15:45:52何しに来てるのかね？
0690デフォルトの名無しさん
2008/09/04(木) 15:50:35Haskellがどういうものだと思っているんですか？
0691デフォルトの名無しさん
2008/09/04(木) 17:36:250692デフォルトの名無しさん
2008/09/04(木) 19:33:03全角数字を見るといらっとくる人が使う言語
0693デフォルトの名無しさん
2008/09/04(木) 19:35:160694デフォルトの名無しさん
2008/09/04(木) 21:21:38それはカルシウム不足
0695デフォルトの名無しさん
2008/09/06(土) 23:15:53出来るだけ変数使わない方がいいとか、何が何でもポイントフリーにするとか、
あるいはそれ以外でも、何でも。
0696デフォルトの名無しさん
2008/09/06(土) 23:55:28y f = f (y f)
0697デフォルトの名無しさん
2008/09/07(日) 00:05:33haskellでは数学的にきれいなコードが「きれいなコード」と呼ばれます。
0698デフォルトの名無しさん
2008/09/07(日) 00:12:32意味のあるところでControl.*を使う
悪いコード:
ポイントフリーのためにControl.ApplicativeやControl.Arrowをimport
0699デフォルトの名無しさん
2008/09/07(日) 00:15:18>>687
ライブラリはそうだろうけど、普通のアプリを書くときは？
0700デフォルトの名無しさん
2008/09/07(日) 00:33:20複雑な場合には無理をしても分かりにくくなるだけだから悪い。
パターンマッチとは使いどころが違う。
0701デフォルトの名無しさん
2008/09/07(日) 00:34:19圧倒的に短く書けるからだよ。
それにポイントフリーだと関数の入出力の流れみたいなのがまっすぐ表せるから、処理の全貌が見通しやすい
0702デフォルトの名無しさん
2008/09/07(日) 00:41:52というわけで>>>使うのはやっぱダメ?逆なのに脳味噌合わせるべきなの?
0703デフォルトの名無しさん
2008/09/07(日) 00:46:480704デフォルトの名無しさん
2008/09/07(日) 00:59:26逆なの？ y = f x より x f = y が脳味噌に合ってるの？
0705デフォルトの名無しさん
2008/09/07(日) 01:11:04なんでやねん。
unlines . take 10 . filter (> 10) . map read . lines
より、
lines >>> map read >>> filter (> 10) >>> take 10 >>> unlines
の方が、少なくとも俺は脳に優しく感じる。
で、こう書くと、map read と filter (> 10) を分けてるのが冗長でダサい気もするが、
(filter (> 10).read)みたいにした方が良いのか、かえってこっちの方がダサいのか、
あるいは、(filter (\x -> 10 > read x)) みたいにラムダにすべきなのか、綺麗の勘所が判らんのです。
0706デフォルトの名無しさん
2008/09/07(日) 01:12:53あ、前半がStringに戻してないのはご愛敬と言う事で、よろしく。
0707デフォルトの名無しさん
2008/09/07(日) 01:32:55String に戻さないといけないなら
filter ((10 <) . read) だろう。ラムダでもいいけど。
まあ、その辺はこだわるとこでもないかと。
> なんでやねん。
f (g x) と (f . g) x の向きは関係あるんですよ。
数学でも向き的事情から x^f という記法を使うこともある。
0708デフォルトの名無しさん
2008/09/07(日) 02:23:43左から右だろうが右から左だろうがどっちでも一緒だろ。
俺には違いが分からん。
0709デフォルトの名無しさん
2008/09/07(日) 02:27:05こういう反抗したい年頃のやつが言語を汚くしていくんだろうな。
なんでもないものを指差して「使いにくい」などと言ったり、まるでガキ。
0710デフォルトの名無しさん
2008/09/07(日) 03:31:39その方が自然に感じるのは当然と思います。
また、bind演算子が(>>=)で左結合である事を考えても
Haskellを設計した人もその方が自然と感じたのではないでしょうか？
慣れの問題かもしれませんが、
そんなにおかしな意見とは思えません。
0711デフォルトの名無しさん
2008/09/07(日) 07:34:520712デフォルトの名無しさん
2008/09/07(日) 21:48:37所詮バイクシェッド
乱用すれば読みにくいし、パズルみたいにポイントフリーするのは間違ってる
数学的に綺麗綺麗とか、圏論的に自然とかというけれど、誰でも圏論がわかるわけじゃないし。
しかし、いかにポイントフリーで書くか、という事を考えると確かにおもろいよ
0713デフォルトの名無しさん
2008/09/07(日) 21:56:43>>36
>FPGAとかのHDL記述とかに応用したりしてる人いないの？
Lavaがあるよ。並列性とか関係ないし、回路をそのまま関数で書くだけなんだけど。そしてVerilogより使いやすい、なんてこたーない。HDLよりましだが、副作用を書くのがまわりくどい
http://www.cs.chalmers.se/Cs/Grundutb/Kurser/svh/tools.html
0714デフォルトの名無しさん
2008/09/07(日) 22:31:520715デフォルトの名無しさん
2008/09/08(月) 21:55:12ArrowっぽいHDL作りたいな
0716デフォルトの名無しさん
2008/09/09(火) 18:48:21November 15, 2008
待ち遠しい。
0717デフォルトの名無しさん
2008/09/12(金) 22:50:22コスト削減の鍵は純粋関数型言語らしい
http://www.watch.impress.co.jp/game/docs/20080911/epic.htm
071836 ◆K0BqlCB3.k
2008/09/12(金) 22:54:50そうだろうね。
俺はずううっと前からそう論文に書いてたけど。
だんだんpi-calculusの人気が出てきたね。
0719デフォルトの名無しさん
2008/09/12(金) 23:58:55>将来的にゲームプログラミングはそういった処理系に移行していくべきだとした。
>Sweeney氏はそのひな形として言語“Haskel”を挙げているが、
>ゲーム開発のメインストリームたり得る言語はまだ登場しておらず、将来に期待しているという。
なんでHaskellは駄目なんだろう。
ライブラリ含めた開発環境の問題か処理系の最適化の問題か
それとも言語仕様レベルで本質的に向いていないのか。
0720デフォルトの名無しさん
2008/09/13(土) 00:06:190721デフォルトの名無しさん
2008/09/13(土) 00:09:070722デフォルトの名無しさん
2008/09/13(土) 00:48:51遅延評価って言ってみれば、後ろからの逐次でそ？
無限リスト使えないHaskellってHaskell？
0723デフォルトの名無しさん
2008/09/13(土) 07:07:420724デフォルトの名無しさん
2008/09/13(土) 08:23:12前方参照，where構文
0725デフォルトの名無しさん
2008/09/13(土) 09:32:44LETで何が不足よ？
0726デフォルトの名無しさん
2008/09/13(土) 10:42:160727デフォルトの名無しさん
2008/09/15(月) 18:14:08たとえばJavaなどではクラスのインスタンスをオブジェクトと呼びますが、
Haskellの代数的データ型に格納されたデータのことをなんと呼べば良いですか？
0728デフォルトの名無しさん
2008/09/15(月) 18:21:45関数
0729デフォルトの名無しさん
2008/09/15(月) 19:00:09「オブジェクト」に対応する用語は普通は「値」でいいんじゃないか
>Haskellの代数的データ型に格納されたデータ
これどういう意味？
型が代数的データ型であるような値のことならそのまま「代数的データ型の値」
代数的データ型の構築子に渡した値のことなら「フィールドの値」くらいか？
data Point = Pt Int Int
x = Pt 0 3
-- xはPoint型の値
-- xのフィールドの値は0と3
0730デフォルトの名無しさん
2008/09/15(月) 20:26:27ストリーム指向？
0731デフォルトの名無しさん
2008/09/15(月) 20:30:200732デフォルトの名無しさん
2008/09/16(火) 23:55:400734デフォルトの名無しさん
2008/09/17(水) 00:07:44HSHみたいなやつ
探してみた奴だとどれも開発止まってて…
0735デフォルトの名無しさん
2008/09/17(水) 00:09:070736デフォルトの名無しさん
2008/09/17(水) 00:15:110737デフォルトの名無しさん
2008/09/17(水) 00:22:13自然言語じゃないけど
0738デフォルトの名無しさん
2008/09/17(水) 15:52:290739デフォルトの名無しさん
2008/09/17(水) 17:56:300740デフォルトの名無しさん
2008/09/17(水) 18:20:560741デフォルトの名無しさん
2008/09/17(水) 18:31:27使ったこと無いなぁ。
0742デフォルトの名無しさん
2008/09/19(金) 17:29:49並行指向プログラミングというのかな？
このパラダイムはオブジェクト指向よりも現実志向のパラダイムのように思う。
Haskellでも並列化がうまくいけばerlangみたいな仕組みを実装できるかもしれない。
# erlangの構文は糞 糞 糞 糞杉
0743デフォルトの名無しさん
2008/09/19(金) 18:18:310744デフォルトの名無しさん
2008/09/19(金) 20:28:250745デフォルトの名無しさん
2008/09/19(金) 20:34:400746デフォルトの名無しさん
2008/09/20(土) 11:00:42私はProlog屋なので、erlangの構文のクソ部分に敏感でない。
お手数かけて恐縮だが、糞の部分を列挙していただけると有難いのだが。
0748デフォルトの名無しさん
2008/09/20(土) 13:08:030749デフォルトの名無しさん
2008/09/20(土) 13:29:190750デフォルトの名無しさん
2008/09/20(土) 13:56:48743ではないけど、
receive...endとか、カリー化できないとかではないですか?
0751デフォルトの名無しさん
2008/09/20(土) 14:52:33元記事ではSTMが挙げられてるけど、OCamlだと無くね？
>>749
綺麗って何が？Gtk2Hsを使ったコード？
それならあまり綺麗じゃないんじゃない。
GUIを綺麗に書くためのハイレベルなライブラリは
いろいろあるけど、どれも決定打にはなってないような。
0752デフォルトの名無しさん
2008/09/20(土) 15:23:340753デフォルトの名無しさん
2008/09/20(土) 15:27:39>>748な俺からでもそれはわかる。
0754デフォルトの名無しさん
2008/09/21(日) 00:46:57gtk_rc_parse_string相当の関数や、
gtk_widget_modify_cursor（これは新しいからか）相当の関数が見付からなくて諦めたことがあります。。
いや私の検索能力が低いだけだと思うんですが、かなり頑張ってもどうしても見つかりませんでした。。。
皆さんgtkやpango、gdkの関数を捜すときってやっぱり根性ですか？
大抵はキャメルケースにすれば大丈夫ですがそうでない時はかなり困りますよねー。。
■ このスレッドは過去ログ倉庫に格納されています