トップページ⇒tech
983コメント385KB

関数型プログラミング言語Haskell

■ このスレッドは過去ログ倉庫に格納されています
0001デフォルトの名無しさんNGNG
あまり馴染みのない人の多い関数型プログラミング。
Haskellを通じて、みんなで勉強しましょう。
0655649NGNG
>>654
どうもです。
……ちゃんと読んでなかった。
＞The scores in the Scores table can reflect CPU, Memory and/or Lines of Code (LOC).
Cはこの項目がDAMEだった訳か。
0656デフォルトの名無しさんNGNG
>>649
インタプリタのHugsならまだしも、コンパイラのghcで
Rubyよりも遅いのかよ。

でも、個別の試験で見ると、テキスト処理はダメでも
数値計算では勝てるみたいだね。
0657デフォルトの名無しさんNGNG
>649
Javaさん、意外に速いのねぇ。
プリミティブ型のおかげかしらん。
0658デフォルトの名無しさんNGNG
速度の他にHaskellの癖の強い点は，やっぱり遅延評価かな．
lazyなおかげで，えらく簡単に書ける場合もある半面，
どこがいつ評価されるかわからないことも多くて苦労する．
まあそれが嫌ならMLにすれば良い訳だけど...
0659デフォルトの名無しさんNGNG
Haskell 98の規格で決まってるライブラリ関数って、どこまで？
Hugsのライブラリ関数全てが、GHCでも使える訳じゃないんでしょ？
その辺の可搬性はどうなってるの？
0660デフォルトの名無しさんNGNG
仕様書みろ>659
0661659NGNG
あ、これか。
http://haskell.org/definition/
もう日本語訳もあったんだね。
http://www.sampou.org/haskell/library-j/index.html
ｽﾏｿ
0662デフォルトの名無しさんNGNG
>>658
細かく遅延評価をコントロールしてやればある程度最適化は可能だろうけど
プログラムは汚くなるなあ．やっぱりMLjみたいなのが正解？
0663デフォルトの名無しさんNGNG
>658
どこがいつ評価されるかなんて知ってどうするんだ?
それを知らないと困るような状況ってあるのか?
俺はそのような事で苦労したことはないのだが。
0664デフォルトの名無しさんNGNG
>>663
I/Oエラーが起きたとき等は評価の順序を知ることが重要だと思うが。
0665デフォルトの名無しさんNGNG
haskellで実用プログラムなんて無理。
でも好きなのでage
0666デフォルトの名無しさんNGNG
どこかに、命令型言語は「どのように」解くか、で
関数型言語は「何を」解くか、であると書かれていました。

数値計算などには強いのでしょうが、やっぱり実用プログラムは…
その割に、HOpenGLなんてのもあるんですよね。変なの。
0667デフォルトの名無しさんNGNG
Haskellで書かれた(?)ショッピングサイトが
何処かに紹介されてたような気が。
0668デフォルトの名無しさんNGNG
↑んなもんHaskkellで書かれたら誰も引継ぎ・メンテできないよ
0669デフォルトの名無しさんNGNG
>>664
IO なら評価の順序はわかるものだと思うが…
0670デフォルトの名無しさんNGNG
>>68
Haskellが使えたら、相当な高い給料で来てくださいって言われそうだな。（ｗ
0671デフォルトの名無しさんNGNG
>>667
逆に言うと、ショッピングサイトが数式で構築できるのか…
0672デフォルトの名無しさんNGNG
Lispで書かれた大手ショッピングサイトの話もどっかで読んだような？
0673デフォルトの名無しさんNGNG
>>672
http://www.shiro.dreamhost.com/scheme/trans/beating-the-averages-j.html
0674672NGNG
>673
ああ、それそれ。君速いねぇ( ﾟДﾟ)
0675デフォルトの名無しさんNGNG
Lispは、化け物だと思うよ。
俺はLispを少ししか触ってないから厨房的発言かも知れないけど、
Lispほど何処にでも現れて、成果を出している言語なんて
そうそうないんじゃないかなぁ
0676デフォルトの名無しさんNGNG
>>671
「数式で」って君面白いねえ。
Cのprintf("%d\n", ...)もi = i + 1も「式」だって分かってる？
0677デフォルトの名無しさんNGNG
いまんとこ、うちじゃHugs for Winは単なる計算機代わりです。
（前は、Rubyのirbを計算機代わりにしてました。）
でも、インタラクティブに関数定義出来ないのがイタすぎると思われます。
0678デフォルトの名無しさんNGNG
>>677
よくわからんが、fileをloadするのは駄目なのか？
0679デフォルトの名無しさんNGNG
書く
↓
実行

