hayaのHaskell日記

2006-08-22

[] 6.2節 真偽値 18:15

Bool型の値。&&演算子と、||演算子、not演算子さえ知っておけば後は問題ないでしょ。

[] 6.3節 数値 18:15

整数

  • Int型 ... ふつうは32bit signed な整数値。重要なことは、上限があるということ。
  • Integer型 ... 上限がない整数値。

IntとIntegerはHaskellが自動で判断して使い分けるらしい。Integerを使うことを明示したいときは、

12 :: Integer

と::構文を使ってやる。

浮動小数点数

  • Float型 ... 単精度
  • Double型 ... 倍精度

こちらもHaskell勝手に判断して使い分けるらしいので、必要に応じて::構文で明示する。

変換

  • toInteger x ... x ( :: Int)をIntegerに変換
  • fromInteger x ... x (:: Integer)を文脈に合った数値型に変換
  • fromIntegral x ... x (:: Integer or Int)を文脈に合った数値型に変換
  • ceiling x ... x (:: Float or Double)を、xを下回らない整数に変換(切り上げ)
  • floor x ... x (:: Float or Double)を、xを上回らない整数に変換(切り捨て)
  • trancate x ... x(:: Float or Double)を、xと0の間でもっともxに近い整数に変換
  • round x ... x(:: Float or Double)を、xに最も近い整数に変換

他にも数があるもんね

[] 6.4節 CharString 18:32

CharStringおいしい関係

文字リテラルリストが文字列。以上。

特殊文字

大体ふつうのプログラミング言語といっしょ。

ほげほげ

ふがふが

[] 6.5節 タプル 18:32

タプル、それは愛

タプルとは、複数の値の組。リストは要素に同じ型のものしか許さない厳格さがあるが、タプルはどんな型でも寛容に受け入れる深い慈愛に満ちた存在である。しかし、1要素のタプルは存在することはゆるされない。これは、人は一人では生きていけないという教訓を暗示しているものである。

まじめにリテラルとか

タプルのリテラルは、()で要素全体を囲み、複数の要素を,(カンマ)で区切って書く。

ユニット、それは真実

人類が生まれる遥か昔、宇宙は無であった。しかし、無でありながらも宇宙は愛に満たされていた。そう、タプルである。この無でありながらも愛に満たされた状態を、人々はユニットと呼んだ。転じて、無、すなわち何も値がない状態も、ユニットと呼ばれるようになった。

まじめにユニットリテラルとか

()

タプルに関係する関数

[] 6.6節 リスト 18:51

リストの真の姿

[1,2,3]

のような、リストリテラルを使った表記は略記法であり、真の姿は:演算子を使った

1 : 2 : 3 : []

らしい。

数列表記

[1..7] #=> [1, 2, 3, 4, 5, 6, 7]
[1..] #=> [1, 2, 3, 4, ......]
[1, 3..9] #=> [1, 3, 5, 7, 9]
[1, 3...] #=> [1, 3, 5, 7, ......]

これは便利かもしれない。

他にもいろいろ試してみる。

[1.5, 2.5..] #=> [1.5, 2.5, 3.5, 4.5 ......]
[1.1..] #=> [1.1, 2.1, 3.1, 4.1, .....]
[1, 3..10] #=> [1, 3, 5, 7, 9]
[0.0, 0.4..1.0] #=> [0.0, 0.4, 0.8]
[0.0, 0.39..1.0] #=> [0.0, 0.39, 0.78, 1.17]

数列記法の[x, y..z]で、x + (y - x) * n がちょうどzにならない場合は、どうやら x + (y - x) * n で最もzに値が近いものに丸められているみたい。まあ、浮動小数点なんかは、代数的には一致するけど、実際のCPU上での演算ではzと一致しないこともよくあるしね。ちゃんと確認してないけど、[0.0, 0.4..1.0]なんかでわかるように、最後の要素の候補として0.8と1.2がある場合は、小さいほうの0.8で打ち切られるっぽい。

[] 6.7節 実習:cat -n コマンド 19:11

本を伏せて書くのである


main = do cs <- getContents
          putStrLn $ attrLineNum cs

attrLineNum :: String -> String
attrLineNum cs = unlines $ map layoutLineTuple $ zipLines $ lines cs

