関数型プログラミング ..
113:デフォルトの名無しさん
04/04/14 12:02
工科大の
URLﾘﾝｸ(www.teu.ac.jp)
の問題1 ですが、
> sigma :: (Int -> Int) -> (Int -> Int)
> 上記の関数sigmaを，1) ラムダ記法を使って，2) 関数の部分適用を使って，定義せよ．ただし，sigma fは，自然数nに対して
> f 0 + f 1 + ... + f n
> を計算する関数とする．
lambda 版 は以下のように作成しました。
sigmaLambda :: (Int -> Int) -> (Int -> Int)
sigmaLambda f = \x -> sum [f i | i <- [0 .. x]]
で、部分適用版ですが、
sigma :: (Int -> Int) -> Int -> Int
sigma f 0 = f 0
sigma f n = sigma f (n-1) + f n
で、いいんでしょうか。
題意のような関数を返すのですが、部分適用という感じがしません。
出題者がどのような回答を期待しているか知りたいのですが。
(あと、なんか lambda版を、内包表現とか使ってて、出題意図に沿ってないような気がするのです)
114:デフォルトの名無しさん
04/04/14 13:37
>>113
> 題意のような関数を返すのですが、部分適用という感じがしません。
addNum'' n m = n + m に部分適用を使ったといっているのだからそれでいいだろう。
sigmaPartial f n = sum [f m | m <- [0..n]]
> (あと、なんか lambda版を、内包表現とか使ってて、出題意図に沿ってないような気がするのです)
それなら使わなければいいのでは？
sigmaLambda = \f n -> if n == 0 then f 0 else sigmaLambda f (n - 1) + f n
115:デフォルトの名無しさん
04/04/14 14:00
sigma,sigma' :: (Int -> Int) -> (Int -> Int)
sigma f = \ n -> foldl (\ s i -> s + f i) 0 [0..n]
sigma' f = let iter s x = if x < 0 then s else iter (s+f x) (x-1) in iter 0
116:デフォルトの名無しさん
04/04/14 14:37
import Control.Monad.Fix (fix) -- fix f = f (fix x)
sigma = flip fix 0 $ \s t f n -> if n < 0 then t else s (t + f n) f (n - 1)
117:デフォルトの名無しさん
04/04/14 14:38
fix f = f (fix f)ね。
118:デフォルトの名無しさん
04/04/19 19:21
Haskell に例外処理の機構はあるの？
119:デフォルトの名無しさん
04/04/19 19:37
ある。
Haskell98でもIOモナドからthrowできる例外(IOError)があるし、
最近のGHC、Hugsでは普通の関数からも例外(Exception)をthrowできる。
catchはIOモナドの中でおこなう。
参照: Control.Exception
120:デフォルトの名無しさん
04/04/20 23:50
Haskell勉強中なんですけど、
「モナドは継続渡しを提供する」という大雑把な理解でいいでしょうか？
･･･違うかな？
121:デフォルトの名無しさん
04/04/24 22:23
なんで Prelude で (!!) は Integer じゃなくて Int で定義されているの？
122:デフォルトの名無しさん
04/04/25 02:07
>>121
実際問題それ以上使うことはないからだろう。
Haskell 98 Report によると maxBound::Int は少なくとも 2^29-1。
(!!)のインデックスは0-originだから、長さ2^29のリストまで扱える。
これ以上の長さのリストを使う場面は……。
123:デフォルトの名無しさん
04/04/25 12:41
円周率の世界記録に朝鮮したい人はどうすれば？
124:デフォルトの名無しさん
04/04/25 18:11
>>123
自分で最低義すれ。
125:デフォルトの名無しさん
04/04/26 14:54
>>123
円周率は全桁保持していなくても次を計算できたはず。
>>124
アドレスの制限があるから多くの計算機と既存の処理系では
再定義しても無駄。
126:デフォルトの名無しさん
04/04/26 23:48
>>120 こんなん見つけた
URLﾘﾝｸ(www.jaist.ac.jp)
ここの資料はjaistのゼミ資料？
他にはHaskellDBが自分的に興味深い．
TorqueとかHibernateなんて目じゃない． Haskellだけど…
127:デフォルトの名無しさん
04/04/27 14:27
>>121
haskell@でもちょうど議論されてるね。
上ででたものの他に、こういう意見があった。
Integer派:
* Lazyにcreated/destroyedなデータならアドレスの制限を
受けずに大きいものを利用できるはずだ。
* Intは一般的なケースへの最適化であり、
"Premature optimization is the root of all evil."
Integerには反対派:
Integerにするのは、巨大なリストという特殊な状況への最適化である。
(Integral b) => がよろしい。
128:デフォルトの名無しさん
04/04/27 18:46
Hanatani さんすげーな。
オレもああいう凄腕Haskellerになりたい。
129:デフォルトの名無しさん
04/04/28 12:39
>>128
なんか凄いもの作ったの？
130:デフォルトの名無しさん
04/05/05 01:32
しばらく見ないうちに「関数型言語」のスレがひどいことになってるな。
131:デフォルトの名無しさん
04/05/05 02:34
>>130
Aranskさま〜〜早くこのスレにも御光臨してくださいませ〜〜
Aranskさま〜〜早くこのスレにも御光臨してくださいませ〜〜
Aranskさま〜〜早くこのスレにも御光臨してくださいませ〜〜
Aranskさま〜〜早くこのスレにも御光臨してくださいませ〜〜
Aranskさま〜〜早くこのスレにも御光臨してくださいませ〜〜
132:デフォルトの名無しさん
04/06/27 22:34
たま〜にはあげてみる
Haskell Support for the Eclipse IDE
URLﾘﾝｸ(eclipsefp.sourceforge.net)
0.3.0はEclipse最新var.(M9〜正式版)に対応しているぞ。
133:デフォルトの名無しさん
04/06/30 18:10
おお． しかしスクリーンショットがほしい所かも． 後でインスコしてみるか…
Fudgets
URLﾘﾝｸ(www.cs.chalmers.se)
触ってる人いる？ これから弄ってみようと思うのだけど．
featureのページに，
Declarative flavour. While it is possible to enable GUI programming in
a functional language by providing an interface to an imperative GUI toolkit and,
in effect, using an imperative sub-language within the functional language,
Fudgets provide a declarative style of programming also for the construction of GUIs.
とある． なんだか期待大．
134:デフォルトの名無しさん
04/06/30 20:48
>>133
使えたら是非おしえてくれ。
Declarative GUI toolkitって数年前から
どれもメンテが止まってるっぽいんだよな。
最近ではwxHaskellがスタンダードになりつつあるけど、
やっぱりHaskellならDeclarativeにやりたい。
135:デフォルトの名無しさん
04/07/17 08:42
Haskell Marathon
URLﾘﾝｸ(www.sampou.org)
136:デフォルトの名無しさん
04/07/18 09:25
Haskell で Marathon を実装するのかとｵﾓﾀ。
137:デフォルトの名無しさん
04/07/26 01:14
マラソン参加してみようかな。入門ページ読んだくらいで準備はよいだろうか
138:デフォルトの名無しさん
04/07/29 09:20
マラソン直前に台風直撃の悪寒
139:デフォルトの名無しさん
04/08/09 23:33
LL WeekendでのHaskellに対する聴衆の感想は「Haskellのコードはよくわからない」というのが多かったみたいでつね
140:デフォルトの名無しさん
04/08/10 01:19
5分だか7分だかでわかれという方が無理があるという話がある。発表者陣はよ
くやったと思うよ。
「わたしはもうループも書けなくなってしまって……」というのにワロタ。
141:デフォルトの名無しさん
04/08/11 02:33
LL侍はHaskellを斬ったの？
142:デフォルトの名無しさん
04/08/12 01:39
>>141
「Hello, worldもブラックボックス斬り」されてました。
143:デフォルトの名無しさん
04/08/12 13:41
おれはhaskell haskell haskellだ
関数型の haskellだ
短くて 簡潔で 理解しやすいコードを書けるぜ
って、言うじゃない
だけど
難しくて monad が理解できませんから
残念！
「Hello worldさえブラックボックス」
斬り
144:デフォルトの名無しさん
04/08/12 20:55
むしろHello, worldだから難しいような気がする
145:デフォルトの名無しさん
04/08/12 21:58
main = do putStr "Hello, World!"
で済むから、コード自体は特に難しくは見えない。
ただ、入門者が Hello, World に到達するまでの過程が難しいんだよね……。
146:デフォルトの名無しさん
04/08/12 22:00
>>145
そのdoはいるの？
147:145
04/08/12 23:13
この場合はいらないけど、先々のことを考えたら入れた方がいいかな、とちょっ
とだけ思ったのです。
main = do str <- getLine
putStr str
みたいに。
148:デフォルトの名無しさん
04/08/13 07:57
いきなりIOから入るのがまずい。
fact→fib→qsortあたりから入れば
得体の知れないモナドをとりあえず回避できる。
149:デフォルトの名無しさん
04/08/13 16:25
再帰とリスト処理しかできないHaskellちゃん
がんばってもせいぜい二分木
150:デフォルトの名無しさん
04/08/13 17:34
膣門です。
"Hindley-Milner" って、何て読むんでつか？
151:デフォルトの名無しさん
04/08/14 01:49
誰か「モナドだけで書く Haskell プログラミング」を書いてくれい
152:デフォルトの名無しさん
04/08/15 13:29
>>151 Cでも使ってれば？
153:デフォルトの名無しさん
04/08/15 21:34
そういやHaskellのコンパイルはC経由なんだよね
154:デフォルトの名無しさん
04/08/15 22:04
末尾再帰の保証とかC経由じゃ無理だろ
155:デフォルトの名無しさん
04/08/15 22:21
GHCで最適化オプション付けるとCのコード吐くんじゃなかったっけ?
156:デフォルトの名無しさん
04/08/16 02:59
>>150
メール出して聞いたら?
URLﾘﾝｸ(www-maths.swan.ac.uk) J. Roger Hindley
URLﾘﾝｸ(www.cl.cam.ac.uk) Robin Milner
157:デフォルトの名無しさん
04/08/16 05:57
>>156
もちつけ
158:デフォルトの名無しさん
04/08/16 06:12
>>154
そりゃ当然、Cにする前にプログラム変換するだろ
それに大抵のCCには-foptimize-sibling-callsみたいなのがあるだろうし
159:デフォルトの名無しさん
04/08/16 08:24
レベル低いな。っつってもHaskellのことは何も知らないのであれなんだが。。。
ユーザーレベルで言語をマスターするっつーのは、ある処理系を骨までしゃぶり
尽くすことだろ。リスパーのように自作こそ最強だが、複雑な言語ではそこまでは
まあ、なかなか出来るもんでもないしな。
GHCのことについて詳しい奴がいないのを見ると、誰もHaskellでまともに
プログラム書こうとしてないように見える。結局おまいらは、話のネタに
関数型言語を選んでるだけなんだよ。
160:デフォルトの名無しさん
04/08/16 23:20
↑Aransk?
161:デフォルトの名無しさん
04/08/17 00:31
Simon Peyton Jones は C-- もやってるのに、自前でオプティマイズ出来ないってのは意外。
162:デフォルトの名無しさん
04/08/17 00:50
>160
Aranskはいちゃもん言うだけでプログラムすら書かんだろ?
163:デフォルトの名無しさん
04/08/18 12:47
wxhaskellについてですが、
サンプルプログラムのBouncingBalls.hsでセグメンテーションフォールトが
起きます。(URLﾘﾝｸ(wxhaskell.sourceforge.net))
プログラムを起動し、'p'などのアルファベットを入力することで生じます。
そこで小さなプログラムを作って試してみたのですが、
やはり同様な現象が起ります。
$ cat test.hs
import Graphics.UI.WX
main :: IO ()
main = start test
test :: IO ()
test = do f <- frame []
p <- panel f []
set f [layout := widget p]
set p [on(charKey 'a') := print "test ok"]
$ ghc -package wx test.hs -o test
$ ./test
(ここでキーボードの'a'を入力)
セグメンテーション違反です
環境
wxhaskellのバージョンは0.7
wxGTKのバージョンは2.4.2
OSはlinux
他の環境でもこのバグが再現するでしょうか。
164:デフォルトの名無しさん
04/08/19 17:20
>>163
特に問題発生せず
環境
wxHaskell 0.8
wxWidget 2.5.2
MacOS X 10.3
$ ghc -package wx test.hs -o test
$ /usr/local/wxhaskell/bin/macos-app -v test
できたtestをFinderからダブルクリックで起動
真っ白いパネルが出てくる
'a' 押すと「コンソール」に "test ok"
とりあえずバージョンアップしてみれば
165:デフォルトの名無しさん
04/08/22 09:05
wxHaskellを0.8にバージョンアップしたら問題は解決しました。
どうもありがとうございます。
166:デフォルトの名無しさん
04/08/22 09:36
このような関数はどう書けばいいんでしょうか？
f (+) [1 2 3] [4 5 6] => [5 7 9]
167:デフォルトの名無しさん
04/08/22 11:30
f g (x:xs) (y:ys) = (g x y) : f g xs ys
168:デフォルトの名無しさん
04/08/22 11:41
f g xs ys = [g x y | (x, y) <- zip xs ys]
169:デフォルトの名無しさん
04/08/22 11:55
これを拡張したn引数(n階?)の関数とn個のリストをとる
関数はどう書くのがいいでしょう。
f n g [x11, x12, ...] [x21, x22, ...] ... [xn1, xn2, ...]
=> [(g x11 x21 ... xn1), (g x12 x22 ... xn2), ...]
みたいな。lispのmapってこんな感じですよね。あちらは
関数のarityがわかるからnは不要ですけど。
170:デフォルトの名無しさん
04/08/22 12:19
f g = map (hoge g) $ zip
Haskellはよく知らんので、hogeをどうやって書くのか調べてもよく分からん。
171:デフォルトの名無しさん
04/08/22 16:24
引数の数が可変ってhaskellでは書けないような気が。
何か方法あったっけ？
172:デフォルトの名無しさん
04/08/22 16:45
>>166
zipWith (+) [1, 2, 3] [4, 5, 6]
173:デフォルトの名無しさん
04/08/22 17:19
>>171
別に可変個の引数は必要ない。
1引数の関数のリストと引数のリストを受け取って適用して返す演算子をつくればOK。
演算子をxとすると
[f, f, f] x [x11, x12, x13] x [x21, x22, x23]
とか。Haskellの細かい文法知らんのでこう書けるかどうかは知らないけど。
174:デフォルトの名無しさん
04/08/22 17:48
どういう型になるんだ？
175:デフォルトの名無しさん
04/08/22 17:53
map sum $ transpose [[1,2,3],[4,5,6],[7,8,9]] => [12,15,18]
こんなもんでどうでしょうか。
176:デフォルトの名無しさん
04/08/22 20:04
>>174
[a->b]->[a]->[b]かな?
177:デフォルトの名無しさん
04/08/22 20:10
zipWith ($)
178:デフォルトの名無しさん
04/08/22 20:54
Prelude> (zipWith ($)) (map (+) [1,2,3]) [4,5,6]
[5,7,9]
ナルホド。
179:デフォルトの名無しさん
04/08/23 11:43
只の関数適用(f x)と(f $ x)って何か違うところあるの？
それとも( )じゃワケがわからないから($)と書けるように
目に見える演算子として用意されているだけ？
180:デフォルトの名無しさん
04/08/23 12:19
$ は関数合成では？
181:145
04/08/23 12:35
関数合成は . でしょ。
>>179 何も代わらない。関数適用のための演算子だから。
本来の利用法は >>178 みたいなものなのかな(個々の要素にそれぞれ適用する
ためには、関数適用の演算子があると便利)。
f $ g x と書くと、演算子の優先度の関係上 f(g x) と同じことになるので便
利、ついでに結合性の関係で f $ g $ h x とか書ける、というのが個人的に
は嬉しい。カッコの省略にも使える。
関数合成はあくまで関数の合成の演算子なので、 f . g . h x とは書けない。
(f . g . h) x なら書けるけど。
182:デフォルトの名無しさん
04/08/23 16:17
可変個数の zipWith については、
Functional Pearl "Do we need dependent types?"
Daniel Fridlender and Mia Indrika, 2000 J. Functional Programming,
vol. 10, July.
URLﾘﾝｸ(www.cs.chalmers.se)
に載っているので興味があるひとは読んでみるべし。
183:デフォルトの名無しさん
04/08/24 12:40
>>171-181
> 只の関数適用(f x)と(f $ x)って何か違うところあるの？
ある。$はただの関数だから、引数の型がそこで固定される。
f :: a -> (forall b. b -> b) -> a
f x g = g x
とすると、f 0 id はOKだが、f 0 $ id はだめ。
ST Monadなんかをつかっていると結構引っかかる。
184:デフォルトの名無しさん
04/08/24 14:37
-- zipWithN
infixl 2 <$>
infixl 1 <->
(<$>) = map
(<->) = zipWith ($)
-- 例
-- (\x y z -> x + y + z) <$> [3,4] <-> [5,6] <-> [7,8]
----------------------------
-- 可変引数
ncat :: NCat b => b
ncat = ncat' id
class NCat a where
ncat' :: (String -> String) -> a
instance NCat String where
ncat' f = f ""
instance NCat b => NCat (Char -> b) where
ncat' f x = ncat' (f . (x:))
-- 例
-- ncat 'a' 'b' 'c'
# >>183の171は179の間違い。
185:デフォルトの名無しさん
04/08/24 14:38
>>184
型指定が要った。
ncat 'a' 'b' 'c' :: String
186:デフォルトの名無しさん
04/08/24 20:08
携帯から読むと AA 判定されててﾜﾗﾀ >>183-185
187:デフォルトの名無しさん
04/08/26 20:44
AA的プログラミング
188:デフォルトの名無しさん
04/08/26 20:54
(--#) とか (*^-^*) とか？
189:デフォルトの名無しさん
04/08/30 23:20
Categories for the Working Mathematician の訳書ってなんていうタイトルでつか？
190:デフォルトの名無しさん
04/08/30 23:27
スマソ。
「そのうち出る」 = 「そのうち出版される」という意味か。
「テキストの候補に挙がる」ではなく。
191:デフォルトの名無しさん
04/08/31 00:44
誤爆にも程があります
192:デフォルトの名無しさん
04/08/31 12:01
「数学に勤しむ貴方のための圏論」てのがそれらしいが
近刊とあってまだ出てないようだ。
URLﾘﾝｸ(www.kyoto-su.ac.jp)
193:デフォルトの名無しさん
04/09/07 17:30
末尾再起すると、遅延評価されないですね。
(length (hoge xx yy zz)) < 3
とかで困る。かも。
194:デフォルトの名無しさん
04/09/07 20:50
>>193
> 末尾再起すると、遅延評価されないですね。
そんなことはない。
> (length (hoge xx yy zz)) < 3
> とかで困る。かも。
lengthがstrictだからhogeがlazyでも意味がないとはいえるが、
末尾再帰とは無関係なので、意味がわからない。
なにを誤解してるのですか？
195:デフォルトの名無しさん
04/09/08 10:49
>>193
『末尾再帰の最適化』をすると遅延評価できない（或いはその逆）、のことを言いたいのかな。
それだったら解る。
あ、でも例 (length (hoge xx yy zz)) < 3 の意味はやっぱりわからない。
196:デフォルトの名無しさん
04/09/08 18:24
>>195
> 『末尾再帰の最適化』をすると遅延評価できない（或いはその逆）、のことを言いたいのかな。
詳しく説明きぼんぬ。
gotoでジャンプするコードにするとサンクが作れないのかな？
197:デフォルトの名無しさん
04/09/09 23:56
>>195
take n 末尾再帰関数(無限リスト)
みたいなのが出来ないということでは？
198:197
04/09/10 00:26
括弧の位置を間違えた。
take n (末尾再帰関数 無限リスト ・・)
です。
199:193(初心者)
04/09/10 16:18:42
すいません。どっかいってました。
>197さんの言うとおりです。
例は適当にかいたらだめでした。
200:デフォルトの名無しさん
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
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:デフォルトの名無しさん
04/09/10 22:16:02
>>201
nub0 [1..]自体がbottom(無限リストではない)なんだから
末尾再帰も糞もないですよ。
nub0' :: [Int] -> Int
nub0' = foldr (+) 0
だって同じこと。
203:197
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:デフォルトの名無しさん
04/10/08 02:06:46
>>204
URLﾘﾝｸ(www.sampou.org)
ではだめ？
206:デフォルトの名無しさん
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:デフォルトの名無しさん
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
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:デフォルトの名無しさん
04/10/14 08:51:55
（Ｘ * X ) * X = X * ( X * X ) といった「結合側」が成り立つ
の()の意味はなんだ？
単に型が合うかどうかか？演算の時間的な順番か？
210:デフォルトの名無しさん
04/10/14 09:25:14
>>209
演算の順序。
代数の本を読めばどしょっぱなに書いてあるよ。
211:デフォルトの名無しさん
04/10/14 09:29:17
じゃあ（入力 * 出力）* 入力 = 入力 * （出力 * 入力）になって
最初に出力してくれるのかい？
212:デフォルトの名無しさん
04/10/14 11:05:33
コードの結合順序と、実行順序を混同するな。
Cで {{f(); g();} h();} と {f(); {g(); h();}} が同じ結果になる
みたいなものだ。
213:デフォルトの名無しさん
04/10/14 15:33:35
だから（Ｘ * X ) * X = X * ( X * X )ってのはどういう意味なの？
214:デフォルトの名無しさん
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:デフォルトの名無しさん
04/10/14 17:00:35
>>214
> 「結合則は成立するが、交換則は成立していない」
「交換則は必ずしも成立するわけではない」のほうが適当では？
216:デフォルトの名無しさん
04/10/14 17:05:38
この場合の（Ｘ * X ) * X = X * ( X * X )の意味は
どういう風に括弧をつけても関数Xの適用順序は
左から右、右から左と一定であるって意味でいいの？
217:デフォルトの名無しさん
04/10/14 17:17:39
>>215
ああその通りですね。失礼しました。
>>213=216
まあその通りといえばその通りではないかと思います。
*を関数の合成みたいな演算だと考えればよいのでは。
218:デフォルトの名無しさん
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:デフォルトの名無しさん
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:デフォルトの名無しさん
04/10/14 17:33:16
x = yでもa' x と a' yは等しくなくてもいいんじゃない？
221:デフォルトの名無しさん
04/10/14 17:50:24
結合法則は満たすけど交換法則は満たさないって状況、
小学校でやる一般的な算数にある？
222:デフォルトの名無しさん
04/10/14 17:52:51
引き算、割り算
223:デフォルトの名無しさん
04/10/14 18:00:53
結合法則満たすのか？
224:デフォルトの名無しさん
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:デフォルトの名無しさん
04/10/14 18:16:35
>>219
> っていうのは普通の関数とどこが違うの？
> 普通の関数でもそういうのあるんだから、
どこの世界の関数だそれは（ｗ
226:デフォルトの名無しさん
04/10/14 18:23:24
べき乗とかなら交換したら意味がちがうし
x /= y ならば a' x と a' y は等しくないんちゃう？
227:デフォルトの名無しさん
04/10/14 18:27:33
もちつけ。モノイドがモナドなわけじゃないぞ。
> この半群の集合への作用(注1)の仕方を定めたものがMonadです。
228:デフォルトの名無しさん
04/10/14 18:29:58
>>219
逆で、関数でそういう性質が成り立って、文字列の連結や状態遷移でもそういう性質が成り立つからそれらを抽象化してモナドにしたってこと。
連結リストや配列リストの性質を抽象化してリストとして扱うようなのと同じ。
229:デフォルトの名無しさん
04/10/14 18:31:50
じゃあ普通の関数もモナド？
230:デフォルトの名無しさん
04/10/14 18:42:39
>>220
x = y で a' x = a' y でなくても構わないっていうのは数学的にはおかしい
気がしますが。
プログラム的には副作用が起きているなら成立すると思いますが、その副作用
を上手く扱うのがモナドなんじゃないの？
231:デフォルトの名無しさん
04/10/14 18:54:09
順序は正しく守って、毎回違った答えが出ても
処理系はエラーを出さず理論的にもきちんとまとめられるってことか？
232:207
04/10/14 19:02:54
>>218
そうですね。すみません。208は全然ダメです。
モナドをモノイドで押し切ろうというのは無理がありました。
233:デフォルトの名無しさん
04/10/14 19:03:15
>>229
普通の関数だと、たとえば
f(g(x), h(y))
がどの順番で評価されるかは不定。でも、モナドを使えば、その順序を確定さ
せることができる。
……副作用とかいう話じゃなくて、順序を確定させることが重要なのかなあ。
順序が確定的だから、副作用が起きるコードでもOKみたいな感じ？
234:デフォルトの名無しさん
04/10/14 19:06:11
モナドってのは何をさすんだい？
a * bだったらaやbがモナド？それとも*がモナド？
235:207
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:デフォルトの名無しさん
04/10/14 19:18:35
a,bはプログラム中の式
*は各式の関係を表す演算子
237:207
04/10/14 19:27:09
>>232 自己レスもちろん>>207もだめです。
モナドは雰囲気はモノイドなんですがやっぱりモノイドとは
みなせそうにないので、これも嘘です。
> この半群の集合への作用(注1)の仕方を定めたものがMonadです。
予想と違って、正しいかもしれないものだと素直に読んだ方が
多かったようで、申し訳ないです。
238:デフォルトの名無しさん
04/10/14 19:31:13
理解した部分だけ書くと、結合法則を満たす関数の合成を使うと
IOのような実行の順序が重要な意味をもつ関数を（順序不定で）合成しても
合成された関数は一意的な順序でIOが実行される関数になるということか？
順序を保つ合成が結合法則を満たすのは分かったが、
結合法則を満たす合成は全て実行の順序を保つでいいのか？
239:デフォルトの名無しさん
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:デフォルトの名無しさん
04/10/14 21:26:54
じゃあモナドは実行の順序が決められてる関数の中の一つってことか？
241:デフォルトの名無しさん
04/10/14 21:57:19
例えば左から右へ順番に実行する関数hogeが定義できて、
hoge getLine getCharから
getLine >>= (\s -> getChar >>= (\c -> putStr (s, [c])))と
同じ動作を定義できるのか？
242:デフォルトの名無しさん
04/10/15 01:54:14
>結合法則を満たす合成は全て実行の順序を保つでいいのか？
これは成り立たないと思う。
モナドの結合法則の概念と順序は本来関係ないんじゃないかな。
たまたま順序を組み立てるのにﾓﾅﾄﾞが使えるってだけだと思う。
URLﾘﾝｸ(www.sampou.org)
↑のListモナドとかは
順序とは関係なさそうだし。（関数から複数の遅延込みの非正格値を返すためのもの？）
モナドの用途は順序の決定のみにあらずってとこか。
243:デフォルトの名無しさん
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:デフォルトの名無しさん
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:デフォルトの名無しさん
04/10/15 08:50:04
そうだよなあ。
モナドが「暗黙の引数world」と「関数のeagerな評価」を意味するだけなら，結合法則はなくてもよい。
246:デフォルトの名無しさん
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:デフォルトの名無しさん
04/10/15 12:01:44
>>246
ありがとう、やっとすっきりした。
つまり継続を渡しているわけね。
248:デフォルトの名無しさん
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:デフォルトの名無しさん
04/10/15 17:24:40
>>248
>順番は問題。
>>256は
> putStrはStringを引数としてとり、
>「その文字列を表示する動作」を返す関数。
という前提だからいいんじゃないの?
250:デフォルトの名無しさん
04/10/15 18:08:50
>>249
putStr "Hello " >> error "Error."
の右辺を先に評価したら"Hello"が表示される前にerrorで終わってしまうでしょ。
正格性解析かなにかで>>の左辺と右辺が
Strictにしかも_|_にならずに評価できると知っていたら
何かの気まぐれで右辺から評価するかもしれないけど、基本は左から。
ちなみに右から(Lazyに)評価したら末尾再帰も無意味になるし無限ループも書けない。
251:デフォルトの名無しさん
04/10/15 20:36:06
ちなみに右から(Lazyに)評価したら末尾再帰も無意味になるし無限ループも書けない。
どういう意味だ？
252:246
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:デフォルトの名無しさん
04/10/15 23:06:59
どうも隔靴掻痒の感があるな。
モナドの表示的意味は言語仕様に書いてないのか？
[| >> |]ρσ = ...?
254:デフォルトの名無しさん
04/10/16 05:09:35
>>252
いったいどういう原理によって
> まずputStr "Hello "がプログラムの実行に必要とされ、その後にputStr "World"が必要とされるためであり、
こうなってると思ってるわけですか？
mainや(>>)は関数じゃなくてなにかすごく賢い"評価器とは切り離された装置"
が何が必要かを見切って必要なところだけ評価するという立場？
それならそれでもいいですが…
私は、State(World)についてStrictなMonadだと思えば、
なぜ(>>)の左が先に必要になったのかが、説明できると書いたわけです。
255:デフォルトの名無しさん
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:デフォルトの名無しさん
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:デフォルトの名無しさん
04/10/16 09:30:25
これに基づいて議論しませんか？
URLﾘﾝｸ(www.haskell.org)
258:デフォルトの名無しさん
04/10/16 10:36:55
>>257
基づいてないと？
IOの話なら、規格の性質を満たすIOはいかにして定義され得るか
ということを議論しているつもりなんだけど…
259:もなど初心者
04/10/16 18:27:11
なんかグダグダになってんのか話が進んでるのか判断できないんですが
デバッグ辛くないですか？
260:デフォルトの名無しさん
04/10/16 19:02:57
別に。 > デバッグ辛くないですか？
261:デフォルトの名無しさん
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:デフォルトの名無しさん
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:デフォルトの名無しさん
04/10/16 20:43:42
俺はHaskellのことは余りしらないんだけど、Haskellの言語仕様も
MLのように表示意味論（操作意味論でもいいけど）でformalに定義
されてるんじゃないの？
色々と仕様の背後にある意図を考えるのもいいけど、まずちゃんとした定義
を出してくれると素人には有難いなあ。言葉の定義も人によって違うみたいだし。
ちなみに
fがstrict <=> f(_|_) = _|_
lazy evaluation <=> λ計算でいうところのnormal reduction
ということでいいの？
264:デフォルトの名無しさん
04/10/16 21:33:21
>>263
> MLのように表示意味論（操作意味論でもいいけど）でformalに定義
IOはどうなんだろ？
URLﾘﾝｸ(citeseer.ist.psu.edu)
# 個人的にはHaskellのコミュニティはそういう文化じゃないと思ってる。
# formalなsemanticsがどうとかで論文書くんじゃなくて、
# 新しい便利なアイディアをどんどん導入して実際に使う。
# informalなsemanticsだけど気にしない、みたいなことがよく書いてあるきがする。
#
# そういうことに興味がないことによる偏見かもしれない。
ググッたらちょっと古い(1996)けどこんなのも
URLﾘﾝｸ(www-fp.dcs.st-and.ac.uk)
> 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。
次ページ最新レス表示スレッドの検索類似スレ一覧話題のニュースおまかせリスト▼オプションを表示暇つぶし2ch
5384日前に更新/259 KB
担当:undef