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言語などではこんな風に無限列は扱えませんものね。
~/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
>>47 A Short Introduction to Haskell(http://www.haskell.org/aboutHaskell.html) に書かれているHaskellのQuicksortを見たときは、感激というよりも、 「えっ、こんな風に書けちゃうの!?」と驚異を感じました。それ以来、 ずるずるとHaskellの魅力に引きずりこまれています。 (と言うほど最近はいじっていないのですが…)
たとえば、リストの中からxをみつけて、それ以降の リストを返す関数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 というエラーメッセージが出ます。
工科大学の演習問題(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
75 名前: 失業おやじ 投稿日: 2001/07/30(月) 20:47
>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
書籍も良いですが、もしまだお読みになっていなければ A Gentle Introduction to Haskell Version 98 を一度読まれると良いと思います。このスレッドのおかげで 邦訳( http://www.sampou.org/haskell/tutorial-j/index.html )が あることを知りました。私もモナドあたりで挫折しているので、 邦訳版を読み直してみようかと思っています。
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
2+3=5は tasu (Next (Next Zero)) (Next (Next (Next Zero))) -> Next (Next (Next (Next (Next Zero))))
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 ) ...
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に対応する関数です. 例で試してみましょう.
------------------- (++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 の誤植かと思われますが、先生はこのスレッドを見ていらっしゃいますでしょうか?
http://www.teu.ac.jp/kougi/koshida/Prog6/text06.html の課題2の証明中 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 を引いてますが、 こりゃマズイってことに気付きました、これが許されるなら0掛けたらどうなる!! あと、関数の定義で a x = b の時 b = a x と考えて置換、これも多分マズイですよね? a x が b であっても、b であれば a x とは限らないですよね? 反例が浮かばない・・・ あくまでも同等であるということを意識しないといけないですね。
この時 a == b ⇔ ((+) a c) == ((+) b c) (c は必ず整数です) となれば良いのではなかろうかと考えてみました。 a b が共に整数なら自明、それ以外でも、未定義を加算した結果も未定義 一般的には a == b ⇔ f a == f b の時、両辺を置換してしまえる・・・のかな? 大丈夫ですかね?
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)
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入門を整理して自分用マニュアル作ってます。 概ね全体像見えてきたかなって感じです。 やっと羽根伸ばしてプログラムできるかな?
記憶状態は簡単に文字列と整数の対応(Assoc)として定義する。 type Assoc a b = a -> b type State = Assoc [Char] Int 記憶内容へのアクセスと更新のため、次の2つを定義 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)
次に命令コマンドを定義。代入と出力だけとする。 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" といれると 8が帰ってきますね。 記憶状態がnoneからs1へ変化してますね。
でもこれではアウトプットが出ない。 次へ続く。
273 名前: バカボンぱぱ 投稿日: 01/09/08 00:45
>>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 = [] 準備が整ったので次のようなコマンドを実行する。 (1)xに3を代入 (2)yに5を代入 (3)yを出力 (4)x+yをzに代入 (5)zを出力 これは次のように書けます。 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は継続ですが、プログラムカウンタみたい ですね。
ちなみに、Introduction to Functional Programming using Haskell (長いので次回から参照するときは「IFP本」と呼ぶことにします)を 検索したら9箇所しかありませんでした。もっとも、学科の図書室 などでNACSISの検索に引っかからないのも結構あるでしょうから、 置いてある大学はもっと多いかもしれないです。
作者の Mark P. Jones 自身が実装についてのレポート "The implementation of the Gofer functional programming system" を書いていて、これを読みながら、処理系のソースを読むと大変勉強 になります。このレポート読んでソースをイジッテ自分で新しい機構 を追加するなど、しゃぶり尽くすに最高です。
gofc という C へのトランスレータが付属していて、これを 改造して、gofhoge というのをつくるというのはどうですか。
>>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.
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)
>>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は 高階関数は使えない?
getCharが2回続けて出てきたとして、 do c1<-getChar c2<-getChar ... 実行時に起きることの気分は、 let (c1, w1) = (getChar w0) in let (c2, w2) = (getChar w1) in ... みたいな感じだよ? どの行が副作用に見える?
出典は 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. .....
571 名前: Birdさんの本読書中 投稿日: 01/11/09 12:31
>>570 出典訂正 (誤)Introduction Functional Programming using Haskell (正)Introduction to Functional Programming using Haskell
「The Craft of Functional Programming」 これしかないだろ。って他にHaskellと名のつく本は無いらしい。 おれはHaskellなんて知らない。ま、そういうことだw
632 名前: デフォルトの名無しさん 投稿日: 01/11/24 23:14
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冊出て来たが、どうよ? どれが一番簡単で、初心者向きで、実用アプリ志向なの?
[上級問題1](これができれば単位は差し上げます) 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 :: [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
707 名前: デフォルトの名無しさん 投稿日: 01/12/13 15:46
この問題の事か・・・ たしかに線形性ってのは述べにくいよね
maximum segment sum 問題(mss)は、整数列(正とは限らない)を入力とし、その 連続する部分列で和が最大となるものをみつけて、その和を出力とする。 たとえば [2,-3,2,-1,2,3,-5,8,-9,1] の場合 [2,-1,2,3,-5,8] の和 9 が出力で ある。このプログラムを作成せよ。
[上級問題1] maximum segment sum 問題(mss)は実は線形時間アルゴリズムが存在する。その アルゴリズムを実装し、なぜ線形時間であるか理由をしるせ。
>774 俺は Haskell の型システムって結構シンプルだと思うんよ。 だから Haskell の型システムが ML に比べ複雑っていうより ML の型システムが Haskell に比べて貧弱って云った方がしっくりくる。 って意でした。ごめん。
776 名前: デフォルトの名無しさん 投稿日: 02/01/15 22:53
実際に何かを練習がてら作るとしたら何がいいでしょうか?
777 名前: デフォルトの名無しさん 投稿日: 02/01/16 13:58
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 とかもやってみたんですが同じでした。
778 名前: デフォルトの名無しさん 投稿日: 02/01/16 15:00
>>777 > x n= n+x (n-1) これは末尾再帰ではありません。 Version: February 2000 でも「Control stack overflow」と出ました。 その次のは、「Garbage collection fails to reclaim sufficient space」でした。こっちは処理系の問題。
ちなみに、schemeでは (define f (lambda (n s) (if (= n 0) s (f (- n 1) (+ s n))))) で、(f 100000 0)とすると数秒で答えが出る(DrScheme)。 末尾再帰が出来ないとなると、数値計算ではものすごい メモリー食いなHaskell。 というか、数値計算には不向きという評価?
call by name, call by reference 関数fが定義されているとして、f(1+1)を計算する時に 1+1を計算して2という値を渡すのがcall by value。 1+1という式(名前)を渡すのがcall by name。 call by nameは手続型言語ではAlgol、関数型言語ではMiranda, Haskelなど call by valueは大部分の手続型言語と関数型言語ではML, Lispが採用している。
Network Information: [ネットワーク情報] a. [IPネットワークアドレス] 61.207.0.0-61.207.255.0 b. [ネットワーク名] OCN f. [組織名] オープンコンピュータネットワーク g. [Organization] Open Computer Network m. [運用責任者] AY1361JP n. [技術連絡担当者] MO081JP n. [技術連絡担当者] KK551JP n. [技術連絡担当者] IM657JP p. [ネームサーバ] ns-kg001.ocn.ad.jp/61.207.56.0-61.207.255.0 p. [ネームサーバ] ns-kn001.ocn.ad.jp/61.207.56.0-61.207.255.0 p. [ネームサーバ] ns-os001.ocn.ad.jp/61.207.0.0-61.207.37.0 p. [ネームサーバ] ns-os001.ocn.ad.jp/61.207.42.0-61.207.55.0 p. [ネームサーバ] ns-tkb01.ocn.ad.jp/61.207.38.0-61.207.41.0 p. [ネームサーバ] ns-tkb02.ocn.ad.jp/61.207.38.0-61.207.41.0 p. [ネームサーバ] pns.ocn.ad.jp/61.207.0.0-61.207.37.0 p. [ネームサーバ] pns.ocn.ad.jp/61.207.42.0-61.207.55.0 y. [通知アドレス] db-admin@ocn.ad.jp [割当年月日] 2001/05/08 [返却年月日] [最終更新] 2002/01/28 10:53:02 (JST) db-admin@ocn.ad.jp
>>943 自分で試す気がないから「どうなの?」って訊いてるんですよ。 > What You Need > A Windows 2000 system with .NET Release Version installed. とか書いてあるし、正直、めんどくさいのです。 そこまで興味があるわけでもないのです。 でもちょっとは興味あるのです。
というわけで、、、どうなの?
945 名前: なあ、そこんとこどうなってんの? 投稿日: 02/02/16 12:22
Microsoft Visual C++ .NET Standard これっで作ったソフトって配布OKなんでしょうか!?