月: 2006年5月

cf. id:rubyco:20060531:pascal
cf. id:epics:20060530:1149000099

Ruby の Enumerable#inject は Haskell では foldl だ。
というわけで早速やってみよう。ただし，無限リストを扱えるように foldr をつかう。早くしないと 結城さんに先を越されちゃうぞ。

pascalTriangle = foldr (\n i -> [pascal n] ++ i) [[]] [1..]
  where pascal x | x == 1 = [1]
                 | otherwise = (\xs -> zipWith (+) (0:xs) (xs ++ [0])) (pascal (x-1))

結果。

*Main> putStr $ unlines $ map show $ take 10 $ pascalTriangle
[1]
[1,1]
[1,2,1]
[1,3,3,1]
[1,4,6,4,1]
[1,5,10,10,5,1]
[1,6,15,20,15,6,1]
[1,7,21,35,35,21,7,1]
[1,8,28,56,70,56,28,8,1]
[1,9,36,84,126,126,84,36,9,1]

あー，でも，n 列目を作るのに再帰してるのが無駄っぽいなぁ。

データ構成子の引数は具体的な型じゃなくて型変数でもかまわない。

data Cream a b c = Eric a | Jack b | Ginger c deriving (Show)

*Main> [Eric 10, Ginger 'g', Jack 2.4]
[Eric 10,Ginger 'g',Jack 2.4]
*Main> [Eric 1.2, Ginger 3, Jack "2.4"]
[Eric 1.2,Ginger 3,Jack "2.4"]
*Main> [Eric 1.2, Ginger 3.1, Jack 2.4]
[Eric 1.2,Ginger 3.1,Jack 2.4]

引数にどんな型がきてもOK。
ただし，型変数は = の左側にも書いておなかなければいけない。↓の例では c が無いのでエラーになる。

data Cream a b = Eric a | Jack b | Ginger c deriving (Show)

*Main> :l datatype.hs
Compiling Main             ( datatype.hs, interpreted )

