関数型プログラミング言語Haskell
■ このスレッドは過去ログ倉庫に格納されています
0001潜伏していた1
NGNG前スレ
http://pc.2ch.net/test/read.cgi/tech/996131288/l50
関連 >>2 以降
0067Super Combinator
NGNG何がわからないのか、話してみれば?
0068デフォルトの名無しさん
NGNG別に変人じゃなくてナイスガイなんだけど。発表は楽しいし。
006966
NGNGコンビネータといえばCL式
どんなCL式でもIKSを組み合わせたものまで分解できるらしいけど
どうやって？
あとSの意味が判らない。どう使うんだろう？
I = \ x -> x
K = \ x y -> x
S = \ x y z -> x z ( y z )
でも相手にしないでください。
頭正規形(hnf)って何？といぐらいのレベルですから。
ラムダ理論も知らないんですから。
0070Super Combinator
NGNG> あとSの意味が判らない。どう使うんだろう？
> S = \ x y z -> x z ( y z )
Distributor.
Combinator式は、グラフとして素直に表すことができるから、
部分グラフは、元のプログラムを分割したものと考えられる。
部分プログラムxと部分プログラムyの両方に引数zを渡し適用するのが役割。
x側では引数zは必要なければ、
(K x' z) (y z)
てな感じになる。(x ≡ K x')
(x z)を(y z)に適用するのは、部分プログラム同士を結合する方法が、
「適用」以外にはないから。Combinator logicやlambda calculusでは。
RAM(Random Access Machine)ではメモリ参照で、データを扱うわけだけど、
Combinator logicやlambda calculusでは、どんどん受け渡していくことになる。
# lambda calculusのβ簡約をメモリ参照で直感的に理解している人も多いと思うが。
0071デフォルトの名無しさん
NGNGI=SKK
Raymond Smullyan の "To Mock A Mockingbird" という本が楽しめます。
翻訳も出ていたと思う。
0072デフォルトの名無しさん
NGNG『ものまね鳥をまねる』森北出版 isbn 4-627-01901-7
007369
NGNG「プログラミング意味論」 横内寛文著
「計算論 計算可能性とラムダ理論」 高橋正子著
と読み理解しようと奮闘中なのですが、計算機屋の私にはさっぱりです。
しかし理論はむずかしーな。
一度ものにしてしまうと効果絶大なんですけどね。
もうちょっと、がんばってみます。
>>71
>I=SKK
む。なるほど。
上の本で書かれていましたが、改めてみると こういう意味だったんですね。
Sの機能が、ちょっとわかった気がしました。
>>70
>Distributor.
>
>Combinator式は、グラフとして素直に表すことができるから、
>部分グラフは、元のプログラムを分割したものと考えられる。
>部分プログラムxと部分プログラムyの両方に引数zを渡し適用するのが役割。
中略
>(x z)を(y z)に適用するのは、部分プログラム同士を結合する方法が、
>「適用」以外にはないから。Combinator logicやlambda calculusでは。
なるほど。
Sで式同士を組み合わせる。
もしくはSで式を分解できるということなんでしょうか？
>>71
>『ものまね鳥をまねる』森北出版 isbn 4-627-01901-7
ttp://www.morikita.co.jp/bunya/kensaku-bunya.cgi?id=67
よさそうな本ですね。購入したいと思います。
0074Super Combinator
NGNG> 両方に引数zを渡し
だから'分配器(distributor)'です。
Sはドイツ語だったかの頭文字だったはず。
K=cancel
0075石敢當
NGNGただいま amortization の勉強中。
分かったような、分からんような・・・
ということは分かってないんだなぁ。
0076Super Combinator
NGNGamortizationは、時間のかかる処理を、複数の操作に対してひとまとめにして、
平均の計算量オーダーを下げる手法のこと。
木、ソートされたテーブル、pure functional arrayなどの
再構成、構造調節などで利用される事が多い。
0077デフォルトの名無しさん
NGNGどういう物なのか興味あるなー。
教えてSuper Combinatorさん。
0078石敢當
NGNG> 平均の計算量オーダーを下げる手法のこと。
そのような雰囲気は分かるのですが、「分かったぞ！」という実感が
まだ伴っていません。もう少し勉強します。
.NETというのも名前はよく目にするものの中身はさっぱり分からない
のですが、Hugs98 for .NET というものがリリースされたようです。
http://galois.com/~sof/hugs98.net/
0079デフォルトの名無しさん
NGNGamortized analysisの章がありますよ．
0080デフォルトの名無しさん
NGNG満杯になったら新しく大きい配列を用意して全部コピーして追加。
このとき、初期サイズ1で1ずつ大きくして行くとN要素追加するの
に合計コピー回数は1+2+3+…+NだからO(N*N)。定数Cずつ大きく
していくとしても、コピー回数がC分の1になるだけだからO(N*N)
は変わらない。ところが2倍ずつに大きくして行くことにすると、
1+2+4+…+NだからO(N)になるのね。しかし「1個追加するときの
最大計算量」はどの方法でも(その1個であふれた場合はどのみち
コピーするんで)変わらない。逆に言えば、最大計算量を考える
変わりにN個の操作全体の計算量を考えてその平均を取ると
1個追加する際の平均的な計算量はO(1)だよね、っていうのが
amortized analysis。
0081デフォルトの名無しさん
NGNGここに書いてあることかな？
英語が読めない。
0082デフォルトの名無しさん
NGNGだったら、そうだと思う。
でもこのスレの人でも、英語は壁になるんだ…。自動翻訳希望？
008381
NGNG他力本願全開。
0084石敢當
NGNG> 変わりにN個の操作全体の計算量を考えてその平均を取ると
> 1個追加する際の平均的な計算量はO(1)だよね、っていうのが
> amortized analysis。
これは良く分かります。ただ、これだけだと amortization などという
言葉を持ち出すまでもなく、単に「平均」ですよね。（違うのかな？）
もし単に平均コストのことを言っているだけだとすると、
banker's method だの physicist's method （>>79の本では
accounting method と potential method）だのの技法を使い、
多くのページを割いて解説するほどのことじゃないように
思うんです。
>>80の例の場合、配列の確保がサイズに関係なくO(1)で行えると
仮定すると、あふれたときに1度に全部コピーするのではなく、
新しい要素が追加されるたびに要素を2個ずつコピーすることに
すれば1個追加する際の「最大の」計算量がO(1)となります。
結局、amortizationの何が良く分からないのかということを
改めて考えてみますと、amortized analysisで得られた平均
計算量が、平均ではなくて最大の計算量となるような実装が
いつも得られるのだろうか、ということであるような気が
してきました。
まだ良く分かっていません。変なことを書いていたらごめんなさい。
0085デフォルトの名無しさん
NGNG> これは良く分かります。ただ、これだけだと amortization などという
> 言葉を持ち出すまでもなく、単に「平均」ですよね。
「最悪」の場合の1ステップあたりの「平均」ではないでしょうか。
0086デフォルトの名無しさん
NGNG↑
ない・・・
0087デフォルトの名無しさん
NGNG↑
ここも講義録だったような気がするんだけど、つながらない･･･
0088デフォルトの名無しさん
NGNGhttp://www.ipl.t.u-tokyo.ac.jp/~mizuhito/CS/
0089デフォルトの名無しさん
NGNG最初はやはり名前を入力させてXXXさんこんにちは、だと思い試したのですが
putStr "123" とか getLine とか単体では動くのに、次のように組み合わせるとエラーになります。
Prelude> putStr getLine
ERROR - Type error in application
*** Expression : putStr getLine
*** Term : getLine
*** Type : IO String
*** Does not match : [Char]
一行入力をそのままエコーすることを意図しているつもりなのですが、何故でしょうか？
0090デフォルトの名無しさん
NGNGgetLine の型は IO String だが putStr は String 型を貰うので
型エラーになります。(IO が付いているかいないかの違いだけど)
getLine >>= putStr とすれば意図してるように動きます。
「>>= って何?」などと思うのでしょうが、説明するのは大変なので
http://www.sampou.org/haskell/tutorial-j/ などを読んでください。
0091デフォルトの名無しさん
NGNGERROR "ファイル名":3 - Type error in function binding
*** Term : sel
*** Type : a -> IO a
*** Does not match : a -> a
*** Because : unification would give infinite type
というのが消えてくれません。
module Main (main) where
sel x = do putStr "(y/n) ? "; c <- getChar
return (
case c of
'y' -> sel (x + 1)
'n' -> x
_ -> sel x)
main = do putStr (show (sel 0))
selの型は Int -> IO Intのつもりなのですが、型を明示しても駄目です。
いじっていると、IO (IO Int)みたいな型がエラー報告で出るときもあります。
このコードはどうすれば通るのでしょうか？
それと、IOを重ねる意味は無いように思えるのですが、IO (IO Int) というのはどういう状態なのでしょうか？
質問ばかりで申し訳ありません。
0092デフォルトの名無しさん
NGNGcase c of
{'y' -> sel (x + 1)
;'n' -> x
;_ -> sel x}
この式の型は何でしょう?
009391
NGNGそれをreturnで返していますから、selの返値もIO Intで、
selの型は Int -> IO Int …
エラーになるということは、間違った理解なのでしょうけれど…
009491
NGNGとすれば、ただの Int を IO Int に揃える必要があるということですか？
0095デフォルトの名無しさん
NGNG> それをreturnで返していますから、selの返値もIO Intで、
return の型は Monad m => a -> m a です。
>>91 のケースだと m は IO。
> とすれば、ただの Int を IO Int に揃える必要があるということですか？
うん。で、そういう場合に return を使う。
sel x = do
putStr "(y/n) ? "
c <- getChar
case c of
'y' -> sel (x + 1)
'n' -> return x
_ -> sel x
009691
NGNGmodule Main (main) where
sel x = do putStr "(y/n) ? "; c <- getChar
case c of
'y' -> sel (x + 1)
'n' -> return x
_ -> sel x
main = sel 0 >>= putStr . show
(r <- case …にしてその後にputStr "/"とreturn rを続けて書いたら、'n'を打った時も表示されたので)
この場合returnはcaseから抜けているだけですよね？
doを使っている場合も、returnを書かなくても、最後の式が返値になるのですね。
0097デフォルトの名無しさん
NGNG009891
NGNG0099デフォルトの名無しさん
NGNG深い意味はないです。return は、返り値を
もって呼び出し元へ帰る命令ではなく、単に
a 型の値を m a 型の値に写像する関数だと
いってみただけです。
0100デフォルトの名無しさん
NGNG成程…Haskellのreturnはreturnしないのですね。
0101デフォルトの名無しさん
NGNG0102デフォルトの名無しさん
NGNG感じかも。関数型言語の発想が根本からわかってない。
IOモナドって一見して普通の手続き型にも見えますからねえ・・
関数型が全くわからない人は、HaskellのまえにMLを経由した方が良い
というのは正しいのかも。
0103デフォルトの名無しさん
NGNG0104デフォルトの名無しさん
NGNGHaskell（特にGHC）って例外処理とか、入出力じゃない副作用も
どんどんIOモナドに入ってるじゃん。
モナドの合成が理論的に難しいかららしいけど、そのうちに現実的な
プログラムだと何でも一つのモナドの中で書くことになって、ほとんど
MLみたくなったりはしないの？（手続き型言語とまではいわないけど、
「どこでも副作用」って感じで）
0105デフォルトの名無しさん
NGNGモナドは副作用じゃないのでOK OK。
逆に言うとMLの利点がなくなってくる。
0106デフォルトの名無しさん
NGNG0107デフォルトの名無しさん
NGNG0108デフォルトの名無しさん
NGNGなかはわるくないです。
MLとHaskelは
ちょっと雰囲気は違うような気はしますけどね。
でもまあそれは両方使ってみれば解ることで。
0109デフォルトの名無しさん
NGNGHaskell-MLというのが有るらしいですYO!
0110デフォルトの名無しさん
NGNGMLの不純さが嫌なのかも？
どうなの？＞ALL
0111デフォルトの名無しさん
NGNG0112デフォルトの名無しさん
NGNGML(Ocaml)は現実的にある程度の副作用を認めている代わりに
使っているとコンパクトな感じがします。
副作用も使えると言うだけで、副作用のある構文を使わずに書く事は
全然出来ますし、遅延評価もコードによって簡単に実現できます。
未だ出来あがっていないものの、ML2000の仕様書では言語自体に
遅延評価など新しい機能がかなり含まれています。
Haskellは純粋を歌ってはいますが、
結局の所モナドというものに問題を押しこんだだけのようにも思え
美しくないようにも思われます。
仕様もわりとごちゃごちゃしている気がします。
言語の性質上ML並みに速くなる事も難しいのではないかと思います。
0113デフォルトの名無しさん
NGNG0114104
NGNGWadlerとかPeyton Jonesとか面白い人が多いし。（そういう問題か？）
>>113
一応、MLでもHaskellと同様のmonadicなプログラミングスタイルは可能。
MLだと文法的に面倒で、Haskellを使ったほうが楽だから誰もやらないけど…
0115デフォルトの名無しさん
NGNG中途半端な感じが払拭できないということでいいのか？
0116デフォルトの名無しさん
NGNG0117デフォルトの名無しさん
NGNGHaskllを関数型を知らない人に触らせると、
モナドでC言語かよ！ということをやろうとする。
しかして正しく正面玄関から入ろうとすると、難解過ぎる。
MLの方がそういう意味でも適度に関数型な気がする。
純粋関数型を言うならば、遅延ストリームでゴリゴリ書くのが基本に
なってるような言語であるべきかなと思ってみたりする。
0118デフォルトの名無しさん
NGNG多目的言語なんだから。
0119Super Combinator
NGNG> Haskell（特にGHC）って例外処理とか、入出力じゃない副作用も
> どんどんIOモナドに入ってるじゃん。
最近Haskellの動向は探ってないんだけどこれ本当?
IOErrorがIOモナドmoduleにあって、
HaskellがIOError以外ろくに例外をsupportしないだけなんだと思ってたよ。
0120デフォルトの名無しさん
NGNG0121デフォルトの名無しさん
NGNGモナドを使うと、手続き型言語を
関数的に解釈することができますか？
0122デフォルトの名無しさん
NGNG「関数的に解釈」の意味がよくわからない。
Haskellでインタープリタが書けるか？
という意味じゃないよね。
0123デフォルトの名無しさん
NGNG0124デフォルトの名無しさん
NGNGモナドを使うと、どうみても副作用な操作でもfunctionalな
操作と解釈できるわけですが、それと同じように手続き型言
語のプログラムに純関数的な意味を与えることができますか？
という意味です。
0125デフォルトの名無しさん
NGNGIdealized Algolとかいうのがなかったっけ。
0126デフォルトの名無しさん
NGNG0127デフォルトの名無しさん
NGNGできません。
強引に無理矢理こじつけることならできるかもしれないけど意味無し。
0128デフォルトの名無しさん
NGNGモナドを使えば、代入、逐次的実行、手続き型ライクなI/O、例外などを
純関数型の枠組みで扱える。gotoくらいならもともとモナドに関係なく
等価な純関数型言語に変換することができる。
Cは無謀だがMINIMAL BASICくらいなら、純関数型とみなすことは可能だろ
う。
0129Super Combinator
NGNGDenotational semanticsじゃ駄目?
domainの性質がやっかいになるから、いいことないけど。
そもそも「簡単に」できるくらいなら、関数型言語の存在意義が…
0130デフォルトの名無しさん
NGNG手続き型の言語のインタープリタを Haskell で書いたら、
その言語の意味を与えたことになる？
ならない？
0131デフォルトの名無しさん
NGNGなるんじゃない？
きちんとやれば操作的意味論だろ。
0132デフォルトの名無しさん
NGNG実際に各項が何時評価されるか？どういう順番で評価されるか？
ということが予測しづらい(できない)からねー。
その点、正格言語や手続き型言語は評価の順序が一目瞭然だからねー。
Prologにカットオペレータがあるように、Haskellも競争書き込みで
評価の順序を、ある程度コントロールできる様にしたらよいのかな？
0133デフォルトの名無しさん
NGNG？？ 問題なのは結果であって、
順番なんてどうでも良いだろう。
順番じたいが望む結果に含まれる
(例えば入出力とかGUIとか)なら、
そこだけモナド使えば良いしさ。
0134デフォルトの名無しさん
NGNG133も書いていますがコンピュータの入出力は
ストリームを基本としているものが多いですよね。
しかし、ストリームにとって並び方も結果の内ではないでしょうか？
プログラムは外部と入出力して、なんぼのものだと私は思っています。
ゆえにストリームのようなモノに対して実行順序がコントロールできることは
プログラミング言語にとって重要であると思います。
そうじゃなきゃPrologもカットオペレータなんて付けなかった
と思います。
あと私のような消防には、実行される順序が予測できないと
デバッグしづらいです。(もしかして、こっちが本題か？)
0135デフォルトの名無しさん
NGNGほんとに消防だな。Haskellだって
ストリームの順番が狂うわけはないだろう。
ストリームは「いくらでも長くなりうる列」
というデータだ。関数型の基本はデータの値を
求めることなんだから、モナドなんか用いなくたって
ちゃんと求まる。
0136チュウボウ
NGNG副作用あり＝＞参照透過性がない＝＞数理論理的でない
数学って、まったく副作用のない構成になっているの？
0137デフォルトの名無しさん
NGNG副作用がなんなのかわかってる?
0138デフォルトの名無しさん
NGNG0139チュウボウ
NGNGオレの理解
状態という一種の記憶域のようなものがあってその値が
変わること。
数学ではオートマトンとか除けば、状態のような概念は
知らない。
0140デフォルトの名無しさん
NGNG評価順序に依存してるから
0141チュウボウ
NGNG0142デフォルトの名無しさん
NGNGそう思えるのはモノが単純な場合だけ
0143チュウボウ
NGNG主語＋述語が人間の頭にあってるような気がする。
（状態があるならば副作用があると思ってる）
ペトリネットなんかかじってみてると、そんな気がしてきた。
ttp://www.aichi-pu.ac.jp/ist/~qua/intropn/intropn.html
0144デフォルトの名無しさん
NGNG「なぜ関数プログラミングは重要か」に副作用が無い事のよさが力説されてた。
実感湧かなかったが。
0145デフォルトの名無しさん
NGNG日本語は主語なんかなくても良い言語だよ。英語カブレめ（ｗ
実際この書き込み(145かな？)のなかに主語のある文は一つもないが、
意味はちゃんと通じるだろ？
0146５月病
NGNG努めたわけよ。モナドの意味もつかもうとしてがんばった
んだけど、あるときふと、こんなに無理して副作用さけよう
という努力はなんなんだろうと感傷的になるわけよ。
0147デフォルトの名無しさん
NGNG0148チュウボウ
NGNG>日本語は主語なんかなくても良い言語だよ
おお、そうであった。日本語は述語だけでつうじるのだ。
日本語こそ真の関数型言語であった。なんてわけないか。
0149デフォルトの名無しさん
NGNGつーか…
プログラムって要するに「入力と出力の関係を記述する」
ってだけで良いはずなのに、状態を持ち出すとよけい面倒に
なることも多いでしょ。
0150５月病
NGNGストイックに記述する。そうすると見えるすばらしい世界
を教えてください。
0151デフォルトの名無しさん
NGNG> 入力と出力の関係を記述する
時系列的な入力と出力の表現には内部状態があった方が記述が楽。
あと、入力の長さが不定なときも。
だから入力に対して反応するタイプのプログラムでは状態記述がないと不便。
>>145
主語がなくていいのは主語が明らか（容易に推測可能）な時だけだよ。
フォーマルな文章では日本語だって主語が必要。ここはかなりインフォーマルだからね。
ちなみに英語でも命令形などでは明らかな主語が省略されている。
0152デフォルトの名無しさん
NGNGなんで、ストリームやモナドなどではプログラムの動作が完了した時点では
入力が決定して、出力も決定する筈ということに注目して、
実行時に対応関係を組み立てるわけだ。
0153デフォルトの名無しさん
NGNG無限列の有限部分列から有限部分列への対応関係なら書ける。
そしてその対応関係が再帰的に定義できているなら、
限りなく計算を続けられる。
ただ、有限部分列の入力から続きを計算する際に何度も同じ計算が
繰り返される場合がある。そういう場合は内部状態としてメモしておけば
計算効率が改善される。
0154デフォルトの名無しさん
NGNG現実的にはどんなケースがありますか？
0155デフォルトの名無しさん
NGNGしておけばJavaなんかでも再帰的に記述できるよ。
0156デフォルトの名無しさん
NGNGhttpプロクシサーバとか。
リクエストは無限列とみなせる。
以前にあったリクエストなら、内部状態としてキャッシュしとけば
速くなる。この場合でも副作用は別に必須じゃないけどね。
0157デフォルトの名無しさん
NGNG今はC、C++、C#、Javaで手一杯だよ･･･
0158デフォルトの名無しさん
NGNG副作用が絡むのは配列やオブジェクトの部分更新とかが絡むときが典型。
もちろん更新する値以外も全部複製してしまえば副作用は消せるが、
効率は･･････（ガクガクブルブル）
----
>>155
遅延評価は評価の仕方を「メモ」って行くわけだが、
結構、後でそのメモ・ツリーを辿るのに時間がかかったりする。
0160デフォルトの名無しさん
NGNGシンタックスだけはJavaに似てるけど。逆に言語から仮想環境を想定するとしたら
どんなものになるんだろね。Hakell、というより関数型言語全般のために
作られたようなもの。あるとしたらどんなもんでしょ？
0161153
NGNG0162デフォルトの名無しさん
NGNG0163134
NGNG>ストリームは「いくらでも長くなりうる列」というデータだ。
確かに漏れも、そう思います。ストリーム()
しかし、haskellのモデルではIO入出力はストリーム(ぎリスト)ではないですよね。
ということは結局、評価の順序が入出力に影響するはずですよね。
評価の順序を強制するためにモナドというものを利用しているんじゃないですかねー？
どうなんでしょ。
0164デフォルトの名無しさん
NGNGここの下の所に「Programming Languages：Concepts and Constructs 2/E」
の「日本語訳版を期待」という文字が見えるんですが、今翻訳中なのでしょうか？
もしそうなら超期待！！
>>158
どうも効率面を問題にされているようですが、
私自身たいして関数型言語の経験はありませんが、
仕事の関係上感じている事です。
コンパイラ作ってると、この副作用がないというのが
結構オプティマイズに有効だったりするので、
結構これからの言語の核にすえるのは悪くないと最近思ってます。
計算の依存関係が明白でないと最近のスーパスカラーみたいに
命令スケジュールが必要だと面倒です。
全体的とはいわなくても部分的には関数型言語が高速化への寄与大きいと考えています。
計算機の並列度が上がってくると、少し考え方を変えてみるのも悪くはないと思っています。
ちなみにモナドはあんまり良くわかっていません。(TT)
だれか教えてくれー
0165デフォルトの名無しさん
NGNG昔のバージョンではストリームでI/OやってたんだよHaskellは。
I/Oエラーが扱いにくくってなあ…
モナドの方が楽だよ。
0166134
NGNG本当ですか？
何時の頃のモノなんでしょう？
処理系の名前とバージョンを教えてもらえませんか？
>I/Oエラーが扱いにくくってなあ…
>モナドの方が楽だよ。
たしかに、そうですね。
うーん、モナドから逃げてるのかなー？俺は
■ このスレッドは過去ログ倉庫に格納されています