Software Engineering Lecture s02-1
Menu Menu
Haskell でのデータ構造
λ式ですべてを完結させることもできるが、あまり現代的ではない。Haskell では、data 構文でデータ構造を定義することができる。
Prelude> data Product a b = P a b
Prelude> let p = P 1 2
product.hs
これは a と b という型を持つ二つのデータを持つデータ構造を定義している。a b は型変数と呼ばれる。Haskell では型変数は小文字でなければならない。小文字一文字を使うのが慣例になっている。
P はデータ構造の constructor である。 P は以下のような型を持っている。
Prelude> :t P
P :: a -> b -> Product a b
a と b の型を持つ何かを二つ受けとって、Product を返す。Product は直積というつもりの名前である。
直積の中身を取り出すには、accessor という関数を用意する。
Prelude> let first ( P a b ) = a
Prelude> let second ( P a b ) = b
data の P は入力のパターンとして使えるようになっている。
型を調べると、
Prelude> :t first
first :: Product t t1 -> t
Prelude> :t second
second :: Product t t1 -> t1
となっている。
Prelude> let p = P 5 7
Prelude> first p
5
Prelude> second p
7
Prelude> let p2 = P ( P 1 2 ) 3
Prelude> first ( first p2 )
1
といように使用する。
p はそのままでは表示できないが、
Product a b = P a b
deriving (Show)
とすると表示できるようになる。
*Main> let p = P 1 2
*Main> p
P 1 2
*Main>
Haskell 内蔵の直積
let p = (1,2)
fst p
snd p
が用意されている。
しかし、
let t = (1,2,3)
t には、fst は使えない。型が異なるからである。
fst に相当するものは自分で書く必要がある。
型class
Haskell のclassはオブジェクト指向言語のclassとは異なり、Java の Interface のようなものになっている。class は、そのclassが持つ関数の型を表す。
class Say a where
say :: a -> String
class を実装するには、この関数を定義してやれば追い。
data Mammal s = Cat { name :: String, color :: s }
| Dog { name :: String, color :: s }
deriving (Show)
instance Say (Mammal s) where
say (Cat n c) = "myaou"
say (Dog n c) = "bau"
Sum type の場合はすべての場合に対して定義する必要がある。{ name :: String, color :: s } という構文では、直積の要素に名前を付けている。
*Main> let c = Cat "pochi" "red"
*Main> c
Cat {name = "pochi", color = "red"}
name や color は関数として定義される。
name c
color c
関数の組み合わせ
List の tail を
let t2 = tail tailとして、tail を二回働かせることはできるだろうか。これは、エラーになる。
<interactive>:123:12:
Couldn't match expected type `[a0]' with actual type `[a1] -> [a1]'
In the first argument of `t', namely `t'
t をちゃんと関数として呼び出すには、
t (t x)
という形にする必要がある。
let t2 = \x -> t (t x)とすれば良い。これで、
t2 "abcde"を実行すると、"cde" が返るはずである。
さらに、t を引数にすると、
let x2 = \t x -> t (t x)1引数関数を受け取って二回関数適用(apply)する関数ができる。
x2 tail "abcde"を試してみよう。これは、
tail (tail "abcde")と同じ。
let x2 f = f f ではダメである。何故か?
関数を二つ取って、それを順番に適用する関数を作ろう。
let comp x y = \z -> x (y z)あるいは、
let comp x y z = x (y z)これは、(.) として、infixとして定義されている。(.) と comp が同じ型を持つことを確認せよ。
let apply f x = f xとすると関数の適用を関数にすることができる。これは、($)として infix で定義されている。
括弧の数が減る利点がある。
遅延評価
Prelude> let c = getChar
c :: IO Char
Prelude> c
g'g'
it :: Char
Prelude> let b = c
b :: IO Char
Prelude> b
k'k'
it :: Char
getChar を代入した時点では、文字入力は要求されない。
c を表示しようとした時点で要求される。
再帰的な処理
変数の値を関数中で変えることができないので、 while 文などは、再帰で置き換える。例えば、Ruby の fibonacci
fib n # write Fibonacci series up to n
result = []
a, b = 0, 1
while b < n do
result.push(b)
a, b = b, a+b
end
return result
end
は、以下のようになる。 ループで使う変数をすべて引数にしてしまうのが簡単。
fib n = fib1 0 1 n
fib1 a b n =
if b < n then
(b : fib1 b (a + b) n)
else []
:l fib.hs
*Main> fib 10
[1,1,2,3,5,8]
fact.hs
逆順のリストを作る
こういう方法でリストを作ると、一番先に入れたものが先頭に来る。逆順のリストを再帰で作るには、最初に [] を引数で渡してしまうと良い。
rev x = rev1 x []
rev1 [] x = x
rev1 (x:xs) y = rev1 xs (x:y)
異なる決まった値の入力を複数の関数で選択するのは、パターン、あるいはルールと呼ばれる。ここではリストの終了と cons pair を選択している。
rev2 n =
if n==[] then
[]
else
(rev2 (tail n)) ++ [head n]
この方法だと ++ を n 回繰り返すことになる。
rev1 は、
rev3 n t =
if n==[] then
t
else
rev3 (tail n) ((head n) : t)
と書いても同じ。(この方が普通っぽい?)
無限リスト
inc 0 = []
inc n = n : inc (n + 1)
inc 1 は、普通止まらない。これは無限リストを表している。でも、Haskell では必要とされる分しか計算されない。
take1 0 x = []
take1 n (x:xs) = x : take1 (n-1) xs
というのを作り、
*Main> take 10 (inc 1)
[1,2,3,4,5,6,7,8,9,10]
というように使うことができる。
Tree
data を使ってを作ろう。List は同じ型の要素しか持てない。入れ子になった List を作ることはできない。そこで、入れ子を作れる Node を定義する。Node は 値を持つLeaf か 二つの Node を持つかどちらかと考える。
data Nodes a = Node (Nodes a) (Nodes a)
| Leaf a
deriving (Show)
| がどちらかというのを表している。
deriving (Show)を使うと、表示できるようになる。a はList でも使われていた型変数である。
*Main> let a = Leaf 1
*Main> a
Leaf 1
*Main> let b = Node a a
*Main> b
Node (Leaf 1) (Leaf 1)
*Main> let x = Node (Node (Leaf 1) (Leaf 2)) (Leaf 3)
このように入れ子構造を作ることができる。
flatten n = case n of
Node s t -> (flatten s)++(flatten t)
Leaf v -> [v]
この関数を使うことにより、
*Main> x
Node (Node (Leaf 1) (Leaf 2)) (Leaf 3)
*Main> flatten x
[1,2,3]
と平坦にすることができる。