でなく

エディタ起動
↓
書く
↓
ファイルに保存
↓
ロード
↓
実行
↓
めんどくせぇ!

ってこと?
0680デフォルトの名無しさんNGNG
>679
そゆことです。
0681デフォルトの名無しさんNGNG
面倒かな？

インタプリタで試す。
↓
エディタのソース画面に貼り付け。
↓
ロード
↓
また試す。

これでいいんじゃないかな？
0682デフォルトの名無しさんNGNG
アホな事を聞くようでアレなんだが、
Haskellは再帰とかでいくら関数ネストしてもスタックあふれない、の？
0683デフォルトの名無しさんNGNG
>>682
そんなことはない(スタックじゃなくてヒープを使うかも知れんが)。
でも、末尾再帰(要するにループ)ならメモリは全く食わない。

末尾再帰ってのは、再帰呼び出しの値がそのまま関数の値になる、Cなら
int f(int x) { ..... return f(...); ....}
みたいな再帰呼び出しのこと。
(Cコンパイラでもジャンプに直す処理系があるよね。)
0684682NGNG
>683
ｻﾝｸｽｺ

Cとは全然勝手が違うので混乱気味な漏れなんだが、
SOEって言うのかな？　『The Haskell School of Expression』って本を
読み始めたよ。
全くの初心者を対象にしてるらしく、読みやすくてとっつきには
いい本だと思う。値段も高くないし、他のHaskell初学者にもお薦め。
あとは、これで日本語だったら完璧だったのになぁ。
0685デフォルトの名無しさんNGNG
>>683

ただ、Cと違って
int f(int x) { return g(x); }
int g(int x) { return f(x); }
も関数型言語だとジャンプになるけどな。(無限ループになる。)
0686671NGNG
>>676
分からないから、式と数式の意味の定義を説明してくれる？
0687デフォルトの名無しさんNGNG
>>685
Cでもなるよ。
0688デフォルトの名無しさんNGNG
>>687
ならねーよばか
0689仕様書無しさんNGNG
int f(int x) { return f(x); }
なら、まだわかる。
無限に呼び出しが続いたりはしないが。
0690デフォルトの名無しさんNGNG
>>685
Cの場合は、末尾再帰を最適化してくれるコンパイラなら、
ベースポインタを呼び出し前の状態に戻してジャンプだな。
スタックを積み上げる必要はないから、無限に呼び出し（ジャンプ）が続く。

ところでHaskelだと一応環境をヒープからアロケートしなおさないといけなくないか？
（現環境を廃棄できるから、無限に呼び出しを続けられるが）
0691hGetContentsNGNG
ファイルを全部一気に読み込んだ事にしても、実際にはlazyだから
必要な時に必要な分だけ読んでくれるんだね。
ちょっと萌えた。

でも効率は知らん。
0692デフォルトの名無しさんNGNG
>>691
ファイルIOとか、そういう処理にlazyかよ。
信じられん言語だな。
デバッグ大変そう。（ｗ
0693デフォルトの名無しさんNGNG
>>692
I/Oはlazyにした方が効率よいことも多いよ。
仮想記憶ベースのmemory mapped I/Oもcacheのflushもcopy on writeも…
0694デフォルトの名無しさんNGNG
つーかproxyパターン
0695デフォルトの名無しさんNGNG
東京工科大学の演習、一通りやってみました。
次なる修行はどんなのが良いでしょうか？
0696デフォルトの名無しさんNGNG
Lispよろしく、コンパイラなんてどうでしょう?
筑波大のどっかの研究室に、MLでコンパイラ作成ってのがありましたよね。
確かこのスレのどこかにもリンクがあったはず。
趣味じゃなかったらいいんですけどね。
0697デフォルトの名無しさんNGNG
>695
東工大のhaskellの授業です。講義のページにも下の方に演習がありますよ

