関数型プログラミング言語Haskell Part19
■ このスレッドは過去ログ倉庫に格納されています
0001デフォルトの名無しさん
2012/06/27(水) 10:21:10.18ttp://www.haskell.org/
日本語サイト
ttp://www.sampou.org/cgi-bin/haskell.cgi
ttp://www.shido.info/hs/
過去ログ
関数型プログラミング言語Haskell
Part1 ttp://pc.2ch.net/tech/kako/996/996131288.html
Part2 ttp://pc2.2ch.net/test/read.cgi/tech/1013846140/
Part3 ttp://pc8.2ch.net/test/read.cgi/tech/1076418993/
Part4 ttp://pc8.2ch.net/test/read.cgi/tech/1140717775/
Part5 ttp://pc8.2ch.net/test/read.cgi/tech/1149263630/
Part6 ttp://pc11.2ch.net/test/read.cgi/tech/1162902266/
Part7 ttp://pc11.2ch.net/test/read.cgi/tech/1174211797/
Part8 ttp://pc11.2ch.net/test/read.cgi/tech/1193743693/
Part9 ttp://pc11.2ch.net/test/read.cgi/tech/1211010089/
Part10 ttp://pc12.2ch.net/test/read.cgi/tech/1231861873/
Part11 ttp://pc12.2ch.net/test/read.cgi/tech/1252382593/
Part12 ttp://hibari.2ch.net/test/read.cgi/tech/1272536128/
Part13 ttp://hibari.2ch.net/test/read.cgi/tech/1286706874/
Part14 ttp://hibari.2ch.net/test/read.cgi/tech/1299385928/
Part15 ttp://hibari.2ch.net/test/read.cgi/tech/1310199414/
Part16 ttp://toro.2ch.net/test/read.cgi/tech/1317958045/
Part17 ttp://toro.2ch.net/test/read.cgi/tech/1325510368/
Part18 ttp://toro.2ch.net/test/read.cgi/tech/1331902463/
0655デフォルトの名無しさん
2012/09/05(水) 22:48:08.880656デフォルトの名無しさん
2012/09/05(水) 22:51:14.87この型の評価順序がわかりません
0657デフォルトの名無しさん
2012/09/05(水) 23:17:24.700658デフォルトの名無しさん
2012/09/05(水) 23:36:45.54もうだめだー！
0659デフォルトの名無しさん
2012/09/05(水) 23:47:51.560660デフォルトの名無しさん
2012/09/06(木) 07:06:57.80そもそも、型に評価順序なんてありません。
評価順は関数の定義によります。
（だから >>657 は完全に嫌みでしょうね）
その型の関数を使って例えば print (f a b) を評価した場合に、
関数の定義によっては a b の順に評価されるかも知れないし、
b a の順に評価されるかも知れないし、a は評価されないかも知れない。
様々なことが考えられます。
0661デフォルトの名無しさん
2012/09/06(木) 09:37:20.600662デフォルトの名無しさん
2012/09/06(木) 10:57:28.34If p fails and consumes some input, so does lookAhead.
この so does は fails のみに掛かってるのですか？
それとも fails と consumes の両方に掛かってるのですか？
0663デフォルトの名無しさん
2012/09/06(木) 11:28:55.19プログラムの動作で判断して
0664デフォルトの名無しさん
2012/09/06(木) 11:59:32.63結局コードを読むか自分で書くかしないと分からない英文ってのもあるから
0665デフォルトの名無しさん
2012/09/06(木) 12:19:02.340666デフォルトの名無しさん
2012/09/06(木) 12:37:50.090667デフォルトの名無しさん
2012/09/06(木) 14:10:26.760668デフォルトの名無しさん
2012/09/06(木) 15:28:46.82イグザグトリィッ！
0669デフォルトの名無しさん
2012/09/06(木) 22:14:03.2048時間でSchemeを書こう
ttp://ja.wikibooks.org/wiki/48%E6%99%82%E9%96%93%E3%81%A7Scheme%E3%82%92%E6%9B%B8%E3%81%93%E3%81%86
0670デフォルトの名無しさん
2012/09/06(木) 22:23:53.090671デフォルトの名無しさん
2012/09/06(木) 23:03:30.83IORefを使ったら処理が悉くIOアクションになってしまってなんか悲しい
せっかくだから、一般化set!とか、call/ccとか、その他諸々をきっちり実装したいな
0672デフォルトの名無しさん
2012/09/06(木) 23:24:27.880673デフォルトの名無しさん
2012/09/07(金) 00:06:31.49「モナドとは簡単な概念に難しい名前がついているだけです。」
www
0674デフォルトの名無しさん
2012/09/07(金) 00:09:02.920675デフォルトの名無しさん
2012/09/07(金) 02:23:07.740676デフォルトの名無しさん
2012/09/07(金) 02:30:32.23schemeって文法セットがすごく小さいんじゃなかったっけ。wikiとかに載ってるんじゃないかな
0677デフォルトの名無しさん
2012/09/07(金) 02:53:08.03フルセットのSchemeは楽と呼べるほど簡単でもないと思う
0678デフォルトの名無しさん
2012/09/07(金) 07:43:15.880679デフォルトの名無しさん
2012/09/07(金) 07:47:51.370680デフォルトの名無しさん
2012/09/07(金) 14:12:59.23自分のモジュール名で修飾すればいいですが冗長な気がします
This.みたいな修飾ができないものでしょうか
0681デフォルトの名無しさん
2012/09/07(金) 15:29:16.000682デフォルトの名無しさん
2012/09/07(金) 18:53:43.090683デフォルトの名無しさん
2012/09/07(金) 19:08:55.030684デフォルトの名無しさん
2012/09/07(金) 19:32:57.950685デフォルトの名無しさん
2012/09/07(金) 19:56:21.800686デフォルトの名無しさん
2012/09/08(土) 02:24:00.86インポートするときに自分で省略形を决める
なんだかんだ言って省略しない方が良かったりするのは同意
0687デフォルトの名無しさん
2012/09/08(土) 02:28:22.390688デフォルトの名無しさん
2012/09/08(土) 03:15:43.870689デフォルトの名無しさん
2012/09/08(土) 04:02:35.60自分のモジュールインポートするときに名前指定できなかったっけ？
SOURCE と boot で
0690デフォルトの名無しさん
2012/09/08(土) 12:34:51.91import {-# SOURCE #-} Test As T
0691デフォルトの名無しさん
2012/09/08(土) 14:59:56.680692デフォルトの名無しさん
2012/09/08(土) 15:26:05.94おおこれは面白そうだ
でもS式パーサ位ジェネレータ使わずに書きたい
0693デフォルトの名無しさん
2012/09/08(土) 16:07:29.54内容はいいんだけど、次のページに進むリンク設けて欲しい。作り忘れかな
0694デフォルトの名無しさん
2012/09/08(土) 17:06:48.030695デフォルトの名無しさん
2012/09/08(土) 18:05:20.060696デフォルトの名無しさん
2012/09/08(土) 18:44:15.82今のGHCではできません。
0697デフォルトの名無しさん
2012/09/08(土) 20:04:45.61え、おれ695じゃないけど、これマジ？
.hs ファイルが長くなってきてどうしようか悩んでたんだけど、、
0698デフォルトの名無しさん
2012/09/08(土) 20:13:01.030699デフォルトの名無しさん
2012/09/08(土) 20:18:27.50ファイルをインクルードできないのなら、モジュールをインポートすればよいのではなくって？
あと、Haskellの仕様ではないが、ghcからCプリプロセッサを呼べば、ファイルのインクルードもできると思う
0700デフォルトの名無しさん
2012/09/08(土) 23:08:50.890701デフォルトの名無しさん
2012/09/08(土) 23:09:58.880702デフォルトの名無しさん
2012/09/08(土) 23:42:29.66ちょっと想像できない。
Haskellでプログラムするの辛いの？
0703デフォルトの名無しさん
2012/09/09(日) 02:43:53.940704デフォルトの名無しさん
2012/09/09(日) 03:05:10.410705デフォルトの名無しさん
2012/09/09(日) 07:59:37.650706デフォルトの名無しさん
2012/09/09(日) 15:00:24.27Lambda-caseは便利そう
0707デフォルトの名無しさん
2012/09/10(月) 23:11:10.73f (a -> b)は、文脈中の関数
ここでの文脈の厳密な定義ってなんなの？
0708デフォルトの名無しさん
2012/09/10(月) 23:41:12.680709デフォルトの名無しさん
2012/09/11(火) 00:05:06.950710デフォルトの名無しさん
2012/09/11(火) 10:46:08.58main = getContents >>= (return . length . lines) >>= (putStrLn . show)
自分は、これは各行が短い場合はlengthがすぐlinesのリストの要素を捨ててくれるので何とかなるが、
数GBとかの長大な行の入力が合った場合、その分、つまり一行分のメモリを食ってしまうのではないかと思いました。
というのも、linesとlengthが別個にコンパイルされてオブジェクトコードになっているなら、
lengthがリストの要素を捨てられるのはlinesが一つの要素を確定してからになるのではないかと思ったからです。
しかし、そんなことはないようです。ghcはどんな仕組みでメモリ消費量を抑えているのでしょうか。
0711デフォルトの名無しさん
2012/09/11(火) 19:38:06.70> linesとlengthが別個にコンパイルされてオブジェクトコードになっているなら
ここで言うオブジェクトコードというのが、
gcc がリンクするためのオブジェクトコードという意味なら、それはないと思う。
ライブラリが個々にオブジェクトコードになってたら、インラインできん。
で、本題だが
lines 関数のソースを見ると、__GLASGOW_HASKELL__ の場合、
String型のリストを作るのに遅延パターンを使っている。
これがメモリ消費量が抑えられている肝になるのではないかと思う。
試しに、遅延パターンを使わない方の lines 関数を自作してやってみてくれないか。
これでメモリ消費が明らかに増えれば、遅延パターンの恩恵だと言えそうだ。
ハズレかも知れんがな。
0712711
2012/09/11(火) 19:58:31.220713711
2012/09/11(火) 20:29:00.92length 関数は引数が [] にマッチするか (_:xs) にマッチするかだけを見ている。
その引数である lines 関数は、その内部で
文字列を \n の前と後で分けるために break 関数を使っている。
その break 関数の型は、次の定義になっている。
break :: (a -> Bool) -> [a] -> ([a],[a])
break _ xs@[] = (xs, xs)
break p xs@(x:xs')
| p x = ([],xs)
| otherwise = let (ys,zs) = break p xs' in (x:ys,zs)
ここで、break 関数の戻り値てであるタプルの第１要素の「内容」が必要であれば、
in (x:ys,zs) の部分の x:ys によって、メモリがどんどん使われる。
しかし、今回は内容は一切使われていない。
と言うのも、lines 関数の中では break 関数の戻り値であるタプル (x:y) を
x:y というリストに変換して返している。
このリストは length 関数の引数に渡されるが、
リストという形になっているかどうかしか見ていないため、
break 関数の x:ys が使われていない。
よって、文字列の全てをスキャンすることはするが、
スキャンした結果の文字列はメモリに保存されてはいないため、
結果してメモリ消費量が抑えられたと思われる。
文字で説明するのは難しいな。
length、lines、break それぞれの関数をよく見れば、分かると思う。
0715デフォルトの名無しさん
2012/09/11(火) 20:31:58.14こうかな？
0716711
2012/09/11(火) 20:35:16.89あわわ ごめん
大きな間違いをもういとつ訂正。
> lines 関数の中では break 関数の戻り値であるタプル (x:y) を
> x:y というリストに変換して返している。
lines 関数の中では break 関数の戻り値であるタプル (x:y) を
x:(y の次の文字から再び lines) というリストに変換して返している。
あと、lines 関数のソースに __GLASGOW_HASKELL__ ではない定義もあるけど、
そちらでも同じ事。
・・・スレを汚してしまった
逝ってくる
0717デフォルトの名無しさん
2012/09/11(火) 20:55:33.69似たような話が ふつうのH に載ってた気がする
0718デフォルトの名無しさん
2012/09/12(水) 00:07:43.22ここの内容の邦訳ってないのですか？
0719デフォルトの名無しさん
2012/09/12(水) 00:30:09.97目が悪いのか、それとも頭が悪いのか。両方か。
0720デフォルトの名無しさん
2012/09/12(水) 00:46:18.770721デフォルトの名無しさん
2012/09/12(水) 00:50:12.89ttp://ja.wikibooks.org/wiki/Haskell/%E5%9C%8F%E8%AB%96
0722デフォルトの名無しさん
2012/09/12(水) 00:52:10.29そりゃ独創性なんか生まれるわけないわな。ちっさ。
0723デフォルトの名無しさん
2012/09/12(水) 01:04:26.160724デフォルトの名無しさん
2012/09/12(水) 02:16:36.140725デフォルトの名無しさん
2012/09/12(水) 02:29:14.650726デフォルトの名無しさん
2012/09/12(水) 02:58:23.550727デフォルトの名無しさん
2012/09/12(水) 07:08:44.61>>722 のように思って何もしない奴とでは、今後の成長に差が出そう
0728デフォルトの名無しさん
2012/09/12(水) 07:51:38.120729デフォルトの名無しさん
2012/09/12(水) 07:53:24.62何と戦ってるのか知らんが。
0730デフォルトの名無しさん
2012/09/12(水) 08:04:52.79本当に多いのかな？
どうやって多いことを示したのだろうか？
0731デフォルトの名無しさん
2012/09/12(水) 08:07:03.970732デフォルトの名無しさん
2012/09/12(水) 08:26:09.55なぜプログラム板にいるのかってことだ
0733デフォルトの名無しさん
2012/09/12(水) 08:31:54.50どうして一方を立てれば他方が立たないと思ったのでしょうか？
0734デフォルトの名無しさん
2012/09/12(水) 08:53:36.560735デフォルトの名無しさん
2012/09/12(水) 09:29:01.800736710
2012/09/12(水) 10:13:45.76ありがとうございます。ちょっと自分ではまだ解明を進められていません。すいません。
確かに遅延評価を行っているなら最終的に各々の値が必要なのか分かっている状態になってから計算を始めるので、
ある値を計算する段階で必要ではない値は計算しない事で
(x:ys)のような不必要な値を残さない事が可能である事は理解できます。
ただ、それを実際どのように実現しているのか不思議に思いました。
というのも、haskellはコンパイラ言語であるので最終的に機械語の状態で解釈され計算を行うはずです。
ここでもしlengthやlinesが完全に機械語に変換されているならばlengthがlinesに実はその値は要らないんだ、
という事を知らせる事は不可能ではないかと思ったのからです。
今はいくつかの可能性を考えています。
一つはガーベージコレクタなどのメモリ管理モジュールに全てを任せてしまう方法です。
この場合(x:ys)は一応計算されメモリにストアされるものの、lengthが参照していないので、
GCが動作した時に全て破棄されてしまうという可能性です。
もう一つは一つのhaskell関数を幾つもの小さい関数としてオブジェクトファイル(.oファイル)に格納する方法です。
これにより、ある関数内部の必要な計算と不必要な計算を、小関数単位で呼び出す事で呼出側が制御する事が可能になり、
最終的にリンカのみで不必要な計算を排除出来る可能性があります。
まだよく分かって無いので、もうすこし調べてみようと思います。ありがとうございます。
0737デフォルトの名無しさん
2012/09/12(水) 12:42:32.480738デフォルトの名無しさん
2012/09/12(水) 12:50:31.15> 確かに遅延評価を行っているなら最終的に各々の値が必要なのか分かっている状態になってから計算を始めるので、
違うよ。
遅延評価だけど、最終的に各々の値が必要なのかは、その時になってみないと分からないよ。
値が評価されたら、評価された値はメモリに残る。
しばらくメモリに残って、ガベージコレクタが動いたときにもう必要ないなら、
その時点でメモリから消される。
今回の (x:ys) は「評価されなかった」からメモリに残らなかった。
と考えてほぼ間違いない。
Haskell コードは GHC によってどのような C ソースにコンパイルされるかと言うと、
lengthやlinesなどがそのまま完全に機械語に変換されている訳ではない。
いわば中間コードのような形でプログラムがデータ化されている。
まず、その中間コードを「弱頭部正規形」という形に簡約する。
そうすると中間コードの頭の部分だけ明確になって評価可能状態になるから評価する。
で、その頭の部分を評価してるときに、中間コードの残りの部分が必要になる。
必要になったら、また残りの部分を「弱頭部正規形」に簡約し、頭を評価する。
当然、if や case of などので分岐するから、中間コードと言っても、
一列に数珠繋ぎのようになっているわけではない。
またグラフで管理してて、一度簡約した関数は再び簡約処理することは無いし、
本当はもう少し効率よくやってるが、イメージとしてはこんな感じ。
必要なら弱頭部正規形 --> 評価 --> 必要なら弱頭部正規形 --> 評価 --> ・・・
これを繰り返てプログラムを実行することで、遅延評価を実現している。
0739デフォルトの名無しさん
2012/09/12(水) 13:47:36.22パフォーマンス的にどうなんでしょう
0740デフォルトの名無しさん
2012/09/12(水) 14:43:21.89まるまるインタープリタとも違うんだ。
中間コードのようなものとイメージして簡約処理を説明できるけど、
BASICとかC#のような中間コードではない。
あとグラフ簡約がパフォーマンスの要の一つになってる。
0741デフォルトの名無しさん
2012/09/12(水) 15:00:53.46ここのPDFを読むと良い
Implementing Functional Languages
http://research.microsoft.com/en-us/um/people/simonpj/papers/pj-lester-book/
0742710
2012/09/12(水) 18:26:23.26ありがとうございます。
(x:ys)はサンクが作られたが、
lengthが中身を見なかった、つまり評価されなかったので
メモリ消費量が増えなかったと言うことですね
遅延評価の実現方法は興味深いです
>>741の資料を読んでみます
ありがとうございました
0743デフォルトの名無しさん
2012/09/12(水) 19:12:38.150744デフォルトの名無しさん
2012/09/12(水) 19:25:43.73「訳す根性がありません」なら使ってもいいッ！
0745デフォルトの名無しさん
2012/09/12(水) 19:46:43.16ネットで訳すだけでよんだ気持ちになってるのか…
そりゃ、釈迦の言葉がただの呪文になっちゃうのもうなずける
0746デフォルトの名無しさん
2012/09/12(水) 19:48:33.78そんなこと言われても、申し訳ないが私の力ではもうどうすることもできん。
現時点で、実装方法に関してまとまった資料としては
>>741 が一番具体的でわかりやすいと思う。
他の資料は断片的なことしか書かれてなく、それもかなり抽象的だ。
まして、実装に関わる（まともに使える）日本語の資料なんてのは、
私が探した限りでは無かったよ。
あとは、これ以上探るのは諦めるか、日本語資料が出るのを待つか、
納得できなければ資料をなんとか読める程度まで英語力を上げるしかない。
ただ、>>710 の疑問を解消するのに実装方法を知る必要は無いよ。
遅延評価がまともに機能する実装なら、どんなものでも同じ結果だ。
0747デフォルトの名無しさん
2012/09/12(水) 19:51:56.330748デフォルトの名無しさん
2012/09/12(水) 19:55:40.93すまん、何言ってんだか分からん
0749デフォルトの名無しさん
2012/09/12(水) 20:01:41.12それで >>710 の疑問が解消されそうなら、何ページのどこどこにあるとか言って、
もう少し詳しく勧めてやってくれ。
そうすれば立ち読みしたり図書館で読んだりできると思う。
面倒でになければ、その部分だけ要約して解説してあげると喜ぶだろう。
私は生憎とその本を持っていないので薦めることも解説もできん。
0750デフォルトの名無しさん
2012/09/12(水) 20:39:54.75.NETではHaskellの実装が非効率過ぎて無理だったという話を聞いたことがあるんだけれど、何かご存じないですか？
0751デフォルトの名無しさん
2012/09/12(水) 21:29:59.89しらん
が、予想してみると・・・
Haskell コードをバカ正直に中間コードに変換し、
それを .NET 上で動く「Haskell ランタイム」上で解釈するような事をしてたら、
そりゃ実際に動かしてみるまでもなく非効率すぎるだろうと誰もが分かってる。
（ランタイム on ランタイムなんて馬鹿げてる）
従って、そうではなく、GHC が Haskell コードを、
簡約すべき関数情報と簡約する手続きを直接実行する形の C 言語に変換してるように、
Haskell コードを同じような形の C# や MSIL のコードに変換したんじゃないかな。
でも、http://twtrland.com/profile/kazu_yamamoto の
「飲み屋で二人の Simon に・・・」の件にあるように、
CLR はグラフ簡約マシンを作るには機能が足りないそうだ（古い情報だけどね）。
グラフ簡約を実現する部分はクラスを駆使しなければならなかったんだと思う。
グラフ簡約で使うグラフはサンクもポイントするし、そのサンクは GC にも関わる。
よって、Haskell らしさを表現する大部分をクラスを使って実現することになる。
これはもう、ほとんどランタイム on ランタイム状態と言っていいと思う。
グラフ簡約マシンを作るに足らない機能とやらが具体的になんなのか知らんが、
たぶん効率的なポインタ操作関連ではないかと、私は予想する。
0752デフォルトの名無しさん
2012/09/13(木) 00:35:44.370753デフォルトの名無しさん
2012/09/13(木) 16:05:16.54:m+ Control.Applicative.Parameterized
とか。
0754デフォルトの名無しさん
2012/09/14(金) 02:55:34.75■ このスレッドは過去ログ倉庫に格納されています