Haskell 言語 (第２回)、立木秀樹

前回の復習

○　Haskell では、再帰呼び出しでプログラムを書く。

fac1 n = if (n == 0) then 1  else (fac1 (n-1)) * n

fact 0 = 1
fact n | n > 0  = n * fact (n-1)

○　Haskell では、高階関数を書くことができる。

twice f x = f (f x)

twice f = \x -> f (f x)

twice = \f -> (\x -> f (f x))

Main> :t twice
twice :: (a -> a) -> a -> a

-------------
３．リスト

リストは、同じ型のものの列。

Main> [1,2,3]

Main> [1..10]

Main> [1,3..9]

無限リストも使える。無限リストの表示を止めるには、Ctrl-C を(２回）押す
か、WinHugs では、ストップボタンを押す。

Main> [1,1..]

Main> [1,2..]

Main> :t [1,2,3]
[1,2,3] :: Num a => [a]

[a] は、型 a のもののリストを表す型。

リストに対しては、様々な操作が用意されている。

: は、要素とリストをもらい、その要素を前にくっつけたリストを返すオペレータ。

Main> 1:[2,3]
[1,2,3]

: は後ろに結合する。つまり、1:2:[3] は、1:(2:[3]) の意味。

1:[2,3] も 1:2:[3]、1:2:3:[]　も同じ値である。

他のオペレータと同じで、(:) とすると、関数としても用いられる。

Main> :t (:)
(:) :: a -> [a] -> [a]

: は、型 a と型 [a] の要素をもらい [a] の要素を返す。

head :: [a] -> a　  		先頭要素を返す
tail :: [a] -> [a]　		残りの要素を返す
take :: Int -> [a] -> [a]	先頭から指定された個数だけ取り出したリスト返す
length :: [a] -> Int            リストの長さを返す。
(++) :: [a] -> [a] -> [a]       リストを結合する
concat :: [[a]] -> [a]　　　　　リストのリストを１つのリストにする。
reverse:: [a] -> [a]

Main> length [1,3,..,100]
1
Main> tail [1..10]
[2,3,4,5,6,7,8,9,10]
Main> take 3 [1..10]
[1,2,3]
Main> take 10 [1,2..]
[1,2,3,4,5,6,7,8,9,10]
Main> length [1,3..100]
50
Main> [1,2,3] ++ [4,5,6]
[1,2,3,4,5,6]
Main> length [[1,2,3],[4,5],[],[6]]
4
Main> concat [[1,2,3],[4,5],[],[6]]
[1,2,3,4,5,6]
Main> reverse [1,3,4]
[4,3,1]

４．リストと再帰的関数

リストに関する関数は、再帰的に書くことができる。

例えば、上に書いた関数は、次のように書ける。

length1 []  = 0
length1 (a:x) = 1 + length1 x

-- conc1 は、(++) のこと。
conc1 [] y  = y
conc1 (a:x) y  = a:conc1 x y

concat1 [] = []
concat1 (a:x) = conc1 a (concat1 x)

練習問題１：  数のリストをもらい、中身を２乗にしたリストを返す関数 sqares
を作成せよ。

Main> squares [3,4,5]
[9,16,25]

練習問題２：  reverse関数を自分でかいたもの reverse1 を作成せよ。

リストを再帰的に書けるのは偶然ではない。リストは、 (1) [] であるか、
(2) あるリスト x と要素 a に対し、a:x であるかどちらかである。そして、
リストとは何かは、この２つのことより完全に定義される。
（このような定義を、再帰的定義という）。

自然数も再帰的に定義された。すなわち、自然数は (1) 0 であるか、
(2) ある自然数の次の数であるか、どちらかである。そして、このように定義
されたものが自然数である。

このように再帰的に定義された対象の上では、関数は、再帰的定義によって書
くことができる（すなわち、(1) の場合と (2) の場合の場合分けで、(1) の場
合は直接に、(2) の場合は、その中に現れる自分自身に、今定義しようとして
いる関数を適用した結果を用いて関数を定義する。）

また、このように再帰的に定義された対象の性質は、数学的帰納法により証明
できる。リストに対する数学的帰納法は、次の形をとればよい。(1) [] の場合
は直接証明する。(2) a:x の場合には、x に対して証明できると仮定して、
a:x の場合の証明を行う。これにより、全てのリストに対して証明を行ったこ
とになる。

５．リストと高階関数

リストを扱う処理は、再帰的定義と高階関数で書けるものが多い。

map 関数 リスト　　　
		関数をリストの各要素に適用する。
型：	 map :: (a -> b) -> [a] -> [b]
使用例： map square [1, 2, 3]
使用例： map (\x -> x * x) [1,2,3]

filter Bool値関数 リスト　
		Bool値関数を適用した結果が True のものだけのリスト
型：	 filter :: (a -> Bool) -> [a] -> [a]
使用例： filter (> 4) [ 1, 5, 2, 3, 6]

foldr 2引数関数 初期値 リスト 
	2引数関数を初期値からはじめてリストの要素に右からつぎつぎかける。
型：	 foldr :: (a -> b -> b) -> b -> [a] -> b
foldr (+) 0 [1..10]
　　　　1 + 2 + ... (9 + (10 + 0))

foldl 2引数関数 初期値 リスト 
       	2引数関数を初期値からはじめてリストの要素に左からつぎつぎかける。
型：	 foldl :: (a -> b -> a) -> a -> [b] -> a
foldr (+) 0 [1..10]
	 ((0 + 1) + 2) + ... + 10

これらの関数は、再帰的に定義できる。

map1 f [] = []
map1 f (a:b) = f a: (map1 f b)

練習問題３:  filter を自分で書いてみよ。(filter1)

６．リストの内包表現

リストは、集合の内包定義のように書くことができる。

Main> [2*x |x <- [1..10]]　

これは、x が [1..10] のリストの要素を動くときの、2*x のリストである。

Main> [x |x <- [1..10], rem x 2 == 0]

Main> [2*x |x <- [1..10], rem x 2 == 0]

rem は、割った余りを返す２引数関数である。
これは、x が [1..10] のリストの要素の中で、rem x 2 == 0 が真であるもの
のリスト、および、それらの2倍のリストである。前者は
filter (\x->rem x 2 == 0) [1..10] と同じである。

引数 a の中で、10 より小さい数だけのリストを返す関数は、次のように
定義できる。

smaller10 a = [x |x <- a, x < 10]

リストの要素を小さい順に並べ替える操作を、ソートという。リストをソート
する手順に、クイックソートと呼ばれるものがある。これは、リストの先頭の
要素 a に対して、先頭を除いた残り p に対し、「p の中で a より小さいもの
をソートしたもの」 「a」「p の中で a より大きいものをソートしたもの」に
並べ替えるというアルゴリズムである。この中で、a より小さいもの、大きい
ものをソートするのには、再帰呼び出しを用いる。 qsort は、次のように書け
る。

qsort [] = []
qsort x = (qsort (filter (<(head x)) (tail x))) 
           ++ [head x]
           ++ (qsort (filter (>=(head x)) (tail x))) 

練習問題４：　qsort を、filter の代わりに、内包表記を用いて書き直せ。

練習問題５：円盤 n を from から to に移動するというのを(n,from,to) の三
つ組みとして表現し、n 段のハノイの塔の解法をそのような三つ組みのリスト
として作成する関数 hanoi n a b c　を作れ

Main> (hanoi 3 "A" "B" "C")
[(1,"A","B"),(2,"A","C"),(1,"B","C"),(3,"A","B"),(1,"C","A"),(2,"C","B"),(1,"A","B")]

練習問題６：
上記のリストをもとに、次のような文字列のリスト
"Move 1 from A to B." といった文字列のリストに変える関数 hshow をつくれ。

　　ヒント1：show :: Show a => a -> Stringは、様々なものの値を画面に表
　　示する文字列を作成する関数である。文字列は、++ でつなげられる。
  
    Main> "aaa" + show 2
    "aaa2"

    ヒント２：パターンマッチは強力なので、３つ組のリストの上の関数は、
    hshow [] = ...
    hshow ((a,b,c):x) = ...

    と書ける。

７．無限リストと遅延評価

無限リストを使用できるのも、Haskell の特徴である。
 
Main> take 10 [1,2..]

は、引数（すなわち、1,2,... という無限リスト）を作成してから take
が実行されるのではない。（それだと、途中で無限に時間がかかってしまい、
take が実行されない）take の方で必要なだけ、[1,2..] の計算を行う。

これを用いると、素数を無限に書き続けることも一行でできる。

Main> [x| x <-[2,3..], and [rem x y /= 0| y <- [2,3..x-1]]]

  rem x y　は割り算の余り、/= 0 は not equal, つまり等しくない時に True
  and は、and :: [Bool] -> Bool という型をもち、引数のリストが True
  ばかりだと True である。

このような記述は慣れないと難しいが、数学的な定義をそのまま書いていると
言って過言ではないだろう。Haskell を用いると、数学的な記述に近い形でプ
ログラムが書けるということを体感してほしい。

--------------------------------------------------------------

レポート：

注意：１月２３日の授業をうけて、レポートの内容に変更が加えられることがある。
また、このファイルそのものも変更が加えられることがあるので、注意すること。

Lesson1, Lesson 2 の内容を、自分で演習してみよう。 
そして、このファイルの中の、練習問題１、２、３、４、５、６に答えよ。

１つ以上正解していれば、このレポートに関しては合格点があると思っていい。


締切：２月６日（月曜）午後５時