練習問題

入門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 の3つの内のいずれかの値を取る,ということ。

*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.

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

Newton法で平方根をもとめる

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

ふむ,よさげ。

Haskellプログラマ進化論

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

 The Evolution of a Haskell Programmer

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

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

練習問題

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

(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 のうち,どれか1つを自分で定義し,残りの2つはその定義した関数をもとに定義しなさい。ほかの Prelude 関数を使ってもかまいません。

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

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 を使って他の2つを定義。

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)

原始的なピタゴラス数(こんどこそ)

cf. id:takatoh:20060519:pythagorean

昨日のダメダメなのを修正するぞ。
いや,実はアップしてからすぐに気が付いたんだけど時間がないから後にしよう,なんて考えたら,案の定ツッコまれた。
というかアップする前に気づけ。

というわけで,昨日のでは条件が足りなかったようだ。必要な条件は次の3つ。1つ目だけは昨日のにも入っていた。

  • m > n
  • m と n は互いに素
  • m – n が奇数

で,こうなった。

pPythagorean a = [(m*m-n*n, 2*m*n, z) | m <- [1..a], n <- [1..a], m>n, gcd m n == 1, odd (m-n), let z = m*m+n*n, z <= a]

結果。

*Main> pPythagorean 100
[(3,4,5),(5,12,13),(15,8,17),(7,24,25),(21,20,29),(9,40,41),(35,12,37),(11,60,61
),(45,28,53),(33,56,65),(13,84,85),(63,16,65),(55,48,73),(39,80,89),(77,36,85),(
65,72,97)]

これでOKかな。

練習問題

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

lattice 関数を改良し,現在の2次元格子点限定から任意のn次元格子点に対応するように Integer -> Integer -> [ [Integer] ] の型 を持つようにしなさい。また,それを利用して all_lattice も n次元格子点をすべて順番に列挙するように改良しなさい。

※注意:ヒントにtypo というか文字の取り違えがある。紛らわしい。

これは簡単。

lattice 1 n = [[n]]
lattice d n = [a:b | a <- [0..n], b <- lattice (d-1) (n-a)]

all_lattice d = concat [lattice d i | i <- [0..]]

結果。

*Main> take 50 $ all_lattice 2
[[0,0],[0,1],[1,0],[0,2],[1,1],[2,0],[0,3],[1,2],[2,1],[3,0],[0,4],[1,3],[2,2],[
3,1],[4,0],[0,5],[1,4],[2,3],[3,2],[4,1],[5,0],[0,6],[1,5],[2,4],[3,3],[4,2],[5,
1],[6,0],[0,7],[1,6],[2,5],[3,4],[4,3],[5,2],[6,1],[7,0],[0,8],[1,7],[2,6],[3,5]
,[4,4],[5,3],[6,2],[7,1],[8,0],[0,9],[1,8],[2,7],[3,6],[4,5]]
*Main> take 50 $ all_lattice 3
[[0,0,0],[0,0,1],[0,1,0],[1,0,0],[0,0,2],[0,1,1],[0,2,0],[1,0,1],[1,1,0],[2,0,0]
,[0,0,3],[0,1,2],[0,2,1],[0,3,0],[1,0,2],[1,1,1],[1,2,0],[2,0,1],[2,1,0],[3,0,0]
,[0,0,4],[0,1,3],[0,2,2],[0,3,1],[0,4,0],[1,0,3],[1,1,2],[1,2,1],[1,3,0],[2,0,2]
,[2,1,1],[2,2,0],[3,0,1],[3,1,0],[4,0,0],[0,0,5],[0,1,4],[0,2,3],[0,3,2],[0,4,1]
,[0,5,0],[1,0,4],[1,1,3],[1,2,2],[1,3,1],[1,4,0],[2,0,3],[2,1,2],[2,2,1],[2,3,0]
]

OK。…と思ったら型が合わない。

*Main> :t lattice
lattice :: (Num a, Num a1, Enum a) => a1 -> a -> [[a]]

ああ,そうか。Int でもかまわないものな。それに,引数に整数以外を与えてしまうとおかしなことになる。
これは宣言してやればいいだけだ。

lattice :: Integer -> Integer -> [[Integer]]

リスト内包表記と無限リスト

(i,j) の無限リストを得ようとして,素朴にこんな風にやっても期待通りにはいかない。

Prelude> [(i,j) | i <- [0..], j <- [0..]]
[(0,0),(0,1),(0,2),(0,3),(0,4),(0,5),(0,6),(0,7),(0,8),(0,9),(0,10),(0,11),(0,12
),(0,13),(0,14),(0,15),(0,16),(0,17),(0,18),(0,19),(0,20),(0,21),(0,22),(0,23),(
0,24),(0,25),(0,26),(0,27),(0,28),(0,29),(0,30),(0,31),(0,32),(0,33),(0,34),(0,3
5),(0,36),(0,37),(0,38),(0,39),(0,40),(0,41),(0,42),(0,43),(0,44),(0,45),(0,46),
(以下略)

いつまでたっても i が 2 にならない。i が 2 になる前に, i が 1 で j が 1.. の (i,j) をすべて列挙しようとするからだ。

こういう場合は,まず i+j == 1 であるような (i,j) を列挙し,次に i+j == 2 の (i,j) を……というふうにする。こんな感じ。

all_lattice = concat [lattice k | k <- [0..]] lattice k = [(i, k-i) | i <- [0..k]]
*Main> take 100 $ all_lattice
[(0,0),(0,1),(1,0),(0,2),(1,1),(2,0),(0,3),(1,2),(2,1),(3,0),(0,4),(1,3),(2,2),(
3,1),(4,0),(0,5),(1,4),(2,3),(3,2),(4,1),(5,0),(0,6),(1,5),(2,4),(3,3),(4,2),(5,
1),(6,0),(0,7),(1,6),(2,5),(3,4),(4,3),(5,2),(6,1),(7,0),(0,8),(1,7),(2,6),(3,5)
,(4,4),(5,3),(6,2),(7,1),(8,0),(0,9),(1,8),(2,7),(3,6),(4,5),(5,4),(6,3),(7,2),(
8,1),(9,0),(0,10),(1,9),(2,8),(3,7),(4,6),(5,5),(6,4),(7,3),(8,2),(9,1),(10,0),(
0,11),(1,10),(2,9),(3,8),(4,7),(5,6),(6,5),(7,4),(8,3),(9,2),(10,1),(11,0),(0,12
),(1,11),(2,10),(3,9),(4,8),(5,7),(6,6),(7,5),(8,4),(9,3),(10,2),(11,1),(12,0),(
0,13),(1,12),(2,11),(3,10),(4,9),(5,8),(6,7),(7,6),(8,5)]