Newton法
章1.1.3にでてくるNewton法をやってみます。
Newton法とは、数xの平方根の値の予測値yがあれば、yとx/yの平均値とるという計算でさらにより路側値が得られるというものらしい。
とりあえず、本どおりに実装。
goodEnough guess x = (abs ( x - (guess * guess) )) < 0.001 improve guess x = (( x / guess ) + guess) / 2 sqrtIter guess x |goodEnough guess x = guess |otherwise = sqrtIter ( improve guess x ) x sqrt' x = sqrtIter 1 x *Main> sqrt' 3 1.7321428571428572 *Main> sqrt' 4 2.0000000929222947
このやりかたでは、非常に大きい値や小さいあたいではうまくいかないらしいので、guessの変化に注目し、変化が予測値にくらべ非常に小さくなったときに停止するように作ろうというのが問題1.7。自分なりの実装。
sqrt' x = sqrtIter 1 x goodEnough17 guess x = (abs ( 1( guess - ( improve guess x ))) < 0.0001 sqrtIter17 guess x |goodEnough17 guess x = guess |otherwise = sqrtIter17 ( improve guess x ) x sqrt17 x = sqrtIter17 1.0 x
で、確認のためにnobsunさんのschemeでの解答を見てみると、ちょっと違う。実際に動かしてみると
*Main> sqrt17 4 2.0000000929222947 *Main> sqrt17 1.0E-6 1.0338412392442034e-3 *Main> sqrt17 1.0E29 3.162277660168379e14
大きい値(1.0E29)ならいっしょだが、小さい値(1.0E-6)だとダメみたい。そうか。このやりかただと、小さい値にたいして、差が小さい値とはいえないのね。なので、実装を直してみる。
goodEnough17 guess x = (abs ( 1 -( guess / ( improve guess x )))) < 0.0001 sqrtIter17 guess x |goodEnough17 guess x = guess |otherwise = sqrtIter17 ( improve guess x ) x sqrt17 x = sqrtIter17 1.0 x *Main> sqrt17 1.0E-6 1.0000001533016628e-3
これで大丈夫。問題1.8は、立方根版の実装。近似の式は、
x/y^2+2y -------- 3
となるらしい。実装は、
improve18 guess x = ( ( x / (guess * guess) ) + (2 * guess)) / 3 goodEnough18 guess x = (abs ( 1-(guess / ( improve18 guess x )))) < 0.0001 qubicroot guess x | goodEnough18 guess x = guess | otherwise = qubicroot ( improve18 guess x ) x qubic x = qubicroot 1.0 x *Main> qubic 2 1.259933493449977 *Main> qubic 8 2.000004911675504
nobsunさんの結果とあわないなぁ。近似の式の書き方がちがうからか。自分の解釈ならこういう式になったんだけど。naoya_tさんの解答も式が違うし。どれが正しいんだろう?
SICPの問題解いてくよ-問題1.3
次は、問題1.3。3つの引数をとり、そのうち大きい2つの引数の2乗を足したもの返す関数を定義するという問題。
とりあえず、addpow :: (Num a) => a -> a -> aという、ふたつの引数の2乗を足す関数を定義。
addpow x y = (x*x) + (y*y)
あとは、if文で大小関係をもとめて、addpowにわたしてあげる。
twomax x y z = if ( x > y ) then if ( y < z ) then addpow x z else addpow x y else if ( z < x ) then addpow x y else addpow z y
また、長かったのでblogに書く際に改行いれました。で、実行。
haskell$ cat sicp1_3.hs addpow x y = (x*x) + (y*y) twomax x y z = if ( x > y ) then if ( y < z ) then addpow x z else addpow x y else if ( z < x ) then addpow x y else addpow z y Hugs.Base> :l sicp1_3.hs Main> twomax 2 3 4 25 Main> twomax 4 3 2 25 Main> twomax 4 2 3 25 Main> twomax 4 2 5 41 Main> twomax 4 2 4 32
SICPの問題解いてくよ
またまたまたおひさしぶりです。Haskoです。
今日から、SICPこと計算機プログラムの構造と解釈の問題をHaskellで解いていこうかと思います。もともと、このネタは、日本のHaskellerなら誰もが知っているだろうnobsunさんこと山下伸夫さんがやられていたのを自分の勉強のために真似をしてみようと思います。
まずは、練習問題1.2から。
問題は、
4 5 + 4 + ( 2 - ( 3 - ( 6 + - ))) 5
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
- -
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
を前置記法に直せという問題。
schemeの場合、+などは、そのまま前置記法でつかえるので、2 + 7は、(+ 2 7)となります。
Haskellの場合は、(+)と括弧で囲まなくてはなりません。なので、
Prelude> (/)((+) 5 ( (+) 4 ( (-) 2 ( (-) 3 ( (+) 6 ( (/) 4 5)))))) ( (*) 3 ( (*) ( (-) 6 2) ((-) 2 7))) -0.24666666666666667
あまりにも長くなりすぎたので、改行していますが、ほんとはひとつづきです。
と、このように括弧だらけになります。
ファイルを読み込む
少し御無沙汰でした。
今回はファイルを呼んで表示してみようと思います。
他の言語では、基本的な機能で簡単に実現できますが、Haskellではこのような入出力などは、副作用のあつかいとなりちょっと面倒です。
入出力など順序が重要になるような処理では、モナドというものをつかって関数の順序を記述します。
import System import System.IO main = do fname <- getArgs -- 引数をfnameに h1 <- openFile (head fname) ReadMode --ファイルを開く list <- hGetContents h1 --ファイルを全て読み込む putStrLn list --listを表示 hClose h1 --ファイルを閉じる
main関数を定義しているdoを含めた書き方がモナドをしている部分です。ちなみにhaskellでは「--」から行末まではコメントになります
今日も問題を
今日も問題をといてみます。
今日の問題はこちら
ちょっと考えすぎて時間がなくなってしまったので、課題1、2それぞれ片方のみやってみます。もう一方のやりかたは別の日にでも。
ソースはこちら。
hasko$ cat kougaku2.hs
maxOccursList l = ( maxis l , howMany (maxis l) l )
where maxis l = foldr1 max l
howMany m l = length [ n | n <- l, m == n]
myunique =
myunique (x:xs)
| elem x xs == True = myunique (filter (\n -> x /= n) xs)
| otherwise = x : myunique xs
myuniqueの中で、filterが返すリストに対して再帰をさせるのを忘れはまってしまいました。
ちなみに、filterは、関数とリストをとり、リスト中の要素が関数で真になるもののみをとりだしリストをつくる、文字どおりのフィルターです。elemは、最初の引数のものが、第二引数のリストに存在するかを調べる関数です。
それでは、実行結果。
Main> maxOccursList [3,2,5,2,4,5,2] (5,2) Main> myunique [3,2,5,2,4,5,2] [3,4]
maxOccursListはすんなりできたけど、uniqueの方は、ちょっとてこずってしまいました。まだまだ勉強不足と慣れが足りないようです。
遅延評価
Haskellでは、必要なときに、必要なだけし評価しないという、なまけもの遅延評価があります。
きのうn9dさんがコメントしてくださったように、遅延評価のおかげで、無限リストも作れちゃいます
[1..] Prelude> take 5 [1..] [1,2,3,4,5]
takeは、ひとつめの引数ぶん、ふたつ目の引数のリストから要素をとりだします。遅延評価が存在しない言語では、ふたつ目の引数である無限リストをつくりだしてからtakeを実行しますが、Haskellでは、遅延評価のおかげで、takeに必要なぶんだけの無限リストがつくられます。
必要なときに、必要なときだけ。