http://www.brl.ntt.co.jp/people/mizuhito/CS/
0698デフォルトの名無しさんNGNG
↑の12月13日のところの上級問題が解けたら凄いですね
0699デフォルトの名無しさんNGNG
解けない・・・
0700695NGNG
どもです。>>696-697
0701デフォルトの名無しさんNGNG
age
0702デフォルトの名無しさんNGNG
[上級問題１]（これができれば単位は差し上げます）
maximum segment sum 問題(mss)は実は線形時間アルゴリズムが存在する。その
アルゴリズムを実装し、なぜ線形時間であるか理由をしるせ。

mss :: [Int] -> Int
mss = maximum . mss' 0
where
mss' n [] = [n]
mss' n (x:xs)
| n + x < 0 = n : mss' 0 xs
| x < 0 = n : mss' (n+x) xs
| otherwise = mss' (n+x) xs

線形時間であるのは自明ってことで許して。
0703702NGNG
mss [-1,-4,-5] => 0

間違ってるやん…
出直してきます…
0704702NGNG
そもそも mss [] が 0 でいいものなのか…
0705デフォルトの名無しさんNGNG
宿題解かせようとしてる東工大生の陰謀に引っかかるなよ。（ﾜﾗ
0706ad-hocNGNG
mss :: [Int] -> Int
mss [] = error "mss []"
mss xs = case maximum $ mss' 0 xs of
0 -> maximum xs
n -> n
where
mss' n [] = [n]
mss' n (x:xs)
| n + x < 0 = n : mss' 0 xs
| x < 0 = n : mss' (n+x) xs
| otherwise = mss' (n+x) xs
0707デフォルトの名無しさんNGNG
この問題の事か・・・
たしかに線形性ってのは述べにくいよね


maximum segment sum 問題(mss)は、整数列（正とは限らない）を入力とし、その
連続する部分列で和が最大となるものをみつけて、その和を出力とする。
たとえば [2,-3,2,-1,2,3,-5,8,-9,1] の場合 [2,-1,2,3,-5,8] の和 9 が出力で
ある。このプログラムを作成せよ。

[上級問題１]
maximum segment sum 問題(mss)は実は線形時間アルゴリズムが存在する。その
アルゴリズムを実装し、なぜ線形時間であるか理由をしるせ。

[上級問題２]
2-maximum segment sum 問題(2-mss)は、整数列（正とは限らない）を入力とし、その
重なりのない高々二つの連続する部分列で、それぞれの和の和が最大となるものを
みつけて、その和を出力とする。
たとえば [2,-3,2,-1,2,3,-5,8,-9,1] の場合 [2,-1,2,3] と [8] の和 14 が出力で
ある。このプログラムを作成せよ。

[上級問題３]
2-maximum segment sum 問題(2-mss)は実は線形時間アルゴリズムが存在する。その
アルゴリズムを実装し、なぜ線形時間であるか理由をしるせ
0708関数プログラマNGNG
Haskellの構文ちょっとわすれちゃったからCで許して

/* nはx[]の長さ．n > 0を仮定 */
int mss (int x[], int n) {
　　int p, q, i;

　　p = x[0];
　　for (i = 1; i < n; i++)
　　　　if (x[i] > p) p = x[i];
　　/* x[]の最大値が負の数なら，それがmss */
　　if (p < 0) return p;

　　/* x[]中には少なくとも1個正の数がある */
　　p = q = 0;
　　for (i = 0; i < n; i++) {
　　　　if ((p += x[i]) < 0) p = 0;
　　　　if (q < p) q = p;
　　}
　　return q;
}
0709関数プログラマNGNG
Scheme版も書いてみました．

(define (mss xs)
　(define (pmss xs p q)
　　(if (null? xs) q
　　　　(let ((pp (+ p (car xs))))
　　　　　(pmss (cdr xs) (max pp 0) (max pp q)))))
　(let ((m (apply max xs)))
　　(if (< m 0) m
　　　　(pmss xs 0 0))))

