カテゴリー: Haskell

データ構成子が重複すると

エラーになる。たとえば

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.

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

代数的データ型の宣言

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]

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) 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)

練習問題

「入門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]]

原始的なピタゴラス数（こんどこそ）

cf. id:takatoh:20060519:pythagorean

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

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

  • 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かな。

原始的なピタゴラス数

互いに素である３数からなるピタゴラス数を原始的な（または素な）ピタゴラス数というらしい。

　cf. http://ja.wikipedia.org/wiki/%E3%83%94%E3%82%BF%E3%82%B4%E3%83%A9%E3%82%B9%E6%95%B0

これには公式があって，内包表記で次のように書ける。公式について詳しくは上のリンク先を見よ。
頭の p は primitive の p。それから let ～ も使ってみた。

pPythagorean a = [(m*m-n*n, 2*m*n, z) | m <- [1..a], n <- [1..a], m>n, let z = m*m+n*n, z <= a]
*Main> pPythagorean 100
[(3,4,5),(8,6,10),(5,12,13),(15,8,17),(12,16,20),(7,24,25),(24,10,26),(21,20,29)
,(16,30,34),(9,40,41),(35,12,37),(32,24,40),(27,36,45),(20,48,52),(11,60,61),(48
,14,50),(45,28,53),(40,42,58),(33,56,65),(24,70,74),(13,84,85),(63,16,65),(60,32
,68),(55,48,73),(48,64,80),(39,80,89),(28,96,100),(80,18,82),(77,36,85),(72,54,9
0),(65,72,97)]

z <= a を let z = ～ よりも前に書いてはいけない。Not in scope: `z’ だと怒られる。

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

(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)]