zipLines :: [String] -> [(Int, String)]
zipLines lines = zip [1..] lines

layoutLineTuple :: (Int, String) -> String
layoutLineTuple (n, line) = replicate (6 - length (show n)) ' ' ++ (show n) ++ " " ++ line

show nが2回出てきているのはDRYでなくあまり美しくない。ちょうどふつケルのrjustを簡約した形になった。

[] 6.8節 練習問題 20:24

次のソースコードはそれぞれどのように解析されるか。括弧を使って答えよ。

Q1:
resolve f (x:xs) = textify x ++ resolve f xs
Q2:
getenv key env = fromMaybe &quot;&quot; $ lookup key env
Q3:
readTemplate id = readFile $ prefix repo ++ "/" ++ id

さて、解いてみる

あたりの決まりに注意すればできるかな

A1
resolve f (x:xs) = (textify x) ++ (resolve f xs)
A2
getenv key env = (fromMaybe &quot;&quot; (lookup key env))
A3
readTemplate id = readFile ((prefix repo) ++ "/" ++ id)
Q3を間違えた

readTemplate id = readFile ((prefix repo) ++ "/" ++ id)

readTemplate id = readFile ((prefix repo) ++ ("/" ++ id))

著者の青木さんは結合の順番を間違えていたっぽい。

...

(゜д゜)

つい先日買ったばかりなのに第一刷!?

富山で買わずにAmazonで買えばよかったorz

[] Tea break: Haskellフィボナッチ数列 00:58

定番の話題。

愚直に実装

fib :: Integer -> Integer
fib n
  | n < 0     = 0
  | n == 1    = 1
  | n == 2    = 1
  | otherwise = fib (n-1) + fib (n-2)

これだと、n < 100 で既に爆発する。

何が問題か

フィボナッチ数列の定義より、n番目の数値を得るためには、n-1番目とn-2番目の数を足す。n-1番目の数値を得るためにはn-2番目とn-3番目の数値を足す・・・と繰り返していくと、最終的に 1 + 1 の繰り返しまで還元される。ちなみに、50番目のフィボナッチ数は12586269025であるから、fib 50 を実行すると、+が12586269024個くらい並んだ式をHaskellは一旦生成し、それを計算していくのである。爆発している。

爆発シミュレーション

fib 6 = 8 を展開してみる。簡単のために、一部遅延評価とは異なる順序で簡約する。

fib 6
=> fib 5 + fib 4
=> (fib 4 + fib 3) + (fib 3 + fib 2)
=> ((fib 3 + fib 2) + (fib 2 + fib 1)) + ((fib 2 + fib 1) + fib 2)
=> (((fib 2 + fib 1) + fib 2) + (fib 2 + fib 1)) + ((fib 2 + fib 1) + fib 2)

fib 1 と fib 2 は共に1に置き換えられるから、あとは足し算をどんどんと実行していくだけである。最後の行には7個の+演算子がある。fibの現在の定義では、fib n を計算するときに、(fib n) - 1個の+演算子が並ぶことになる。

爆発する理由: フィボナッチ数列は指数関数的に増加する

フィボナッチ数列F_nの一般式は

F_n = \frac{1}{\sqrt{5}}\left{ \left(\frac{1+\sqrt{5}}{2}\right)^n - \left(\frac{1-\sqrt{5}}{2}\right)^n \right}

であるから、フィボナッチ数はnに関して指数関数的に増加する。

つまり、計算量が指数関数的に増加するため、すぐに爆発してしまう。O\left(\left(\frac{1+\sqrt{5}}{2}\right)^n\right)アルゴリズムなのである。

より速いアルゴリズムを求めて

素直にググる

そして発見。http://kerolin.jspeed.jp/Computer/Linux/fib060810.html

2つ覚えれば、全てが解決する

普通人間がフィボナッチ数を計算するときはどうするだろうか。

1,1
=> 1,1, 1+1
=> 1,1,2, 1+2
=> 1,1,2,3, 2+3
=> 1,1,2,3,5, 3+5

のように計算していくが、注目しているのは常に計算しているフィボナッチ数の2つ前までである。2つより前の数は、忘れてしまってもフィボナッチ数は計算することができる。

前述の愚直な方法は、計算しているフィボナッチ数の前の2つの数字を覚えていなかった。何も覚えていなかったから、1 + 1になるまで遡って計算していたので、とんでもないことになっていたのである。