datatype.hs:1:42: Not in scope: type variable `c'
Failed, modules loaded: none.

新しく宣言した型を何らかの型クラスのインスタンスとして宣言するには，instance 宣言を使う。が，いくつかの型クラスに関してはもっと簡単な方法がある。data 宣言と一緒に deriving 修飾子を使うのがそれ。
次のようにすると，Cream 型を宣言すると同時に，Eq，Show，Read クラスのインスタンスとして宣言できる。

data Cream = Eric | Jack | Ginger deriving (Eq, Show, Read)

*Main> Eric == Eric
True
*Main> Eric /= Jack
True
*Main> show Ginger
"Ginger"

deriving で指定できるのは，Eq，Ord，Enum，Bounded，Show，Read の６つだけ。この６つは頻繁に使われるからこういう簡便な方法が用意されているってことのようだ。とくに ghci で表示させるには Show クラスのインスタンスである必要があるので，黙って指定しておくべきだろう。

で，これらのクラスにどんなメソッドがあるのか，調べてみた。

• Eq クラス
  • (==) :: a -> a -> Bool
  • (/=) :: a -> a -> Bool
• Ord クラス
  • compare :: a -> a -> Ordering
  • (<) :: a -> a -> Bool
  • (<=) :: a -> a -> Bool
  • (>) :: a -> a -> Bool
  • (>=) :: a -> a -> Bool
  • max :: a -> a -> a
  • min :: a -> a -> a
• Enum クラス
  • succ :: a -> a
  • pred :: a -> a
  • toEnum :: Int -> a
  • fromEnum :: a -> Int
  • enumFrom :: a -> [a]
  • enumFromThen :: a -> a -> [a]
  • enumFromTo :: a -> a -> [a]
  • enumFromThenTo :: a -> a -> a -> [a]
• Bounded クラス
  • minBound :: a
  • maxBound :: a
• Show クラス
  • showsPrec :: Int -> a -> Shows
  • show :: a -> String
  • showList :: [a] -> Shows
• Read クラス
  • readsPrec :: Int -> ReadS a
  • readList :: ReadS [a]

いっぱいあるな，とくに Ord クラスと Enum クラスが。
ところで上のリストは Hoogle で調べたんだけど，Read クラスのメソッドに read がない。と思ったら別のところに書いてあった。これってつまり，read は Read クラスのメソッドじゃないってことか？

「入門Haskell―はじめて学ぶ関数型言語」　p.101 より。

ところで，あるリストに複数の型を含めたい場合にはどうしたらいいか，という話ですが，そういう場合にも data は便利です。たとえば次のように
data MyType = I Int | F Float | C Char
ここでたとえば [I 10, F 10, C ‘a’] のようなリストがあるとします。

(1)[MyType] から C 要素だけ取り出す関数 filterC を書きなさい。

これは C 要素であるか否かを判定する関数を作って filter すればいいんだろう。判定には case を使って場合分けすればいい。

filterC :: [MyType] -> [MyType]
filterC = filter isC
  where isC x = case x of
                I a -> False
                F a -> False
                C a -> True

結果。

*Main> filterC [I 10, F 10, C 'a']
[C 'a']

OK。

(2) [MyType] から I 要素だけを取り出してその合計を計算する sumI を書きなさい。

sumI :: [MyType] -> Int
sumI = sum . map pickI
  where pickI x = case x of
                  I a -> a
                  otherwise -> 0

*Main> sumI [I 10, F 10, C 'a']
10

なるほど，otherwise も使えるんだな。

(3) [MyType] から，I 要素はそのまま，F 要素は整数にし（truncate 関数が使えます），C 要素はその文字の文字コードを計算し（ Data.Char をインポートすれば ord 関数が計算してくれます），その合計を計算する mySum 関数を書きなさい。

import Data.Char
mySum :: [MyType] -> Int
mySum = sum . map toInt
  where toInt x = case x of
                  I a -> a
                  F a -> truncate a
                  C a -> ord a

*Main> mySum [I 10, F 10, C 'a']
117

‘a’ のコードは 97 だから全部足すと 117。OK。

ところで，GHCi で表示できるように，MyType の宣言は次のようにしている。

data MyType = I Int | F Float | C Char deriving (Show)

data宣言を使って，新しい型を宣言することができる。こんな感じだ。

data Cream = Eric | Jack | Ginger

data に続いて型のなまえ，= の右側には取りうる値を | で区切って列挙する。値は大文字で始まる必要があり，データ構成子（data constructor）という。上の例では，Cream 型は Eric，Jack，Ginger の３つの内のいずれかの値を取る，ということ。

*Main> :t Eric
Eric :: Cream

値は他の型を引数に取ることができる。引数を取る/取らないは混ぜてもいい。

data Cream = Eric Int | Jack Int | Ginger

*Main> :t Eric 10
Eric 10 :: Cream

引数を取らないデータ構成子に引数を与えるとエラーになる。

<interactive>:1:0:
    Couldn't match `Cream' against `t -> t1'
      Expected type: Cream
      Inferred type: t -> t1
    Probable cause: `Ginger' is applied to too many arguments in the call
        (Ginger 10)

逆に引数を取るデータ構成子に引数を与えないと

*Main> :t Jack
Jack :: Int -> Cream

……えーと，これは関数と解釈していいのかな。

*Main> :t Jack (2*2)
Jack (2*2) :: Cream

追記：
上の Jack は関数と考えて良さそうだ。

*Main> :t map Jack
map Jack :: [Int] -> [Cream]

エラーになる。たとえば

data Cream = Eric Int | Jack Int | Ginger

data Guiterist = Eric | Bill | Frank | Jeff

これを ghci に読み込むと

*Main> :l datatype.hs
Compiling Main             ( datatype.hs, interpreted )

datatype.hs:3:17:
    Multiple declarations of `Main.Eric'
    Declared at: datatype.hs:1:13
                 datatype.hs:3:17
Failed, modules loaded: none.

と怒られる。モジュールを分けるとか，そういうことで回避できるんだろうけど。

cf. http://hpcgi2.nifty.com/1to100pen/wiki/wiki.cgi?p=%CB%E8%C6%FCHaskell 2006-05-21

最近流行りの SICP の 1.1.7 Newton法からお題を拝借。

