関数型プログラミング言語Haskell
■ このスレッドは過去ログ倉庫に格納されています
0001潜伏していた1
NGNG前スレ
http://pc.2ch.net/test/read.cgi/tech/996131288/l50
関連 >>2 以降
0002潜伏していた1
NGNGここがパート2です。鬱。
Haskellの公式HP
http://www.haskell.org
インタプリタHugs
http://www.haskell.org/hugs
日本語サイト
http://www.sampou.org/haskell
http://www.teu.ac.jp/kougi/koshida/Prog6/index.html
0003潜伏していた1
NGNG関数型言語Part2
http://pc.2ch.net/test/read.cgi/tech/1007387924/l50
関数型プログラミング言語ML
http://pc.2ch.net/test/read.cgi/tech/1012445015/l50
LISP Scheme Part3
http://pc.2ch.net/test/read.cgi/tech/1008220265/l50
0004潜伏していた1＠このスレはパート2です
NGNGなぜ関数プログラミングは重要か
http://www.sampou.org/haskell/article/whyfp.html
普通のやつらの上を行け ---Beating the Averages---
http://www.shiro.dreamhost.com/scheme/trans/beating-the-averages-j.html
Why People Aren't Using Haskell
http://www.jelovic.com/articles/why_people_arent_using_haskell.htm
0005このスレはパート2です
NGNG0006デフォルトの名無しさん
NGNG一番下のやつってやる気起きるのか?
英語苦手なんでちゃんと読めてないのですが
とりあえず Haskell を勧めてはいないような…。
0007このスレはパート2です
NGNGなんで使ってくれないんだ? と訴えられると、
「よっしゃ一肌脱いだる」とか思うのは、俺だけですかねぇ。
＃その割に未だ偉そうなプログラムは書けていませんが。
0008デフォルトの名無しさん
NGNGそんなに Haskell 側に立ってる感じでもないような。
0009age
NGNGdata A a = A a
f = id
g :: a -> a
g = A.f
h :: a -> A a
h = A .f
0010デフォルトの名無しさん
NGNG0011デフォルトの名無しさん
NGNG胴囲
どっちかというと、Haskell擁護者よ。
Haskellを普及させたいなら、もっと頑張れみたいな。
たしかにHaskellには、一般向けアプリを作りるには足りないものが多いなー。
TCP/IP鯖作るにしても、ライブラリ作るところから始めなきゃいけないし。(多分)
鯖にTimeOut処理付けるにしても、Timer関数ないし、競争書き込みもしないから
各関数にTimeOut処理付けるしかないのかな？
と言うわけでParalell Haskell燃えー。(といっても何かは知らんがね)
0012デフォルトの名無しさん
NGNGどうしてそういう結論につながるんだよ!
と思ったが、前スレに出てた Paralell Haskell で書かれた web server のことで…か。
とりあえずあれは Paralell Haskell だからライブラリがあるわけでなく
ただ単に GHC に付いてる ライブラリ使ってるだけっぽいですよ。
001311
NGNGこんな関数がほしいのよ。(Haskell消防なので笑わないでね)
readWithTimeOut :: Socket -> Int -> Maybe String
readWithTimeOut s ms = timer ms Nothing || read s
関数timer::Int->a->aは指定された時間簡約が停止する。
その後2番目の引数を返す
関数read::Socket->StringはTCP/IPにデータが来るまで簡約が停止する。
ソケットからByte列をStringとして返す。
演算子||は、競争書き込み。全ての最初に帰ってきた値を値として返す。
他の簡約は、もちろん正常に停止、消去(GC?)される。
もちろん a = b || c || dと複数書ける。
(競争に負けた簡約は、どうしたらいいんだろう？うーん、キャッシュしておく？)
ってParallell G-mahineを実装しているHaskellでも可かな？
このようなことのできる処理系あったら誰か教えて。お願いします。
0014デフォルトの名無しさん
NGNG0015デフォルトの名無しさん
NGNG0016デフォルトの名無しさん
NGNGコンパイラ(GHC)の方にはグラフィック関係のライブラリない
みたい。Hugsでライフゲーム作ってみたけど、遅いので
コンパイルしたいが、GHC使ったことないので教えてくれ。
アニメーションもストリームにしちゃうから、グラフィックIO
も遅延評価じゃなきゃいけないが、このあたりがライブラリー
の作成を難しくしているのかな。
0017デフォルトの名無しさん
NGNGなんたる！
0018デフォルトの名無しさん
NGNG参照の透明性が…（泣
0019デフォルトの名無しさん
NGNG貴様は代入を行った（笑
0020デフォルトの名無しさん
NGNG0021デフォルトの名無しさん
NGNGﾜﾗﾀ
0022デフォルトの名無しさん
NGNG参照透明性くずすな。
002317
NGNG002422
NGNG17−20うまくオチが決まってたので、チャチをいれたくなった（笑）
002517
NGNG＃だとしたら次スレも同じ名前？（笑
0026デフォルトの名無しさん
NGNG002720
NGNG丁度悩ましい思いをしてるトコなもんで(w。
>>25
その場合、このスレに関する型推論はどうなるのでありますか？(w
0028面白そうだけど、調べた事ないー
NGNGなんか、プログラムの停止性と関連付けて、
停止する関数と停止しない関数に分けるのかな？
多相型と関連付けると、ちいと面倒な結果になりそう...
＃真面目に調べたことないけど
0030デフォルトの名無しさん
NGNG作って遊んでます。が、しかし！
コンパイルが異常に遅いです。
ghcってHaskellで書いてあるんですよね？
だとしたらHaskellで書かれたプログラムは
遅いということになったりして・・・鬱
実際にghcでアプリケーション作ってる人の
感想を聞かせてください。
0031デフォルトの名無しさん
NGNG0032デフォルトの名無しさん
NGNGこれはなんでしょうか？
0033デフォルトの名無しさん
NGNG参照透明性が確保できませんよね？
（実行するたび帰り値が違うんですから。）
なんとか参照透明性を確保する方法ってないのでしょうか？
誰か教えてください。
0034デフォルトの名無しさん
NGNGおおHaskell.NETのBetaすか？
いいですねー。
今度Downしてみよう。
0035デフォルトの名無しさん
NGNG「入力」の仲間だと思えば継続(continuation)かMonadかなぁ。
無限リストで乱数列を表し遅延評価というのも、
形式的には面白いが実際に書くと重いだろうなぁ。
まー、擬似乱数を線形合同法とかでつくるなら、
お手軽には直前に出力された数を呼出し毎に渡すとか……。
0036デフォルトの名無しさん
NGNGhttp://www.sampou.org/haskell/library-j/random.html
ほとんど>>35の言う通りのやり方。
>>35
> 無限リストで乱数列を表し遅延評価というのも、
> 形式的には面白いが実際に書くと重いだろうなぁ。
そこまで重くなるとは思えないけど?
というか、他の部分も遅いだろうから、
特別その部分が遅い気はしないだろうっていうほうが正しいか(w
003733
NGNGお答えいただき有難うございます。
>ttp://www.sampou.org/haskell/library-j/random.html
この方法ですか。なるほど。
質問してから解決策を考えていたのですが
乱数表を使うか、この方法かどちらかかなとしかないかなと
思っていたので納得出来ました。
それにしてもHaskellのIO型って変ですね。(名前が)
非決定なものは、すべてIO型なんですね。
うーん、もっと良いネーミングしてほしい。
0038デフォルトの名無しさん
NGNG0039デフォルトの名無しさん
NGNG重くなるっていうか、乱数って最新の一個だけが必要なことが多いから
過去の値が全部リストになって残ると、沢山利用した時にメモリを無駄に圧迫するかなと。
GCで回収されるならまだいいんだけど。
0040デフォルトの名無しさん
NGNG参照されていないオブジェクトは回収されないんですか？
0041デフォルトの名無しさん
NGNGクライアントは再帰中なので、
生成された乱数は、参照可能だからかな？
そりゃ、回収されんわな。
0042デフォルトの名無しさん
NGNGIO monadは、最初は本当に入出力用だったのに、
後からいろいろと付け足したのだと思われ。
別々のmonadにすればいいじゃん、と思うかもしれないが
一緒に使いたくなったときに困る。
monadの合成は、理論的に自明じゃない問題があるので。
0043デフォルトの名無しさん
NGNGだから>>36のやり方は別に特殊じゃないよ。
0044デフォルトの名無しさん
NGNG末尾再起なら回収できないかな？
0045デフォルトの名無しさん
NGNG末尾再起じゃなくて乱数リスト回収できない事気にするくらいなら、
リストよりでかいスタックを解放するようにプログラム書き換えろ。
sagesage
0046デフォルトの名無しさん
NGNG0047言語障害なんです
NGNGhttp://www.geocities.co.jp/SiliconValley-Cupertino/6957/HaskellIsOOpl.ja.html
>>13はゆーあいさん疑惑
http://www.geocities.co.jp/SiliconValley-Cupertino/6957/diary200202.ja.html
思っているだけで作る気はない疑惑
http://www.geocities.co.jp/SiliconValley-Cupertino/6957/mylang.ja.html
typo がやたら多いという罠
0048デフォルトの名無しさん
NGNG0049デフォルトの名無しさん
NGNG0050デフォルトの名無しさん
NGNG0051デフォルトの名無しさん
NGNG「lambda lifter」って、どういう処理なんでしょうか？
局所関数(関数内の関数)を展開して外側の関数と一体化する処理らしいですけど
実行速度改善のための最適化処理の一種だと考えてよいのでしょうか？
http://citeseer.nj.nec.com/lester91modular.html
それと関数型言語にある代表的な最適化処理があれば教えてください。
0052デフォルトの名無しさん
NGNGCのインラインと違うの？
0053デフォルトの名無しさん
NGNG実行時までどんな関数が来るのか分からない
らむちゃんなんだから全然違うだろ。
0054無名λ式
NGNGlambda liftingというのは、
一言で言えば、自由変数を除去する変換の事です。
・funarg問題がなくなる
・環境の扱いが簡単になる
・lazinessの境界がはっきりする
などなどの利点があります。
lifterはその変換器の名前です。
Super combinatorというのありました。(これは変換後のλ式の名前)
Prentice-Hallから処理系実装の本が出ていましたが、
> それと関数型言語にある代表的な最適化処理があれば教えてください。
こういう観点で非常にいい読物だと思います。
# 今やMicrosoft Research(CLI!)のSimon P. Jonesのが一冊、
# もう一冊はHughesじゃなかったかな? 教科書になって答えがWebで配布された奴。
驚きなのはcombinatorが非常に古い概念であるにも関わらず、
λ計算において非常に本質的な役割を担うことです。
0055無名λ式
NGNG> 実行時までどんな関数が来るのか分からない
> らむちゃんなんだから全然違うだろ。
λ式ちゃんは、Lisp野郎ほど酷くないですけどね。
奴の場合、cons, eval, macroと何でもありなので。
0056デフォルトの名無しさん
NGNGhttp://research.microsoft.com/~simonpj/Papers/papers.html
ここ (の一番上のとこ) から落とせるやつですな。
0057無名λ式
NGNGこれ面白いよね。この作業苦痛じゃないのかな...
0058デフォルトの名無しさん
NGNGなんだか大変そうですね。これホントに自分でやってるのかな？（藁
0059デフォルトの名無しさん
NGNG0060デフォルトの名無しさん
NGNG0061デフォルトの名無しさん
NGNGコンビネータ、結合子ですか？
圏論？λ理論の話でしたか？
うーん難しい。
0062デフォルトの名無しさん
NGNG理論的には難しいとおもうけど、
"Implementing Functional Languages: tutorial"
には実装についてわかりやすく書いてありますです。
0063デフォルトの名無しさん
NGNGサイモン パイソン ジョーンズさんがM$用に書いたやつだよね？
どのチャプターに書いてあります？
(ファイルは持ってるんだけどねー。軟弱ものなので読んでません。)
0064デフォルトの名無しさん
NGNGペイトン
0065デフォルトの名無しさん
NGNGLambda lifting については ６章
コンビネータ実装のはなしは
"Implementation of Functional Programming Language"
というよく似た名前の本の方でした。これも、どこかのWEBサイトで公開
されてたとおもうですだす。
0066デフォルトの名無しさん
NGNG"Implementation of Functional Programming Language"
本の方は簡単に見つかったけどなー。
判らない。くそー。
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デフォルトの名無しさん
NGNG■ このスレッドは過去ログ倉庫に格納されています