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

1 名前：デフォルトの名無しさん [04/02/10 22:16] Haskellの公式HP www.haskell.org/ 日本語サイト www.sampou.org/cgi-bin/haskell.cgi www.teu.ac.jp/kougi/koshida/Prog6/index.html 過去ログ、関連スレは>>2-5 192 名前：デフォルトの名無しさん mailto:sage [04/08/31 12:01] 「数学に勤しむ貴方のための圏論」てのがそれらしいが 近刊とあってまだ出てないようだ。 ttp://www.kyoto-su.ac.jp/~hxm/hxm.cc/research.ja.html 193 名前：デフォルトの名無しさん mailto:ｓage [04/09/07 17:30] 末尾再起すると、遅延評価されないですね。 (length (hoge xx yy zz)) < 3 とかで困る。かも。 194 名前：デフォルトの名無しさん mailto:sage [04/09/07 20:50] >>193 > 末尾再起すると、遅延評価されないですね。 そんなことはない。 > (length (hoge xx yy zz)) < 3 > とかで困る。かも。 lengthがstrictだからhogeがlazyでも意味がないとはいえるが、 末尾再帰とは無関係なので、意味がわからない。 なにを誤解してるのですか？ 195 名前：デフォルトの名無しさん mailto:sage [04/09/08 10:49] >>193 『末尾再帰の最適化』をすると遅延評価できない（或いはその逆）、のことを言いたいのかな。 それだったら解る。 あ、でも例 (length (hoge xx yy zz)) < 3 の意味はやっぱりわからない。 196 名前：デフォルトの名無しさん mailto:sage [04/09/08 18:24] >>195 > 『末尾再帰の最適化』をすると遅延評価できない（或いはその逆）、のことを言いたいのかな。 詳しく説明きぼんぬ。 gotoでジャンプするコードにするとサンクが作れないのかな？ 197 名前：デフォルトの名無しさん mailto:sage [04/09/09 23:56] >>195 take n 末尾再帰関数(無限リスト) みたいなのが出来ないということでは？ 198 名前：197 mailto:sage [04/09/10 00:26] 括弧の位置を間違えた。 take n (末尾再帰関数 無限リスト ・・) です。 199 名前：193(初心者) mailto:sage [04/09/10 16:18:42] すいません。どっかいってました。 >197さんの言うとおりです。 例は適当にかいたらだめでした。 200 名前：デフォルトの名無しさん mailto:sage [04/09/10 16:25:19] >>197-198 なにができないと？ take' 0 xs = xs take' n (x:xs) = take' (n - 1) xs  take n (take' 10 [0..]) 201 名前：197 mailto:sage [04/09/10 21:59:52] >>200 返値も無限リストの場合です。 nub0 :: Eq a => [a] -> [a] nub0 = nub0' [] nub0' l [] = l nub0' l (x:xs) 　　| elem x l = nub0' l xs 　　| otherwise = nub0' (x:l) xs take 10 (nub0 [1..]) 202 名前：デフォルトの名無しさん mailto:sage [04/09/10 22:16:02] >>201 nub0 [1..]自体がbottom(無限リストではない)なんだから 末尾再帰も糞もないですよ。 nub0' :: [Int] -> Int nub0' = foldr (+) 0 だって同じこと。 203 名前：197 mailto:sage [04/09/10 23:25:33] いろいろと書き方がまずくてすみません。 nub0 を末尾再帰で定義したから、nub0 [1..] が bottomになったわけで、Hugsでの定義の nub l = nub' l [] where 　nub' [] _ = [] 　nub' (x:xs) ls 　　| x `elem` ls = nub' xs ls 　　| otherwise = x : nub' xs (x:ls) のようにすれば nub [1..] は無限リストになる、という意味です。 204 名前：デフォルトの名無しさん [04/10/07 21:01:01] いいかげん誰かモナドをわかりやすく説明してくんない？ 関数型言語のキモは副作用とのコラボレーションなんだし 205 名前：デフォルトの名無しさん mailto:sage [04/10/08 02:06:46] >>204 www.sampou.org/haskell/a-a-monads/html/index.html ではだめ？ 206 名前：デフォルトの名無しさん mailto:sage [04/10/14 01:54:56] んじゃ自分の理解度の確認を兼ねて。（突っ込みよろしく） モナドは数学上はモノイドといって単位元を持つ半群のこと。 一応簡単な説明。 （Ｘ * X ) * X = X * ( X * X )　といった「結合側」が成り立つ演算＊があって （Ｅ * X ) = ( X * E ) = X となる単位元Ｅを持つようなＸのこと。 X　が整数だとすれば * は足し算 E は 0 もちろん * を掛け算 E は １としてもいい。 * を文字列の結合 , Eを空文字列 "" とすれば文字列もモノイドとみなせる。 で、ＨａｓｋｅｌｌのＩＯ型には 上の文字列モナド(モノイド)の1文字づつの代わりにＯＳのシステムコール呼び出しの機械語が 入っていると思えばいい。 ＩＯﾓﾅﾄﾞA( [キー入力] ) >> ＩＯﾓﾅﾄﾞB( [画面出力] ) 　を適用すると　 　 ＩＯﾓﾅﾄﾞＣ( [キー入力]の次に[画面出力] )　になる みたいな。 で　どんどん >> や >>=で繋いでいくわけ。 もちろん結合則も成り立つ。 ちなみにreturn 関数が返すＩＯ型が単位元になってる。 これはreturnの返すＩＯには何もシステムコール？が含まれてないから 上の文字列モナドの空文字列みたいな感じ これで宜しいでしょうか>>204 207 名前：デフォルトの名無しさん mailto:sage [04/10/14 03:55:12] >>206 Monoidだと思って話すなら: 結合法則: (a * b) * c = a * (b * c) を満たす演算*が定義されていて、 単位元 e (e * a = a * e = a をみたす) を持つような集合を Monoid(以下、単に半群という)といいます。 例えば"行列"や"微分方程式の解作用素"は半群になっています。 *** Point(1): a * b /= b * a。順序は変えられない この半群の集合への作用(注1)の仕方を定めたものがMonadです。 return == e で、あとは * にあたるものが >>= となります。 そういうと、return :: a -> M a (M "a" なのは単位元だから) なんだから、 >>= :: (s -> M t) -> (t -> M u) -> (s -> M u)  じゃないのかと思うかも知れませんが、 >>= :: M t -> (t -> M u) -> M u でもいいのです。 というのは、(c * d)' x = c' (d' x)なので、*を決めることと、 M sの任意の元(d' x 等)をどこにうつすかを決めることは同じことだからです。 続く。 208 名前：207 mailto:sage [04/10/14 03:57:32] この行は前のメッセージの最後にあるべきでしたが、 *** Point(2): x /= y ならば a' x と a' y は等しくなくてもよい さて、例えばIOモナドなら、putStr :: String -> IO ()  は上のaやらbやらにあたります。ではgetLine :: IO Stringはというと、 元を一つしか持たない集合をUとしてgetLine :: U -> IO String の省略記法 なのです。元が一つしかないのだから、わざわざU->を考える必要はありません。 Point(1)、(2)がIOの、順序を変えられない、毎回違う答えが帰るかもしれない という性質を満足させてくれます。 main = getLine >>= putStr は、(putStr * getLine) と同じもので、 実行するのは putStr' (getLine' world) を計算することです。 getLineが毎回異なる文字列をputStrに>>=で与えても、それはworld が違ったからだと思えばなにも問題はありません。 *1 (作用)     行列をベクトルにかけるとベクトルができますが、これと同じように、     半群(M)の元(a, b, ..)をある集合(S)の上の関数とみなすことができます。     好き勝手に関数とみなすのではなく、次の性質をみたすとき、     半群MがSに作用している、ということにします。関数とみなすときには'をつけます。     (a * b)' x = a' (b' x) (x は S の元)      # monoidとmonad (triple)はどちらも数学の概念で、似ていますが別物です。 209 名前：デフォルトの名無しさん mailto:sage [04/10/14 08:51:55] （Ｘ * X ) * X = X * ( X * X )　といった「結合側」が成り立つ の()の意味はなんだ？ 単に型が合うかどうかか？演算の時間的な順番か？ 210 名前：デフォルトの名無しさん mailto:sage [04/10/14 09:25:14] >>209 演算の順序。 代数の本を読めばどしょっぱなに書いてあるよ。 211 名前：デフォルトの名無しさん mailto:sage [04/10/14 09:29:17] じゃあ（入力 * 出力）* 入力 = 入力 * （出力 * 入力）になって 最初に出力してくれるのかい？ 212 名前：デフォルトの名無しさん mailto:sage [04/10/14 11:05:33] コードの結合順序と、実行順序を混同するな。 Cで {{f(); g();} h();} と {f(); {g(); h();}} が同じ結果になる みたいなものだ。 213 名前：デフォルトの名無しさん mailto:sage [04/10/14 15:33:35] だから（Ｘ * X ) * X = X * ( X * X )ってのはどういう意味なの？ 214 名前：デフォルトの名無しさん mailto:sage [04/10/14 16:42:30] >>213 モノイドの説明だとしたら、その式はそうとしか言えないのでは。整数上の加 算について考えると、 (1+2)+3 = 1+(2+3) が結合則。 1+0 = 0+1 = 1 が単位元の性質ということ。数学の話だよ。 モナドだとすれば、 >>207-208 じゃないのか。 (f * (g * h)) x = ((f * g) * h) x = f(g(h(x))) という風に理解したんだがこれは当ってる？ Haskell の記法を使えば、 x >>= (\x -> x >>= h >>= g) >>= f = x >>= h >>= (\x -> x >>= g >>= f) かな？ モナドというのは、「評価の順序を保証するもの」という風に考えているんだ が、その事を「結合則は成立するが、交換則は成立していない」という事で表 現しているということなのでは。 副作用の話は 208 の方に書いてあると思うんだが、こっちはよくわからない……。 215 名前：デフォルトの名無しさん mailto:sage [04/10/14 17:00:35] >>214 > 「結合則は成立するが、交換則は成立していない」 「交換則は必ずしも成立するわけではない」のほうが適当では？ 216 名前：デフォルトの名無しさん mailto:sage [04/10/14 17:05:38] この場合の（Ｘ * X ) * X = X * ( X * X )の意味は どういう風に括弧をつけても関数Xの適用順序は 左から右、右から左と一定であるって意味でいいの？ 217 名前：デフォルトの名無しさん mailto:sage [04/10/14 17:17:39] >>215 ああその通りですね。失礼しました。 >>213=216 まあその通りといえばその通りではないかと思います。 *を関数の合成みたいな演算だと考えればよいのでは。 218 名前：デフォルトの名無しさん mailto:sage [04/10/14 17:22:34] で、208に質問なんですが、 > *** Point(2): x /= y ならば a' x と a' y は等しくなくてもよい はわかるとして、 GetLine :: U -> IO String であり、 U が一点集合なのだ としたら、これは x = y である(にもかかわらず a' x /= a' y になりうる) 例のように読めてしまったのですが、どこで間違えているんでしょうか？ getLine' world というのは、常に world が与えられるが、 world が毎回異 なるので返り値が異なることがあるっていうこと？　でもそれって一点集合な んでしょうか？ 219 名前：デフォルトの名無しさん mailto:sage [04/10/14 17:26:23] 結合法則は分かったが *** Point(1): a * b /= b * a。順序は変えられない *** Point(2): x /= y ならば a' x と a' y は等しくなくてもよい Point(1)、(2)がIOの、順序を変えられない、毎回違う答えが帰るかもしれない という性質を満足させてくれます。 っていうのは普通の関数とどこが違うの？ 普通の関数でもそういうのあるんだから、 モナドとかいわずに普通の関数と一緒に扱えばいいじゃない。 220 名前：デフォルトの名無しさん mailto:sage [04/10/14 17:33:16] x = yでもa' x と a' yは等しくなくてもいいんじゃない？ 221 名前：デフォルトの名無しさん mailto:sage [04/10/14 17:50:24] 結合法則は満たすけど交換法則は満たさないって状況、 小学校でやる一般的な算数にある？ 222 名前：デフォルトの名無しさん mailto:sage [04/10/14 17:52:51] 引き算、割り算 223 名前：デフォルトの名無しさん mailto:sage [04/10/14 18:00:53] 結合法則満たすのか？ 224 名前：デフォルトの名無しさん mailto:sage [04/10/14 18:01:04] perl -e '$op="-"; print eval "4 $op (3 $op 2)"' perl -e '$op="-"; print eval "(4 $op 3) $op 2"' これ、答えが違っちゃうけど、、なんか間違ってます？ 225 名前：デフォルトの名無しさん mailto:sage [04/10/14 18:16:35] >>219 > っていうのは普通の関数とどこが違うの？ > 普通の関数でもそういうのあるんだから、 どこの世界の関数だそれは（ｗ 226 名前：デフォルトの名無しさん mailto:sage [04/10/14 18:23:24] べき乗とかなら交換したら意味がちがうし x /= y ならば a' x と a' y は等しくないんちゃう？ 227 名前：デフォルトの名無しさん mailto:sage [04/10/14 18:27:33] もちつけ。モノイドがモナドなわけじゃないぞ。 > この半群の集合への作用(注1)の仕方を定めたものがMonadです。 228 名前：デフォルトの名無しさん mailto:sage [04/10/14 18:29:58] >>219 逆で、関数でそういう性質が成り立って、文字列の連結や状態遷移でもそういう性質が成り立つからそれらを抽象化してモナドにしたってこと。 連結リストや配列リストの性質を抽象化してリストとして扱うようなのと同じ。 229 名前：デフォルトの名無しさん mailto:sage [04/10/14 18:31:50] じゃあ普通の関数もモナド？ 230 名前：デフォルトの名無しさん mailto:sage [04/10/14 18:42:39] >>220 x = y で a' x = a' y でなくても構わないっていうのは数学的にはおかしい 気がしますが。 プログラム的には副作用が起きているなら成立すると思いますが、その副作用 を上手く扱うのがモナドなんじゃないの？ 231 名前：デフォルトの名無しさん mailto:sage [04/10/14 18:54:09] 順序は正しく守って、毎回違った答えが出ても 処理系はエラーを出さず理論的にもきちんとまとめられるってことか？ 232 名前：207 mailto:sage [04/10/14 19:02:54] >>218 そうですね。すみません。208は全然ダメです。  モナドをモノイドで押し切ろうというのは無理がありました。 233 名前：デフォルトの名無しさん mailto:sage [04/10/14 19:03:15] >>229 普通の関数だと、たとえば f(g(x), h(y)) がどの順番で評価されるかは不定。でも、モナドを使えば、その順序を確定さ せることができる。 ……副作用とかいう話じゃなくて、順序を確定させることが重要なのかなあ。 順序が確定的だから、副作用が起きるコードでもOKみたいな感じ？ 234 名前：デフォルトの名無しさん mailto:sage [04/10/14 19:06:11] モナドってのは何をさすんだい？ a * bだったらaやbがモナド？それとも*がモナド？ 235 名前：207 mailto:sage [04/10/14 19:15:28] >>233 順序と、引数返り値に直接アクセスできないところが味噌です。 type IO a = world -> (a, world) なら、main world0 = let (s, world1) = getStr world0 in print s world0 とかやってしまえないようになるところ。 >>234 a, bと*の組みです。 行列群が、行列と行列のかけ算の両方がないと考えられないのと同様に。 236 名前：デフォルトの名無しさん mailto:sage [04/10/14 19:18:35] a,bはプログラム中の式 *は各式の関係を表す演算子 237 名前：207 mailto:sage [04/10/14 19:27:09] >>232 自己レスもちろん>>207もだめです。 モナドは雰囲気はモノイドなんですがやっぱりモノイドとは みなせそうにないので、これも嘘です。 > この半群の集合への作用(注1)の仕方を定めたものがMonadです。 予想と違って、正しいかもしれないものだと素直に読んだ方が 多かったようで、申し訳ないです。 238 名前：デフォルトの名無しさん mailto:sage [04/10/14 19:31:13] 理解した部分だけ書くと、結合法則を満たす関数の合成を使うと IOのような実行の順序が重要な意味をもつ関数を（順序不定で）合成しても 合成された関数は一意的な順序でIOが実行される関数になるということか？ 順序を保つ合成が結合法則を満たすのは分かったが、 結合法則を満たす合成は全て実行の順序を保つでいいのか？ 239 名前：デフォルトの名無しさん mailto:sage [04/10/14 21:14:39] >>238 順序不定には合成できないから、明示的に順序をつけることを強制できる。 putStr (getLine, [getChar]) でなく getLine >>= (\s -> getChar >>= (\c -> putStr (s, [c]))) か getChar >>= (\c -> getLine >>= (\s -> putStr (s, [c]))) 240 名前：デフォルトの名無しさん mailto:sage [04/10/14 21:26:54] じゃあモナドは実行の順序が決められてる関数の中の一つってことか？ 241 名前：デフォルトの名無しさん mailto:sage [04/10/14 21:57:19] 例えば左から右へ順番に実行する関数hogeが定義できて、 hoge getLine getCharから getLine >>= (\s -> getChar >>= (\c -> putStr (s, [c])))と 同じ動作を定義できるのか？ 242 名前：デフォルトの名無しさん mailto:sage [04/10/15 01:54:14] >結合法則を満たす合成は全て実行の順序を保つでいいのか？ これは成り立たないと思う。 モナドの結合法則の概念と順序は本来関係ないんじゃないかな。 たまたま順序を組み立てるのにﾓﾅﾄﾞが使えるってだけだと思う。 www.sampou.org/haskell/a-a-monads/html/introII.html ↑のListモナドとかは 順序とは関係なさそうだし。（関数から複数の遅延込みの非正格値を返すためのもの？） モナドの用途は順序の決定のみにあらずってとこか。 243 名前：デフォルトの名無しさん mailto:sage [04/10/15 04:12:02] >>241 hoge :: IO String -> IO Char -> IO () hoge f g = f >>= \s -> g >>= \c -> putStr (s, [c]) getLine :: String、getChar :: Char だったら無理。 244 名前：デフォルトの名無しさん mailto:sage [04/10/15 04:13:08] >>242 > List モナドは非決定性をもつ計算の連鎖を、演算をそれぞれのステップで可能なすべての値に適用することで、合成する戦略を内包しています。 だけなら、モナドでなくてもいいね。 ------------ module MList where data MList a = a :*: (MList a) | MNull deriving (Eq, Show) infixr 3 :*: instance {- Broken -} Monad MList where   (x :*: xs) >>= f = merge (f x) (xs >>= f)     where        merge (x :*: xs) ys = x :*: merge ys xs       merge MNull ys = ys   MNull >>= f = MNull   return x = x :*: MNull   fail s = MNull toMList xs = foldr (:*:) MNull xs (>=>) = (>>=) -- 2ch : ">> が多すぎます！" (>=>) :: Monad m => m a -> (a -> m b) -> m b test f = test1 f == test2 f test1 f = f [1,2] >=> \x -> f [3, 4] >=> \y -> f [5, 6] test2 f = (f [1,2] >=> \x -> f [3, 4]) >=> \y -> f [5, 6] 245 名前：デフォルトの名無しさん mailto:sage [04/10/15 08:50:04] そうだよなあ。 モナドが「暗黙の引数world」と「関数のeagerな評価」を意味するだけなら，結合法則はなくてもよい。 246 名前：デフォルトの名無しさん mailto:sage [04/10/15 11:05:46] IOモナドについて。 話の流れから多少それるのかもしれませんが、 IOモナドの僕のとらえかたは以下のような感じです。 putStrはStringを引数としてとり、 「その文字列を表示する動作」を返す関数。 であり、putStr "Hello " >> putStr "World" とした場合、putStr "Hello "とputStr "World"のそれぞれが評価される 順番は問題ではない。 putStr "Hello "が評価された時点では、 "Hello "は出力されずに、「"Hello "を出力する動作」が 決定するだけである。 そして、putStr "Hello " >> putStr "World"は、 "Hello "を出力した後に"World"を出力する動作として評価される。 この時点では何の出力も生じない。 この動作は、main = ...というように、mainに代入されることにより、 評価器とは切り離された装置によって出力に変えられる。 つまり、putStr "Hello " >> (putStr "World" >> putStr "\n") とした場合、putStr "World >> putStr "\n"の部分が先に評価されて、 「"World"を出力した後に、"\n"を出力する動作」となり、 その後に、putStr "Hello "と結び付けられて、 「"Hello "を出力した後に「"World"を出力した後に"\n"を出力」する動作」 となる。 これは、 「「"Hello "を出力した後に"World"を出力」した後に"\n"を出力する動作」 と等しい。 247 名前：デフォルトの名無しさん mailto:sage [04/10/15 12:01:44] >>246 ありがとう、やっとすっきりした。 つまり継続を渡しているわけね。 248 名前：デフォルトの名無しさん mailto:sage [04/10/15 12:14:00] >>246 > であり、putStr "Hello " >> putStr "World" > とした場合、putStr "Hello "とputStr "World"のそれぞれが評価される > 順番は問題ではない。 順番は問題。これは左から評価しないと(されるように>>が定義されてないと)、 putStr "Hello ">> error "Error." 等が正しくうごかない。 > この動作は、main = ...というように、mainに代入されることにより、 > 評価器とは切り離された装置によって出力に変えられる。 上とも関連して、出力しながら内部の式を評価するわけで、 評価し終わったものを実行するのでは「ない」のだから、  main world を評価すると考えるほうがいいのでは。 上で自分でもただStateモナドのようにかいてしまったけれど、 IO a = World -> (a, World) {- ただしStrict -} と思うことにして。  (正則性と関連して実はIOはモナドの結合法則を満たしていなかったような) > つまり、putStr "Hello " >> (putStr "World" >> putStr "\n") > とした場合、putStr "World >> putStr "\n"の部分が先に評価されて、 ここも左から評価される。 あとは大体OKと思う。 249 名前：デフォルトの名無しさん mailto:sage [04/10/15 17:24:40] >>248 >順番は問題。 >>256は > putStrはStringを引数としてとり、 >「その文字列を表示する動作」を返す関数。 という前提だからいいんじゃないの? 250 名前：デフォルトの名無しさん mailto:sage [04/10/15 18:08:50] >>249 putStr "Hello " >> error "Error."  の右辺を先に評価したら"Hello"が表示される前にerrorで終わってしまうでしょ。 正格性解析かなにかで>>の左辺と右辺が Strictにしかも_|_にならずに評価できると知っていたら 何かの気まぐれで右辺から評価するかもしれないけど、基本は左から。 ちなみに右から(Lazyに)評価したら末尾再帰も無意味になるし無限ループも書けない。 251 名前：デフォルトの名無しさん mailto:sage [04/10/15 20:36:06] ちなみに右から(Lazyに)評価したら末尾再帰も無意味になるし無限ループも書けない。 どういう意味だ？ 252 名前：246 mailto:sage [04/10/15 21:53:07] 評価という言葉を誤用したみたいです。 putStr "Hello " >> putStr "World"は、 "Hello "を出力する動作の後に、"World"を出力する動作を続けた動作と解釈される。 と言いかえるべきなのかな。 (1+3) : []を、(4ではなく)1+3を空のリストに加えたものと解釈される。 というのと同じで、この1+3が4になるのはmainに関連づけられたとき (とhugsなどで、返り値の表示を求められたとき)のみである。 つまり、putStr "Hello " >> putStr "World"が左から評価されるのは、 print ((1+2)：(2+3)：[])が左から評価されるのと同様、 値が必要になった時点で評価されるという、遅延評価の性質から理解できる。 print ((1+2):(2+3):[])でまず1+2が、つぎに2+3が評価されるのは、 (:)に左から順に評価するという性質があるのではなく、 必要とされるのが1+2のほうが先であるというためである。 これは、print $ reverse ((1+2):error "foo":(2+3):[])の出力が[5,となる点からも確認できる。 それと同様にputStr "Hello " >> putStr "World"が左から評価されるのは、 まずputStr "Hello "がプログラムの実行に必要とされ、その後にputStr "World"が必要とされるためであり、 (>>)が左から評価されるといった性質を持っている必要はない。 (しかし、(>>)の右側が左側よりも先に必要とされるという状況は考えられないので(>>)が左から評価される性質を持つというのは そんなに間違いではないかもしれない。) putStr "Hello " >> error "Error."がうまく評価されるのも同様で、 "Hello "の出力の際にはerror "Error."を評価する必要がないためである。 現時点での僕の解釈ですので、間違いもあると思います。 Haskellに積まれた概念は非常に興味深いので、 今後も熟考していこうと思っています。 253 名前：デフォルトの名無しさん mailto:sage [04/10/15 23:06:59] どうも隔靴掻痒の感があるな。 モナドの表示的意味は言語仕様に書いてないのか？ [| >> |]ρσ = ...? 254 名前：デフォルトの名無しさん mailto:sage [04/10/16 05:09:35] >>252 いったいどういう原理によって > まずputStr "Hello "がプログラムの実行に必要とされ、その後にputStr "World"が必要とされるためであり、 こうなってると思ってるわけですか？  mainや(>>)は関数じゃなくてなにかすごく賢い"評価器とは切り離された装置" が何が必要かを見切って必要なところだけ評価するという立場？ それならそれでもいいですが… 私は、State(World)についてStrictなMonadだと思えば、 なぜ(>>)の左が先に必要になったのかが、説明できると書いたわけです。 255 名前：デフォルトの名無しさん mailto:sage [04/10/16 05:13:41] >>251 まず、mainだけ特殊な評価をうけるとは考えないことにします。 右から評価されると無限ループも書けないというのは、 main = loop where   loop =  act >> loop                     act = print "x" ここでloopの右辺を先に評価したらact >> (act >> (act >> ..))と ネストした列ができるだけでloopの処理が進まないという意味です。 末尾再帰も同様のことになります。 先に述べたように、特殊な評価装置や特殊ルールは考えないので、これは、 (>>)がそういう順序に評価を導くように定義されているということを意味します。 単にmainそのものを評価しても、(\_ -> ...)の形か、 (コンストラクタ) ...の形になって...の部分は評価されずに終わります。 これでは...の中に書いてあるIOアクションの列をどう評価、 実行していけばいいかはわかりません。 そこで、mainは関数であって(type IO a = World -> (a, World)、 プログラムの実行とはmain worldを評価する、つまりmain worldの 返り値を求める評価を行うことだと考えることにします。 例えば(putStr "X") worldを評価すると、 "X"が出力されたWorldを返します("X"が出力される)。 256 名前：デフォルトの名無しさん mailto:sage [04/10/16 05:15:13] これは、普通の評価なので、main worldの返り値(a, world)が求まれば いいので、まず返り値に必要な部分から計算されます。 したがって、遅延評価ならば、a >> bにおいてworldに最後に関与する 「外側」にある"b"のほうから評価が行われるはずだということになります。 これが「右から(Lazyに)」の意味です。 ちろんこれではループも書けないのでIOモナドとしては使えません。 しかし、WorldについてStrictなモナドだとすれば、 左から評価されるようになります。 -- typeではモナドの定義がHaskell98では書けない。 newtype IO a = IO { runIO :: World -> (a, World) } instance Monad IO where     ioact >>= f = IO $ \world -> world `seq`         let (a, world') = runIO ioact world          in  runIO (f a) $! world' もしよくわからなければ、Control.Monad.Stateのlazyなstateモナドで loopや末尾再帰のプログラムを書いて挙動を観察してみてください。 257 名前：デフォルトの名無しさん mailto:sage [04/10/16 09:30:25] これに基づいて議論しませんか？ www.haskell.org/definition/haskell98-report.pdf 258 名前：デフォルトの名無しさん mailto:sage [04/10/16 10:36:55] >>257 基づいてないと？ IOの話なら、規格の性質を満たすIOはいかにして定義され得るか ということを議論しているつもりなんだけど… 259 名前：もなど初心者 mailto:sage [04/10/16 18:27:11] なんかグダグダになってんのか話が進んでるのか判断できないんですが デバッグ辛くないですか？ 260 名前：デフォルトの名無しさん mailto:sage [04/10/16 19:02:57] 別に。 > デバッグ辛くないですか？ 261 名前：デフォルトの名無しさん mailto:sage [04/10/16 19:06:52] >>257のreportを見る限り，どちらの方法でもIOモナドの外部仕様を満たせるんじゃない？ The >>= operation passes the result of the first operation as an argument to the second operation. ということなので，f >>= gに対して，fの中で起こる副作用がgの中で起こる副作用より先に起こる ようにするには， (1) >>=は，左辺の引数についてstrict (2) g（正確にはgの中での副作用の呼び出し）がstrict のどちらでもよい（ように思える）． 262 名前：デフォルトの名無しさん mailto:sage [04/10/16 20:00:26] >>261 > どちらの方法でもIOモナドの外部仕様を満たせるんじゃない？ だれが(1)を主張しているの？ > (1) >>=は，左辺の引数についてstrict f >>= g のfが先に評価されるだけで、actionの実行とは関係ない。 例えば、f >> (g >> (h >> ..)) の無限列ができるだけでactionが実行されない こともあり得る。 > (2) g（正確にはgの中での副作用の呼び出し）がstrict なにがいいたいのかよくわからない。 Monadの話をしているのだから>>=の性質について話さないと。 >>255-256理論のことなのかな(そうは読めないけれど)。 それから、IOモナドはこれ > Special operations (methods in the class Monad, see Section 6.3.6)  > sequentially compose actions,  > corresponding to sequencing operators (such as the semicolon) in imperative languages.   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ を要求してるからf >>= gのfが先に評価されるのであって、 >>261の部分からはそうなるとは限らないことに注意。(cf. LazyなStateモナド) 263 名前：デフォルトの名無しさん mailto:sage [04/10/16 20:43:42] 俺はHaskellのことは余りしらないんだけど、Haskellの言語仕様も MLのように表示意味論（操作意味論でもいいけど）でformalに定義 されてるんじゃないの？ 色々と仕様の背後にある意図を考えるのもいいけど、まずちゃんとした定義 を出してくれると素人には有難いなあ。言葉の定義も人によって違うみたいだし。 ちなみに fがstrict <=> f(_|_) = _|_ lazy evaluation <=> λ計算でいうところのnormal reduction ということでいいの？ 264 名前：デフォルトの名無しさん mailto:sage [04/10/16 21:33:21] >>263 > MLのように表示意味論（操作意味論でもいいけど）でformalに定義 IOはどうなんだろ？ citeseer.ist.psu.edu/peytonjones93imperative.html # 個人的にはHaskellのコミュニティはそういう文化じゃないと思ってる。 # formalなsemanticsがどうとかで論文書くんじゃなくて、 # 新しい便利なアイディアをどんどん導入して実際に使う。 # informalなsemanticsだけど気にしない、みたいなことがよく書いてあるきがする。 # # そういうことに興味がないことによる偏見かもしれない。 ググッたらちょっと古い(1996)けどこんなのも www-fp.dcs.st-and.ac.uk/~kh/papers/io-tutorial/section3_7.html > No formal semantics for these I/O primitives is possible at present,  > because there is no complete formal semantics for Haskell itself. formalでないと理解した気がしないなら、 Concurrent Haskell (Simon PJ他)の論文でIOのsemanticsは誰かの論文を参照、 みたいなことが書いてあった気がするから、探してみたら。 > fがstrict <=> f(_|_) = _|_ > lazy evaluation <=> λ計算でいうところのnormal reduction いいんじゃない。ちなみにdataコンストラクタはlifted。 265 名前：デフォルトの名無しさん [04/10/16 22:00:24] normal order reduction ≠ lazy evaluation 266 名前：デフォルトの名無しさん mailto:sage [04/10/16 22:26:55] >>265 等しくはないね。 でもλ計算でいうところのnormal-order reductionをするわけでしょう？ 267 名前：デフォルトの名無しさん mailto:sage [04/10/16 22:48:32] どうもありがとう。 Simon Peyton Jones, Andrew Gordon and Sigbjorn Finne. Concurrent Haskell, POPL, 1996. をざっと見たところ、その辺の詳しい話は Roy L. Crole and Andrew D. Gordon. A Sound Metalogical Semantics for Input/Output Effects, CSL, 1994. Andrew D. Gordon. Functional Programming and Input/Output, Cambridge University Press, 1994. を参照と書いてあった。暇なときにみてみよう。 ちなみに"Concurrent Haskell"の論文も結構面白い。IOの話については 下のような記述があった。ご参考…といってもここの人には常識か。 The sequencing combinators, >> and >>=, feed the result state of their left hand argument to the input of their right hand argument, thereby forcing the two actions (via the data dependency) to be performed in the correct order. ... In principle, then, a program is just a state transformer that is applied to the real world to give a new world. In practice, however, it is crucial that the side-effects the program specifies are performed incrementally, and not all at once when the program finishes. A state-transformer semantics for I/O is therefore, alas, unsatisfactory, and becomes untenable when concurrency is introduced, a matter to which we return in Section 6. 268 名前：Ｈａｓｋｅｌｌ？？？なにそれ？食えるの？ [04/10/17 01:10:13] 【ビギナ】初心者が習うべき言語は？ part6【必読】 pc5.2ch.net/test/read.cgi/tech/1092932484/494- おい。 Ｒｕｂｙにケチ付けてるこの馬鹿引き取ってくれよ。 269 名前：デフォルトの名無しさん mailto:sage [04/10/17 01:41:49] ほっといてやれ 270 名前：食べられません。 mailto:sage [04/10/17 01:47:28] >>268 > Ｒｕｂｙにケチ付けてるこの馬鹿引き取ってくれよ。 事実誤認だよ。 >>269 ありがとう。 271 名前：デフォルトの名無しさん mailto:sage [04/10/17 03:02:52] >>265 normal reduction = leftmost reduction = lazy reduction じゃなかったっけ 272 名前：デフォルトの名無しさん mailto:sage [04/10/17 03:09:20] eager evaluation と call-by-value が対応して lazy evaluation と call-by-need が対応して normal-order reduction というと call-by-name が対応するといいたいんじゃない？ 273 名前：デフォルトの名無しさん mailto:sage [04/10/17 11:45:11] >> 254 > なにかすごく賢い"評価器とは切り離された装置" が必要性を判断してくれると仮定しなければ、 print $ [3, 1+2, 4] !! 0 で1+2が評価されない理由は説明できないと思う。 具体的にはその装置はHaskellの一部であって、 Haskellプログラムの内側では議論できない実装に近い部分の話になって くるんじゃないかな。 >>255,>>256のような議論は有意義だと思うが、 上述したような「装置」によって、(：)と(>>)を同列に扱えるのであり、 (:)にその「装置」が必要とされている以上、 (>>)に他の特別な理論をあてはめるよりは、 必要に応じて評価される。という lazy evaluationの原則を単純にあてはめればすむのではないかと思う。 ちなみに、 IOというものは[](リスト)と同様にそこにある何かであり、 たとえばputStrLn "Hello"が実行されると"Hello"を出力するのは、 [1,2,3]が(!!1)で2を返すのと同様にとらえられるのではないだろうか。 IOは評価時点では出力されずに、実行という次のステップで出力が生じる。 これは、 main = putStr "Hello " `seq` putStrLn "World" での出力が World であるという点からも理解されるのではないだろうか。 HaskellのIOでは評価と実行は切り離されている。ということに今日気付いた。 274 名前：デフォルトの名無しさん mailto:sage [04/10/17 13:33:11] 「評価する」というのと「印字する」というのが微妙に混同されているような、いないような。 275 名前：デフォルトの名無しさん mailto:sage [04/10/17 14:12:57] >>274 > print $ [3,1+2,4] !! 0 あたりのことを言われてるのかな？ Haskellにおいて、評価は印字などの動作によってしか引き起されない。 だから、とりあえず単純な印字の例を挙げただけ。 べつに print $ replicate ([3,1+2,4]!!0) "foo" のような例でもかまわない。 (当然この場合も1+2は評価されない。) Haskellでは、IOに関連づけられなければ、式が評価されることはない。 対話的環境でも暗黙のprintがなされていると考えられると思う。 (ちなみに、対話的環境では返り値がIOならばそれの実行を、 それ以外だったらprintをするようになっているのだと思う。) 当然、print $ [3,1+2,4]!!0で、 1+2が印字されないことをもって、評価されないと言っているわけではない。 print $ [3,error "foo", 4] !! 0 で、エラーが生じないというのと同じことを言ったつもりである。 もしかしたら、もっと根本的な誤りを突いているのかもしれない。 そうだったらもう少し詳しい説明をよろしくおねがいします。 276 名前：デフォルトの名無しさん mailto:sage [04/10/17 17:56:48] >>273 を読んで分かった… 君はlazy evaluationがそもそも分かってないんだorz lazy evaluationが、「必要」に応じて評価されるのは、 > > なにかすごく賢い"評価器とは切り離された装置" > が必要性を判断してくれると仮定しなければ、 こういうのがなにかが必要性を判断するわけじゃないよ。 単にoutermost leftmost reductionをしてるだけ。 質問に答えて欲しい。 (0) [3, 1+2, 4] !! 0 と length [0..] > 0 の評価はそれぞれどう進む？ (1) seqの初心者が陥りやすい誤解について説明せよ (2) Stateモナドは自分で書ける？ (Yes/No) (3) その評価の順序が分かる？ (Yes/No) (4) (Lazy)Stateモナドで無限loopが書けないのはわかってる？ (Yes/No) > IOというものは[](リスト)と同様にそこにある何かであり、 リストモナドも自分で定義できるし… 277 名前：デフォルトの名無しさん mailto:sage [04/10/17 18:17:15] >>275 > 対話的環境でも暗黙のprintがなされていると考えられると思う。 それってLispでいうrea-eval-print loopなんじゃないの？ 278 名前：haskell初心者 [04/10/19 17:22:32] 先月から勉強しているのですが、 haskellでｎ個の中から、ｍ個を取り出す組み合わせの数、mＣnのプログラムの書き方がわかりません。 だれか教えてください。お願いします。 279 名前：デフォルトの名無しさん mailto:sage [04/10/19 17:31:30] 宿題ですか? せめて自分でどこまでやったか書け。 280 名前：haskell初心者 [04/10/19 17:36:04] 課題です、すいません。 漸化式で作るところまでは考えたのですが、C++と違ってfor文が使えないので、 自分ではどうしたらよいかわからなくなってしまいました。 281 名前：デフォルトの名無しさん mailto:sage [04/10/19 18:01:50] 解1: マジメに計算する。階乗はどう書く？　mPn はどう書く？　両方が出来 たら適切な引数を与えて割ればいいよね。 解2: mCn = .. + .. といった形で書ける。 .. と .. はどちらもコンビネー ションだけど、 m と n の部分が少し小さい。で、m や n が 0 とか 1 だったらどうなるか、というのを考える。そしたら再帰で書けるよな。 という2つの考え方があるよ。 282 名前：haskell初心者 [04/10/19 18:06:43] なるほど！ ありがとうございました。 283 名前：デフォルトの名無しさん mailto:sage [04/10/19 18:42:26] ここは優しいインターネッツですね 284 名前：デフォルトの名無しさん mailto:sage [04/10/19 20:27:15] haskellの課題が出る講義があることに驚き。東大情報？ そのレベルの学生が再帰プログラムに不慣れなことにも驚き（失礼！）。 285 名前：デフォルトの名無しさん mailto:sage [04/10/19 21:05:26] 東大理情ではOcamlはやりますがHaskellはやりません。 工学部計数工学科（武市先生のいるとこ）ではHaskellをやる（人もいる）。 それにしても「関数型プログラムは理解し易くて初心者向き」なんじゃないのか... 286 名前：デフォルトの名無しさん mailto:sage [04/10/19 21:39:10] 東京工科大じゃないの？ www.teu.ac.jp/kougi/koshida/Prog6/index.html と思ったけど課題内容が違うから違うのかな。 287 名前：デフォルトの名無しさん mailto:sage [04/10/19 22:15:31] 京都産業大学？ 288 名前：デフォルトの名無しさん mailto:sage [04/10/19 22:29:15] >>287 呼んだ？ 289 名前：デフォルトの名無しさん mailto:sage [04/10/20 02:30:38] 漸化式が作れたのならプログラムのほとんどができたようなもんじゃないか 290 名前：デフォルトの名無しさん mailto:sage [04/10/20 04:03:09] -- 数え上げobscured。c 10 3 などとして使う c = flip ((length .) . filter . (. length . filter id) . (==)) .        (foldl ((=<<) . (. (return .) . (:)) . (>>=) ) [[]]) . (flip replicate [True, False])  291 名前：デフォルトの名無しさん mailto:sage [04/10/20 18:34:44] ぐっ。↑を導いた過程の解説きぼんぬ。 292 名前：デフォルトの名無しさん mailto:sage [04/10/20 18:53:01] コマンドプロンプトみたいなものを作ろうと思ってまず下のような単純なのを作って hugsで動かしてみたら問題なく動いたのですが、ghcでコンパイルして実行すると、 プロンプト "$ " が表示されず、適当にキー入力したあと ":!" でループを抜けると、 入力した個数分のプロンプト "$ " がずらずらと表示されてしまいます。 ちなみに、ghciではhugsと同様に期待通りの動作です。 いったいどうすればghcでも期待通りの動作になるんでしょう？ main = do { putStr "$ "; str <- getLine; case str of { ":!" -> return (); _ -> main } } ghcはver 6.2.2と6.2.1で試してみましたがどちらも同じ結果でした。

---

---

[ 続きを読む ] / [ 携帯版 ]

read.cgi ver5.27 [feat.BBS2 +1.6] / e.0.2 (02/09/03) / eucaly.net products.
担当:undef