たぶんHaskellだともっとスマートにかけると思います．
それにしても全角スペースをいれてインデントするのは面倒ですね．
0710関数プログラマNGNG
線形性は自明ですが，このアルゴリズムがmssを計算していることを
示すほうが面倒といえば面倒ですね．
0711デフォルトの名無しさんNGNG
>>709
Schemeよりスマートに書ける言語なんてありません。
0712デフォルトの名無しさんNGNG
age
0713デフォルトの名無しさんNGNG
>>709
&nbsp;に置換してもらうほうが
こぴぺする側としてはありがたい。
0714デフォルトの名無しさんNGNG
自慢の関数言語で痴漢スクリプト書けばいいだろ
0715デフォルトの名無しさんNGNG
>>713
連続した半角スペースは消えるんじゃないの？
0716デフォルトの名無しさんNGNG
>>715
nbsp;は何個書いても消えないよ。
0717厨房丸出しNGNG
ghc、なんだかよくわかんねーけどすげーYO！
0718デフォルトの名無しさんNGNG
GHCはGarded Horn Clauseのことです。
0719石敢當NGNG
Hugsの新版がリリースされました。

http://cvs.haskell.org/Hugs/pages/latest.htm

再びグラフィックライブラリが使えるようになったので
嬉しいです。
0720ﾊｸﾞﾊｸﾞNGNG
ところでHugsって、なんて読むの？
ﾊｸﾞｽﾞ？
0721デフォルトの名無しさんNGNG
嬉しいage
0722デフォルトの名無しさん NGNG
あ、石敢當さんだ！
お久しぶりです。
0723デフォルトの名無しさんNGNG
>>720
"ハグズ"だよ．
0724720NGNG
>723
あ、ﾊｸﾞｽﾞでいいんだ。

それにしてもライブラリがたくさん増えたなぁ。
もしやと思ってgrepかけてみたけど、Win32 OLEなライブラリは無かった。
これが有ると、世間的にもウケがいい気がするんだけど。
0725石敢當NGNG
>>722
ご無沙汰してました。（見てはいたんですけどね）
Birdさんの本(>>277)を最初からゆっくり読むことにしていました。
exerciseは適当にやったりとばしたりして、やっと100ページくらい
読んだところです。約1/4くらいまで来ましたが、だんだん中身が
濃くなってきたので読むペースも落ちてきました。Haskellで何か
すぐに作らなきゃいけないわけじゃないので、まあのんびりいきます。

>>723
身近にHaskellをいじっている人がいないので、HaskellもHugsも
実際に発音したことないです。頭の中では「ハスケル」「ハグス」と
読んでいました。「ハグズ」と濁るのが正しいのですね。
0726デフォルトの名無しさんNGNG
俺は頭の中で「ハッグス」って読んでた。
0727デフォルトの名無しさんNGNG
俺は頭の中で、しいちゃんの「ダッコ」を思い出してた。
0728名無しさん＠ＥｍａｃｓNGNG
こんにちは。Haskell勉強中のものです。
Preludeモジュールに、digitToIntがあるのにstringToIntはないんですね。ちょと不思議。
そこで自分で作ってみました。

strToInt :: String -> Int
strToInt "" = 0
strToInt str = digitToInt (last str) + 10* strToInt (init str)

intToStr :: Int -> String
intToStr x
| x `div` 10 == 0 = [intToDigit x]
| otherwise = intToStr ( x `div` 10 ) ++ [intToDigit ( x `mod` 10 )]

こんな風になりました。もっとうまく書けるとか、美しく書けるという人はおしえてくださいな。
0729デフォルトの名無しさんNGNG
>728

read関数があるよ。型に制約かけないとうまく動かんけど。

Prelude>(read :: String -> Int) "1234"
1234

# Hugsはハグスって読んでた
0730デフォルトの名無しさんNGNG
Hugsの開発やってる人達は「ハグズ」って言ってたよ．
0731デフォルトの名無しさんNGNG
正直、Haskellのコードはビジュアル的に美しくないな。
Haskellコードを美しく表示/印刷するための
プリティプリンタが欲しい感じ。
0732デフォルトの名無しさんNGNG
>>728
strToInt "" の時に 0 を返すのはなんかなぁというのと、
効率を気にしてこう書く。

strToInt :: String -> Int
strToInt "" = error "strToInt"
strToInt ('-':cs) = negate $ strToInt cs
strToInt cs = foldl (\x c -> x*10 + digitToInt c) 0 cs
0733デフォルトの名無しさんNGNG
>>728

Int は Read クラスのインスタンスとしてPreludeで宣言されているので、read がつかえるよ。

Prelude> (read "1234")::Int
1234

