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

あまり馴染みのない人の多い関数型プログラミング。
Haskellを通じて、みんなで勉強しましょう。

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

参考スレ：関数型言語
http://piza2.2ch.net/test/read.cgi?bbs=tech&key=987954395

さくっと作ってみた階乗計算。
myfactorial 0 = 1
myfactorial n = n * myfactorial (n - 1)

関数myfactorialの引数が0の時、1を返し、
それ以外なら、n * myfactorial(n - 1)を返します。
再帰を用いて記述しております。
簡単すぎる例かな?

参考図書
「プログラミング言語」

岩波講座　 ソフトウェア科学〔基礎〕4

ISBN4-00-010344-X　　岩波書店

武市　正人　著

菊判　　248頁　　本体 3,200円　　1994年6月17日 発行

関数型プログラミングっていいよね。
Lispのcondや、Haskellの | を読むとき、
その条件ごとの文の内容が、非常に読みやすい。

HaskellはLispと違って、中置記法じゃないのも自分としては良かったかな。

参考図書

>>1 「Haskellを通じて」

ということなので、Haskell以外でも良いのかな？

MLの本になりますけれど、次の本は効率の
良いコードを書くための大変良い参考書となりました。
（後半はほとんど読んでいませんが・・）
Haskellのコードを書く際にも役立つと思います。

Lawrence C. Paulson
"ML for the Working Programmer(2nd Ed)"
Cambridge University Press, 1996


面白そうに思ったので先日つい衝動買いしてしまった本が、

Chris Okasaki
"Purely Functional Data Structures"
Cambridge University Press, 1998

です。最初のほうをパラパラと斜め読みした程度
ですが、面白そうな匂いを感じました。

Haskellなどは趣味でいじっているだけなので、
なかなかゆっくり本を読む時間を取れません。
仕事で使う機会があれば・・という思いは
実現しそうにありません。

あぁしまった
Haskellを通じてどうのこうの、じゃないっすね。
ちなみに、他の関数型言語に関しては、>>3 を参考にされると
よろしいかと思われます。

Haskellで、「状態」を扱いたいときはどう組めばいいんでしょう？
プログラミングレベルでは「状態」でなくても、Haskellで構築された
アプリケーションのユーザーから見て「状態」はどうしても
あるわけですよね？
それをHaskellプログラミングではどのように対処したら良いのでしょう？

関数型言語スレの25を引用すると…
＞純粋な関数型言語(Haskell等)には代入がない。つまり状態はありません。
＞ではどうしているかというと、mainルーチンを現在の計算機の状態をうけとり
＞新しい計算機の状態を返す関数だと考えることで回避しています。

となっております。
…関数型言語の定義から勉強してきます

たぶん 1 はもう知っているんだろうけど。

Why Functional Programming Matters
http://www.cs.chalmers.se/~rjmh/Papers/whyfp.html