計算しては覚える、計算しては覚える、を繰り返していけば、n番目のフィボナッチ数を計算するときの計算量はO(n)になるのである。

じゃあ、実装を見てみるよ

http://kerolin.jspeed.jp/Computer/Linux/fib060810.html

に話を戻そう。

fibStep :: (Int, Int) -> (Int, Int)
fibStep (u, v) = (v, u+v)

fibPair :: Int -> (Int, Int)
fibPair n
  | n == 0    = (0, 1)
  | otherwise = fibStep (fibPair (n-1))

fastFib :: Int -> Int
fastFib = fst . fibPair

ついでに、とてもすばらしい書き下しがあるので引用させていただく。

fastFib 5
=> fst (fibPair 5)
=> fst (fibStep (fibPair 4))
=> fst (fibStep fibStep (fibPair 3))
=> fst (fibStep fibStep fibStep (fibPair 2))
=> fst (fibStep fibStep fibStep fibStep (fibPair 1))
=> fst (fibStep fibStep fibStep fibStep fibStep (fibPair 0))
=> fst (fibStep fibStep fibStep fibStep fibStep (0, 1))
=> fst (fibStep fibStep fibStep fibStep (1, 1))
=> fst (fibStep fibStep fibStep (1, 2))
=> fst (fibStep fibStep (2, 3))
=> fst (fibStep (3, 5))
=> fst (5, 7)
=> 5

2つの値を、タプルで覚える

フィボナッチ数列の注目している(覚えている)2つの数を、()で囲んで見る。順番に計算して、6番目のフィボナッチ数を求めてみよう。

(1,1),2,3,5,8,13,21,34,55, ....

この2つから、1+1でもう1つ先のフィボナッチ数2がわかる。その時点で、小さいほうのフィボナッチ数1はもう計算には不要になる。結果、注目しているフィボナッチ数は次のようになる。

1,(1,2),3,5,8,13,21,34,55, ....

同様に、1つ先のフィボナッチ数を計算して、不要になったフィボナッチ数を忘れると

1,1,(2,3),5,8,13,21,34,55, ....

繰り返し...

1,1,2,(3,5),8,13,21,34,55, ....

繰り返し...

1,1,2,3,(5,8),13,21,34,55, ....

やった、6番目のフィボナッチ数の値が得られた。

さて、ここで括弧で囲んだ部分を、タプルとみなしてみよう。すると、タプルの値の変化は

(1,1) => (1,2) => (2,3) => (3,5) => (5,8)

一回の => のタプルの値の変化を、Haskellで表現できるとうれしい。それに対応する関数が、fibStepである。

fibStep :: (Int, Int) -> (Int, Int)
fibStep (u, v) = (v, u+v)

fibStep (1,1) #=> (1,2)
fibStep (1,2) #=> (2,3)
fibStep (2,3) #=> (3,5)

(3,5) 
<= fibStep (2,3)
<= fibStep fibStep (1,2)
<= fibStep fibStep fibStep (1,1)
<= fibStep fibStep fibStep fibStep (0,1)

つまり、n番目のフィボナッチ数を得るには、(0,1)にn回fibStepを適用して、その結果得られたタプルの最初の値を取り出してやればいい。

この方法が愚直な方法と違って優れていることは、計算量がO(n)ですんでしまうことである。指数関数的に増加する計算時間を、多項式時間にできた(しかも1次の)ことにより、爆発的に計算が速く終了する。

ReynaldoReynaldo2007/05/11 17:13http://cb7a416616f2eb5dba240cf5837ca9fd-t.eslyki.info <a href="http://cb7a416616f2eb5dba240cf5837ca9fd-h.eslyki.info">cb7a416616f2eb5dba240cf5837ca9fd</a> [url]http://cb7a416616f2eb5dba240cf5837ca9fd-b1.eslyki.info[/url] [url=http://cb7a416616f2eb5dba240cf5837ca9fd-b2.eslyki.info]cb7a416616f2eb5dba240cf5837ca9fd[/url] [u]http://cb7a416616f2eb5dba240cf5837ca9fd-b3.eslyki.info[/u] 1918e506ec14eb4ca3235afa2674a1a4

トラックバック - http://haskell.g.hatena.ne.jp/harg/20060822