Int は Show クラスのインスタンスとしてPreludeで宣言されているので、show がつかえるよ。

Prelude> show 1234
"1234"
0734デフォルトの名無しさんNGNG
＞731
a2psの-Eオプションと--highlight-levelオプション使ってみては?
->はちゃんと→になるし、::はなぜか集合の"is an element of"の記号になるけど。
それなりに綺麗にはなるかと。
というか、GHCのサイトのリンクにプリティプリンタがあった気がする。
0735名無しさん@Vim%ChaliceNGNG
age
0736デフォルトの名無しさんNGNG
age
0737デフォルトの名無しさんNGNG
>>732
strToInt "----3" が3になるのは嫌だ。
0738732NGNG
>737
そうだね。俺も嫌(w
0739デフォルトの名無しさんNGNG
>>734
A→Bてのは、→をバイナリオペレータとした、
AからBへの関数全体の集合のことだから、
f∈A→Bは変ではないと思う。
0740デフォルトの名無しさんNGNG
Hugsの新版をインストールしたら、editerをいちいち閉じないと
動かなくなってしまった。これバグ？ Win98使用。
0741デフォルトの名無しさんNGNG
>>739
それはわかってるんだけど、他の言語でNameSpaceを指定したりするのに
::を使ったときも∈になったら鬱とか思った。というか、MLのcons operatorとか。
0742デフォルトの名無しさんNGNG
NameSpaceならそれなりに意味は通じないでもないが、
Consが∈はイヤすぎだな（藁
0743あげあらしNGNG
http://lc.linux.or.jp/lc2001/papers/haskell-paper.pdf
のHaskell Emacsについてどう思いますか？
0744デフォルトの名無しさん NGNG
ghqでインラインアセンブラのようなことは出来ますか？
0745石敢當NGNG
GHCのversion 5.02.2がリリースされました。

---

年末年始は少し時間を取れたのでIFP本(>>277)を読み進めました。
難しくて良く分からないところなどはとりあえず飛ばして、
Monadの手前の9章まで読みました。大変勉強になります。

>>420 に「O(1) で挿入、削除を出来る queue を作れますか?」
という投稿がありましたが、O(1)で操作できるキューの実装も
出ていました。Chris Okasaki氏の考案によるものだそうです。
短いコードで、O(1)で操作できる理由も書かれているのですが、
まだ私には理解できていません。

今度はexerciseをやりながら読み返してみようと思います。
0746石敢當NGNG
すみません。sageてしまいました。
0747デフォルトの名無しさんNGNG
山下さんが Why Functional Programming Matters の訳を公開してますね。
http://www.sampou.org/haskell/article/whyfp.html
0748デフォルトの名無しさんNGNG
『Craft of Functional〜』本を読んで、ﾓﾅﾄﾞがぼちぼち解りかけてきたが、
Stateﾓﾅﾄﾞは尚一層難しいね。
0749デフォルトの名無しさんNGNG
デバッガ(?)が有る事を今知ったage
http://www.cs.chalmers.se/Cs/Grundutb/Kurser/d1pt/d1pta/lecture8a.pdf

↑に出て来るcountOccurrencesって関数、ｶｺｲｲけど
自分じゃ絶対思いつけないなぁ。
0750デフォルトの名無しさんNGNG
関数型言語に取り組もうと思うのですが、
Haskell と ML の差(言語、勢力などあらゆる側面において)に
ついて比較していただけませんか？

歴史という意味では ML の方が長い訳だし、パフォーマンスという
意味でもコンパイラまで装備された ML のほうに分がありそうに
見えます。

しかしここのところの人気は Haskell のほうがあるように見えます。
いったいこれはどうした訳なんでしょうか？
0751デフォルトの名無しさんNGNG
Haskell、コンパイラあるよ
0752デフォルトの名無しさんNGNG
>>750
Haskellが人気有るのは2chだけのような気が……。
0753デフォルトの名無しさんNGNG
>750
我々に ML を貶せと仰る?

つか、そんなこと気にしてないで
さっさとどっちでもいいから取り組み始めたほうがよろしいかと。
最終的には両方やればいいし。

あと Scheme も忘れずに。
0754747NGNG
ガハハハ！　これ、すごいわ。
http://www.puchiwara.com/hacking/
■ このスレッドは過去ログ倉庫に格納されています