おわっと，流行だったのか。もしかして乗り遅れた？

上の [1..100]>>=pen さんのもそうだし，hasko さんとこ（id:hasko:20060520:1148133213）のコメントにもあるように，先に予測値のリストを作ってしまうことにしよう。

guess x = iterate (\g -> (g + x/g) / 2.0) 1.0

goodEnough eps old new = abs (1.0 - old/new) < eps

find2 f i (x:xs) | f i x = x
                 | otherwise = find2 f x xs

squareRoot x = find2 (goodEnough 0.0001) x (guess x) 

guess で予測値のリストを作って，goodEnough で判定。判定は新旧予測値の比を利用し，引数で指定できるようにした。 で，あとは適当な値をリストから探すだけなんだけど，ちょうどいい関数が見あたらなかったので find2 を定義してみた。 結果。

*Main> squareRoot 4
2.000000000000002
*Main> squareRoot 1.0e-6
1.0000000000000117e-3
*Main> squareRoot 1.0e29
3.162277660171076e14
*Main> (squareRoot 1.0e-6) ^ 2
1.0000000000000235e-6
*Main> (squareRoot 1.0e29) ^ 2
1.0000000000017057e29

ふむ，よさげ。

• http://www.city5.org/rhg_200605/index.html

「入門Haskell―はじめて学ぶ関数型言語」の著者・向井さんによるRHG読書会での資料。

えーと，どこで見つけたかわかんなくなっちゃったけど。

　The Evolution of a Haskell Programmer

階乗を求める fac 関数にこんなに書き方があるなんて。

俺はさしずめ Another senior Haskell programmer あたりかな。まだまだ先は遠いな。Interpretive Haskell programmer とか Origamist Haskell programmer とかなんて，何をやってるのかさっぱりだ。
でも最後の Tenured professor は可笑しい。

「入門Haskell―はじめて学ぶ関数型言語」　p.86 より。昨日より１ページ戻ったけど。

(1) repeat，cycle，iterate をそれぞれ自分で定義しなさい。

これは簡単。再帰を使ってこうだ。

myRepeat a = a:map id (myRepeat a)

myCycle a = a ++ myCycle a

myIterate f a = a:map f (myIterate f a)

結果は省略。

(2) repeat，cycle，iterate のうち，どれか１つを自分で定義し，残りの２つはその定義した関数をもとに定義しなさい。ほかの Prelude 関数を使ってもかまいません。

こっちはちょっと難しい。とくに iterate でかなりつまった。
まずは repeat を使って他の２つを定義。

myCycle2 = (foldr (++) []) . myRepeat

myIterate2 f a = map (\x -> x a) (rep f)
  where rep = (scanl (.) id) . myRepeat

結果。

*Main> take 50 $ myCycle "abc"
"abcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcab"
*Main> take 50 $ myIterate2 (+1) 1
[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,3
0,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50]

よし，うまくいってるみたいだ。myCycle2 はこないだ覚えた foldr で無限リスト。
myIterate2 のほうは，myRepeat で関数 f のリストを作っておいて，scanl1 で合成している。これで [id, f, (f . f), (f . f . f), …] というふうなリストができる。かなりトリッキーな気がするけど，いいんだろうか。ま，結果はうまくいってるみたいだけど。

myCycle を使って他の２つを定義。

myRepeat3 a = myCycle [a]

myIterate3 f a = map (\x -> x a) (cyc f)
  where cyc g = scanl (.) id (myCycle [g])

myRepeat3 は大した工夫ではなし，それができればあとは myIterate3 は上の myIterate2 とおなじ。

*Main> take 50 $ myRepeat3 'a'
"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"
*Main> take 50 $ myIterate3 (+1) 1
[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,3
0,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50]

最後。myIterate を使って。

myRepeat4 = myIterate id

myCycle4 = (foldr (++) []) . (myIterate id)

*Main> take 50 $ myRepeat4 'a'
"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"
*Main> take 50 $ myCycle4 "abc"
"abcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcab"

追記：
myCycle2 と myCycle4 は foldr じゃなくて concat を使った方が簡単だな。

myCycle2 = concat . myRepeat

myCycle4 = concat . (myIterate id)