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

2006-08-21

[] 4.1節 モジュール 10:26

特筆することもなく。

[] 4.2節 総合演習 10:26

ここだけ必要な何か

where節を使うと、ある関数の中だけで使える関数を定義できる。関数だけでなく、他にも使い道はあると思うけど。

[] 4.4節 練習問題 10:39

sort

import List

main = do cs <- getContents

putStrLn $ unlines $ sort $ lines cs

uniq

import List

main = do cs <- getContents

putStrLn $ uniq cs

uniq :: String -> String

uniq cs = unlines $ map head $ group $ lines cs

[] 5.1節 遅延評価 18:22

遅くたっていいじゃないか、Haskellだもの

Haskellは、遅延評価遅延評価は、計算を進めるためにどうしても値を知る必要があるときになって、やっと値を計算する。値を計算する前は、関数の定義に従って置き換えのみが行われる。このように、定義に従って置き換えていく方法で動作を説明するのが、置き換えモデル

Haskell遅延評価は、最外簡約(outermost reduction)とグラフ簡約(graph reduction)を組み合わせたものである。

限りなく透明なHaskell

Haskellは参照透明である。参照透明とは、同一スコープ内で、同じ表現があった場合に、全て同じ値に置き換えられるということ。いまいち名前と意味が頭の中でマッチしないが、Haskellをもっと知ればわかる日が来るのだろうか。

透明 → 純粋あのころ君は若かった → いつまでもそのままの君で → 参照透明な君で (・ω・)

[] 5.2節 遅延評価シミュレーション 18:55

実際にどのような順序で評価されるのかの例。

[] 5.3節 遅延評価のメリット・デメリット 18:55

メリットとデメリットは、表裏一体

メリット by ふつケル著者
デメリット by ふつケル著者
  • 思った順番で操作を実行するのが難しい
  • デバッグしにくい

無限リスト( ゜д゜)?

n以上の全ての数を含むリストを返すints関数

ints n = n : (ints (n+1))

最初はポカーンだったけど、よく考えれば遅延評価の最も基本的なことがわかってれば、このリストHaskellで扱えることは理解できる。例えば

ints 10

の先頭の3つの要素が読み出される場合は

ints 10

10 : (ints (10 + 1))

10 : (ints 11)

10 : 11 : (ints (11 + 1))

10 : 11 : (ints 12)

10 : 11 : 12 : (ints (12 + 1))

となって読み出した分の先の要素は、評価されないままints (12 + 1)として放置される。まったく、Haskelllazyな奴である。

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

2006-08-20

Haskell勉強します 11:46

何かと流行ってる関数プログラミングの波に乗るべく、Haskellやります。

[] 3.1節 型と値 11:55

引数をIntとStringの2つをとって、戻り値Stringの場合

関数名 :: Int -> String -> String

と宣言できる。複雑な関数の場合、宣言しないとコンパイルできないこともあるらし。

関数名 :: Int, String -> String

というように書かないのは、単に記述の簡単さのためか、あるいはSemanticな理由があるのか、わからない。勉強しているうちにわかるようになるかな。

[] 3.2節 高階関数 12:27

メタ

引数関数を取れる関数のことを、高階関数(higher order function)。

square :: Int -> Int

square n = n * n

map square [1, 2, 3] #=> [1, 4, 9]

mapが高階関数。mapには、square [1,2,3]が評価されて渡されるのではなく、squareと[1,2,3]が別個に引数として渡される。Haskellでは、関数に当てられた名前は、ある処理を行う関数の実体に束縛された変数とみなすらしい。関数ポインタっぽい認識でOK? 高階関数イメージとしては、値のみを引数にとる関数を、メタ的視点から操作できる関数、という感じだろうか。

あと、演算子の定義。等価(Haskell同値性のみ)かどうかを評価する2項演算子==も一種の関数であり、関数名は(==)となる。この段階で、ふつケルには2項演算子の定義方法は出てこないが、少し調べて自分で2項演算子を定義する方法を見つけた。

point: 2項演算子は名前が記号だけで構成される関数である

たとえば、==と等価な2項演算子<><>が次のように定義できそうな気がする。

(<><>) :: a -> a -> Bool

a <><> b = a == b

しかし、実際にはコンパイルエラーとなる。ふつケルにある(==)関数の型宣言をそのまま真似しても動かないらしい。関数の型宣言を

(<><>) :: Char -> Char -> Bool

とすることによりコンパイルできた。ちゃんと<><>でChar同値評価もできているっぽい。

エラーメッセージを手がかりに検索した結果、Eqクラスが関係するらしいということはわかったが、クラスについてはまだわからないため、このエラーについては解決を先送りにしようと思う。

expand ver. 1

ふつケルのサンプルプログラムexpandでconcatをさりげなく使う感じがとてもいい。さりげなさ重要

[] 3.3節 パターンマッチ(1) 14:42

特別なものから、お先にどうぞ

Haskellパターンマッチは、引数の種類によって処理を切り分けることである。種類とはいえ、受け入れられる型の範囲内で、ということだけど。

ふつケルでの例:

expandTab :: Char -> String

expandTab '\t' = replicate 8 ' '

expandTab c = [c]

関数の型宣言では、expandTab関数は、Char引数としてとることになっている。そこで、実際に呼び出されたときに、引数がタブ文字だったら半角スペースを8回繰り返した[Char]*1戻り値とし、そうでなければ引数の文字をリストにした[c]を戻り値とするようになっている。

つまりは、expandTabが評価されるときに、上から順に実際に渡された引数に当てはまるものがないか探してゆく。なので、(特定の文字や、特定の型など)特別なもの、カバーする範囲が狭い引数パターンが上に書かれているべきであり、最後は関数の型宣言で宣言した引数の型を全て拾う関数の定義*2があるべきである。

このパターンマッチは、Javaの既習者には、switch構文に、Rubyの既習者には、case構文に置き換えればわかりやすい。自分はRubyistなので、Rubyでのサンプル。*3

case c

when '\t'

' ' * 8

else

[c]

end

[] 3.4節 パターンマッチ(2) 15:34

mapの定義から、:演算子の使い方をみる。

:演算子は左から順に結合していく。つまり

1:2:3:4:5: #=> 1:(2:(3:(4:(5:)))) #=> [1,2,3,4,5]

である。

*1:あるいはString

*2:この例ではexpandTab c

*3Javaは半年以上書いてないので、忘れたという噂もある