じゃあ、とりあえず、
　ﾓﾅ度がワケ、分か、らん┐(´_`)┌

http://tanaka-www.cs.titech.ac.jp/%7Eeuske/scm/index.html
> Why Functional Programming Matters
> なぜ関数型言語が重要なのか、その利点をわかりやすく解説した ためになる文書。翻訳したいなあ。
してよ。

っつーか、やっぱ Haskell の前に英語勉強した方がいいよな。

質問君ですみません。
foo :: Int -> Int
のような、関数の引数と返り値の型定義を行っても行わなくても
関数は実行できるのですが、これは実行速度の向上や、
不正な型が来たときにエラーを返すため、と考えていいのでしょうか?

実行速度とかには影響無いです。>>14
(コンパイル速度は変わりそうだけど。)
fooの定義だけで入出力の型が決定すれば、
明示的な型宣言は必要無いんじゃなかったかな。
もし、型が曖昧であれば、コンパイル時に処理系がエラーを返す筈。

あと、haskellは静的型付けだから、実行時に不正な型とかで
エラーになる様な事は無い気がするけど。
Haskellでも動的型とかで実行時型エラーって起きるのかな？

Haskell 入門は読んだはいいけど、
その先、親しみやすいサンプルプログラムがないんですよね。
他にも僕みたいな人は結構いると思うので
なんか面白いソースで短いのあったらみんなで載せていく、っていうのはどうでしょう。

一生懸命、東工大の課題を解いていますが、
それの答えを載せてしまっては、東工大の学生さんに申し訳ないですよね

Haskell本出ないのかなぁ。
つーか、1に出てる東工大の先生に書かせるしか。

Hugs98使ってみようと思うんですが、
落とすファイルってこれだけでいいんですかね？
hugs98-Feb2001.zip
win32exes.zip
hugs.hlp
(コンパイラ(GHC)の方は大きい(22M)ので止めた)

あ、winhugs.exe実行したら、無事窓が出て、
Prelude>
とプロンプトまでは出ました。

さて何しよう・・・

とりあえず、東工大の演習問題で鍛えてみるのはいかがでしょう?

>>20
ちなみに先に言っておくと、
そのHugsはソースファイルをエディタで作って、窓にドロップするしか、関数定義する方法はありません。
どうやっても環境中で関数定義はできないのでご注意を。

東工大って>>2のこれ↓ですか。
http://www.teu.ac.jp/kougi/koshida/Prog6/index.html

>>8
やっぱりHaskellのみですね。すみません。

それじゃあ>>2からたどっていける所にありますが、次の本をあげときます。

The Haskell School of Expression（以下「SOE本」と記す）
http://haskell.cs.yale.edu/soe/


Haskellでは遅延評価を採用しているので無限リストを扱える・・
と読んでもピンと来ませんでした。

SOE本の無限リストに関する章に母関数を使ってフィボナッチ
数列を求めるExerciseがあります。つまり、

1/(1 - x - x^2) = 1 + x + 2x^2 + 3x^3 + 5x^4 + ...

x^nの係数がフィボナッチ数列の第n項となるというものです。

無限列に対する四則演算を準備しておけば、
a = [1, 0, 0,0,0,...(以下すべて0)]
b = [1,-1,-1,0,0,...(以下すべて0)]
fib = a / b
とするだけで上記母関数が得られます。実際にこのコードを
書いてフィボナッチ数列が出てきたときは結構感激しました。
C言語などではこんな風に無限列は扱えませんものね。

>>16 同感です。

>>17 コードの表現方法は幾通りもあるでしょうか、その中の
ひとつということでよろしいのではないでしょうか。掲載された
ものが自分のよりも良いコードであれば勉強になるし、自分の方が
良いと思って優越感に浸れるかもしれないし。
私はまだ東工大の演習は読んでいませんが・・。

誤）コードの表現方法は幾通りもあるでしょうか、
正）コードの表現方法は幾通りもあるでしょうから、

東工大資料の「リスト」って所の課題3がね、
どうしたら一番スマートか、って悩んでる。
fillもfactもできているんだけど、どう出力するのが一番かな?と…
nもfact nも数字だから、文字列に変換しなければならないんだが、変換だるい(wara

>>27 変換だるい

showを使っておけばどうでしょ？
(例 show 12345 = "12345")

> 実際にこのコードを書いてフィボナッチ数列が出てきたときは結構感激しまし
> た。C言語などではこんな風に無限列は扱えませんものね。

exact real numberって知ってる？

東京工科大学じゃねぇか。
東工大と間違われるとは、幸せな大学だな。（ｗ

東京工科大学なんてドキュ大でHaskellを教えるのかぁ。

>>29
詳しく教えてくれません？

>>29
不勉強にして知りません。名前からすると多倍長（無限）精度演算
ライブラリのようなものに思えますが、遅延評価を行えるもの
なのでしょうか。概略を教えて頂ければ幸いです。

>>31
ドキュ大とは思わんが、トップレベルの大学ではないからわかりやすく説明してあるんだろ。
いいことじゃないか。東大だったら難しく書いてあるだろ。

□□□□■□□□□□■□□□□□□□□□□□□□□□□□□□□□
□□□■■□□□□□■□□□□□□□■■■■■■■■■■■■□□
□□■■□□□□□■■■■■■□□□□□□□□□□□□□■■□□
□■■□□■□□□■□□□□■□□□□□□□□□□□□■■□□□
□□■□■■□□■■■□□■■□□□□□□□□□□□■■□□□□
□□□■■□□■■□■■■■□□□□□□□□□□□■■□□□□□
□□■■□□□□□□□■■□□□□□□□□□□□■■□□□□□□
□□■□□□■□□□■■■■□□□□□□□□□□■□□□□□□□
□■■■■■■□□■■□□■■□□□□□□□□□■□□□□□□□
□□□□■□□□■■□□□□■■□□□□□□□□■□□□□□□□
□□■□■□■□□□□■■□□□□□□□□□□□■□□□□□□□
□□■□■□■□□□□□■■□□□□□□□□□□■□□□□□□□
□■■□■□■□□□□□□□□□□□□□□□□□■□□□□□□□
□■□□■□□□□■■■□□□□□□□□□□□□■□□□□□□□
□□□□■□□□□□□■■■□□□□□□□□□□■□□□□□□□
□□□□■□□□□□□□□■■□□□□□□■■■■□□□□□□□





続きはコチラです
http://www.geocities.com/entry_k/main/main01.html

haskellにもgcってやっぱ必要？

というかGCある。

>>35
おまえ生きる価値無し。死ね

Cygwin上で噂のHaskellを使ってみるかー

~/hugs98/src/unix $ ./configure

無事通過。

~/hugs98/src $ make
gcc -c -g -O2 hugs.c
hugs.c: In function `initialize':
hugs.c:278: warning: assignment makes pointer from integer without a cast

あやしい・・・。

~/hugs98/src $ hugs
__ __ __ __ ____ ___ _________________________________________
|| || || || || || ||__ Hugs 98: Based on the Haskell 98 standard
||___|| ||__|| ||__|| __|| Copyright (c) 1994-2001
||---|| ___|| World Wide Web: http://haskell.org/hugs
|| || Report bugs to: [email protected]
|| || Version: February 2001 _________________________________________

0 [main] hugs 1256 open_stackdumpfile: Dumping stack trace to hugs.exe.stackdump
Segmentation fault (core dumped)

~/hugs98/src $ make install
unix/install-sh -d /usr/local/bin
unix/install-sh hugs /usr/local/bin
mv: `hugs' and `/usr/local/bin/#inst.1428#' are the same file
make: *** [install_bin] Error 1

インストールすらできねー俺になにか助言ない？

>>39
何故コンパイルするの?
http://www.cse.ogi.edu/PacSoft/projects/Hugs/pages/downloading.htm#Win32

Windous Installerで一発だったけど・・・なにか？

もー、しょうがねーなー。
Windowsのバイナリの方つかうわい。

>>33
無限精度の計算を行なう枠組です。
Haskel上の実装は遅延評価を用いています。
http://www.dcs.ed.ac.uk/home/mhe/plume/node95.html
http://www.dcs.ed.ac.uk/home/mhe/plume/
http://www.btexact.com/people/briggsk2/XR.html
言語が遅延評価を備えてない場合も実質的に同じ事をやる必要があります。

>>39
WinのバイナリをCygwinの/usr/local/なんたら に置いて
/usr/local/binに、必要なプログラムのシンボリックリンク貼ればOKよ。

何か、有りがちで単純なコマンドラインツールをHaskellで組み直して
「こんな感じで組めるぜ」と提示してみてくれよ。

まずおまえがやれ>45

非常に感動したのが、関数型言語スレで登場していたquicksortです。
これを転載します。
qsort [] = []
qsort (x:xs) = qsort [a|a<-xs,a<=x] ++ [x] ++ qsort [a|a<-xs,a>x]
これは、例えば[3, 2, 4, 6, 1, 8]なるリストがあるとき、
先頭の3より小さいもの[2, 1]と大きいもの[4, 6, 8]に分け、
小さい数字のリスト＋先頭の数字＋大きい数字のリスト、と結合します。
再帰前＞[2, 1, 3, 4, 6, 8]
小さい数字リストと大きい数字リストは再帰呼び出しなので、
完全にソートされる、というわけです。
関数型言語故の、本質を忠実に表現している記述ですね。

>>43
ありがとうございます。無限精度の演算プログラムを作って遊んでいた
ことがあったので、XRに興味があります。私は高速乗算の実装で挫折して
しまいました。ここはHaskellのスレッドなのでこのくらいにしておきます。

>>47
A Short Introduction to Haskell(http://www.haskell.org/aboutHaskell.html)
に書かれているHaskellのQuicksortを見たときは、感激というよりも、
「えっ、こんな風に書けちゃうの！？」と驚異を感じました。それ以来、
ずるずるとHaskellの魅力に引きずりこまれています。
（と言うほど最近はいじっていないのですが…）

>>47
> 関数型言語故の、本質を忠実に表現している記述ですね。

関数型言語というより、ZF記法とlist処理のpowerだと思われ

Prologも美しい。

qsort([], []):-!.
qsort([X], [X]):-!.
qsort([P|X], S):- partition(X, P, L, H), qsort(L,SL), qsort(H,SH),append(SL, [P | SH], S).

partition([], _, [], []).
partition([X|Y], P, [X|L], H):- X<=P, partition(Y, P, L, H).
partition([X|Y], P, L, [X|H]):- X>P, partition(Y, P, L, H).

;; partitionがZF記法の役割。[ | ]はLispの( . ) と同じ。

美しく感じるのは、要素の移動に相当する操作を、
ZF記法(と++)では陽に見えないconsとgcに任せているから。

つかみんななに作ってんの？

放っておいてよ！

いや、今のところ勉強してるだけ。理由はかっこいいから(ﾜﾗ

確かに出来上がったコードが数学的でカッコイイYO

それより、Haskellを構築してる理論の中で難しい研究の成果を使ってるところがｶｺｲｲ

パターンマッチで同じ変数を使えないのはなぜなんでしょう。

たとえば、リストの中からｘをみつけて、それ以降の
リストを返す関数searchなるものを定義すると
search x [] = []
search x (y:ys)
| x==y = y:ys
| otherwise = search x ys
とするとOKなのですが、
search x [] = []
search x (x:xs) = x:xs
search x (y:xs) = search x xs
とすると
Repeated variable "x" in pattern
というエラーメッセージが出ます。

ちなみにPrologでは
search(X,[],[]).
search(X,[X|S],[X|S]).
search(X,[Y|S],Z) :- search(X,S,Z).
でOKなのです。

Prologのようにパターンマッチで同じ変数を使えると便利だと
思うのですが、どうして使えないんでしょうね？

今日初めてHello,worldしてみた。
> の後にコードを書くってに驚いた。

それって*.lhsのファイルですかね?
通常(?)の*.hsだと、>から始めないので平和です。

>>57
そうそう、lhsで作った。
コード主体で書く方法は *.hs か、なるほど。
拡張子でフォーマットを判断しているわけやね。

このスレとか見てるとやっぱり関数型言語にこそプログラミングの未来があると思う。
象牙の塔とか言う人も多いみたいだけど、オブジェクト指向もそうだったんだし。

OOでは一部で「有機的なプログラミング」みたいな考え方があるみたいだけど
そういうのに不信感を抱くんだよね。

って単なるOO批判になってしまったけど。

>>57
*.lhsの「>」形式のコードはクセがあると思いません？

だれかRubyチックに「関数型スクリプト言語」作らないかな？
使いやすくして。

>>59
何が言いたいのかさっぱり分からん。
オブジェクト指向言語と関数型言語は直交する概念だろ。

>オブジェクト指向言語と関数型言語は直交する概念だろ。
状態を持つ/持たないという意味で対立しているようにも思える
解説してちょ

>>62
だからこそ、今後のプログラミングにおける主要な概念は
関数型言語的なアプローチに移っていくだろう、と言いたいわけです。

オブジェクト指向言語と関数型言語って関係あるの？

>>65
むしろ排他的でしょう。

じゃあ、>>62は何の事をいってるの？

Haskellは人の名前なのね

モナドって何ですか？食べ物ですか？

最近関数型言語に非常に重要性を感じてたりするのですが、
日本語のHaskell解説書とかないんですかね？
だれか翻訳しないかな〜

例えば、CSVファイルを読み込んで、各フィールドの合計値を出すだけのプログラムは
どう書くの？
漏れは、Stringをsplitする関数作っただけで疲れ切った。
つか、既存のモジュールにそういう関数（汎用的なwords？）があるのかどうかさえ分からんかったよ。ﾄﾎﾎ
あと、Intを16進数の文字列として出力するにはどうするのか、教えてきぼん。

>>60
> *.lhsの「>」形式のコードはクセがあると思いません？

Knuthの文芸的プログラミングの影響を受けて、
codeとdocumentを同時に書く、ってやりかた。
Mirandaにも同じようなモードがあった。

>>71
実用的によく利用するI/Oのライブラリを整備することは、
実績のあるSchemeあたりでも立ち後れている分野ではあり
ますね。みんな関心がないんだろうなあ。

SML/NJには、yacc/flexをSML/NJで実装したライブラリが
あったと思いますけど、それあたりを参考にすればいける
のでは。

# と思いつつ、僕はHaskellに興味を持ってまだ3日なので、
# 具体的なコードはパス

工科大学の演習問題(11／17)の2番がいまいちわからん。
下の通りでいいと思うんだけどなぁ。
iter :: Int -> (a -> a) -> a -> a
iter n f x = f (iter (n - 1) f x)
iter 1 f x = f x

＞Intを16進数の文字列として出力するにはどうするのか、教えてきぼん

だるだるコードだけどこんなので
toHexCode x　= map ("0123456789abcdef"!!) (toHex x)
toHex x
| q < 16 = q:r:[]
| otherwise = toHex q ++ (r:[])
where q = div x 16
r = mod x 16

ところで俺５５だけど、パターンマッチングの仕組み誰か教えてきぼん

>>75
55の質問には、仕様ですとしか答えられない自分(鬱
Prologは触ったことがないので間違いかも知れませんが、
Prologは論理を記述するから、同じ変数＝同じものとなる(?)のでしょうが、
Haskellは論理記述とは少々異なる雰囲気を醸し出しているので…

参りました。降参します(鬱)

>>66
HaskellにもSchemeにもオブジェクト指向機能があるけど？
OOってのは汎用的な抽象化技術に過ぎないから、特にコンフリクトするとは思わないけどな。
逆にオブジェクト指向型言語を関数型言語みたいな考え方で使うのも楽しい。

>>75
あー、やっぱ自分でそういう関数書かなきゃだめか。
こういう基本的な関数は、普通の開発環境には付属してるような気がしたんだが。

>>55 そりゃすべての typeが Eqのインスタンス (i.e. (==) を持つ)
であるとは限らないから。
でいいかな?
# 東工大で haskellを教えてる先生がいるかと思ってびっくりしたよ..

>>72
\begin{code} ... \end{code}で囲まれている部分にプログラムコードを
置き、それ以外の部分には任意のテキストを書けるというものですね。
ちょっと試してみたことがありますが、良いのかどうか、経験が浅くて
なんとも言えません。どなたかが作られたLaTeXのマクロもどこかに
あったように思います。

以前、HaskellのMLで "Literate Programming"というテーマが上がった
ことがありました。お名前は忘れましたが、\begin{code} ... \end{code}
のスタイルは全然ダメだ、ということを言っている人がいました。
どのような理由でダメだと言っていたのか忘れてしまいましたが、
個人的には毎行頭に > をつけるよりは書きやすいのではないかと
思います。（読みやすいかどうかは保留）

>>74
iter 1 f x の定義を iter n f x の前に持ってこないと再帰が
終わらないです。

大学の演習なので、本文で使っている foldr などを使うことを期待されて
いるのかもしれません。

iter :: Int -> (a -> a) -> a -> a
iter n f x = foldr (\x y -> f y) x [1..n]

[1..n]のリストは単にn回繰り返すためだけのものです。
(\x y -> f y)は引数x, yに対して f(y) を返す関数です。
（つまり、回数カウントのためだけのリストの要素 x を無視する）

あるいは次のように書いても同じです。

iter n f x = foldr g x [1..n]
where g x y = f y

（より簡単に where g x = f とも書けます）

まだ出てなかったので。

お勧め図書：

Conception, Evolution, and Application of Functional Programming Languages, P. Hudak, ACM Computing Surveys, 21(3):359-411.

関数型言語の歴史からHaskellに至るまでのお話が面白い。関数型言語の基本も易しく説明してくれます。

英語ダメダメだけど、洋書買っちゃうゾ〜
お勧め洋書って何かありますかね?＞石敢當さん

HaskellでGtk+, Gnomeライブラリ群を紹介しているらしい
http://www2.ttcn.ne.jp/~aee0372/bindings/haskell.html

>>82
ぞのうち読んでみたいですが、これはACMの会員にならないと
入手できないものなのでしょうか。大学の図書館でも使えれば
いいのですが、大学関係者じゃないものですから・・。

>>71
CSVか〜、関数型言語で使ったことねーよ。
"["と"]"で挟めばList型の表現だから簡単だな。

import IO
calcSum :: String -> Integer
calcSum s = (sum . fst . head) ((reads ("[" ++ s ++ "]")) ::[([Integer],String)])
printSum :: String -> IO ()
printSum s = putStr (show (calcSum s) ++ "\n")
main = do file <- openFile "test.dat" ReadMode
cvs <- IO.hGetContents file
rows <- return (lines cvs)
sequence_ (map printSum rows)

こんな感じでどう？ (offside ruleに気を付けてねー)

IO _型を理解しないと単純なfilterも書けないよ。do, return, sequence_など。

>>55
pattern matchでの制限は、計算がprologと違い一方向であること、
eqの問題、lazinessを制御したいことがあること辺りが理由だと思うけどね〜。
実際、分解とmatchingのruleとformalなsemantics考えるのうっとうしいよね。
eqが複雑なdata typeの場合があるから。ruleによって関数のstrictnessが変わってくるでしょ。

>>85
ほとんどの大学が身分証明書があれば入れるよ。事前に電話して聞いてみれば？
閉架か開架なのかも調べた方がいいな。開架じゃないといろいろ見れなくてつまらないでしょ。

>>86に、http://www.haskell.org/tutorial/書き忘れた。

>>87
ああ、雑誌は学科の図書室にあるのか、図書館にあるのか、も。
図書館の所蔵で学科に置いてあるってのが良くあるパターンなので。

CSVファイルをエディタでhaskellなりschemeなりのリストに書き換えちゃうのって
反則？ ほとんど手間はないんだけど。

>>83 お勧め洋書って何かありますかね?＞石敢當さん

Haskellの本で持っているのは >>24 に書いたSOE本1冊だけですので、
「これがいいよ」と薦められるほど知っていません。

本当は http://www.haskell.org/bookshelf/ に載っている、
Haskell: The Craft of Functional Programming または
Introduction to Functional Programming using Haskell を
予約するつもりで洋書屋さんに行ったのですが、たまたまSOE本が棚に
乗っていて、現物を見たら買わずにはいられず買ってしまったのです。
SOE本には"Learning Functional Programming through Multimedia"
という副題がついていて、Haskellでマルチメディアをやろうとは
思っていなかったので違う本にしたかったのですが、買って読んで
みたところ読みやすいように感じました。
Haskellの解説の章とグラフィックスを使った演習みたいな章が
交互に出てくるような構成になっていて、色々と楽しめました。
Hugs用のグラフィックスライブラリがあったのですが、最新の
"Feb 2001 version"では使えなくなっているようなのがちょっと残念です。

>>7 に書いた、Chris Okasaki氏の本ではMLのコードが使われて
いますが、巻末にHaskellのコードも掲載されていますのでHaskellの
学習にも使えるかもしれません。ただ、この本は私にとっては手ごわい
です。SOE本は「ふむふむ」とか「なるほど！」などと思いながら、時々
辞書を引いて読み進むことができましたが、Chris Okasaki氏の本は
やたらと知らない単語が出てくるので辞書を引いてばかり、まるで英語の
授業の予習をしているような気分になります。単に私の英語力がないだけ
なのですけれども、勝手ながらコンピュータの本は平易な文章で書いて
欲しいなと思いました。というわけで、こちらはほとんど読めていません。

書籍も良いですが、もしまだお読みになっていなければ
A Gentle Introduction to Haskell Version 98
を一度読まれると良いと思います。このスレッドのおかげで
邦訳( http://www.sampou.org/haskell/tutorial-j/index.html )が
あることを知りました。私もモナドあたりで挫折しているので、
邦訳版を読み直してみようかと思っています。

↑ごめんなさい。長すぎでした。

>>87
身分証明書は運転免許証などでいいのでしょうか？
ACM Computing Surveys を置いてあるかどうかも問題ですね。
そのうち調べてみます。ありがとうございました。

55だけど、76、86さんありがとさん。

パターンマッチのこと、俺も考えなおしてみた。
Prologは述語論理式で同じ変数が２度でてもおかしくないけど、
Haskellは関数で、仮引数に同じ変数が２度でると、確かに
おかしいな。
　述語論理式で　f(X,X)　としても全然OKだけど、
　関数の仮引数で　f(x,x)　とするのは確かに変な記述だ。

もうひとつ質問なんだけど、
エラーやら無限大やら、定義できない値を表現するＴをさかさまに
した＿｜＿というやつ、実際にHugs98でどのようにコードするの
か教えてくれ。

f x
| エラーの起こる条件 = error "error message"
とかかなぁ。
これは簡単なエラーメッセージを出力する方法だけど、
エラー処理でしか書けないような?

>>92
>エラーやら無限大やら、定義できない値を表現するＴ
lispならそういう場合、単に適当な未定義のシンボル
（infinityとか）置いておくだけだと思うけど、
haskellってそういう場合どうすんのかね。なんかあるの？

オンラインで関数型言語周りのプログラミングの独学教材でいいのありますか？
やっぱりSICPとかいわれているSchemeのやつですか？

あれもpdf化されるとよさそうですけどね

ところで、Concurrent Cleanって知ってますか？
並列プログラミングをサポートしたHaskellの発展形のような
感じのものなんですけど？　どうでしょう？

>>92
> エラーやら無限大やら、定義できない値を表現するＴをさかさまに
> した＿｜＿というやつ、実際にHugs98でどのようにコードするの
> か教えてくれ。

扱えない。そもそも未定義な値がbottomなんだから。
ある時に明示的に値を未定義にしたいならば、そこで、

bottom = bottom

とでも定義しておいて使えばいいけど、普通はexception使うよ。
ちなみにghcでこの式使うと無限ループでexceptionが起きるよ。

>>89
やっぱ、一番敷居が高いのはmonadの考え方とその利用だと思うよ。
それさえこなせば、後は簡単。文字列操作は(効率はともかく)非常に得意。
なんせ文字列は文字のリストだから。リスト処理はギャフンと言うくらい強い。

>>95
> オンラインで関数型言語周りのプログラミングの独学教材でいいのありますか？

>>90に上がっている奴でいいんじゃないの？
Monadは載ってないけど、武市正人(訳). 関数プログラミング. 近代科学社, 平成3年(1991).
(原著: R.Bird and P.Wadler. Introduction to Functional Programming. Prentice-Hall, 1988).
はめちゃ「(BakusのFP的)リスト遊び」が楽しい本。

>>99
そういや、その訳者の人の授業受けたよ。

>>96
ちょっとだけ説明があった
http://www.sra.co.jp/people/nishis/learning/fpl/stairway.html

こっちから見た方がいいかも
http://www.sra.co.jp/people/nishis/learning/fpl/index.html

>>97
>扱えない。そもそも未定義な値がbottomなんだから。

やはりそうか。

「関数プログラミング」バード著にでてくる
擬リスト（partial list)なんかは表現できないわけか。

普通のリストは基底に空リスト[]をもってくるが、
擬リストは基底にbottom（さかさまＴ）をもってくる。

　普通のリスト　1:2:3:[]
　擬リスト 1:2:3:bottom

無限リストを擬リストのリストの極限と定義すると
便利そう。擬リスト使う方法だれか工夫してくれ。

> 擬リスト（partial list)なんかは表現できないわけか。

これならpseudo bottomで十分だから、

bottom = bottom

でよい。
実際のbottomは、未定義になる式全体と同等である仮想的な対象。
∞みたいなもの。

>>96
なにはともあれ、FAQ。
http://www.cs.nott.ac.uk/~gmh//faq.html#clean

並列系は総じて仕様が美しくない。ちなみにghcにもPVMで実行するoptionがある。
data parallelのNESL(http://www.cs.cmu.edu/~scandal/nesl.html)は面白い。

＞＞104
＞これならpseudo bottomで十分だから

ほんとだ、コロンブスの卵だ

(1:2:bot) ++ (3:4:[]) where bot = bot

とすると　[1,2 {Interrupted}

すごいすごい。partial list ですね。

このスレッドすごく役立つ。１０４サンキュー。

「関数プログラミング」すごくいい本だけど、haskellについては
触れていないことと、練習問題の解答がないことが難なんだよね。

>>106
Web上に転がってるかもしれないですよ
（昔SICPの解答は見つけたので）

ちょと訂正。

> 実際のbottomは、未定義になる式全体と同等である仮想的な対象。
> ∞みたいなもの。

未定義になる式「全て」。(そのような式の「集合」ではない)

あと、>>86のprogram滅茶苦茶なseparationだな。恥かしぃ...

import IO
getList :: String -> [Integer]
getList s = (fst . head) ((reads ("[" ++ s ++ "]")) ::[([Integer],String)])
printlnInt :: Integer -> IO ()
printlnInt i = putStr (show i ++ "\n")
main = do file <- openFile "test.dat" ReadMode
cvs <- IO.hGetContents file
rows <- return (lines cvs)
sequence_ (map (printlnInt . sum . getList) rows)

こうしないと機能単位に分かれてないな。U2 that she know...

-- hGetContentsの関数名は処理系選ぶと思います。GHC 5.0を使ってます。

型、型変数、型コンストラクタ、型クラスの関係がわからん。
Javaにたとえれば　型がクラスで、型変数がオブジェクト、
型クラスがスーパークラスないしインターフェースといった
ところか。でもいまいちJavaにたとえるのは概念的に違う感じ
もあるな。このへん　すっきりした説明　お願い。

>>110
型変数とオブジェクトはまるで違うものだろ。

型のお勉強のため自然数型を作って、
たし算とかけ算の証明をしてみた

data Sizensu = Zero | Next Sizensu　deriving (Show)
tasu Zero x = x
tasu (Next x) y = Next (tasu x y)
kakeru (Next Zero) x = x
kakeru (Next x) y = tasu (kakeru x y) y

２＋３＝５は
tasu (Next (Next Zero)) (Next (Next (Next Zero)))
-> Next (Next (Next (Next (Next Zero))))

2 * 3 = 6は
kakeru (Next (Next Zero)) (Next (Next (Next Zero)))
-> Next (Next (Next (Next (Next (Next Zero)))))

ということで、正の数については順調。

で、負の数も含めて整数型に拡張したいのだが、これなかなか
うまくいかない。
（−２）＊　（−３）＝　６
をやってみてくれ。

>111
>型変数とオブジェクトはまるで違うものだろ

型がクラスとすると、型変数は型の要素だからオブジェクト
と、単細胞に思ったが、違うと言われればそうだな。
型変数は型の要素ではなく、変数だから型のハンドルか。
ということはクラスか。

いかん、混乱してきた。

>>110
type: 一般名詞としての型あるいはHaskellの単純型

type class: Haskellにおけるクラス
constructor class: Haskellにおけるクラス(Jonesによる新用語)

type constructor: Haskellにおけるコンストラクタ
constructor: Haskellにおけるコンストラクタ

type variable: 型を値にとる変数

>>112
負の数を表現できない"Sizensu"で、負の数を扱おうとするのは無理難題。

型変数は C++のtemplateにおける...なんていうんだ。述語知らん。
Javaには現在ない概念。JDK1.5になったら入るかも?

type constructorは型を取って型を返す関数のような
[]: *→* (,): *→*→* (か?)
constructor classは type constructorのクラス (特定の操作を持ったもの)
だね。mpjえらい。つーかそのために gofer作ったってほんとか?

goferの source見ると、8086の compactモデルで使えるように、TurboCで
compileできるように書いてあってちょっと嬉しかった。当時 DOS machineしか
持ってなかったし。

>>112
自己レスだけど、「関数プログラミング」に以下のような
感じで書いてあった。

自然数はゼロとある数の次の数を指定する方法で作成できる。
マイナスを含めた整数は自然数にある数の前の数を指定する方法を
追加するとできると思うだろうけど、でもそれではなかなかうまく
いかないんだよ。
これ練習問題にとっとくから、自分でやりなさあい。
まいった。

つーか基礎数学論の領域に入ってきてるような、、、
関数言語ってそのための物なのか？

つーか基礎論そのものが、もはやコンピュータサイエンス用の応用数学じゃん。

工科大のテキストを読んでいます。

11/17の課題より：
「整数リストに対し，正の要素の2乗の和を返す関数を定義せよ．」

これは簡単に書けます（インデントが分かるように > を入れました）：

>func1 :: [Int] -> Int
>func1 [] = 0
>func1 (x:xs)
> | x > 0 = x * x + func1 xs
> | otherwise = func1 xs

やっていることは明らかだと思います。
ただ、リスト処理関数 zip, filter, map などの説明の後にある
課題ですので、これらを使用した定義が期待されているのでしょう。
次のようなものを作ってみました。

>func2 :: [Int] -> Int
>func2 xs = sum (map (\x -> x * x) (filter (> 0) xs))

これも右辺を右側から見ていくとやっていることは明らかです。まず
filter で正の要素のみを抽出し、map で各要素を2乗し、sum で和を求める。
しかし、filter, map の処理が終わるたびに新しいリストが生成され、
func1 よりも効率が悪いのではないか、という気がします（本当かな？）。

（続く）

（↑の続き）

func2 をちょっと書き換えると次の定義が得られます：

>func3 :: [Int] -> Int
>func3 = sum . map (\x -> x * x) . (filter (> 0))

func2 と func3 とでは、処理効率に違いがあるのでしょうか。
いずれ profiler でも使って調べてみたいところです。

また、これら3つの定義に（処理速度以外の点で）何か優劣が
あるでしょうか。

>>119
func1 のほうが中間のリストを生成しない分効率がいいと思います。
deforestation とかなんとかいう(うろ覚え)最適化の手法は、
func2 のような中間構造の生成を回避して、func1 のような定義を
導く手法ではなかったかなあ。言葉だけ覚えていて、内容をしらない。^^;;

>>120
３つとも処理効率はほとんど同じと思う。
リストの長さをNとすると、O(N)だろう。
>>121
>func1 のほうが中間のリストを生成しない分効率がいいと思います
Haskellは最外簡約法だから、この場合Lispと違って中間リストなんか
生成しないだろう。

違ってたらごめん。

型変数まだよくわからないが、
現時点で型変数についての想像を書くと

CとかJavaとかでは int x; と書くと、ｘは整数型の変数で
1とか２とか−999とかを指示するものなのだが、
型変数というのは、その型の要素を指示するようではない
らしい。その型そのものを指したり、その型から継承される型
を指したりするんじゃなかろうか。

ちゃんとした本読んだ方がいいんじゃない？>123

>>119-122
hugsで試したところ、func1が 89reductions
func2が 96reductions
func3が 98reductionsでした。
ただ、リストの中の負の数が増えると func3が func1を下回りました。
まあよくわかんないけど、func3の書き方が関数型っぽくて
かっこいいと思いました。

>>118
なーるほどね、納得

>>121
ごめんよ。おれ122だけど、言っている意味取り違えた。
「中間のリストを生成」をリストの結果を生成と読んでしまった。
121の言っているのは　(a:bottom) bottomはこの場合、まだ計算
や簡約されていないものを指す。　という意味のリストを生成する
と言ったんだろう。

>>125
無限リストに適用して速さ比べするのは

たとえば、[1,-2,3,-4,5,-6....] といったリストの部分リスト
のリストを作ってfunc1,2,3を適用してみると

inits [] = [[]]
inits (x:xs) = [[]] ++ map (x:) (inits xs)
func1' xs = map func1 (inits xs)
func2' xs = map func2 (inits xs)
func3' xs = map func3 (inits xs)
suretu :: [Int]
suretu = [ (-1)^x * x | x <- [1..] ]

func1' suretu -> 0,0,4,4,20,20,56,56....

初心者です、私も仲間にいれてくれ〜
ど素人質問です
http://www.teu.ac.jp/kougi/koshida/Prog6/Text03/index.html
ここ読みながらやってるんですけど、

type hoge = ( Int , Int )
maxThreeAux :: Int -> hoge-> hoge
maxThreeAux a b
　　| a < fst( b ) = b
　　| a == fst( b ) = ( a , snd( b ) + 1 )
　　| a > fst( b ) = ( a , 1 )

maxOccursThree :: Int -> Int -> Int -> hoge
maxOccursThree a b c = ( maxThreeAux a ( maxThreeAux b
　　( maxThreeAux c ( 0 , 0 ) ) ) )

とすると type の行でエラーがでるんです。
type ってどこに書けばいいんでしょう？

すなおに、これなら動くんですけど・・・
maxThreeAux :: Int -> ( Int , Int ) -> ( Int , Int )
...

>>129
http://www.sampou.org/haskell/tutorial-j/goodies.html
> 読者のみなさんは気づいたでしょうか、特定の型を表わす識別子は大文字ではじまっています。たとえば、Integer や Char です。また、 inc のような値を表わす識別子は小文字ではじまっています。これは単なる習慣ではありません。Haskell の構文規則でそうすることになっているのです。また、先頭の文字だけではなく、そのほかの文字も、大文字か小文字かということは重要で、foo と fOo と fOO はすべて違う識別子として区別されます。

hoge を Hoge にしなされ、ってこと。

>>130
おお、早速のレスありがどうございます。
もう三十半ばも超えて、プログラマだいぶもうろくしとります。
早速試したところ、巧くいきました。

Haskellの文法についての日本語解説書がなくて困っていたが、
よい本があった。
　岩波講座ソフトウエア科学４　プログラミング言語
　武一正人著　3000円
著者は「関数プログラミング」の訳者。
プログラミング言語全般の特徴を関数型言語をメタ言語として
解説するということですが、実際上関数型言語の解説書となって
おります。
HaskellではなくGoferの解説となってますが、文法はまったく
同じみたいです。このままHaskellの教科書になるような感じ。

<<132
大事なこと書くの忘れた。
オレこの本読み始めで、まだ30ページしか読んでない。
132はその上での感想。

古本屋（明倫館）で2000円でゲットしてきた。

http://www.geocities.co.jp/SiliconValley-Oakland/1866/

>>121
リストを食って、結果を生成する状態遷移機械に翻訳します。
http://www.research.avayalabs.com/user/wadler//topics/deforestation.html
Wadlerの初期の論文の方がこれより着眼点が分かりやすいです。

>>116
Nextだけじゃなくて、Prevも作って、
data Seisu = Zero | Next Seisu　| Prev Seisu deriving (Show)
するだけですよ。後は力業。

純粋λ計算でやる時はもうちょっと違うやりかた。

>>136
Church Numerals ? これって、負の数はどう表現するんですか。

IOモナドはなんとなくわかるが
それ以外のモナドはなんのためにあるのかわからん。

誰か教えて。

http://calypso.score.is.tsukuba.ac.jp/~okuma/functional/monad.html
なんとなくわかったような、わからんような…

>>139
このリンクの人わかってないね．
副作用である状態遷移と関数の入出力を混ぜて説明しちゃいかんよ．

>>140
状態遷移を副作用と呼ばずに、関数の入出力ということにしよう
ってのがモナドなんだから、良いんじゃないの？

age

　 ∧＿∧　　／￣￣￣￣￣￣￣￣￣
　（　´∀｀）＜　モナドって何モナー
　（　　　　）　 ＼＿＿＿＿＿＿＿＿＿
　｜ ｜　|
　（＿_）＿）

ああっ、つい。ごめんなさい…。

イスラエルの諜報機関だ。
…くっ、ノックの音がする。後は頼んだ……ぐはっ

>>137
> Church Numerals ? これって、負の数はどう表現するんですか。

2 ≡ λfx.f(fx) ってやり方の延長だと負の数は無理です。

>>144
あー、最初なんのことだかサッパリわからんかったよ。
一応、、、

それはモサドだろっ！！

関数型言語やるならラムダ計算とかの勉強もしたほうがいいのか?

したほうがいい、っていうか自然にやることになるのでは。
SNとか Yコンビネータは知らなくても大丈夫だとは思うが。

>>148
やはりそうですか。

↓がよく理解できず鬱です…。
http://members.tripod.co.jp/nbz/ref/lambda.html

>>125
調べて頂いてありがとうございました。

>>138 それ以外のモナドはなんのためにあるのかわからん。

十数年前、初めてC++の本を読んだときもあまり理解できませんでした。
書いてある中身自体（例えばクラスとそのメンバ）については分からなくも
ないのですが、一体クラスの何が便利なのか？ありがたいのか？という
ことを実感として得られなかったのです。
Monadについても似たような感じを受けています。便利さ・ありがたみを
実感できるときっと「分かった」という気になれるのでしょう。

>>144
板間違えかと思いました。>>146を読むまで気づかなかった…

'`'を使って第二引数を部分適用するのは邪道なんだろうか?
(`map` [1,2,3,4]) (<3)

あと、'-'の第二引数を部分適用できないのがちょっと…
(+ (-7)) みたいに書くのもなんかなぁ。

>>151 あと、'-'の第二引数を部分適用できないのがちょっと…

(+ (-x)) のように書いても勿論OKですが、このような場合のために
subtract :: Interger -> Interger -> Interger がPreludeに用意されて
います。去年のメーリングリストで知りました。
http://www.mail-archive.com/[email protected]/msg06737.html

>>149
そのページの別のところでIE5のブラウザがクラッシュするページがあるよ、
修正してもらえるとうれしいのぉ。
せっかく興味深いページなのにのぉ。
ついでにトライポッドは広告ウインドウがウザイのぉ。
読ませてもらってる分際でいうことじゃないけど・・・

>>151
> あと、'-'の第二引数を部分適用できないのがちょっと…

二項演算子と単項演算子の二つに兼用される'-'ちゃんは、ちょと可哀想。
部分適用がない言語では問題にもならないが。

>>147
> 関数型言語やるならラムダ計算とかの勉強もしたほうがいいのか?

いいかどうかは分からないが、関数型言語面白い人は面白いと思うが。
http://www.amazon.co.jp/exec/obidos/ASIN/4320023773/t/249-4845079-9009138
あたりだとprogramming言語よりで面白いんじゃないかな。
純粋型なしλ式での負の数の表現も載ってるよ。

>>153
> ついでにトライポッドは広告ウインドウがウザイのぉ。

Javascript off or w3mだから、tripodが広告window出すって知らなかった…
今"page source"して始めて知った。mmmの人はいるのかな？

演算子って再定義できなかったっけ？

>>151 flipつかえばいいやんけ! って思ったら
subtractの定義はそうなってた。hugsの場合。

工科大の最後の講義に、整数リストの各要素の4乗の和を求めるコードが
載っています。
http://www.teu.ac.jp/kougi/koshida/Prog6/text13.html より：

sumFourthPowers n = sum (map (^4) [1 .. n])

これの計算過程の説明もありまして、それによると頭から順に4乗を
計算してsumに送り込んでいるようで、ともかく、[1,16,81,...]
という中間リストは生成されないのだそうです。>>122で
「Haskellは最外簡約法だから…」と書かれているのはこのことを
さしていたのでしょうか。

そうしますと、>>119で私が書いたfunc2の例でも中間リストなどは
生成されず、効率良く処理されるのかもしれません。

なかなか奥が深いものです。

日本語通る？

putStrなどは、8bit through。しかしただそれだけ。

ocaml(http://www.ocaml.org)は日本語化されたものがあります。
Web browser, MMMも日本語化されていました。
http://caml.inria.fr/archives/200005/msg00082.html

どうも状態ベースで考えてしまう。
えらいこっちゃ

結構はげしいのお、東工大の授業は。

Haskell 始めてやっと一週間だが、わしは自分のことをけして
トーシロとはおもっとらんが、内容キツイ。
「リストを扱うプログラム (2)プログラムに対する推論」
まで、やっとたどりついたが、かなり息切れ気味じゃよ。
証明のコツなかなかつかめん、これは数日ではムリだ、
今週の課題になってしもうた。

基底＝公理みたいなもんかい？
置換でゴリゴリ押していって、同一になる手順を探し出せっちゅう
ことなんだろうけど、黄金パターンみたいなのはそう簡単には
できそうになさそうじゃ。
むずかしいのぉ。
他にも勉強せんにゃならんもん多かろうに、学生はがんばるのぉ。

>>599
でも、THashedStringListって、なんでClassesじゃないのかな？
IniFilesユニットなんかに入れないでほしかった。
あと、TColorBoxって色が漢字で表示できるよね。
その色の漢字（"黒"とか"赤"）が配列に直接書いてあったよ。
別に使わないからいいけど。

>>161
> 基底＝公理みたいなもんかい？

基底式は、自然数上の帰納法だとn=0の式、
リスト上の帰納法だとn=[]の式、のような奴らの事。
数学的帰納法の終端になるから、基底。

難しい漢字使っているけど、要するにbase。難しく考える事ない。

この週は数学的帰納法の証明があるから、慣れないと難しいかもね。
けど、慣れればなんて事ないと思う。

text07は関数型言語版design patternですね。

普通、東工大っつーと東京工業大学の事。
話題のページは東京工科大学にある。

東京工業大学はめちゃくちゃ頭のいい大学として有名。
東大京大の次ぐらいかな。

学歴板へｶｴﾚ!

間違いを指摘しただけでしょ。

SOE本のExercise 9.9より

「関数fixを、fix f = f (fix f) と定義した場合、fix の型は何か？」

fix fの型をaとするとfの型が a -> a となるので、fixの型が
(a -> a) -> a であることはすぐに分かります。これはいいのですが、
ではこの fix という関数は一体何を意味しているのか、これが
どうも分かりません。

実はこのExerciseには続きがあります。

>remainder :: Integer -> Integer -> Integer
>remainder a b = if a < b then a
> else remainder (a - b) b

これはaをbで割ったときの余りを求める簡単な関数ですが、
このように定義された関数 remainder を関数 fix を使って再帰的でない
ものに書き換えよ、という設問です。

色々考えてはみたものの、答えを得るには至りませんでした。
設問には "tricky!" と書かれているので、ウラ技的なことを
しないといけないのかもしれません。

>>168
トリッキーというよりは不動点による再帰の理論的意味づけを
そのままプログラムとして書くとどうなるかという話ですね．

fixは関数を引数に取りその関数の不動点（fixed point）を返す関数です．
ある値xがfの不動点であるとはf xの値が元のxであるということです．
fix f = f (fix f)ですからfix fはfの不動点になっています．

するとこれを利用して再帰的に定義される関数を直接定義することができます．
例として次の再帰的関数を考えましょう．
remainder a b = if a < b then a else remainder (a - b) b
このときまずfを次のような関数とします．
f = \g -> (\a -> (\b -> if a < b then a else g (a - b) b))
remainderの定義のremainderのところを変数gに置き換えたような
形をしていますね．この関数の型は
(Integer -> Integer -> Integer) -> (Integer -> Integer -> Integer)
です．これにfixを適用してやります．するとこの場合fix fの型は
Integer -> Integer -> Integer
となります．このfix fがremainderに対応する関数です．
例で試してみましょう．

(fix f) 12 5
-> (f (fix f)) 12 5
-> if 12 < 5 then 12 else (fix f) (12 - 5) 5
-> (fix f) 7 5
-> (f (fix f)) 7 5
-> if 7 < 5 then 7 else (fix f) (7 - 5) 5
-> (fix f) 2 5
-> (f (fix f)) 2 5
-> if 2 < 5 then 2 else (fix f) (2 - 5) 5
-> 2

もう少し詳しいことを言うと一般には関数の不動点は一つとは限りません．
ここで述べているのはその中で「情報量が最小」なものを
選んでいることに当たります．
つまり普通の再帰的定義で計算される情報だけを返し
それ以上の情報をもたらさないような関数を
不動点として選んでいるということです．
このあたりの正確な議論が知りたい人は関数型言語のスレで挙がっていたような
プログラム言語の意味論のテキストを参考にしてください．

>>169
早速ご助言を頂きありがとうございます。
fixが不動点を返す関数であること、fix f で余りの計算ができる
ことなどは分かりました。分かったような気がしているだけかも
しれません。
大変勉強になりました。

「情報量が最小」の意味など、分からないこともありますが、
意味論のテキストなどを調べて勉強してみたいと思います。

素数の無限リストを効率よく作れます?
自分はいくら考えても激しく遅いのしか思いつかない…。

http://www.teu.ac.jp/kougi/koshida/Prog6/text13.html
ここにあったや……

実は、>>169の「関数の不動点を返す」という箇所を読んだとき、
例えば、

>f :: Int -> Int
>f x = 2 * x - 1

と定義すると fix f が 1 を返すのかと（ちょっとだけ）期待して
しまいました。これはうまくいかないですね。これがうまくいく
ということは、

>x = 2 * x - 1

とやったら x = 1 が得られるというのと同じことですものね。

＞プログラム言語の意味論のテキストを参考にしてください．

図書館へ行って「プログラミング言語理論への招待」という本を
借りてきました。副題が「正しいソフトウェアを書くために」と
なっています。「再帰の数学」という章があって、ここでは
かなりのページをさいて関数の不動点について説明されています。
「最小の不動点」という節もありますが、これが>>169に書かれて
いる「情報量が最小」ということなのでしょうか。じっくり読んで
みようと思います。

この手の本を読むのは全然嫌いじゃない、というか結構好きですが、
このような理論を理解してからでないとHaskellの「良い」プログラムが
書けないのだとしたら、やはりHaskellはちょっと敷居の高い言語
なのかな、という気もしました。

>>173
その本は関数プログラミングとは少しだけ、ずれてない？
たしかに重複する部分もたくさんあると思うけど。
EiffelとHaskellって全然違うし。

>>173
お盆でも図書館が開いているのですね．
そうです，最小不動点のことです．
その本なら多分きちんと書いてあるでしょう．

まあ，不動点を使ったプログラミングは
実用的なプログラムでは絶対必要な知識というわけでもないと思います．
上の例ではfixを定義するのにそもそも再帰を使っているのだし，
再帰で書けるのなら再帰を使えばよいだけのこと．
それよりもHaskellならモナドを理解するほうが大事でしょう．

言語設計としてはたとえ理論的には複雑でも
それを知らなくても良いプログラムが書けることがとても大切だと思います．
例えばC++のI/Oストリームなんて型はかなり複雑ですが
それを意識しなくても書けますからね．
この意味でHaskellのモナドはもう少し工夫の余地があると思います．
あれこそ理論を知っているほうが「良い」プログラムが書ける
という言語設計じゃないかな．
関数A->BをA->m(B)と考えるのが計算のモナドの本質であることは
言語仕様からは中々理解しづらいのでは．

>>173,174
あ，本を間違えていました．岩波の二分冊の本のつもりでした．
174さんのおっしゃるように
Mayerさんの本ならば関数型にかぎらずいろいろなトピックがあった
ように思いますが，最小不動点の基本的な部分は
多分使えるのではないかと思います（手元にないのでわかりませんが）．

>「プログラミング言語理論への招待」という本を
昔買っちゃったけど、あの本の内容、ｻﾊﾟｰﾘわからんかった。

age

皆さん、勉強してますな。
小生もラムダ計算とやらを勉強するために、
「岩波ソフトウエア講座12　計算理論の基礎理論　井田哲雄著」
を古本屋でゲット。
ほとんど数学のお勉強になってきた。

そう言えば、数式ソフトのマスマテカって関数言語だよね？

>>179
自己レス。本の名前間違えた。
（誤）計算理論の基礎理論
（正）計算モデルの基礎理論

マセマティカ

>>179-180
その本をうちの研究室のM2の人が読んでますが、教官は「肝心のところで
あやふやな部分がある」と憤慨してました。M2の人は「わかりやすい」と言ってました。
私自身はまだその本を読んではいないのですが、
「数理情報学入門 ― スコット・プログラム理論」中島玲二著 朝倉書店
「プログラム言語の基礎理論」大堀淳著 情報数学講座９ 共立出版
を読み始めたところです。
「プログラム言語…」の方は大型書店にいけば売ってますね。

なんだか関数型言語のスレに以前あったような話になってきましたね．

>>182
> その本をうちの研究室のM2の人が読んでますが、教官は「肝心のところで
> あやふやな部分がある」と憤慨してました。M2の人は「わかりやすい」と言ってました。

あの本はたぶんオムニバス的に眺めるという趣旨で書かれた本なのでしょう．
あまり数学的にきちんと突き詰めて理解するようには書かれていなかったと思います．
（中身を見たのがだいぶ前なのであやふやですが）．
その教官は理論をちゃんとやってきた人なのでしょう．

> 「数理情報学入門 ― スコット・プログラム理論」中島玲二著 朝倉書店
> 「プログラム言語の基礎理論」大堀淳著 情報数学講座９ 共立出版

これらはきちんと書かれています．が，その分とっつきにくいかもしれません．
理論を研究で使うならこれらをしっかり読むのはとても良いことだと思います．
ぜひぜひがんばってくださいな．
つーか，182さんがどの辺の人かわかってしまいそう．

それから言うまでもありませんが
Haskellプログラミングそのものにはこういう話は別に必要ありません．>all
むしろプログラミングが得意な人にはがんがん環境を整備して欲しい．
今どきのプログラミングは充実したライブラリがないと中々難しいし．
やっぱりHaskell.NETに期待か？

そういや、Haskell.NETあったな。
すっかり忘れてたが、笑える。

>>184
いや，Peyton-JonesがいるからMSRではやるんじゃない？
それに趣味で実装する分には面白そうかも，とちょっと思ったり．
.NET関係のきちんとした仕様書って手に入るのかな？
Linuxとかでやってる人はどうしてるんだろう？

このスレって.NETとか、そっち方面には疎い人多そう。

ふぅ、徹夜してしまった。
でも、だいぶん証明にもこなれて来ました。
http://www.teu.ac.jp/kougi/koshida/Prog6/text06.html
をやっと突破できました。

コツは

１．証明が必要なものと、証明不要なものをしっかりと分類して整理する。
２．帰納するときの直前直後の要素を混同しないよう、記号をはっきりと意識する。
　要するに、証明すべき P(xs) -> P(x:xs) の xs および x:xs に注目する。
３．証明の最初は、帰納法の仮定 hyp 目指して置換してゆく。

ちゅう事なんですね。

今週の成果です。

勘違いは、ないでしょうか？
暇な方いらっしゃいましたら添削お願いします。
記号は私の好みで勝手に変えてしまいました。

全ての有限リスト a ，b 及び c に対し次の式を証明せよ
a ++ [] == a　　　　　　　　　　　　　　　　　(++3)
a ++ (b ++ c) == (a ++ b) ++ c　　　　　　　　(++4)

-------------------
(++) の定義
[] ++ ys == ys　　　　　　　　　　　　　　　　(++1)
(x:xs) ++ ys == x:(xs ++ ys)　　　　　　　　　(++2)

-------------------
(++3)の証明
　[] ++ [] == []　　　　　　　　　　　　　　　(base:要証明)
　(ah:at) ++ [] == (ah:at)　　　　　　　　　　(ind:要証明)
　at ++ [] == at　　　　　　　　　　　　　　　(hyp:証明不要)

　------------------
　(base:要証明)の証明
　[] ++ [] = []
　[] == []　　　　　　　　　　　　　　　　　　(++3)
　証明終わり

　------------------
　(ind:要証明)の証明
　(ah:at) ++ [] == (ah:at)
　ah:(at ++ []) == (ah:at)　　　　　　　　　　(++2)
　ah:at == (ah:at)　　　　　　　　　　　　　　(hyp:証明不要)
　証明終わり

(base:要証明)および(ind:証明不要)より
a ++ [] == a
証明終わり

-------------------
(++4)の証明
　[] ++ (b ++ c) == ([] ++ b) ++ c　　　　　　(base:要証明)
　ah:at ++ (b ++ c) == (ah:at ++ b) ++ c　　　(ind:要証明)
　at ++ (b ++ c) == (at ++ b) ++ c　　　　　　(hyp:証明不要)

　------------------
　(base:要証明)の証明
　[] ++ (b ++ c) == ([] ++ b) ++ c
　b ++ c == b ++ c　　　　　　　　　　　　　　(++1)*2
　証明終わり

　------------------
　(ind:要証明)の証明
　ah:at ++ (b ++ c) == (ah:at ++ b) ++ c
　ah:(at ++ (b ++ c)) == (ah:at ++ b) ++ c　　(++2)
　ah:(at ++ (b ++ c)) == ah:(at ++ b) ++ c　　(++2)
　ah:((at ++ b) ++ c) == ah:(at ++ b) ++ c　　(hyp:証明不要)
　ah:((at ++ b) ++ c) == ah:((at ++ b) ++ c)　(++2)
　証明終わり

(base:要証明)および(ind:証明不要)より
a ++ (b ++ c) == (a ++ b) ++ c
証明終わり

ところで、ここの課題2の問題
sum (xs ++ ys) = sum xs ++ sum ys
は、
sum (xs ++ ys) = sum xs + sum ys
の誤植かと思われますが、先生はこのスレッドを見ていらっしゃいますでしょうか？

さて、来週は楽になるかのぉ

>>187, >>188
＞暇な方いらっしゃいましたら添削お願いします。
あんまり暇じゃないですが…

＞(ind:要証明)の証明
＞(ah:at) ++ [] == (ah:at)

A = B の証明をするのに、A = B から書き出すのは良い書き方では
ないと思います。普通は
　　A = ...変形をしてゆくと... = B、 よってOK、
とか
　　A = ...変形すると... = X, B = ...変形すると... = X、
よってA = Bなどと書くのが一般的と思います。

内容は間違っていないように思います。

http://www.teu.ac.jp/kougi/koshida/Prog6/text06.html 課題１にある
「シーケンス」という言葉を見て思い出しました。

http://www.teu.ac.jp/kougi/koshida/Prog6/Text12/index.html
ここの問題2です。

リストの全サブリストを返す subLists という関数、
リストの全サブシーケンスを subSequences という関数を定義せよ、
という問題です。

subLists は簡単で、与えられたリストを x:xs とすると、xsの
サブリストを再帰的に求め、各々の要素に x を含むものとそうでない
ものを考えれば良いので、例えば次のように定義できます。

>subLists (x:xs) = [e | ys <- subLists xs, e <- [x:ys, ys]]

subSequences の要素は、元のリストの先頭または末尾からそれぞれ
連続した任意個の要素を省いたものなので、
　　sub1 [x1,x2, .. ,xn] = [[x1, .. ,xn],[x2, .. ,xn], .. ,[xn]]
　　sub2 [x1,x2, .. ,xn] = [[x1, .. ,xn],[x1, .. ,x(n-1)], .. ,[x1]]
となるような関数を定義してなんとか作ることはできましたが、
もっとすっきりできないかと思案中です。subLists 程度の簡単な
関数を作れると良いのですが…。

>>190
石敢當さんの言ってるのだと
subSequences [1,2,3,4] =>
[[1],[1,2],[1,2,3],[1,2,3,4],[2,3,4],[3,4],[4]] -- []も入るのかな？
のようになるような感じですが
問題のほうを読むと、[2,3]も入ってないといけないような気が…。

>>191
[1,2,3,4]の場合ですと、
sub1 [1,2,3,4] = [[1,2,3,4],[2,3,4],[3,4],[4]]
となり、この各々に sub2 を適用して、
sub2 [1,2,3,4] = [[1,2,3,4],[1,2,3],[1,2],[1]]
sub2 [2,3,4] = [[2,3,4],[2,3],[2]]
sub2 [3,4] = [[3,4],[3]]
sub2 [4] = [[4]]
となる、という意味で書きました。sub1, sub2 を使って定義すると、

subSequences xs = [zs | ys <- sub1 xs, zs <- sub2 ys]

となります。この定義では [] が出てこないので、[] も
サブシーケンスとみなすのであれば [] を追加する必要があります。

あまり長くならないようにしようと多少端折って書いたので
分かりにくかったかもしれません。

>>192
なるほど！
なんか、十分すっきりしてるように見えます…。

>>189
お忙しいところ、どうもありがとう御座います。
早速、勘違いとか問題点とか見つかったので良かったです。
なにを勘違いしていたかというと、方程式を解くようなイメージを持っていたということで、こんなことやってしまってました。

http://www.teu.ac.jp/kougi/koshida/Prog6/text06.html の課題２の証明中
　ah + (sum at ++ b) == ah + (sum at) + sum b　　(sum2)
　(sum at ++ b) == (sum at) + sum b　　　　　　　(-ah)
　sum at + sum b == (sum at) + sum b　　　　　 　(ind:証明不要)
二行目のところ、両辺から ah を引いてますが、
こりゃマズイってことに気付きました、これが許されるなら０掛けたらどうなる！！
あと、関数の定義で a x = b の時 b = a x と考えて置換、これも多分マズイですよね？
a x が b であっても、b であれば a x とは限らないですよね？
反例が浮かばない・・・
あくまでも同等であるということを意識しないといけないですね。

コツ＋１
１．証明が必要なものと、証明不要なものをしっかりと分類して整理する。
２．帰納するときの直前直後の要素を混同しないよう、記号をはっきりと意識する。
　要するに、証明すべき P(xs) -> P(x:xs) の xs および x:xs に注目する。
３．証明の最初は、帰納法の仮定 hyp 目指して置換してゆく。
４．左辺＝右辺を証明するとき、左辺の変形と右辺の変形はしっかり区別しておく事。
　そのためには、式を混ぜずに別々にやるべきである。
　両辺を変形するのはゴール地点を増やして、道しるべを作っておくことである。

Haskellといいますか、プログラムの証明をやると、
自分のやってた算数がいかにいい加減だったかよくわかる。(^^;

ところでやってしまった例の２行目なんですが、少なくともこの場合は上手いきます。
しかも便利はいいので（特に長いプログラムでは）、そこで問題点を洗い出して使えるようにしてみようと思ってる訳ですが・・・

例えば足し算の時、
　((+) 整数 整数)
　((+) 未定義 整数)
の全部で２パターンがあると思います（まだあるのか？）

この時
a == b ⇔ ((+) a c) == ((+) b c)　　(c は必ず整数です)
となれば良いのではなかろうかと考えてみました。
a b が共に整数なら自明、それ以外でも、未定義を加算した結果も未定義
一般的には a == b ⇔ f a == f b の時、両辺を置換してしまえる・・・のかな？
大丈夫ですかね？

>>190
美しく書かれた、汎用の語彙スキャナは確かに最初に欲しいですね。
私も多分 Haskell を憶えたら、まっ最初に作ると思います。
ちなみに現在「オーバーロードとクラス」にアタック中です。

>>195
あっ、スキャナじゃなかった、サブリストだ、失礼しました。

> この手の本を読むのは全然嫌いじゃない、というか結構好きですが、
> このような理論を理解してからでないとHaskellの「良い」プログラムが
> 書けないのだとしたら、やはりHaskellはちょっと敷居の高い言語
> なのかな、という気もしました。

全然必要じゃねー。

最小不動点にしても、スコット理論にしても、
プログラムの意味を数学的な構造と関連付けて理解するという
表示的意味論の世界であって、programmingそのものには関係ない。
ただ、「継続」を理解すれば、モナドは楽勝かも。
>>182
> 「数理情報学入門 ― スコット・プログラム理論」中島玲二著 朝倉書店
には、「継続」がごく簡単に説明されていたと記憶する。
多値の中の一つとして継続(の一部)を直接扱うためにliftしたというだけの話なので。

>>193
sub2 の定義がどうもすっきりしてないように見えるんです。
リストの末尾の方から要素を省いていくって面倒ですよね。

>>197
＞全然必要じゃねー。

そう言われると多少気が楽になります。
でもまあ、理屈の話も面白いのでそれなりに…。

＞ただ、「継続」を理解すれば、モナドは楽勝かも。

この「モナドは楽勝かも」という言葉には惹かれますが、
調べてみたら、最寄の図書館にはこの本がなかったのが残念です。

>>197
そこでいう「継続」って Scheme のやつと同じもの？

表示的意味論の「継続」は「全」状態の1 snapshotを表している。

これがschemeのccの由来。Lisp programmingに有用なものだけ抜き出してある。
だからcall/ccしても大域変数の値がbacktrackしたりはしない。
機能はスタックがスタックフレームのリストだったInterlispにinspireされたと思う。
用語や意味づけは表示的意味論から持ってきた模様。

「モナドとかいっても結局状態を扱ってるんだろ」という極論は、
「オブジェクト指向とかいっても結局変数とサブルーチンなんだろ」
という極論と似ていると思った。

>>201
いやむしろ、状態を扱わないようにするのがモナドだと思ってるのが勘違いでは？

{-

そうだね。間違えた。

終わりを忘れずに♪
-}

実用プログラムとして、無限リストのルンゲ・クッタ法を
実現しようかなと考えているものの、まだ未着手(wara

ラムダ式をHaskellで表現したいのだが、うまくいかない。

ラムダ式は
<<λ項>> ::= <<変数>> | <<λ項>><<λ項>> | λ<<変数>>.<<λ項>>
と表現できるらしいが、
これをHaskellのデータ型で定義したいのだが、なかなかうまく
いかない。だれか教えて。

わしもついでに質問します。
http://www.teu.ac.jp/kougi/koshida/Prog6/text09.html
の問題1やっているところです。

どうしても上手くいかなくて、テストのもっと簡単なのをつくって見ますと・・・
同じ書き方なのに、なぜオーバーロード関数を見つけない？
という問題に出くわしました。

class Visible a where
　xshow :: a -> String

instance Visible Char where
　xshow a = "test-char"

instance Visible Int where
　xshow a = "test-int"

xshow 'a' とすれば、上手く "test-char" と表示されるんですが。

xshow 1 とすると・・・

ERROR - Unresolved overloading
*** Type : (Num a, Visible a) => [Char]
*** Expression : xshow 1

とメッセージ出します、なんででしょ？

type Var = String
data Term = Var Var | Aplly Term Term | Lambda Var Term
deriving (Eq, Read, Show)

Haskellはなんと読みますか。

ハスケル
ハズケル
アスケル
ハースケル
アシュケル
アシュカル
ハスキル

ガッコで教わったときは、先生はハスケルと読んでたよ。

>>208 確か 1 は Intではないため。
1 :: Num a => a だな。
Visible (1::Int) ってやればとりあえずエラーは出ないのでは。
もしくは
instance Num a => Visible a
xshow a = 'test-num'
だと動作が違っちゃうね。

http://www.score.is.tsukuba.ac.jp/~minamide/lectures/compiler.htm

簡単なコンパイラでも作ってみようかな?
Pascalあたり簡単そうだね。
けど、ただのお遊びで終わる感が…

>>209　さん、どうも。

ためしに、以下のように入力するといずれもエラーとなるのだが？

Aplly "x" "y"
Aplly (Var "x") (Var "y")
Lambda "x" "y"
Lambda "x" (Var "y")

>>215
2番目と4番目はエラーにならないのだが？

>>216
やはり、Hugs98ではエラーとなるなあ。どうしてかな。

「計算モデルの基礎理論」を読んでて、λ式の変形、簡約って
けっこう面倒なので、Haskellでλ式処理できればいいなと
思って。

>>217
こっちもHugs98(win)なんだが…。

>>209の deriving (Eq, Read, Show) をインデントしてるよね？

うーん…

>>218
>deriving (Eq, Read, Show) をインデントしてるよね？
Tab入れたら動いた。>>209 をそのままコピーしたので、
オフサイドしてたわけね。

data Term = Var Var の　Varを２個並べるのって変な感じ。
前者のVarはデータコンストラクターで後者はStringを意味
するんだよね。すっきりしない。

>>190
以前に書いたサブシーケンスの問題、多少簡潔に書けました。
（前回のsub1, sub2を使ったものは10行以上ありました）

>subseq :: [a] -> [([a], Bool)]
>subseq [] = [([],True)]
>subseq (x:xs) =
> [(x:ys, True) | (ys, flag) <- yss, flag || null ys] ++
> [(ys, False) | (ys, flag) <- yss]
> where yss = subseq xs

x:xs のサブシーケンスを求めるのに xs のサブシーケンスを
使っています。ys を xs のサブシーケンスとするとき、x:ys も
サブシーケンスになるには、ys が xs の先頭要素から始まって
いるか、ys が [] である場合だけです。前者の条件を満たす
場合に flag = True となるような、サブシーケンスとフラグの対
からなるリストを生成しています。

subSequences は subseq の結果からフラグを取り除けはOKです。

>subSequences :: [a] -> [[a]]
>subSequences = map fst . subseq

>>220
あまりエレガントな感じしないなぁ。
sub1, sub2 が長いのがいやなら、既存のものを使うとか。

import List
subSequences xs = nub [zs | ys <- tails xs, zs <- inits ys]
-- nub で消してるのは [] だけよ。

>>197
> ただ、「継続」を理解すれば、モナドは楽勝かも。

どちらかというと逆で，具体的にどう書くかは別にして，
モナドを使うと一種の継続を表現することができます．
えーと，Rを仮想的な結果の型として
関数A->BをA->((B->R)->R)と見なすようにモナドを定義します．
このときB->Rが型Bの継続の型です．
また，これは状態遷移のモナドとはちょっと違うことに注意してください．
こちらはSを状態の型として関数A->BをA->(S->(B,S))と見なすように定義します．
これはAとSを同時に引数にとると考えると（この変換を非カリー化といいます）
(A,S)->(B,S)となるので状態がくっついている様子がよくわかります．

繰り返しておくと，上の定式化を比較すればわかるように
関数A->BをA->M(B)と見なすということが計算のモナドの基本的アイデアであり
状態遷移はその適用例の一つに過ぎません．
もともと表示的意味論を整理してモジュール化するというのが
意味論にモナドを持ち込んだ目的の一つでしたので，このメカニズムにより
状態や継続などを表現することは最初から考えられていました．

>>200
> 用語や意味づけは表示的意味論から持ってきた模様。

というかSchemeの仕様書の最後の方に表示的意味論使って書いてあるんじゃない？

http://www.teu.ac.jp/kougi/koshida/Prog6/Text03/index.html
ここの課題２って、こういう感じでいいのでしょうか。
もっと単純にかけそうな気がするというか、
エレガントに書けそうな気がするんですが。

maxOcc :: Int->Int->(Int,Int)
maxOcc a b
| a>b =(a,1)
| a<b =(b,1)
| a==b=(a,2)


maxThreeAux :: Int->(Int,Int)->(Int,Int)
maxThreeAux a (b c)
| a == b =(b c+1)
| a >b =(a 1)
| b <a =(b 1)


maxOcc3 :: Int->Int->Int->(Int,Int)
maxOcc3 a b c =maxThreeAux a (maxOcc b c)

>>221
＞あまりエレガントな感じしないなぁ。

しないですね〜（笑）。特にフラグってのが良くないです。
subSequences xs の結果を直接的に使ってみたかっただけなんですが、
スマートにやるのは難しいです。

>>212
どうもです、
1 というのは Int 型ではないのか・・・
確かに、文法考えると Float なのか Int なのか区別つかないから適当に推定しないといけないですからね。
Haskell はこの推定部分をプログラムできるような構造をもっているということなんでしょうか。
とりあえず (1::Int) として指定すれば、良いみたいですね。
なんとかしてやろうと思って、他の関数はどうなってるのか
Prelude.hs を見てみましたら、謎のキーワードの山でひっくりかえってしまいました。

>>223
私もそうしてしまいました、基本は全部列挙、内容が自明で個数が数行で
書ききれるならば、条件別に全て書いてしまうべきだという
変なポリシーあったりしますので。
そういったものが沢山あるとき、一旦一般化した関数を作ってそれを使うのが
もっとも良いのではと思います。

λ演算てなんですか。ハスケル用語ですか。

ハスケルってケミカルに似てますね。

このスレでだれかが紹介していた「ラムダ演算のABC」
>http://members.tripod.co.jp/nbz/ref/lambda.html

http://www.teu.ac.jp/kougi/koshida/Prog6/Text11/index.html の問題３
をやっております。

とりあえず作ってみたが、もっと格好のよい例はないもんかのぉ
なかなかええのができん、もっと良い方法で解かれた方はおりませんか？

とりあえず、格好の良い関数の条件
１．(+) を新しく作ったりしない事。
２．エラーは maybe 一丁で全部処理する、maybe もどきは作らない。

-- 一番最初に考えた格好の悪い例
-- 問題点は maybe 関数が引数を一つしか取らないのが問題かと思い
-- 引数をまとめてしまうことを考えてみた、・・・しかし
-- そもそもグループ化する意味がないのが悲しい
-- 伝播する意味がない、どちらかが Nothing と判明した時点
-- で 0 で終了が確定するわけで・・・
-- 使いどころを探して無理やり maybe を使ってみましたという
-- 強引さが否めない。
-- さらには (+) を新たに起こしている時点で死刑
grp :: Maybe a -> Maybe a -> Maybe (a,a)
grp (Just a) (Just b) = Just (a,b)
grp _ _ = Nothing

process :: [Int] -> Int -> Int -> Int
process l a b = r
　where
　p = errPos l
　ab = grp (p a) (p b)
　add = (\(a,b) -> a + b)
　r = maybe 0 add ab

おまけ
-- とりあえず素直な形の物を作ろうと考えた例
-- maybe は使いませんでした
-- 直感とマッチする、まだ上の例より良い印象がする。
process :: [Int] -> Int -> Int -> Int
process l a b = r
　where
　add (Just x) (Just y) = x + y
　add _ _ = 0
　p = errPos l
　r = add (p a) (p b)

なんか楽しそうな言語だな。
ソース見ても何やってるかさっぱり分からん。

Windows用のインタプリタ拾ってきたんで遊ぼうかな。

とりあえず関数型言語の基礎を固めよう、ってわけで、
「関数プログラミング(R.ワード、P.ワドラー共著)」
という本を買ってきました。
まだはじめしか読んでいませんが、
文法が非常にHaskell似(というか他の関数型言語似?)なので
とっつきやすいです。

>>222
> > 用語や意味づけは表示的意味論から持ってきた模様。
>
> というかSchemeの仕様書の最後の方に表示的意味論使って書いてあるんじゃない？

そりゃまあみんな知ってるさ…

そもそもActorを実装を通して理解しようとしたのがSchemeの始まりだから、
asynchronous messageを使ったinteractionをLisp上で実装しようとして、
continuationを使うalphaを導入した。

表示的意味論を元に考えた機能というよりも、
必要に迫られた機能をSussmanが表示的意味論で料理した。

と記憶しているけど、どうかな？ > 古い人

Haskellあんまり関係ないのでsage

>> 231
個人に向けたわけでもないので気を悪くしてたらごめんね．
もちろん知っている人は皆知ってますけど，
そもそもよく読んでない人のほうが多いと思うんで．
設計の内部事情についてはよく知らないので古い人おねがい．
ただ当時のMITあたりでは表示的意味論は
相対的に今よりもずっとポピュラーだったと思うよ．

>>230
Haskell の構文はこの本で処理系の実装としてとりあげられている
Miranda の構文を元にしているような。リストの内包表記なんかは
Miranda が最初かなあ。

状態モナドを使ったら、参照透過性が崩れてしまうということは
ないんですか？
状態を保持する変数があったら、変数の内容が変わるから
参照透過性が崩れてしまうような気がするのですが。

あと、関数型だと何が便利になるんでしょうか？
やはり参照透過性を確保するためでしょうか？
参照透過性以外の理由で、何か理由があるのでしょうか？

>>234
>状態モナドを使ったら、参照透過性が崩れてしまうということはないんですか？

状態モナドは参照透明性を確保しつつ、状態を扱うためのテクニックです。

>参照透過性以外の理由で、何か理由があるのでしょうか？

高階関数による抽象化。

>>190
やっとそこに、たどり着きました
自分の頭で考えたら、
リストの内包表現を使いさえすればよい例って感じになってしまった。

subLists :: [a] -> [[a]]
subLists (ah:[]) = [ [ah] , [] ]
subLists (ah:at) = [ ah:t | t <- (subLists at) ] ++ [ t | t <- (subLists at) ]

subSequences :: [a] ->[[a]]
subSequences (ah:[]) = [[ah]]
subSequences (ah:at) = [ take n (ah:at) | (x,n) <- zip (ah:at) [1..] ] ++ (subSequences at)

なんかただ使ってみたって感じがしますね。
特に subSequences は zip やら take やら、入っていてやな感じ。
もうちょっと考えてみよう。

しかし石敢當さんの subLists は凄いですね。
今日はこれから http://www.teu.ac.jp/kougi/koshida/Prog6/text13.html やります。

>>228
私も作ってみましたが、あんまりすっきりしたものができません
でした。何の制約もなければ簡単に書けるプログラムですが、
「maybe と errPos を使って」という制約がありますので、
Maybe型に慣れるための演習と思うことにして、すっきりした
コードはあきらめました。

>>236
subListsの別定義を考えてみました。構成する方法は以前と同じですが、
要素の並びを変えてあります。

subLists :: [a] -> [[a]]
subLists [] = [[]]
subLists (x:xs) = y : map (x:) (y:ys) ++ ys
where y:ys = subLists xs

以前の定義と比べて何が良いかと言うと、整数型のように
大小を比較できる要素のリストの場合、昇順にソートした
リストを渡すと得られる結果もソートされている点です。

例) subList [1,2,3] = [[],[1],[1,2],[1,2,3],[1,3],[2],[2,3],[3]]

リストで集合を扱う際などには、このようになっていたほうが都合の
良いときがあります。

Haskellでファイルの入出力方法がわからんage
この辺がモナドってやつに関係するのかな?

>>238
ん？工科大のテキストしか読んでないのか？

http://www.sampou.org/haskell/tutorial-j/index.html
とかも読め。

>>239
これを読んでモナドわかった人いる？
入出力のやり方ぐらいは見様見真似で出来るようなるけど。

http://www.sampou.org/haskell/tutorial-j/monads.html
の9.3のところでいきなりわからなくなるんだけど、

data SM a = SM (S -> (a,S)) -- The monadic type

これ、両辺にSMが出てきてるよね？
すると、このSMって同じ物を表してるんだよね？
ということは、SM a が SM (S -> (a,S)) と一緒？
ということになると、aが(a,S)を返す関数ってことになって
つまり、自分自身を含む組を返す？
頭がこんがらがってきます。

で、正確にはどう解釈したらいいんだろう？

>>240
> このSMって同じ物を表してるんだよね？
違います。左辺のSMは型構築子右辺のはデータ構築子。
http://www.sampou.org/haskell/tutorial-j/goodies.html#sect2.2

> で、正確にはどう解釈したらいいんだろう？
SM a という型は S -> (a,S) という型の関数に構築子 SM を適用した型。

モナド以前sage

>>240
http://www.sampou.org/haskell/tutorial-j/goodies.html
の2.2に書いてありますね．最初のSMは型構築子，
次のSMはデータ構築子（データにくっつくタグみたいなもの）です．
名前空間が違うので同じ名前を使えますが別物です．

241の方が242よりも詳しいのに、242の方が
いい人に見える不思議。

関数言語って、ちょっと深くやろうとすると難しいね。
写像の連続で意味を追うというのも、疲れるね。
状態の変化を追う方が楽なような気もする。

どんなプログラムを作るのに向いてるの？

自分で考えなさい。(１問２０点)

>>245
まだやり始めて短いですが、現状見た感じですと・・・趣味ですね。(^^;
あと、他言語でのプログラミングスタイルの強化や修正とか。
プログラムというものの本質をみる言語じゃないかな。
プログラム言語を考えるためのプログラム言語とかどうでしょう。

そうそう、あと無限リストが取扱えるというのは結構衝撃ですよ。
もちろんそれっぽいものは、他言語でもできますが、Haskellは綺麗にやってのけてます。
こんな感じで
a = [x * 2 | x <- [1..] ]
[1..] は 1〜∞ までの自然数のリスト a は 2,4,6〜∞ のリスト
普通の言語だと、こんな書き方するとメモリーが足らない上に停止しない。
このへんが面白いです。

>>241-242
どうもありがとうございます。
左辺と右辺のSMは別物だと捕らえたらなんとか理解できました。

しかし、SMの定義を見てると何か釈然としないものを感じます。
例えば、状態を読み取る時は

runSM s0 readSM

となるんだろうけど、これは(s0,s0)を返すにすぎませんよね？
これでは何の意味があるのだか良く分かりません。
状態を読み取ると言っておきながら、自分で状態を指定してるではない
ですか？また、状態を更新する時なのですが、

runSM s0 (updateSM f)

これは要するに、”前の状態と変化の仕方を引数として、後の状態を返す”
というのと同じことで、普通にそういう関数を作っても全く副作用は
無いと思いますが、なぜモナドにする必要があったのでしょうか？
あと、モナドを返す文と新たな文をくっつけて、またモナドを返すように
するというように、”>>や>>=やreturnを使って、モナドを返す部分を
どんどん伝染させていってる”ように感じるのですが、これは何のために
やってるんでしょうか？

あとは、getCharでちょっとした疑問があるのですが、getCharは場合によって
IO 'a'を返したり IO 'b'を返したりするはずです。これは参照透明性を失って
いるようにみえるけど、なぜ大丈夫なんでしょうか？

HaskellでOOPするにはどうやるんだ？
Haskellにはオブジェクトの内部状態という概念が無いから困るだろう。
モナドを使うのか？

>>245
>どんなプログラムを作るのに向いてるの？

たぶん、抽象度の高いものに向いてるんだろう。
記号処理とか。
OOPとかは、シュミレーションなどの実際のデータ
変化を伴うものは書きやすいが、記号処理なんか
はOOPで書くの大変だろう。

でも、これだけオブジェクト指向ありきの世の中になってまで、
オブジェクト指向が出来ないってのは相当な痛手だと思うけど。

大学の「情報工学」と名の付く学科を出ていながら、関数型言語やプログラムの基礎理論
のことをなに一つ知らない連中もちょっと問題ありだけどね。

>>251
Haskell は、OOPで実装しても意味がないんじゃよ、時間軸が言語から分離消失してるからね。
考えること事態がナンセンスや、それでも OOP とは違うが似た概念はあるで。
class とか instance とか、実装されとる。
だが、実体はOOPとは全くの別物やね。

まあ、詳しいことは一度やってみるとええ。
プロセス型言語とは決定的に違うHaskellの世界で常識をいっぺん引っくり返してみ。
もっともわし、始めて２ヶ月やからトンデモないことぬかしとるかも知れんが・・・（笑）

>>248
「同じ文脈(用語は不安ですが)では、同じ変数は同じ値を表す。」
というのが参照透明性ですが、
getChar は同じ文脈では１度しか出現できないので、参照透明性
が保たれていると言えます。

>>236
＞今日はこれから http://www.teu.ac.jp/kougi/koshida/Prog6/text13.html やります。
私も考えてみました。問題2だけ書きます。

2, 3, 5 で順に割ってみて2, 3, 5以外の素因子がないものだけを
拾い出せばokですが、これだととっても時間がかかります。
[2^a * 3^b * 5^c | a <- [0..], b <- [0..], c <- [0..] ]
と書ければ簡単ですが、これだとaとbが永遠に0のままですので細工を
しないといけません。まず、3つ組を順に生成する関数を定義します。

type Triplet = (Int, Int, Int)

nextTriplet :: Triplet -> Triplet
nextTriplet (0, 0, c) = (c + 1, 0, 0)
nextTriplet (a, 0, c) = (a - 1, c + 1, 0)
nextTriplet (a, b, c) = (a, b - 1, c + 1)

triplets :: [Triplet]
triplets = (0,0,0) : [ nextTriplet t | t <- triplets ]

こうすると非負整数から成る全ての3つ組の列 triplets が得られ
ますので、これを用いて

humming2 :: [Integer]
humming2 = [ 2^a * 3^b * 5^c | (a, b, c) <- triplets ]

と定義すれば、順に割っていく方式のものよりははるかに高速です。
（ただし、このリストは小さい順には並んでいないです）

Haskell の拡張だけど一応
http://www.cs.chalmers.se/~nordland/ohaskell/
http://www.cs.chalmers.se/~rjmh/Software/h++.html

俺は Haskell で OOP なんてしたいと思わないけど。

>>254
俺は、getChar というか IO レベルでは
同じ式でも違う値を返し、参照透過性を保ってないと理解しているのだけど。

でも、IO a 型のデータ構築子は定義されてないので
a の値だけを取り出すことは出来ないため、
IO ってタグが付かない場所では IO を使うことが出来ないので
IO 以外のレベルでは参照透過性は保たれるので大丈夫。
って事だろうと理解している。

間違ってたら訂正きぼん > 識者

追記。
IO a 型のデータ構築子云々ってのは
IO ってデータ構築子があるのなら
fromIO :: IO a -> a
fromIO (IO x) = x
って書けるって話。

オブジェクト指向が出来ない言語なら実用性に疑問が残るね。

OOPとは何ができることか考え直してみればHaskellでもかなりのことはできます．
大まかに言えばOOPの静的な側面，例えば継承，多相型，抽象型などは
type classやmoduleなどで大体可能です．以下にも例があげられています．
http://www.sampou.org/haskell/tutorial-j/classes.html
http://www.sampou.org/haskell/tutorial-j/modules.html
難しいのは動的な側面，例えば並列的なメッセージパッシングに伴う
非決定性などですが，開発手法としてのOOPは主に前者に関わるので
かなりのことができるというのが相応しい評価だと思います．

モナドについては，図がかけないとちょっと説明が面倒ですが，，，．
ちょっとだけ言葉で説明してみます．

248さんが言うようにどんどん伝染していっているという感覚は正しいです．
前にも書きましたがモナド関数はA->M(B)という形を基本にして考えて，
通常A->B,B->C,C->Dという関数を合成していく代わりに
A->M(B),B->M(C),C->M(D)というモナド関数をつなげていきます．
この操作が>>=の果たしている役目です．
これが通常の合成ではないところがポイントであり，
IOなどのモナド計算はこのつないでゆく所で起こると考えることができます．

さらにもう一つ必要になるのが通常の関数A->Bを
モナド関数A->M(B)に持ち上げる操作ですが，
これはB->M(B)のある関数と普通に合成してやればできます．
これがreturnの果たす役目です．
計算のモナドで本質的に重要な操作はこの二つです．

main,getChar,getLineなどはこのような形をしていないように見えますが
これは一般に()->AとAは理論的には同じと見なせるのでこのようにしています．
（これらが関数であると上記のチュートリアルにも書いてあるのはこのためです）．
これは例えば，ある集合Sと，一点からなる集合{*}からSへの関数全体の集合とは，
各関数において*がSの一つの要素を決定するので
実質的に同じ集合になるのと同じようなことだと考えてください．

もうひとつ．例えばgetCharの返す値はIO Char型であり，
非決定的な動作はまだ起こっていません．この段階では参照透過性は保たれています．
このIOの結果を直接参照できるならば参照透過性が失われます．例えば
unsafePerformIO :: IO a -> a
のような結果を取り出す関数があると参照透過性が失われます．
do（つまり>>=）で取り出せているように見えるのに
参照透過性が失われないのはその参照がdoの中だけだから，
言い換えれば>>=の第二引数である関数における仮引数の参照に過ぎないからです．

ついでに
>>257
データ構築子と関数は別物です．
データ構築子はタグみたいなものであってデータの一部です．
実行時に評価されるわけではありません．
（言いたい事はわかりますが）．

>>262
ごめんなさい，寝ぼけてました．関数はfromIOのほうでしたね．
もう落ちた方がよさそうです．

>>244
> 写像の連続で意味を追うというのも、疲れるね。
> 状態の変化を追う方が楽なような気もする。

うまく出来るよう訓練すればと、
状態バリバリから脱却した設計、他の言語でもかなり容易になると思われ

> どんどん伝染させていってる”ように感じるのですが、これは何のために
> やってるんでしょうか？

効能に射影して語れ、ということらしいのでIOについて考えると、

時系列情報がどこかにないと、遅延評価した時に、
本来は後から実行されるべきgetCharが先に実行されかねない。

モナドを利用すれば、モナドの皮を剥かなければ、
中身は取り出せないので、モナドの連鎖をうまく構築してやれば、
評価順序を規定してやる事が出来る。

偶数番目の文字だけリストにする関数を書いて追ってみては？

>>255
うわぁ、細かい工夫はいってるなぁ。
ちなみに私の回答はといえば・・・

prim :: [Int]
prim = sieve [2..]
　where
　sieve (x:xs) = x : sieve [ y | y <- xs , y `mod` x /= 0 ]

isPrim :: Int -> Bool
isPrim n = isPrimS1 n prim
　where
　isPrimS1 :: Int -> [Int] -> Bool
　isPrimS1 n (x:xs)
　　| n == x = True
　　| n < x = False
　　| otherwise = isPrimS1 n xs

humming = [ x | x <- [1..] , [ f | f <- factors x , f > 5 , isPrim f ] == [] ]
なーんも工夫しとらん、というか工夫できなかった(泣)・・・です。
素数は難しいです。
とりあえず、工科大のテキストは一通り終わらせたので、
やさしいHaskell入門を整理して自分用マニュアル作ってます。
概ね全体像見えてきたかなって感じです。
やっと羽根伸ばしてプログラムできるかな？

何か面白い問題ない？

>>264
>状態バリバリから脱却した設計、他の言語でもかなり容易に
>なると思われ

事象を写像でとらえる。ひたすら精進あるのみか。
でも写像の写像（高階関数）になると、とたんに難しくなる
んだなあ。

今読んでる本。
「プログラミング言語　武市正人著　岩波」
Haskell(Gofer)をメタ言語として普通の命令型言語を書く
というのが主題なんだが、継続のあたりまでくると
難しくてなかなか読みすすまない。
継続::状態->結果　とすると継続はプログラムカウンタに
あたるとか。うーんわからん。

XMLの本立ち読みしてたら、XSLTとかという言語があって、
これは　宣言型言語で副作用のない言語とか書いてあった。
なんか似てるね。　

>>254 >>256 >>260-261

いまだに完全には理解できないのですが、IOがついてるから
大丈夫ということのようですね。
参考になるレスをありがとうございました。

>>267

その本いくらくらいします？　本屋においてありますか？

>>269
書　名　　岩波講座ソフトウェア科学　４
　　　　　プログラミング言語
著　者　　長尾真、武市正人
出版社　　岩波書店
本体価格　\3,200
発行年月　1994/06
ISBN　　　400010344X

近くの書店に問い合わせてみたところ、店頭にはないが
取次にあるので取り寄せまで約4日、ということでした。

私はかなり以前に図書館で借りたことがあるような気が
するのですが、読んだ記憶は無し。また借りてみようかな。

　命令型言語をHaskellで書いてみる。継続によってアウトプットも出してみる。
「プログラミング言語　武市正人著」の内容をデフォルメ。

記憶状態は簡単に文字列と整数の対応(Assoc)として定義する。
type Assoc a b = a -> b
type State = Assoc [Char] Int
記憶内容へのアクセスと更新のため、次の２つを定義
mylookup :: Assoc a b -> a -> b
mylookup h x = h x
myupdate :: Eq a => Assoc a b -> a -> b -> Assoc a b
myupdate h x v y
| x == y = v
| otherwise = mylookup h y
式を次のように定義。変数、整数値、足し算と掛け算に限る。
data Expr = Var [Char]
| Num Int
| Plus Expr Expr
| Times Expr Expr
式の値を以下のようにする。
expval :: Expr -> State -> Int
expval (Var x) s = mylookup s x
expval (Num n) s = n
expval (Plus e e') s = (expval e s) + (expval e' s)
expval (Times e e') s = (expval e s) * (expval e' s)

長くなったので次に続く。
バカボンのパパは失業して、ひまなのでだらだら書くのだ。

>>271 のつづき。

次に命令コマンドを定義。代入と出力だけとする。
data Cmd = Assign Expr Expr　| Output Expr

最初は状態の変化を返すコマンド実行を定義。
cmdexe :: Cmd -> State -> State
cmdexe (Assign (Var x) e) s
= myupdate s x (expval e s)
cmdexe (Output (Var x)) s
= s
状態の変化は追えるけど、出力は出せませんね。
ためしに、
none :: Assoc a b
none x = undefined
s1 = cmdexe
(Assign (Var "x") (Plus (Num 3) (Num 5))) none
として、mylookup s1 "x" といれると　８が帰ってきますね。
記憶状態がnoneからs1へ変化してますね。

でもこれではアウトプットが出ない。
次へ続く。

>>272　の続き。
アウトプットを出すため、継続::状態->出力を定義。
なお、ここでの出力は整数リストとする。
type Result = [Int]
type Cont = State -> Result
コマンド実行はコマンド->継続->継続とする。
cmdexec :: Cmd -> Cont -> Cont
cmdexec (Assign (Var x) e) p s
= p (myupdate s x (expval e s))
cmdexec (Output e) p s
= expval e s : p s
継続停止のため
stop :: Cont
stop s = []
準備が整ったので次のようなコマンドを実行する。
（１）ｘに３を代入　（２）ｙに５を代入　（３）ｙを出力
（４）ｘ＋ｙをｚに代入　（５）ｚを出力
これは次のように書けます。
p1 = cmdexec (Assign (Var "x") (Num 3)) p2
where
p2 = cmdexec (Assign (Var "y") (Num 5)) p3
where
p3 = cmdexec (Output (Var "y")) p4
where
p4 = cmdexec (Assign (Var "z")
(Plus (Var "x") (Var "y"))) p5
where
p5 = cmdexec　(Output (Var "z")) p6
where
p6 = stop
ここで　p1 none　と入れると　リスト[5,8]　が出力されます。
p1,p2,p3,p4,p5,p6は継続ですが、プログラムカウンタみたい
ですね。

おわり。

オマエモナー
ド

ゴルァ！

今年の ICFP Programming Contest で Haskell を使ったチームが 1 位になった模様。

http://piza2.2ch.net/test/read.cgi?bbs=tech&key=987954395&st=571&to=571

去年買いそこねた、というか、SOE本を買ってしまったので
買うのをやめていた、
Introduction to Functional Programming using Haskell
を買ってきました。これは second edition ということに
なっていますけれども、"using Haskell"とついているのは
2nd Ed.からなんですね。初版から10年を経て分量も100ページ以上
多くなったようです。全部で12章あり、気の向いたところを
何箇所か読んでみましたが、exampleが多くて読みやすいように
思いました。面白そうに感じたのは、7章の Efficiency,
9章の Infinite lists, そして10章の Monads です。あちこちを
パラパラ眺めたあと第10章を読んでいますが、Monads が
なんとなく分かってきたような感じがします。>>260で司馬乱さんが
書かれていることも分かってきました。

難点は高いことかな。税抜きで\9,990でした。ちゃんと読んで
中身も理解できたら安いもんですけど。

>>277
amazonで検索したら、
Introduction to Functional Programming using Haskell
の本２種類あった。
著者がAntony J.T.DavieさんのとRichard Birdさんの。
どちらの本のこと言ってるの？

>>277
それと、もし都内で売っている本屋あれば教えて

>>278
＞著者がAntony J.T.DavieさんのとRichard Birdさんの。
＞どちらの本のこと言ってるの？
Richard Birdさんのほうです。

＞もし都内で売っている本屋あれば教えて

店内在庫があるか？という意味でしたら良く分からないです。
私は注文して買ったのですけど、国内の取次に在庫があったらしく
１週間くらいで入手できました。

ご参考までに：
http://web.comlab.ox.ac.uk/oucl/publications/books/functional/

>>280
> Richard Birdさんのほうです。

お？やっぱりBirdが出してるの？(ついにHaskellか…)
じゃあ>>99で話した奴が増補Haskell版になって帰ってきたってことか…俺も買おう。

haskellは.netに対応するそうで。。既出？

>>282
>>183-186あたりに出てる。
つか、.NET が Haskell に対応って書くべきでは。

>>276
課題に出てくる SML/NG、SML/NJとは全然関係ないのね。
出題者の遊び心かな。入賞プログラムにSML/NJがなくて
出題者は残念？

>>82 のACMの文書を読もうと思って、大学に籍のある友人に尋ねて
みたところ、「NACSISで検索したら色々な大学に置いてある
みたいだけど、うちにはない」と言われました。

NACSIS ( http://webcat.nacsis.ac.jp/webcat.html ) という
検索サービスは始めて知りました。大学の図書館にある図書・
資料の検索ができるもので、便利そうです。

ちなみに、Introduction to Functional Programming using Haskell
（長いので次回から参照するときは「IFP本」と呼ぶことにします）を
検索したら9箇所しかありませんでした。もっとも、学科の図書室
などでNACSISの検索に引っかからないのも結構あるでしょうから、
置いてある大学はもっと多いかもしれないです。

学外者が利用できる大学図書館もあるようなので、そのうち
どこかを利用しようと思いますが、中にはコピーを1枚とるのに
100円も取るところもあるようでびっくりしました。
( http://www.lib.st.keio.ac.jp/service/annai-p6.html )
1枚100円はちょっとひどいなぁ。

ACMのmembershipがあれば、
http://www.acm.org/pubs/contents/journals/surveys/
でPDF取得できるけど、高いからねー。

http://www.acm.org/pubs/contents/journals/surveys/1996-28/
は面白いの一杯あったよ。

afe

Haskell の欠点ってなんだろう？

>>13
現在翻訳中だってさ。

新山さん萌え。

>>267
その本ついさっき読み終わったけど、特に後半なんかはあまり良い解説じゃないね。
いい加減な解説になってる。本書くのが大変で無理矢理本にしたって感じだね･･･

www.haskell.org にある "Haskell Humor" に新しく追加された
リンク The Evolution of a Haskell Programmer に昨日気づきました。
( http://www.willamette.edu/~fruehr/haskell/evolution.html )
>>4 にもある階乗のプログラムを20種以上、よくもまあと思うほど
掲載されています。書いた人の肩書きと合わせてコードを読むと
なかなか面白いです。もっとも、後半の方にあるものはあまりにも
コードが長くて真面目に読む気がしないですが(真面目に読むと
面白いのかな？）。

この元ネタとなったらしい The Evolution of a Programmer も一読の
価値あり。最後に登場する Chief Executive のところでは思わず
笑い声がもれてしまいました。

>>288
構文が特殊

>>292
特殊か？
どんなところがよ？
特殊だとしても欠点なのか？

>>292
特殊とする根拠が「自分の知っている○×言語と違いすぎる」だとしたら劇萎え。

構文が普通 => Lisp
構文が特殊 => Haskell

とか？

構文が普通 => APL

でない事を祈る。

>>288
状態が無い。
ポインタが無い。
委譲の概念が無い。
その他動的な概念が無い。
カリー化された関数が複数絡まる式が読みにくい。
習得が難しい。

GUIやゲームなんかの俗っぽい(?)プログラミングとの親和性はどうなの？

>>298
相当マスターしないと無理だろ。
モナドの使い方、Haskell風のプログラミングへの慣れが必要
だろ。

型変数の辺りとか>>293

仕様の変更に対応しづらそう>>298
GUIやゲームは仕様変更の連続だから
(偏見かしら?)

>>301
仕様変更への対応のしやすさは、プログラミング言語よりも
仕様そのものの構成に依存するのではないかと思うけど。

Goferってどうでしょう？

>>303
いいっすよぉ。ほとんど Haskell 。とうか、Haskell の仕様は
Gofer の実装後に確定したものが結構多いです。Monadic IO も
Gofer での実装が先だったと思います。

作者の Mark P. Jones 自身が実装についてのレポート
"The implementation of the Gofer functional programming system"
を書いていて、これを読みながら、処理系のソースを読むと大変勉強
になります。このレポート読んでソースをイジッテ自分で新しい機構
を追加するなど、しゃぶり尽くすに最高です。

gofc という C へのトランスレータが付属していて、これを
改造して、gofhoge というのをつくるというのはどうですか。

>>304
比較的小さくて良い感じですね。

ここ読んでもモナドについてはっきりしない。
「副作用が含まれる部分をモナド部分に分離できる。」
なのか、
「モナドだから副作用では無い。」
なのか、はっきりして欲しい。

それから、英語でも学術的な内容でも構わないからモナド
がはっきりわかるように詳しく解説した文献何かない？
やはりBirdの本が良いのか？

>>306
http://www.research.avayalabs.com/user/wadler//topics/monads.html

ここに行くと Philip Wadler氏 が書いたMonadに関する文書を
いくつか見ることができます。メーリングリストで、この中にある
"Comprehending monads" をお薦めしている人がいたので近々
読んでみようかと思っています。私はまだ読んでいませんので、
この文書が「モナドがはっきりわかるように詳しく解説した文献」
かどうかは分かりません。

もしどなたか読まれた方がいらっしゃればコメントを頂けませんか？

モナドってお菓子ありそう。
ナボナ

>>306
モナドってただ単に高階関数作って
操作を順序付けするって事なんじゃないの？

>>309
全然答えになってない。

>>310
模範解答してくれyo!

>>309
もしそうだとしたら、何でＩＯ処理がモナドなんですか?

IO処理は順序付けが必要だから>312

順番つけるだけ？だとしたら副作用は許容されるの？

>>314
副作用は、
状態を高階関数の引数で受け取る様にすればいい。

>>315
それだと、自分で状態を与えなくてはいけなくなりません？
状態を読み取る時はどうするんですか？
また外部からの入力で与えられた変化にはどうやって
対処するんですか？

haskellは知らんのでschemeでのmonadのサンプル
for-eachに渡るリストをmonadのストリームと見なします。

(define (do-monad-output action . monad-stream)
　(for-each
　　(lambda (x) (if (procedure? x) (action (x)) (action x)))
　　monad-stream))

(define (do-monad-input action . monad-stream)
　(for-each
　　(lambda (x) (if (procedure? x) (x (action)) (action)))
　　monad-stream))

出力
(do-monad-output display
　"a b c 3と出力:"
　(lambda () 'a) " "
　(lambda () 'b) " "
　(lambda () 'c) " "
　(lambda () (+ 1 2)) "\n")

result>a b c 3と出力:a b c 3

入力
;副作用のある入力
;(文字列中の文字を一文字ずつ返すclosureを作成して返す)
(define (make-getchar s)
　(let ((pos 0))
　　(lambda ()
　　　(if (< pos (string-length s))
　　　　　(prog1
　　　　　　(string-ref s pos)
　　　　　　(set! pos (+ 1 pos)) ;副作用
　　　　　)
　　　　　#f))))
(define (putchar ch) (display ch))
(define skip 'skip)

(do-monad-input (make-getchar "a b c 3と出力:")
　putchar skip
　putchar skip
　putchar skip
　putchar skip)

result>abc3

出力で(lambda () 'a)
としているのは、遅延評価の代わりです。(delayでも良かった)

>>307
お、さんきゅ。

>>309
副作用を起すためには命令の順序を明確にしないといけないのは
確かだが、monadoってそういう意味なのか？
リストさえ作れば順序ぐらい明確になるだろ。

>>317-319
やってることはわかるがaction関数で副作用が起こってるように
しか見えない。
やはりmonado内で副作用を起すのが目的ってことか？

>>321
> 副作用を起すためには命令の順序を明確にしないといけないのは
> 確かだが、monadoってそういう意味なのか？
> リストさえ作れば順序ぐらい明確になるだろ。

遅延評価する処理系でも?
applyによるズル剥けに注目

何が重要なのかと言うとdo-monad-output（またはdo-monad-input）
を呼び出さない限り、何も起らないという事です。したがって、
monad-stream(ここではリスト)は処理自体ではなく、単にその見込みを
表現しています。monadが適用される場合に限り、actionが強要されます。
haskell識者の見解をお願いします。

>>323
評価戦略によらず評価順序を定める例としては面白いですね．
ただ，for-eachがリストの順序どおりに処理するということを
仮定しているという点では，これはシミュレーションですよね．
それに本来のモナドのモジュール化と切り分けが異なるし用語法が違うので
両方を理解していないと混乱を招くと思います．
例えばHaskellの>=に当たる部分がdo-monad-*に含まれてしまっているし，
putcharやskipの部分をモナドと呼ぶのは適切ではありません
（Haskellの用語としてもカテゴリー理論の用語としてもおかしいです．
どこかでこういう用法をご覧になられたのですか？）．
むしろこちらをアクションといった方がHaskellの用語に近いと思います．
そもそも切り分けが違うのでどうやってもぴったりは合いませんが．

>>321
あと副作用については話が混乱してますが書いてる時間がないな．
一言で言うと，環境の変化という副作用と新たに実装する副作用は
別だということです．モナドでできるのは後者です．
schemeの例ではその部分ははしょって
そのままschemeの破壊的操作を使っていますね．
これも混乱のもとかな．

age

[1..100] >>= (\x -> "age ")

で、モナドの決着はついたの？

全然わからん。

モナドを使った短小プログラムぎぼん。

月並みだけど、小文字入力すると大文字出するやつ
toBig = getLine >>=
(\s -> if s == ""
then putStr "\n"
else (putStr (s >>= (\c -> [chr (ord c - 32)]))
>> putStr "\n" >> toBig))

>>330
toUpper 使おうよ。

n+kパターンって
dec (n+1) = n
ってやつですか？

ナニソレ

>>333
よくしらんけど
http://www.haskell.org/onlinereport/preface-13.html#sect1.4

http://www.pro.cs.titech.ac.jp/~tomo/programming.html

ここで言ってるCPSって何よ？

Haskellで実用的なコード書いる人いるの？
つーかHaskellで実装可能な
実用的なコードってどんなの？

> Haskellで実用的なコード書いる人いるの？
書ける人はいる。書いてる人は少ない。多分。

> つーかHaskellで実装可能な実用的なコードってどんなの？
質問の意図が微妙。
Haskell で書かれた実用的なプログラムのコードが見たいのか？

「VB で書かれた有名なソフトって何があるの？」
みたいな意味だと推測。

>>335 Continuation Passing Styleだね。
継続を渡す奴だ。って俺もまじめに使ったことない。

>337
言語って基本的に問題を解決する手段だと思うんだけど
Haskellっていったいどんな問題を解決するのかって事。

VBよりGUIが作りやすく、Perlよりお手軽で、C++より大規模開発に向くのか、
それとも単にマニアが習得を「目的」にしているのか？とかね。

MLかHaskell覚えようかなと思ってるんだけど、
応用がきかずに結局習得しただけだったってのも悲しいので。

>>340
>VBよりGUIが作りやすく、

現在はGUIを作るライブラリがそもそも無いんじゃないか？
ただ、将来はHaskell.NETが出るらしいからそれで劇的に状況が
変化するかも知れない。

>Perlよりお手軽で

インタプリタはあるし、簡潔な表現は出来る。だが、慣れないと
難しいという意味ではお手軽とはいえないかもしれない。
ライブラリの多さにも疑問が残る。

>C++より大規模開発に向く

モジュールシステムはあるが、C++のクラスに相当するものは無い。
これは意見が分かれるところだろう。

MLかHaskellなら、挫折が嫌ならML、理解力に自信があるならHaskell
という選びかたをすればいいと俺は個人的に思う。

> 現在はGUIを作るライブラリがそもそも無いんじゃないか？
ありますよ。
http://www.haskell.org/libraries/#guigs
でも Haskell で GUI は大変そう。

> C++より大規模開発に向く
俺は Haskell のほうが断然向いてると思うよ。

>>342
使ったこと無いけど、なんか全部UNIX系のっぽいし、日本語通らなそうだね。
これは偏見で悪いけど、多分使いもにならないんだろうな。

>>343
まあ，ちょっと前のRubyなんかと状況は同じと思えばいいんじゃない？

age

>>343
たとえば日本語文字列をRubyなみに簡単に取り扱うには、
組み込みの関数ではぜんぜん足らないので、自作するか、
誰かが作ってくれるのを待つしかない。そういう意味では
「実用性に乏しい」と言えるだろうね。

さらに言えば、MLやHaskellの強みって、robustなプロ
グラムを支援するところだと思うんだけど、いわゆる
「実用的なプログラム」の世界ってのは、robustである
ことよりも、むしろquick and dirtyであることが期待
されていることが少なくないよね。そういう意味ではML
やHaskellは「実用的」ではないと言えるでしょう。

これは僕の期待だけど、任意の言語から呼び出し可能な、
robustなライブラリってのはすごくニーズがあると思う。
MLなりHaskellなりで書かれた関数が、シームレスかつ効
率的にRubyあたりから呼び出し可能だと、すごくありがた
い。

>>346
Haskellはccallで直接C関数が呼び出せるし8-bit cleanだから，
後はどれだけよってたかって整備するかというstatusだと思うけど．
素性として実用的ではないというのと，現時点で実用的でないというのは違うしね．

>任意の言語から呼び出し可能な、robustなライブラリ
っていうのはどっちかって言うと.NETの世界かな？能書き通りにいけばだけど．

お前等sageすぎ
真面目な話してるときぐらいageようや

>>346
＞robustなプログラム
例えば、原子炉制御システムのプログラムに、プログラム正当性の証明も付けて
提出したとか、そういうことですか？

>プログラム正当性の証明
無理です

>>350え！？

おめーら、遊んでる場合か〜！
御仕置だべ〜！

モナドどうなったのよ？
あの説明でいいの？

モナドはモジュール化のタメにあるのです。

R
R
R
R
R
RR
RRU
UUUU

UBBBBBBBBYYYYYYYYYYRRRRRRRRRUUUUUU
BBBBBBBBYYYYYYYYYYRRRRR
RRRRUUUUUUBBBBBBBBYYYYYYYYYYRRRRRRRRRUUUUUUBBBBB
BBBYYYYYYYYYYRRRRRRRRR
UUUUUUBBBBBBBBYYYYYYYYYYRRRRRRRRRUUUUUUBBBB
BBBBYYYYYYYYYYRRRRRRRRRUUUUUUBBBBBB
BBYYYYYYYYYYRRRRRRRRRUUUUUUBBBBBBBBYYYYYYYYYY

>>355
ああウザイ

英治

>>355
shigeは帰っていいよ。
おまえのようなアフォには関数型言語は高級すぎる。

age

>>356 >>358
反応するな。
放置せよ。

GHC 5.02 がリリースされました。
5.00 - 5.00.2のときは提供されていなかった（と思う）Windows版の
バイナリーもあります(26.1MB)。ただ今ダウンロード中……。

>>360
Mucho hacking on the .NET code generator, including some FFI
extensions for .NET interop. It's still severely b0rk3d,
so won't do anything useful. Yet.

だって．ほんとにやってるのね．

ヨ−ロッパの方ではコンピュ −タサイエンスの学科の人が初めて教わるプログラミング言語が Haskellだということが結構あるらしいですね。

Amazonから
Introduction to Functional Programming using Haskell
second edition by Richard Bird
が届いた。Prefaceにこの本はプログラミングの経験は必要と
していないが、数学的推論の素養は必要とするとある。

追加。
この本は1年生のプログラミング教育に最適とある。
University of Oxford で。

>>363
私もその本を注文しました。
もう一冊の洋書も併せて注文しましたが、
いろいろ小面倒なルートを経て手元に来るらしいので、
あと1ヶ月はかかりそう(爆)
やっぱりamazonは偉大ですね…

>>360
いくつか不備があったということで、新しいバイナリーが再アップ
されています(26.7MB)。

>>365
私もある洋書を近くの書店で注文したら1週間ほど経過した頃に
「入手できない」と言われ、アマゾンで注文したところ、約2週間で
届きました。初めて利用しましたが、配送料も取らないみたいですし
なかなか便利です。

初めてGHCiを使ってみました。
Hugsと同じ感覚で使えるのですぐに使えます。
ファイル読み込み時に

Compiling Main

などと表示されるので、読むと同時にコンパイルもしているので
しょうか（マニュアルをまだよく読んでいない）。
そのせいかどうか、実行速度が速いです。Hugsで40秒弱かかる
プログラムがGHCiでは6秒ほどで終わりました。

HaskellとSchemeってどっちが良い？

１年生にを教えるプログラム
MITではScheme、OxfordではHaskellらしいが本当？

そんな事よりも
SchemeとHaskellの違いが知りたい
SchemeはMIT発祥だから・・・

Schemeの方が簡単だと思うけど

schemeすぐわかったけど、
haskellわけわからん。

>>370
違いなんて、見ただけでわかると思うけど？

見た目の違いじゃないだろ（笑）

ところで、
「haskell使い」と自分で名乗れる様な人はこの板にいるの？

モナド解説してほしいので

＞scheme使い
うざい。

とりあえず、見ただけでわかった違いを言ってみろよ
どーせ、どっちも使えないカスなんだろ

Scheme 正格
Haskell　非正格　遅延評価

こういうつらない話題は止めよう。
Schemeは別スレがあるからそっちで
やるのがよろし。
比較するのは関数言語スレでお願いします。

ちょっと前にGUIの話が出てましたが
http://www.haskell.org/mailman/listinfo/
にあるHaskellやGUIのメイリングリストで，
汎用GUIインタフェースの設計について色々議論されています．
ログも見ることが出来るので英語を苦にしない方は覗かれるといかがでしょう．
この手の議論って結構楽しいんですよねー．

で、モナドは？

やっぱHaskellとSchemeの最大の違いは型システム
だろうね。
あと、Schemeが状態バリバリの命令型に近い言語に
対して、Haskellはモナドをバリバリに使わない限り
関数型のスタイル。

Haskellで何か実用的なものを作ろうとしたら
何がいいかな？

>>384
正直言ってWindowsではGUIさえ出来ればいろいろ
作れると思うのだが、GUIが出来るのかどうかが
問題だな。

Windowsに限らずGUI無しで実用的なプログラムは
ちょっと思いつかない。

>>385
おまえ、>>342にあるURLのpage見ろよ。
>>386
おまえ、programmer止めた方がいいよ。

>>387
なら何か提案しろyo！

Win中心に物事を考えるのって、なんか寂しいよね…

基本はコンソールだ！ｺﾞﾙｧ！！
やっぱりダメなものはダメって言わないと！　ぁぅぇ？

で、Haskellで作ると良い実用的なアプリって何？

別にHaskellは汎用言語なんだから、何でも好きなものを
作ればいいんじゃないの。現状の処理系で気軽に作れる実
用的なアプリって話だと、たとえばXMLパーザとかHTML構
文チェッカなんかはどうかね。正当性の確認みたいな作業
は、厳密さが価値だからね。

haskellの様な型推論ありの処理系を、
自分で作るとなると難しいでしょうか

>>393
言語仕様によるとしか言えないよね。

たまにこのスレに出てくる「モナド」って、
何の事ですか？

>395
I/Oの多いプログラムの事を「ﾓﾅ度が高い」と言います。

ｿｳｶﾓﾅ…

ruby撲滅スレ
http://piza2.2ch.net/test/read.cgi?bbs=tech&key=1001125342
ruby撲滅スレ
http://piza2.2ch.net/test/read.cgi?bbs=tech&key=1001125342
ruby撲滅スレ
http://piza2.2ch.net/test/read.cgi?bbs=tech&key=1001125342
ruby撲滅スレ
http://piza2.2ch.net/test/read.cgi?bbs=tech&key=1001125342
ruby撲滅スレ
http://piza2.2ch.net/test/read.cgi?bbs=tech&key=1001125342
ruby撲滅スレ
http://piza2.2ch.net/test/read.cgi?bbs=tech&key=1001125342

type で作った型シノニムを class の instance にしたいと、よく思う age

http://www.genpaku.org/monadj.html

ヴィトゲンシュタインの哲学書のようなモナドってなあに？

>>400
楽しい？

>>402
まったく関係ないわけでもないのだけど…

>>1発見!

http://cocoa.2ch.net/test/read.cgi/unix/990764339/300-305
>>365

>>255
hugs98/demos/Examples.hs でこんなもの見つけた。

hamming :: [Integer]
hamming = 1 : (map (2*) hamming || map (3*) hamming || map (5*) hamming)
where (x:xs) || (y:ys) | x==y = x : (xs || ys)
| x<y = x : (xs || (y:ys))
| y<x = y : (ys || (x:xs))

>>405
hugs98/demos の下はそのうちゆっくり見ようと思いながらまだ
見ていませんでした（見た記憶があるのはQueen.hsくらいかな）。

この hamming 、とても速いです。しかも私が作ったものとは違って
ちゃんと小さい順序にならんでいるし・・。コードを見ると、
「ああ、なるほど」とは思いますが、自力じゃなかなか思いつかない
ような気がします。修行が足りないなあ。

ところで、このハミングの綴りは Examples.hs にある hamming が
正しいようですね。

age

Haskellは趣味でいじっているだけので、本業が忙しくなると全然遊ぶ
時間が取れず困ります。

>>286
＞ACMのmembershipがあれば、
＞http://www.acm.org/pubs/contents/journals/surveys/
＞でPDF取得できるけど、高いからねー。

比較的そばにある図書館で読めることは分かったのですが、なかなか
足を運ぶ時間が取れないし、いちいちコピーするのも面倒なので
ACMのmembershipを買ってしまいました。高いことは高いですが、
読みたいと思ったものがあったときに自宅ですぐダウンロードできるのは
やはり便利ですものね。

＞http://www.acm.org/pubs/contents/journals/surveys/1996-28/
＞は面白いの一杯あったよ。

記事の数がとても多くてタイトルを眺めるだけでも結構時間がかかります。
いずれ時間ができたときにゆっくりと見てみたいです。

>>408
俺も研究の方が忙しくて、なかなか手が出せない。
つい最近、アッカーマン関数を定義したけど(笑)
acker :: Integer -> Integer -> Integer
acker x y
| y == 0 = 0
| x == 0 = 2 * y
| y == 1 = 2
| otherwise = acker (x - 1) (acker x (y - 1))
たったこれだけ…。
けど、C言語を泣く泣く使うよりも楽しいな。

age

なにが楽しいのかわからん

monadはmonoid（群のなりそこない）のパクリらしいとの
話もあるが本当か？

あるかのいど！
あるかで思い出したけど
アルカードはドラキュラのアナグラム

へぇー！

>>412
http://www.matematik.su.se/~haberg/で許してくれないか…

monoid 単位半群

http://www.gavo.t.u-tokyo.ac.jp/~hosoyama/softkiso/soft1b.html

Wadler先生のMonadの論文が日本語で解説されてるぞ。
monoidも説明されてる。
http://www.is.titech.ac.jp/~kando9/work/Progress/Monad/Monad.html

>>417
さっぱりわからないけど、IO aというのは意図だったのか。
値が違っても意図は同じだから、意図は参照透過って意味ならなんか納得。

Category theorists are infamous for stealing terms from
philosophy, starting with the theft of category itself
from Kant. The abduction of monad from Leibniz was aided
and abetted by the pun on monoid. (by Richard Bird)

Haskell で計算量 O(1) で挿入、削除を出来る queue を作れますか?

>>417のリンク先を書いた人の趣味：
http://www.nerimadors.or.jp/~chihiro/

ｽﾃｷ

http://mentai.2ch.net/test/read.cgi/philo/1002692332/
ﾗｲﾌﾟﾆｯﾂﾏﾝｾｰ

モナド理解できない。イロイロ妄想が膨らむなあ。
アマゾンみてたらこんなのもあった。

唯心論物理学の誕生―モナド・量子力学・相対性理論の統一モデル
と観測問題の解決
中込 照明 (著)
ライプニッツのモナドを論をヒントに観測問題をついに解決！
意志・意識を物理学の範疇に取り込んだ新しい究極の物理学。
コペルニクス的転換の書。

観測問題ってのは解決しないから問題として取り上げられる
もんだと思ってたけどちがうんか。。。

ライプニッツごとき盗人の話を信じてはいかん。

最近このスレ廃れてきてるよな…。
もう潮時かね…。

>>427
スレ半分まで来たんだおー。あと一息だおー。

ここが正念場、これを乗り切ればSchemeスレのように黙っていても
スレが育つようになります>>427

>>420
このあたりの議論はIFP本(>>277)に詳しく書かれているようです。
まだちゃんと読んでいませんので、O(1)で実現できるのかどうか
理解していません。また、関数型言語向けのデータ構造については
Chris Okasaki 氏の本(>>7)が詳しいです。
内容のない投稿ですが、スレを伸ばすためということでご勘弁を…。

これらの本をゆっくり読みたいなぁ。。。

モナドは理解するのは諦めて、使い方を学ぶことだけに
徹するのが良い。
使えるだけで十分。

言葉を学ぶことはその用法を、ってやつだね

おれもさっさと用法をマスターしないとｗ

>>424
電波くせー

Haskellって日本語の本はないんですよね？
このスレを興味深く読んでたんですが何から
読み始めればいいのやら

>>434
>>2にある日本語サイトである程度学べるよ。

>>435
ありがとうございます。
最近寂しいこのスレを盛り上げられるよう勉強して
いきたいです。

>>435　436です
http://www.amazon.co.jp/exec/obidos/ASIN/4756103170/
とりあえず古本屋で買ってそのままになってた
こっちから勉強します。関係あるかどうかよく分かんないん
ですが関数の集合的な記述の仕方とかためになりそうなんで、
まずはこれをやってからにします。

O(1)で動くQueueのことちょっと考えたが、
Queueの前に配列ってHaskellでどうimplementする？

配列をリスト使って、(!!)演算子使ってindex指定し
ても、O(n)かかるしな。

ようするに、O(1)で作動する配列(Array)を教えてくれ。

>>438-439
import Array
ではいかんのですか?

でもリングバッファみたいなやりかただと
要素数が限られてきて、一杯になったときのことを考えると
ちょっと不満だったり。
まあ、実際に使う分には、うまくやれば大して問題ないだろうが。

>>430
英語の本か…
とりあえず Chris Okasaki 氏の edison ってライブラリ
http://www.cs.columbia.edu/~cdo/edison/
に queue があるのでそれを読んでみている。

でも、実際には stream が queue みたいなものだし、
Haskell でプログラミングしていて queue が必要になることは
あまり無いのかも。
-- 実際必要になっても O(1) じゃなくてもいいなら手はあるし。

なんか、うまくやれば、綺麗に実装出来そうな気もするんだがねぇ。

>>440
サンキュー。
ライブラリーにあるArray.hs見たけど、修業たりなくて
すぐにはわからないな。

>>441
Array は primitive ばかりで見てもわからなくってあたりまえ。

http://www.sampou.org/haskell/library-j/array.html
こっち見てくれ。

お、ライブラリの解説があったんだ。
>>442
ありがとう。これから読んでみる。

HaskellでHashとか実現できるんですか?
データを保持する「変数」がないから、どうなんだろう?

444ｵﾒﾃﾞﾄｳ>444

>>444
出来ますよ。
というか、ハッシュ法と変数(というか代入)は関係ないような。

ってなんか語弊がありそうな表現だな…。

>>446
＞出来ますよ。
それは自然に、あたりまえにできるという意味ですか？
精いっぱいがんばって(それでも遅いけど)、なんとかできました、
って事じゃないのですか？

へ？そんなの当たり前に出来るだろ。標準のライブラリに無かったか？

標準のにあったぞ。
assocs :: (Ix a) => Array a b -> [(a,b)]
assocs a = [(i, a!i) | i <- indices a]

>>449
それっって違うんじゃ…。

>>447
まあ、自然にできますな。大した苦労もせず。
といっても、処理系が配列を巧く扱ってくれないと遅くはなるかもしれないが
大抵はうまくやってくれるかと。
つか配列の話はハッシュに限ったことじゃないな。

age

正直、Lispを越えられるか?と思ってHaskellを勉強したんだけど
Lispの強力な記述能力を超えられると思う?

>>452
もしかすると、超えてないかもしれないけど、Haskellと同等の記述をLisp
で得るにはHaskellインタプリタをLispで書くのと同じぐらいの労力を払った後、
やっと出来るようになる、と思う。

>>452
つまらん答だが柔軟性と安全性のどちらに体重をかけるかによる．
記述能力といっても一種類じゃない．

>>454
あと、理解のしやすさや簡潔さも。
これを無視すればアセンブラが一番柔軟とも言えるよね。

>>455
Haskellも楽しいけどこういうのもなかなか．
ttp://www.csl.sony.co.jp/person/fnami/asm.htm

LISPのインタープリタをJAVAで書いたことがあるが、
Haskellのインタープリタも書いてみたい。
遅延評価ってどう実装する？
LISPの評価は関数呼び出して、その結果を受けるだけと
素直だが、遅延評価はどないしよう。
イベント送信して受信するようなことするか？？？

IOモナドは意図なのか
俺のような初心者に実感のある関数（例えばf1とf2とする）
はたとえ高階関数であっても引数にapplyさせてみて返って
きた値（実感のある数や文字列だとする）を見比べればf1と
f2が同じか違うかをなんとなく感じることができるけど
IOモナドはどうやって比べられるのだろう？IOモナドに何か
applyさせても返ってくるのはIOモナドなんだよね。出力を
見比べていいの？出力は副作用の結果だから比べちゃいけ
ないような気がしたんだけどそんなことない？

おれもIOわからん。
IO :: ((IOError -> IOResult) -> (a -> IOResult) ->
IOResult) -> IO a

>>457
効率よく実装するのは大変だが、安直にやるなら…
直感的には、すべての関数呼び出しの実引数をdelayでくるんで、
仮引数を参照するときにforceを付ければよい。

>>458-459
Worldという、コンピュータの全状態を表す型があるとする。
もちろんこの型のオブジェクトは１つしか存在しない。
IO tは「Worldを受け取り、状態を変化させたWorldを返すコマンド」型。

例えば
putChar :: Char -> IO ()
は、「Charを与えると、IOコマンドが返ってくる」関数。
返ってきたコマンドにWorldを与えると、状態が変化したWorldが返る。

main = do
　　　　putChar 'a'
　　　　putChar 'b'
とすると、mainはIO ()型になる。
システムがこれにWorld型の引数を与えて呼び出す。

ミソは、このインターフェースだとWorld型のデータに直接さわれないこと。
なので、「状態が変化する前のWorld」と「変化したあとのWorld」が
同時に存在して困る、などということが起きない。

>>459
サンクス。なんとなくわかったような。
delay, force ってメソッド？　javaやlispにはないよね。

>>453
> Haskellと同等の記述
ってどの程度のこと言ってるの?
遅延評価だけなら結構簡単にできるよね?
型システムも?
curried function とかも?(これは簡単そう)

どうでもいいけど、curried function と S式って、相性悪いよな…。

>>461
おおよそ　IO::World -> World って感じなのかな。
IO t でｔに（ ）以外の値とることある?

>>463
>curried function と S式って、相性悪いよな…。
そうかなあ？　S式は一つ目に関数名がきて、後は
引数がだらだら続くから、curryのように思える。
そんなに相性悪くないと思うが。。。

>>465
Haskell 風に書くと
f :: a -> b -> c -> d
のような関数があると
((((f a) b) c) d)
って書かないといけないような…。

(f a b c d)
((f a b c) d)
(((f a) b c) d)
のような書き方も合法とするのは、なんだかねぇ…。

と、俺は思うのだが…。なんかズレてる?

>>462
delayとforceはSchemeにあるよ。

>>464
まあそう。IOは、最初はST(State Transformer)と呼ばれてた。
getCharはIO Char型だよ。
do
　c <- getChar
　putChar c
は、実はsyntax sugarで、getChar >>= \c.(putChar c)のこと。
(>>=)はIO a->(a->IO b)->IO b型の演算子。

システムは、まずWorldを引数にgetCharを呼び出す。
返ってきたIO Char型の構造体からCharを取りだし、
\c.(putChar c)を呼び出すと、IO ()が返ってくる。
それをWorldを引数に呼び出す。

>>464
もちろんあるよ．
World->Worldっていうのは気分であって裏でやる計算だから表には現れない．
一方その計算の結果として表である値を返すときはモナドにその型が入る．
IOに限らずモナドの型 M t というのは
裏である計算をして表でtを返すことを表している．
モナドの定義はその裏の計算を定義しており
一種のメタレベルの記述と見なせる．
だから状態とかインタプリタの例がよく出てくるわけ．
ちなみにHaskellの()は値がないわけじゃなく一つしか値がない型
を表している．ただその値は自明なのでいちいち書かないだけ．つまり上で，
ある値を返すときと書いたが，関数型だから実は必ず値を返している．

つか、d も渡してるし…
> f :: a -> b -> c -> d -> e
に訂正

　この職って会社のどんな事に役立ってるのですか？
まだ社会人ではないのでまったく想像できません。
ソフトってものはどんなものなのか・・・・・？
それが何の役に立つか何を作っているのか・・・・・？
みなさん教えてください。

>>466
なるほど、言われてる意味がわかりました。
f::a->b->c->d
(((f a) b) c)
(f a)も((f a) b)も関数ですね。
(f a)::b->c->d
((f a) b)::c->d
ということね。
でも実際は(((f a) b) c)と書くとエラーよね。
高階関数を使えるというのがHaskell。lispは
高階関数は使えない？

>>467
MLやHaskellで、多引数っぽい関数を書くのに
a->b->c->dみたいにカリー化するのと、
(a,b,c)->dみたいにデカルト積を使う流儀とあるよね。

Haskell: f a b c
Lisp: (((f a) b) c)

Haskell: f(a,b,c)
Lisp: (f a b c)

って感じでは？

>>467 じゃなくて >>468 でした。

>>471
LispだとエラーだけどSchemeだとエラーにならない。
Lispだと(funcall (funcall (funcall f a) b) c)。欝。

>>471
そんなことないです。
(define (f a b c)
<code>)
を
(define (f a)
(lambda (b)
(lambda (c)
<code>)))
で curried 関数の出来上がり。

って、Lisp は高階関数使えないのか…?
scheme しか知らん…。

そういえば、いまだにgetCharが参照透明性を失ってない理由がわからない。
IO 'a'とIO 'b'は別の値ということで良いんですか？
別の値なのに、参照透明性を失ってないということなんですか？

>>477
http://piza2.2ch.net/test/read.cgi/tech/996131288/248-263
これの続き?

>>477
「getCharを呼ぶとCharが返ってくる」と思うと副作用に見えるかも知れない。
この解釈は間違い。

World型の値w(プログラマには見えないし触れない)があるとして、
(getChar w)を計算した結果、「状態が変わったw」と文字が得られる。

do
c<-getChar
putChar c

の実行を図にするとこんな感じ。

　　　　　　　 World
　　　　　　　　 ↓
getChar　　→ コマンド → cの値
　　　　　　　　 ↓
putChar c　→ コマンド
　　　　　　　　 ↓
　　　　　　　変化したWorld

式で書くと
let (c,w2)=(getChar w)
in ((putChar c) w2)
みたいな感じ。

>>479
つまり、見えない「w」という引数が省略されてるって事か？
「getChar」と書いてあるのだが、実は「getChar w」だった
というような。

>>480
気分としてはそういうこと。
wはプログラマからは決して見えない
（ように設計してあるものをモナドという）。

納得行かんなあ。副作用が無いんじゃなくて、副作用の部分を
書いてないんでは？
プログラムが未完成で、実行時に補完してるのか？

>>482
まあ「副作用の部分を書いてない」といえばその通りだが...

例えば配列aのn番目にvを代入するのに、
set_array :: Array a->Int->a->Array a
という関数があるとして、

let a2 = set_array a n v
in
...
set_arrayが「変更された後のa」をa2として返すものとする。
これは参照の透明性を何ら損なわないよね？ ただし、破壊的に
代入はできない。aを（少なくとも変更部分だけ）コピーして
おかなければならない。

ここで、「set_arrayが値を返した後は、古いaが使われることはない
（古いaの値を見ているやつは誰もいない）」と保証できたとする。

すると、わざわざコピーしなくても、上書きしてしまっても、
誰も副作用に気が付かない。つまり、コピーしても
上書きしても意味としては同じことになる。

「Worldへの参照が、必ず1個所しか存在しない」ことを保証する
ように工夫したのがモナド。純粋に関数的に解釈するなら、
「putCharするごとにWorldがコピーされる」と思えば良い。
ただし、実際には副作用を使っても、絶対に誰も違いに気が付かない。

>>483
ということは、モナドを返す関数は、引数が省略されてる特別な関数だと
いうことになるわけ？
Worldを参照してそれを表記では省略しなくちゃいけないのだから、
普通の関数とは働きが違う。
働きが同じだとするとWorldの参照が副作用になってしまう。
つまり、モナドクラスはただのクラスじゃなくてなにか特別な
意味を持つクラスだとしなければつじつまが合わない。

ライプニッツ入門みたいにも読めるこのスレ大好き！

>>484
monad と IO を区別しようよ。

>>484
別に特別というわけではないよ。
ただの高階関数。何も省略なんかしていない。
do以外は、特別な文法を加えたわけでもない。

引数を一部しか与えないなんて、Haskellでは普通の話。

また、Worldという型が直接は触れなくて、IO a
を通してしか操作できない、というのも普通の
抽象データ型。良くある話。

参照が副作用になるってどういう意味？

>>486
別にmonadの例としてIOを語ってもいいんじゃない？
IOはMonadのinstanceなんだし。

>>484
何も省略してないという意味は、
「Main.mainにWorldを引数として与えるのは
システムの仕事。プログラマがmainを呼び出したりは
しない。」と言う意味。
Cで、mainに引数を与えて呼び出すのが
システムの仕事であるのと同様。

もしかしてgetCharの返す値って「入力した一文字を返すと
いう処理」そのもの（マシンレベルでいえば入力した一文字
を返すという処理を行なう機械語列）のこと？それなら
「意図」も腑に落ちるのだけれど。外してる？

補足
処理そのものと解釈すれば
>>= および return を支配している法則
return a >>= k = k a
は「aが返されてそれに対してkすることはaをkすることに等しい」
m >>= return = m
は「mしてreturnすることはmすることに等しい」
と読めるのだけれど。

おお，話が進んでいる．
>>490
そう．裏で実行される計算を返す．それが（裏で）実行されるのは>>=のとき．
ユーザ定義でないモナドであればマシン語レベルと言ってもよい．

>>477
IO Char という型はありますが、IO 'a' や IO 'b' という値(データ)
はないのでは。。。

>>493
でも、Charという型には'a'っていう値があるんじゃないの？

>>487、>>489
でもWorldという値はどこにも定義されてないよね？
やっぱりそういうどこでも定義されてない裏の値みたいなのを使うのは
副作用なのでは？

自動詞の暗黙の目的語としてのWorld（むちゃくちゃかも。藁）

>>495
言いたいことが良くわからない。何がどう副作用なの？
IntやCharの本体の定義も無いと思うが？

>>494
data Foo Char = Foo (Char -> Int)
としたら、
Foo Char という型はあっても、Foo 'a' という値はないのでは。。。
型構築子とデータ構築子とが混同されているような気がしたもんで。。。

>>497
IntやCharは型でしょ？
Worldは実際の変数でしょ。
だから、その変数の定義が無いと値が決定できないと思うんだけど。
外部から取得したことになっちゃわない？

>>499
World型って言っとるやん。
それに、実際には直接出てこないんだからさ。
CでFILE*使ってもデバイスドライバに関するデータが
プログラム中に出てこないのと同じ。

こんな例はどうだろう。

C言語でRobotをコントロールする。

このRobotには、例えばforward(前進),turn(回転)などのコマンドが
使えるとする。

roboMainという配列に、
char *roboMain[] = { "turn 45", "forward 10", ...};
のように書いておくと、Robotがこれを読み取って実行するものとする。
Cの世界では全く副作用は起きていない。

しかし、これだとRobotからの値を受け取ることができない。
また、Robotの動きを実行時に変えることもできない。

なので、配列に入れるのではなくて、lazyなリスト構造にしよう。
struct roboProgram {
　command (*command_generator)(void);
　struct roboProgram *(next_command)(int arg);
};

commandは（まあchar*でも良いのだが）Robotへのコマンドを表すデータ。
command_generatorはcommandを生成する関数。
next_commandはプログラムの続きを生成する関数。

関数 make_program(command (*com_gene)(void), struct roboProgram (*next)(int));
で、リスト構造が作れるとしよう。

struct roboProgram *roboMain()
{
　return make_program(turn_45, step2);
}

command turn_45(void) { return turn(45); }
struct roboProgram *step2(int ignore)
{
　return make_program(forward_10, step3);
}

command forward_10(void) { return forward(10); }
struct roboProgram *step3(int ignore)
{
　return make_program(get_x_pos, step4);
}

struct roboProgram *step4(int x_pos)
{
　return make_program(turn(x_pos / 2), robo_stop);
}

＃しかしCでlazyなリスト作るって面倒だな．．．

上で、forward(10)やturn(45)を実行したときにRobotが動くわけじゃない。
"forward 10"とか"turn 45"とかいう「コマンド」を返すだけ。
同様に、get_x_posは常に"get_x_pos"という同じコマンド値を返す。

さあ、どこに副作用がある？（いやsprintfは副作用だけどさ^_^;）

>>500
World型といっても、実際の値があってそれを参照してるよね？
だって、状況によって、モナドが返す値が違うんでしょ？
つまり、それは値を参照して、その値によって返す値を変えてるってことでしょ？
外部から値を参照してるようにしか見えないけど。

>>502
値はオンナジだよ。

>>502
もっと具体的に言って？
どこでWorld型の値を参照してて、
どこで副作用が起きてるように見えるの？

もちろん裏では副作用は起きてるわけだけど、
Haskellの世界では全く見えないはずだが。

ストリーム使ったI/Oや継続使ったI/Oでも、
副作用が単に隠されてるだけなのは同じだよね。

>>504
たとえば、getCharの例を出すと、'getChar'と書いてある所で、'getChar w'を
実行してるかのようにWorld型の変数wを参照してるというのが今までの
説明だよね？
すると、この変数wの中味というのは、外部から与えられた値になると
思うんだけど、このように内容がころころ変わる変数は副作用に思える。

>>492
おー、合ってたか、うれしい。
入出力の章に書いてある
|アクションは式言語のHaskellでは呼出すのではなく定義する
|ものです。アクションの定義を評価することでは、実際のアク
|ションは起こりません。むしろ、アクションは、ここまで考え
|てきた式の評価というものの外側で起こることです
の「アクション」が「処理そのもの」にあたるのだな。

直接触っちゃいけないもの（IOの場合は副作用の起こる処理）
をモナドで包むのね。モナドがコンテナというのはそういうこと
か。Maybeがモナドな理由もこれでわかった。（Maybeは副作用と
は関係ないけど）
んで、直接触っちゃいけないものに触れたものはモナドの演算で
感染していって感染した部分は最小限のモナドで包まれていくと
いうことか。モナドなんとなくわかったよ。
こんな簡単な話だったのか。

>>505
ちゃうよ。getCharと書いてあるところでは
getCharの値（いつも同じコマンド）が返るだけ。

そのコマンドにwを与えて呼び出すのはシステムの仕事。
当然、毎回異なる引数が与えられるから、毎回異なる値が返る。

getChar wを呼び出した結果、World型の値w2が得られたとする。
呼び出す前のwは2度と使われない。

>>501 を見ても分からない？

getCharと書かれた部分は毎回同じ値を返すのか？
yesかnoで答えてくれ。

>>507
>>501を見ても、実行の仕方が書いてないのでなんともいえない。

>>507
どこがちがうの？501も507も俺の思ってるとおりのこと言ってるよ

>>505
>>479 をもっかい見てみたら？

getCharが2回続けて出てきたとして、
do
　c1<-getChar
　c2<-getChar
　...
実行時に起きることの気分は、
let (c1, w1) = (getChar w0)
in
　let (c2, w2) = (getChar w1)
　in
　...
みたいな感じだよ？
どの行が副作用に見える？

>>511
w1とか、w2が省略されてるところが副作用に見える。
省略してる値がころころ変わってるから。

>>508
yes。毎回同じ値を返す。Haskellだから当然。

>>509-510
501のCプログラムのどの行で副作用が起きてる？

あ、ごめん。505にいってたのか

>>508
yes

>>513
501のプログラムは決められたことを決められたように実行してる
だけでは？
IOのように動的に値が変わってない。

じゃあ、
a=1;
a=2;
と同じことをモナドで書くとどうなるの？
どうして副作用が消えるの？

>>512
あー、そうか。

ええっと、
do
　c1<-getChar
　c2<-getChar
と
let (c1, w1) = (getChar w0)
in
　let (c2, w2) = (getChar w1)
　in
　...
が「同じだ」と言ってるわけではないぞ。

do
　c1<-getChar
　c2<-getChar
で「コマンド列」というlazy listが作られる。
このときにはまだwを引数にして呼び出したりしないし、
副作用も起きない。

そのコマンドを1個1個呼び出していくプログラムはシステム側にある。

Cの例で言えば、Robotがlazy listをたぐりながらコマンドを１つずつ
得て、コマンドを実行していく。その過程では当然副作用が起きる。

でも、>>501 で書いたCのプログラムでコマンド列を作っている部分
には副作用なんかないだろ？

>>517
書けない。
副作用はないので、『副作用が消える』ことはない。

>>518
なるほど。副作用の無いプログラムが、副作用のあるプログラムを
作り出してるのか。
作り出すところまでが、Haskellということになるね。
また、何かわからないことがあったら質問します。

>>516
x_posの値は動的に得て、forwardの距離を変えているが...
Robotの位置が最初不定だとすれば、毎回違う動作をするはず。
別にここにif文入れて、「右にturnするか左にturnするか」とか
やってもよいよ。それでも副作用は起きない。

>>517
<-演算子のことを言ってるなら、
左辺は毎回新たに定義される変数だよ。

do
　a<-getChar
　a<-getChar
　...
は、
　getChar >>= \a->(getChar >>= \a->...)
と同じ。

Monadicにやるなら、こんな感じだろう。

instance Monad Var
...

define_var :: String->a->Var ()
　-- 変数を宣言し、初期値を与える
set_var :: String->a->Var ()
　-- 変数に値を代入する
ref_var :: String->Var a
　-- 変数の値を取り出す。

...
　 define_var "my_var" 1 >>
　 ref_var "my_var" >>= \a
　 ->set_var "my_var" (a + 1)
　 ...

define_var, set_var, ref_varは単に「定義しろ」「代入しろ」「参照しろ」
というコマンドを返すだけだから、副作用はない。そのコマンドを解釈実行
するプログラムにはあるかもしらんが。（副作用使う実装なら、Haskell自身
ではもちろん書けない。）

このスレ熱心な良スレだね。

名スレの予感

そう言えば、ghcにはHuggisとか言うGUIライブラリが付いてなかったっけ？
あれもmonad使うの？

>>524
え、Guarded Horn ClausesでGUIができるんか？

>>513
では、getCharがいつも返しているIO Char型の値は
一体何なんでしょうか？
その値はHaskellで直接表記可能でしょうか？
表記可能だとすると、その表記はどうなりますか？

>>525
通じない冗談は哀しいぞ．
そっちも面白いと思うけどね．

getCharが返しているのは>>=を適用したときに裏で実行されるはずの計算．
ユーザ定義でないモナドの場合は表記できない
（表から見ている限りgetCharの動作（意味論）はわからないことに注意．
getCharがランダムに値を返そうと常に同じ値を返そうと関係なく動作する．
これがモナドによる意味論のモジュール化ということ）．
データコンストラクタで陽に表現できるのは，
そのモナドに関する裏の世界が陽に見えるユーザ定義のモナドの場合だけ．

>>526

getCharの値はだから、これまで使っていたたとえで言えば「I/Oコマンド」。

表記可能か？ システム側の作りによるが、普通はstrictなプリミティブ関数
として表現するだろう。Haskellでは書けない。

>>528
Haskellの計算とシステムによる実行が切り分けられないので
foo = getStr >>= \s -> putStr "a"++"b"++s
の例で教えて下さい。
fooを実行（？）したときまずHaskellの計算ではどこまで計算
されるんですか。"a"++"b"は計算されるんですよね。>>=の
適用はまだですか。まだとするとfooの計算結果は
「getStr >>= \s -> putStr "ab"++s」という「意図」ですか。
入力と出力が行なわれるのは残りのシステム側の担当ですか。

関係ないけど、オブジェクト指向の生産性がどうの…
とかいうスレを見かけましたが、
ここで「オブジェクト指向すら無いの?」とわめいていた方々の
運命はどうなるのでしょうか?

>>531
関数型にはgenericがあるから別に・・

>>531
そういう人は、O'Haskellとか、Haskell++使えばいいんじゃない？
オブジェクト指向も関数型も一つの方法論として有効だと思う。

Haskellは完全にオブジェクト指向ではないってわけでもないよね。
例えばオブジェクト指向で重要な概念である、多態生が実現できるし。

>>534
type classは便利だよね。

>>526
一つの可能な実装として、Worldというシステム内でしか
見えないデータ型があるとして、
data IO a = World->(World, a)

instance Monad IO where
　 (l >>= r) w0　= let (w1, a) = l w0
　　　　　　　　　　in r a w1
　 return v w = (w, v)
　 m >> k = m >>= \_ -> k
　 fail s = error s
のような実装も可能だ。

putChar 'c'の値やgetCharは、
Worldが与えられるとI/Oを行うstrictなプリミティブ関数。
ここはHaskellでは書けない。

ホントにPreludeにこう書いちゃうと、
mainはWorld->(World, a)となってしまって
main w = ...
とかくとWorld型の値がプログラマに見えてしまうので欝だが。

>>530
内部でWorldを使って実装したと考えると、

WHNFリダクションは
　 foo w0
→ (getStr >>= \s -> putStr "a"++"b"++s) w0
<ここでシステムが何か良い事をする>
→ (\s -> putStr "a"++"b"++s) <some string> w1
→ (putStr "a"++"b"++ <some string>) w1
<ここでシステムが"ab..."を出力する>
→ ()
のように進む。

ワールドを与える前の高階関数のfooとしては
「getStr >>= \s -> putStr "a"++"b"++s」という「意図」と
「getStr >>= \s -> putStr "ab"++s」という「意図」のどちら
ですか。それとも上記は処理系の話であって計算とは関係ない？
ともかくfooを実行するとワールド込みで実行されてしまうの
ですね。我々はあるワールドの中（？）から観察しているので
副作用に見えるということでしょうか。

>>538
そういう哲学的な話は良くワカラン

"a"++"b"はコンパイラが最適化して先にやるかも知れんが、
lazy evaluationの原則から言えば、putStrが呼び出された
後まで評価されない。

>>538
もういろいろ説明されていますがせっかくなので違う言い方をすると，

表でfooが評価されると>>=が評価されて
あるIO Charの値（次の処理の値）が返されます．
++は>>=に渡される関数値の一部であり表の評価では何も起こりません．
一方このとき「実装」では裏からしか見えない処理も行っています．
ここで++に相当する処理がなされます．
ただしこれは裏からしか見えないので，
表の関数++ではなくあくまで++の「実装」の実行です．

ちなみに「意図」という表現は個人的には気持ち悪い．

なんか変なのでちょっと訂正．

>あくまで++の「実装」の実行です．
あくまで「実装」における++の実行です．

モナドは高階関数で、状態から状態への関数。
よって、モナドを使えば状態自体を表示する必要がなくなる
ので参照透明性が保てるという理解でよいですか。
高階関数であることがポイントという理解だけでは勉強不足？

>>
高階関数というのもあまり気にしなくて良いんでないかな。

状態を操作する関数を組み合わせると、
状態を陽に書かないまま任意の入出力操作が表せる。
組み合わせること自体には副作用が必要ない。

ってとこでは。

ときに、I/O以外のmonadの使い道って何？

よくしらんが副作用全般>547

>>544
未来に対してレスするとは、おぬしやるな！
まさか、547は自分で書くのか？

547は、where句で始めるんじゃないの？

>>543
hugs98/lib/hugs/ParseLib.hs
とか。
面白いし、わかりやすいので読んでみそ。

>>544
別に副作用以外でも monad の使い道はあると思う。

>>545-546
ご期待に添えずすみません。

>>547
monadの使い道知りたい知りたい。
例えばStandard Preludeではリスト[]は
Monadだと書いてあるが、どう使うの？

>>548
monad は do 構文を使うためにあるといってもいいかなあ。
たとえば、リストはMonadなので、

grid :: Int -> Int -> [(Int,Int)]
grid x y = do { i <- [0..x]; j <- [0..y]; return (i,j) }

てな書き方ができます。リストにはリスト内包表記というのがあるので
do 構文を使いたいことはあまりありませんが。。。

grid x y = do { i <- [0..x]; j <- [0..y]; return (i,j) }
これは
grid x y = [(i, j)|i <- [0..x], j <- [0..y]]
と同じ？

そうです。

http://haskell.org/tutorial/monads.html 読んでみた。
むずかしい…

サンキューです 539,540
IOモナドの中には表からはまったく触れられないんですね。
|表でfooが評価されると
この「評価」とは細かく言うとfooの計算ですか、それとも
foo w0の計算ですか。この区別が未だにわからない。
|>>=が評価されて
|あるIO Charの値（次の処理の値）が返されます．
putStrはIO ()だと思うのでこれは多分IO [Char]のことだと思い
ますが、ということは>>=が評価されると「getStr」が返される？
まだわからない。

>>553
あああ，すみません，間違えてます．

まず「評価」はfooの計算のことです．表ですから．
次ですが，おっしゃる通りputStrなのでIO ()のある値が返されます．
これがさらに>>=したときに行われるべき処理の値であることは変わりません．
これじゃ混乱してしまいますね．どうもすみません．

限りなく禿らしくあげ

Lispはプログラムがリストになっていて、自由に
変形、参照したり出来るのですが、これと同じように
Haskellで自分のプログラムをデータとして参照、変形
する方法はありますか？

Lispのreadとかprintみたいなのを言ってるなら、標準ライブラリ
にはないんじゃない？ Haskellの処理系も（きっと）Haskellで書
いてあるんだろうから、ついてくる処理系があっても不思議はない
けど。

Lispのマクロみたいなのを言ってるなら、高階関数はかなり近い
記述力を持っていると思う。

evalの事を言ってるなら逝ってヨシ。

>>557
いいえ、そうではなくて、マクロ展開のようなことを
したいのですが。

こういうスレを見るたびに大学は理系にしておくべきだったって思うよ

>>558
ソース→ソース変換のアルゴリズムを書いてみたい、という
感じなら、自分で構文木の表現を決めて試してみるのが楽。
data Exp = Combination Exp Exp | If Exp Exp Exp | ...
transform :: Exp->Exp
とかね。

本当にHaskellのプログラムを変換したいならパーザを書か
なきゃならないし、実行時に自分のプログラムを変換する
なんてことは無理だが。

age

Haskellやってみたい人が本を一冊買うとしたらどれがいいでしょうか？
テレホ＆洋書売ってる店がないという厳しい環境なので、リファレンスとしても
使えるようなものが欲しいのですが。

とりあえずHello worldはどう書くのさ？

HaskellなんかでCGIプログラムを書けますか？
Rubyは書けますよ。

>>563

module Main where
main = putStr "Hello, World"

>>564
あたりまえ。
shell scriptでも書ける。
何の自慢にもならん。

無限＋自然数＝無限　の証明において
数学的帰納法の基底にpartial number(未定義語、Tのさかさま）を
もってくる証明があるが納得いかない。

自然数を data Nat = Zero | Succ Nat
足し算を(+)::Nat->Nat->Nat, m+Zero=m, m+Succ n=Succ(m+n)
無限を infinity::Nat, infinity=Succ infinity
と定義。
m+n=nをnに関する数学的帰納法で証明
もちろんn=Zeroについては成り立たないからfinite numberに
ついては成立しない。
nがpartial numberのとき(Tのさかさまの表記がないのでUで
表記。すなわちn=Uのとき）
m+Uは足し算の定義のいずれにもパターンマッチしないので
m+U=U　よって成立。
つぎに、nのとき成立すると仮定してSucc nのとき成立する
ことを証明。m+Succ n=Succ(m+n)（足し算の定義より）
これに仮定のm+n=nを代入するとm+Succ n=Succ nでSucc n
についても成立することが証明される。
以上よりn=inifinityのとき上記等式が成り立つことが
証明されると書いてあるが本当？

数学的帰納法の基底に未定義語をもってくるというのは
数学的に正しいんでしょうか？

Birdの本は手元にないので実際のところはわかりませんが，
なんだか構文的な議論と意味論的な議論がごっちゃになっていますね．

ここで定義しているNatはinfinityを値に含むので
無限リストのように無限的なものです．

このようなものは帰納的にではなく余帰納的に定義されているとみなし，
構文的に証明するには帰納法ではなく余帰納法を使います．
この場合は帰納法のような最初の仮定はありません．
その代わりにNat上の同値関係=が
最大の双模倣であることを証明しなければなりません．
上にはこの部分の証明がありません．

また一方で意味論的に証明するにはモデルとその完全性が必要ですが，
そのときにそもそもm+infinity=mが成り立つように定義するので
上のような構文的な証明のステップを踏む必要は特にありません．

たぶん著者は直観的な理解をしてもらうことを優先したのでしょうけど
厳密な証明としてはおかしくなっているように読めます．
どちらにしてもちゃんとした説明はちょっと長くなりますね．

m+infinity=m はもちろん m+infinity=infinity の間違いです．

>>568 説明ありがとうございます。
たしかに直感的にはわかりやすい証明？ですね。
無限を無限によって定義するという、どうどうめぐりの定義が
可能なhaskellではこの証明法けっこう応用できそうな気がします。

まともな数学教育受けてないので、余帰納法とかわかりませんが、
それの説明は難しそうですね。

出典は
Introduction Functional Programming using Haskell
second edition by Richard Bird
p67
3.2.1. Full Induction
...If we want to show that a property P also holds for every
partial number, then we have to prove three things:
Case(U). That P(U) holds. （UはTのさかさまのかわり）
Case(Zero). That P(Zero) holds.
Case(Succ n). That if P(n) holds, then P(Succ n)　holds also.
We can omit the second case, but then we can conclude only
that P(n) holds for every partial number. The reason the
principle is valid is that every partial number is either U or
of the form Succ n for some partial number n. .....

>>570
出典訂正
（誤）Introduction Functional Programming using Haskell
（正）Introduction to Functional Programming using Haskell

Haskellでデザインパターンをやってみるとってのを考えてみたんだが、
どれもかなり自然に書けるような気がする。やっぱりすごい言語だなあ…

Template Methodとかもtype classのおかげでできてしまうなあ。

>>572
あ，先を越された（ｗ

>>572
つーか、関数型言語の研究成果をOOPにフィードバックしたら
デザインパターンになったってところがある（らしい）じゃん。

>>574
どうなんだろうね．Gammaの学位論文はC++だけど．

JavaのGUIクラスライブラリにはデザインパターンがふんだんに
使われてるよね。同じようなライブラリをHaskell用に作るとし
たらmonadicな書き方を多用することになると思うんだが、そう
するとライブラリのかなりの部分がHaskell自身で書けないこと
になっちゃうんじゃなかろうか。だとするとあまり面白くないな。

それとも、一部だけ（例えばJava AWTのGraphicsクラスだけ）用
意すれば、あとはHaskell自身で書けるんだろうか。

モナドの制限がある限りhaskellの発展は無いだろう。

>>576
具体例は？何がどう書けないのかよくわからない．

例えばJavaのComponentだと、

void addActionListener(ActionLitener l)
void removeActionListener(ActionListener l)

なんてメソッドがあるけど、どう書けば良い？

>>579
なんちゅうおぞましいネーミングなんじゃ
Javaやんなんくてよかった、ホッ

>>580
んー、それで中身のある答は？

>>581
Javaやってないっちゅーに、なぜ聞く

>>582
だからHaskellだと？
(意味あること言えないなら黙ってろよ)

>>583
そうカリカリするな。これだからジャバ厨は嫌われる。

>>583
Javaやってないっちゅーに、どうやってJavaをHaskellにせいっちゅーの

結論： Haskellでデザインパターンを使ったライブラリは作れません。

>>579
だからパターンの名前で言ってくれないかな．
大概のものは実装できると思うが．

特定の言語じゃないとパターンを活用できない
と思っている人は本質をとらえていない．
結局どのパターンが使いやすいか使いにくいかの問題．
パターンにも寿命があって生まれたり廃れたりしてゆくんだよ．
たいていのパターンのテキストにも書いてあるでしょ？

Component#addAdapterとComponent#removeAdapterならObserverパターンの
Attach, Detachのことだね。

名前が違った。addActionListener, removeActionListenerだっけか。

自分らCとかjavaが関数型言語だと思ってない？

Haskell洋書を読んでみるage
Haskell : The Craft of Functional Programming SECOND EDITION

>>591
「自分」を二人称に使うとは関西人か？

猿でも分かるここまでの話の流れ：
1.Haskellでもデザインパターンは実現できると言ったやつがいる。
2.本当に関数型以外の言語と同じようにデザインパターンが使えるのか？
　たとえばJavaのGUIライブラリの中にあるObserverパターンはHaskellでどう
　やれば書ける？と聞いたやつがいる。
3.答なし。どうやら1.は嘘だったらしい。

わかった？

将来スタンダードとなりえない言語をやっても仕方がない

>>594
ならやらなきゃいい。
言語たくさんてを出してればそれなりにいい事はある。

>>593
せっかちですね．モナドでobserver一覧を管理して，
インタフェースはモジュールとクラスで提供できるので実装は可能でしょ．
ただ関数型プログラミングとしてうれしいかどうかは別問題．
Haskellで使いやすいパターンとJavaで使いやすいパターンは異なるはずなので
これが出来るかあれが出来るかという議論は不毛だしつまらん．

>>596
「モナドでobserver一覧を管理して」ってのがわからん。
updatableなリストを使うためのmonadを一式Cかなんかで用意しとくということ？

「使いやすいパターン」って、JavaやC++やSmalltalkでは使いにくいパターンっ
て無いんだが。

モナド廃止運動開始！

>>597
もちろんオブジェクト一覧というからには
オブジェクトIDに相当するメカニズムその他も
モナドの向こう側に置かなきゃならないので
どちらかといえばミニインタプリタを実装するのに近くなる．
こういえば大抵のものは実装できるというのが
なんとなくは理解してもらえると思うけど．

GoFパターンにJava etc.で使いにくいのがないのはあたりまえ．
あれはオブジェクト指向プログラミングという問題領域に
ある程度特化したパターンだから．
パターンそのものは色々な問題領域に適用できるもっと一般的なアイデア．

例えばHaskellのモナドはインタプリタ型のプログラミングスタイルに
向いているので，そういったスタイルを活用するパターンを色々提供することが
プログラマにとってはより重要で役立つことだろう．
生のモナドだけではわかりにくいということもあるしね．

ゴタクはいい。

Java房の矛先が今度はHaskellですか・・・

ML系はコンパイル後、Cに匹敵するぐらい速くなるけど、
Haskellはどう？

でもGUIって副作用が必須だから（例えば入力に応じて画面が変わるとか
resizeとか）副作用を伴うパターンがたくさん出てくると思うのだが。

例えば、製図ソフトで図形を追加したり削除したり接続を変えたりすると
そのたびにObserverやMediatorの接続関係が変わったり、個々のオブジェ
クトの内部状態が変わったりするよね。

純関数型言語はGUIに向かない？
あるいは、インタラクティブに何かを編集するという用途に向かない？

Haskellは理論先行型言語なんだよ

で？

モナド知らないからなんともいえないけど、
モナド使えば命令型みたいになるんでしょ？
だったら、モナド使いこなせばいいだけでは？

たしかに実際にモナド使って、Javaの関数を実現してる
例が欲しいところだけどね。
というわけで、詳しい人の登場をキボーン。

ＪＡＶＡなら、あれとかこれとかできるのに、Ｈａｓｋｅｌｌはできないのかよ。
やっぱりＪＡＶＡのほうが上だな。Ｈａｓｋｅｌｌだせー。

JAVAと比べちゃHaskellが可哀想だ

なんか、Javaをけなす方向に持っていこうとして
自作自演してるやつがいない？
どうせ、Haskellやってる人はそんな子供じみた対決に
興味はないよ。

>>609
煽りは無視が一番だね
でも608みたいなのってマジな人が混じってそうでこうぁい

>>603
SICP の三章を読め。
ストリームがあれば副作用が無くても大丈夫に思えてくるぞ。
思えてくるだけで、実際どうなのかはわからんが…。

Javaやってんだったら、
Haskellではなく、
Pizzaにしたら？
一応Javaのスーパーセットってことになってる
http://pizzacompiler.sourceforge.net/
これで色々試してみる方が有益だと思うが。

ま、それかGJとか言うのでもいい。
とりあえずは。
これは、Sunがサポートするといってる奴だ。

age = [1] : [y | a@(x:xs) <- age, y <- [0:a, x+1:xs]]

試行錯誤でゴネゴネ書いたり、遊びで書きたいときは、
やっぱりLispのように、システム上で関数を定義できたらいいなと思う。
hugsは、それの上で定義できないからちょっと寂しいな。

Rubyみたいに実用的な物は書けないの？

>>616
Rubyが実用的かはともかく、気軽には書けませんでした。

age

挫折した人が多そうだね。

習得しても生産性ゼロだからな。
Rubyのほうがよっぽどマシ

Ruby >>>>>> Haskel

ruby駐は（以下略）

ここHaskellのスレじゃなかったの？

>>623
シーッ！
無知なRuby厨を刺激するな。放置しとけ。

>>624 ｵﾏｴﾓﾅｰ
この言葉、久しぶりだｗ

Haskellで○○を作ったって話も挙がらないし、
作ったソースを上げた奴も居ないしで、
このスレの連中は全員挫折したと見てもいいですか？

全員総倒れのスレってのも面白いじゃないか(wara
ちなみに俺はHaskell洋書を読み読み中。
現在14章に突入したところ。
けど、14章を読んだら、ちょっと飛ばしてモナド関連の所を読もうと思う。

>>627
何読んでんの？

>>627
School of Expressionと見た．でもそれ，HudakのいるYaleでは学部1年生の授業に使ってる入門書だよ．

>>629
それではどんな本がいいの？

「The Craft of Functional Programming」
これしかないだろ。って他にHaskellと名のつく本は無いらしい。
おれはHaskellなんて知らない。ま、そういうことだｗ

amazon.co.jpで検索したら、
『Haskell: The Craft of Functional Programming (2nd ed.)』
『An Introduction to Functional Programming Systems Using Haskell (Cambridge Computer Science Texts)』
『The Haskell School of Expression: Learning Functional Programming through Multimedia』
と3冊出て来たが、どうよ？
どれが一番簡単で、初心者向きで、実用アプリ志向なの？

というか、関数型言語の目的ってなんなんですか？
なんで難しい概念をプログラムに取り入れなくちゃならないんですか？
haskellとかMLのコードぜんぜん読めないんですけど。
末尾再帰とか、非破壊変数の意義はなんとなくわかるんですが。

>>633
http://www.haskell.org/aboutHaskell.html
を読め。

神　 超傑作　傑作　佳作　 良作　 凡作　 惜作　 不作　 ｲﾀｼﾞｬﾝ　誰彼　青紫
┠──┼──┼──┼──┼──┼──┼──┼──┼──┼──┨
▲
のごとき完成度の高いスレッドとして、認定されました。
スレを美しく保つためにこれ以降の書き込みを禁止します。
ご協力お願いします。　　　　

>>633
難しいっていうけど、理論的には命令型・手続き型言語よりずっと
シンプルなんだけどなあ…　コードが読めないのは慣れてないだけ
でしょう。

>>633
アルゴリズムを記述するのに向いていると思う。
数学方面行けば難しい概念なんて腐るほどあるさね。

>>635
おいおい、葉鍵のをそのまま持ってこないでくれよ。

>アルゴリズムを記述するのに向いていると思う。
Cと比べてどのくらい綺麗に書けるもんでしょうね。

quick sortとかAVL木とかの基本的な
アルゴリズムとデータ構造記述したサンプルコード集って
どこかにないですか？

それぐらいだったらhaskell処理系に付いてこない？>638

いえ、単に興味本位に眺めてみたかっただけなので
処理系入れるのはちょっと...

>>4
再帰で階乗

>>47
qsort
↓
http://www.haskell.org/aboutHaskell.html

ここにHaskellマルチメディア本のデモがaviで置いてあるけど、
こんな事も出来るんだねぇ。ちょっと意外。
http://haskell.cs.yale.edu/soe/demos.htm

>>638
Cと比べたら，簡潔に書けるよ．
だいたいCって1行あたりの情報が結構少ないでしょ．
HaskellやMLだと，密度が濃いので，他人の書いたものを理解するのは大変だけど．

簡潔で密度が高いってだけならPerlだってそうだろ

>643
コンパイルしたら、Cなみに速いの？

煽りかもしれないけど、もしかしたらHaskellの良さを理解
したいという意図がありそうな発言が多いね。
やっぱり、Haskellを学ぶしかないんじゃないのかな。

個人的な意見としては、なんとなくだけど、一時変数を使わないで
直接的に表現してるのが良いんじゃないかな。
表現力がかなりありそう。

>>644
うーんと，密度の質が違うというか．．．Perlで簡潔に書ける
っていうのは，基本的にCのコードをぎゅっと圧縮した感じだけど
Haskellのコードはもとのアルゴリズムの漸化式なんかをその
まま書き移したような感じ．

>>645
残念ながら，Cよりはだいぶ(最低でも2倍は)遅いと思う．
それでも10倍違うことは少ない，って研究者たちは誇らしげに
言ってるけれど，現場じゃ2倍の違いも致命的だからね．

>>647
現場によるでしょ．
Javaだってそのままじゃ遅いけどつかえる場所じゃ使える．
関数型ならCAMLが一番速いかな．

>>645
http://www.bagley.org/~doug/shootout/craps.shtml
「速さだけ」を比べている訳じゃないけど（LOCって何？）。
HaskellとMLは、これに関しては全くの別物です。
（ほかに、CommonlispやOcamlは処理系によってはC++並に速いと聞いたことが）

やっぱり速度は重要なんでしょうか。
「場合による」のは確かだけど……。

MS信者じゃないけど、.NETなら速度はC#もHaskellも変らないのでは？
使ったことはないからなんとも言えないけど。。

実行速度より飯が食えるかどうかの方がはるかに重要ヽ(´ー｀)ノ

>>651
はいはい，お帰りの時間ですよ．

>>650
というか原理的にはそうだね．JITでどれだけ頑張れるかな．

>>649
LOCはLines of Codeの略。コメントや空行を除いたソース行数。

>>653
残念ながらlazyな言語は現在のCPUだと実行効率が良くない。
たとえ仮想マシンを使っても同じ。

しかし人間の手間の方がコスト的には重要だけどね。

>>654
どうもです。
……ちゃんと読んでなかった。
＞The scores in the Scores table can reflect CPU, Memory and/or Lines of Code (LOC).
Cはこの項目がDAMEだった訳か。

>>649
インタプリタのHugsならまだしも、コンパイラのghcで
Rubyよりも遅いのかよ。

でも、個別の試験で見ると、テキスト処理はダメでも
数値計算では勝てるみたいだね。

>649
Javaさん、意外に速いのねぇ。
プリミティブ型のおかげかしらん。

速度の他にHaskellの癖の強い点は，やっぱり遅延評価かな．
lazyなおかげで，えらく簡単に書ける場合もある半面，
どこがいつ評価されるかわからないことも多くて苦労する．
まあそれが嫌ならMLにすれば良い訳だけど...

Haskell 98の規格で決まってるライブラリ関数って、どこまで？
Hugsのライブラリ関数全てが、GHCでも使える訳じゃないんでしょ？
その辺の可搬性はどうなってるの？

仕様書みろ>659

あ、これか。
http://haskell.org/definition/
もう日本語訳もあったんだね。
http://www.sampou.org/haskell/library-j/index.html
ｽﾏｿ

>>658
細かく遅延評価をコントロールしてやればある程度最適化は可能だろうけど
プログラムは汚くなるなあ．やっぱりMLjみたいなのが正解？

>658
どこがいつ評価されるかなんて知ってどうするんだ?
それを知らないと困るような状況ってあるのか?
俺はそのような事で苦労したことはないのだが。

>>663
I/Oエラーが起きたとき等は評価の順序を知ることが重要だと思うが。

haskellで実用プログラムなんて無理。
でも好きなのでage

どこかに、命令型言語は「どのように」解くか、で
関数型言語は「何を」解くか、であると書かれていました。

数値計算などには強いのでしょうが、やっぱり実用プログラムは…
その割に、HOpenGLなんてのもあるんですよね。変なの。

Haskellで書かれた(?)ショッピングサイトが
何処かに紹介されてたような気が。

↑んなもんHaskkellで書かれたら誰も引継ぎ・メンテできないよ

>>664
IO なら評価の順序はわかるものだと思うが…

>>68
Haskellが使えたら、相当な高い給料で来てくださいって言われそうだな。（ｗ

>>667
逆に言うと、ショッピングサイトが数式で構築できるのか…

Lispで書かれた大手ショッピングサイトの話もどっかで読んだような？

>>672
http://www.shiro.dreamhost.com/scheme/trans/beating-the-averages-j.html

>673
ああ、それそれ。君速いねぇ( ﾟДﾟ)

Lispは、化け物だと思うよ。
俺はLispを少ししか触ってないから厨房的発言かも知れないけど、
Lispほど何処にでも現れて、成果を出している言語なんて
そうそうないんじゃないかなぁ

>>671
「数式で」って君面白いねえ。
Cのprintf("%d\n", ...)もi = i + 1も「式」だって分かってる？

いまんとこ、うちじゃHugs for Winは単なる計算機代わりです。
（前は、Rubyのirbを計算機代わりにしてました。）
でも、インタラクティブに関数定義出来ないのがイタすぎると思われます。

>>677
よくわからんが、fileをloadするのは駄目なのか？

書く
↓
実行

でなく

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

ってこと?

>679
そゆことです。

面倒かな？

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

これでいいんじゃないかな？

アホな事を聞くようでアレなんだが、
Haskellは再帰とかでいくら関数ネストしてもスタックあふれない、の？

>>682
そんなことはない(スタックじゃなくてヒープを使うかも知れんが)。
でも、末尾再帰(要するにループ)ならメモリは全く食わない。

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

>683
ｻﾝｸｽｺ

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

>>683

ただ、Cと違って
int f(int x) { return g(x); }
int g(int x) { return f(x); }
も関数型言語だとジャンプになるけどな。(無限ループになる。)

>>676
分からないから、式と数式の意味の定義を説明してくれる？

>>685
Cでもなるよ。

>>687
ならねーよばか

int f(int x) { return f(x); }
なら、まだわかる。
無限に呼び出しが続いたりはしないが。

>>685
Cの場合は、末尾再帰を最適化してくれるコンパイラなら、
ベースポインタを呼び出し前の状態に戻してジャンプだな。
スタックを積み上げる必要はないから、無限に呼び出し（ジャンプ）が続く。

ところでHaskelだと一応環境をヒープからアロケートしなおさないといけなくないか？
（現環境を廃棄できるから、無限に呼び出しを続けられるが）

ファイルを全部一気に読み込んだ事にしても、実際にはlazyだから
必要な時に必要な分だけ読んでくれるんだね。
ちょっと萌えた。

でも効率は知らん。

>>691
ファイルIOとか、そういう処理にlazyかよ。
信じられん言語だな。
デバッグ大変そう。（ｗ

>>692
I/Oはlazyにした方が効率よいことも多いよ。
仮想記憶ベースのmemory mapped I/Oもcacheのflushもcopy on writeも…

つーかproxyパターン

東京工科大学の演習、一通りやってみました。
次なる修行はどんなのが良いでしょうか？

Lispよろしく、コンパイラなんてどうでしょう?
筑波大のどっかの研究室に、MLでコンパイラ作成ってのがありましたよね。
確かこのスレのどこかにもリンクがあったはず。
趣味じゃなかったらいいんですけどね。

>695
東工大のhaskellの授業です。講義のページにも下の方に演習がありますよ

http://www.brl.ntt.co.jp/people/mizuhito/CS/

↑の12月13日のところの上級問題が解けたら凄いですね

解けない・・・

どもです。>>696-697

age

[上級問題１]（これができれば単位は差し上げます）
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

線形時間であるのは自明ってことで許して。

mss [-1,-4,-5] => 0

間違ってるやん…
出直してきます…

そもそも mss [] が 0 でいいものなのか…

宿題解かせようとしてる東工大生の陰謀に引っかかるなよ。（ﾜﾗ

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

この問題の事か・・・
たしかに線形性ってのは述べにくいよね


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)は実は線形時間アルゴリズムが存在する。その
アルゴリズムを実装し、なぜ線形時間であるか理由をしるせ

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;
}

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だともっとスマートにかけると思います．
それにしても全角スペースをいれてインデントするのは面倒ですね．

線形性は自明ですが，このアルゴリズムがmssを計算していることを
示すほうが面倒といえば面倒ですね．

>>709
Schemeよりスマートに書ける言語なんてありません。

age

>>709
&nbsp;に置換してもらうほうが
こぴぺする側としてはありがたい。

自慢の関数言語で痴漢スクリプト書けばいいだろ

>>713
連続した半角スペースは消えるんじゃないの？

>>715
nbsp;は何個書いても消えないよ。

ghc、なんだかよくわかんねーけどすげーYO！

GHCはGarded Horn Clauseのことです。

Hugsの新版がリリースされました。

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

再びグラフィックライブラリが使えるようになったので
嬉しいです。

ところでHugsって、なんて読むの？
ﾊｸﾞｽﾞ？

嬉しいage

あ、石敢當さんだ！
お久しぶりです。

>>720
"ハグズ"だよ．

>723
あ、ﾊｸﾞｽﾞでいいんだ。

それにしてもライブラリがたくさん増えたなぁ。
もしやと思ってgrepかけてみたけど、Win32 OLEなライブラリは無かった。
これが有ると、世間的にもウケがいい気がするんだけど。

>>722
ご無沙汰してました。（見てはいたんですけどね）
Birdさんの本(>>277)を最初からゆっくり読むことにしていました。
exerciseは適当にやったりとばしたりして、やっと100ページくらい
読んだところです。約1/4くらいまで来ましたが、だんだん中身が
濃くなってきたので読むペースも落ちてきました。Haskellで何か
すぐに作らなきゃいけないわけじゃないので、まあのんびりいきます。

>>723
身近にHaskellをいじっている人がいないので、HaskellもHugsも
実際に発音したことないです。頭の中では「ハスケル」「ハグス」と
読んでいました。「ハグズ」と濁るのが正しいのですね。

俺は頭の中で「ハッグス」って読んでた。

俺は頭の中で、しいちゃんの「ダッコ」を思い出してた。

こんにちは。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 )]

こんな風になりました。もっとうまく書けるとか、美しく書けるという人はおしえてくださいな。

>728

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

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

# Hugsはハグスって読んでた

Hugsの開発やってる人達は「ハグズ」って言ってたよ．

正直、Haskellのコードはビジュアル的に美しくないな。
Haskellコードを美しく表示/印刷するための
プリティプリンタが欲しい感じ。

>>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

>>728

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

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

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

Prelude> show 1234
"1234"

＞731
a2psの-Eオプションと--highlight-levelオプション使ってみては?
->はちゃんと→になるし、::はなぜか集合の"is an element of"の記号になるけど。
それなりに綺麗にはなるかと。
というか、GHCのサイトのリンクにプリティプリンタがあった気がする。

age

age

>>732
strToInt "----3" が3になるのは嫌だ。

>737
そうだね。俺も嫌(w

>>734
A→Bてのは、→をバイナリオペレータとした、
AからBへの関数全体の集合のことだから、
f∈A→Bは変ではないと思う。

Hugsの新版をインストールしたら、editerをいちいち閉じないと
動かなくなってしまった。これバグ？ Win98使用。

>>739
それはわかってるんだけど、他の言語でNameSpaceを指定したりするのに
::を使ったときも∈になったら鬱とか思った。というか、MLのcons operatorとか。

NameSpaceならそれなりに意味は通じないでもないが、
Consが∈はイヤすぎだな（藁

http://lc.linux.or.jp/lc2001/papers/haskell-paper.pdf
のHaskell Emacsについてどう思いますか？

ghqでインラインアセンブラのようなことは出来ますか？

GHCのversion 5.02.2がリリースされました。

---

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

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

今度はexerciseをやりながら読み返してみようと思います。

すみません。sageてしまいました。

山下さんが Why Functional Programming Matters の訳を公開してますね。
http://www.sampou.org/haskell/article/whyfp.html

『Craft of Functional〜』本を読んで、ﾓﾅﾄﾞがぼちぼち解りかけてきたが、
Stateﾓﾅﾄﾞは尚一層難しいね。

デバッガ(?)が有る事を今知ったage
http://www.cs.chalmers.se/Cs/Grundutb/Kurser/d1pt/d1pta/lecture8a.pdf

↑に出て来るcountOccurrencesって関数、ｶｺｲｲけど
自分じゃ絶対思いつけないなぁ。

関数型言語に取り組もうと思うのですが、
Haskell と ML の差(言語、勢力などあらゆる側面において)に
ついて比較していただけませんか？

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

しかしここのところの人気は Haskell のほうがあるように見えます。
いったいこれはどうした訳なんでしょうか？

Haskell、コンパイラあるよ

>>750
Haskellが人気有るのは2chだけのような気が……。

>750
我々に ML を貶せと仰る?

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

あと Scheme も忘れずに。

ガハハハ！　これ、すごいわ。
http://www.puchiwara.com/hacking/

イギリスでもHaskell多いよ。

実際Haskell使ってる人って見たこと無いなあ。
>>750
ML系は出力コードの質が高いのね。
あるベンチサイト見るとC++とタメ張れてる様だし。
型推論って凄いかも。

型推論と出力コードは関係ないだろ。

>>753

実は「どちらをやるか」というのをそれほど気にしているわけ
じゃあないんです。

すでに ML に惚れ込んでいて、そちらでポツポツやり
はじめたところなんですが、
歴史的経緯、その能力などから見て ML がもっとも
成功するべき関数型言語であると漠然と
感じたわけです。

ところがその後 Haskell などの新らしい関数型言語が
再生産されている、これはどうしたことなんだ？ ML に
どのような不満があるんだろう？ こういう観点なんですね。
もちろん本当に納得するには両方やってみるしかないんですが、
まあ聞いてみるか〜と。

今想像しているのは、かっては SML なんかはフリーで
なかったという、開発主導権的な問題が新言語の出生を
促したのかなあ、というものです。Haskell はマイクロソフト
なんかも入れ込んでいるようですから。

一番大きな違いは、MLは作用と副作用が明確に区別できない。
MLは遅延評価じゃない。
と言ったところでは。

そうだよね。MLは遅延評価じゃないから、純粋な宣言的プログラミングには
ならないんだよね。個人的にはMLの「中途半端さ」は悪くないと思っている。
Haskellの研究には頭が下がるけど、まだまだ当分の間、研究の域を出ない
ように思うね。その点、MLはすでに実用レベルじゃない？

# もっともMLは「型のあるScheme」に過ぎないって気もするんだけどね。

Haskellって日本じゃ2chでしか盛り上がってないね。
ユーザー少なすぎ。
2chにはたまたまエヴァンジェリストでも居たのかな？

>>759
あと、型システムがかなり違う。
Haskellの方が型クラスとかあって複雑。

>>762
でもモジュールとかインターフェイスとかはSMLの方がしっかりしてるんだ
よね．

MLは名前が･･･ｶｺﾜﾙｽｷﾞ

メーリングリストは、ML ML？

Pascal->Delphiみたいに
なんか名前考案しる！

用語が一般的すぎると検索で引っかからなくて困るよねえ。

Haskellも人名なので、関係ないページがたくさん引っ掛かるね。

>>760
実用性の面ではどっちも大差ないと思うけど。
なんかどっちも Clean とかに負けてる気もする。

>>762
型クラスって複雑か?
ML の型機構が貧弱なだけなような…。
それをファンクタとかのモジュール機構で補ってる感じ。

あ、あと実用性の面では Ocaml なんかもいい線いってる気がする。

気がするだけで実際は知らないけど…。

>>769-770
あのさ、今はMLとHaskellを比べた場合の話をしてるんだと思うが。

CLOSも、ワインのページがいっぱいひっかかる…

>771
ごめん。十分話題に沿ってるつもりなんだけど。
Clean の名をちょっと出しただけだし。
って、Ocaml もダメだってか?

>>773
それとHaskellの型クラスが複雑なのはMLと比較しての話だと思うが。

>774
俺は Haskell の型システムって結構シンプルだと思うんよ。
だから Haskell の型システムが ML に比べ複雑っていうより
ML の型システムが Haskell に比べて貧弱って云った方がしっくりくる。
って意でした。ごめん。

実際に何かを練習がてら作るとしたら何がいいでしょうか？

hugs(Hugs Version February 2001)にて
x::Integer->Integer
x 0=0
x n=n+x (n-1)
とかやって、
x 1000
くらいなら
500500
という感じで動くのですが、
x 10000
くらいになると
ERROR - Control stack overflow
とか言われてさみしいのですが、
末尾再帰って無いのですか?

x0::Integer->Integer->Integer
x0 0 b=b
x0 a b=x0 (a-1) (a+b)
x::Integer->Integer
x n=x0 n 0
とかもやってみたんですが同じでした。

>>777
> x n= n+x (n-1)
これは末尾再帰ではありません。
Version: February 2000 でも「Control stack overflow」と出ました。
その次のは、「Garbage collection fails to reclaim sufficient space」でした。こっちは処理系の問題。

>>778 February 2001だと、両方とも ERROR - Control stack overflow と言われましたです。

>>779
おかしいなぁ。
後の方はちゃんと末尾再帰になっていますよね……。
？？？