今回からリストに対する再帰について説明する。関数は、入力としてリストを取る。この種の再帰関数は、出力によって大まかに二分できる。
- (リストではない)値を返す
- リストを返す
今回は前者を対象とする。すなわち、入力としてリストを取り、値を返す再帰関数について学ぶ。
GHCi でリストに対する情報を表示させみよう。
% ghci
> :info []
data [] a = [] | a : [a]なんだか分からない情報が表示された。これが分かりにくいのは、表記が揺れていたり、記号を使っていたりするからだ。順にほぐしていこう。まず、角括弧で表現されている型の表記を統一する。
data [] a = [] | a : [] aそして、構成子を前に出す。(Haskell では、アルファベットの構成子の他に、":" から始まる二項演算子としての構成子が許されている。)
data [] a = [] | (:) a ([] a)最後に記号をアルファベットに変えてみる。
data List a = Nil | Cons a (List a)これを自然数の定義と比較してみよう。
data Nat = Z | S NatList は値を格納している以外は、自然数と同じであることが分かる。自然数は再帰的に定義されているので、再帰処理と相性がよかった。同様に、リストも再帰的に定義されているので、再帰処理と相性がよいのである。
リストの基本的な操作は以下の通り。
- 空リストか調べる
- リストの先頭の要素を取り出す
- リストの先頭の要素を取り除いた残りのリストを取り出す
- リストの先頭に要素を加える
Haskell では、1) 〜 3) をパターンマッチで実現する。
my_foo [] = ... -- 引数が空リストのとき
my_foo (x:xs) = ... -- 引数が空リストでないとき、先頭の要素を x、残りのリストを xs とする-
と 3) のために、それぞれ head と tail という関数があるが、ほとんど使われない。
-
のためには、構成子 ":" (cons と読む)を使う。(構成子 ":" は、再帰ドリル(9)で登場する。)
リストの再帰的に処理する関数は、基本的に以下のような形を取る。
my_foo [] = ... -- 基底部
my_foo (x:xs) = ... -- 再帰部例として、リストの長さを測る関数 my_length を考えよう。
my_length [] = 0
my_length (_:[]) = 0 + 1
my_length (_:_:[]) = 0 + 1 + 1
my_length (_:_:_:[]) = 0 + 1 + 1 + 1
my_length (_:_:_:_:[]) = 0 + 1 + 1 + 1 + 1一歩手前を使うとどうなる？
my_length [] = 0
my_length (_:[]) = my_length [] + 1
my_length (_:_:[]) = my_length (_:[]) + 1
my_length (_:_:_:[]) = my_length (_:_:[]) + 1
my_length (_:_:_:_:[]) = my_length (_:_:_:[]) + 1再帰部を一般化するとどうなる？
my_length :: [a] -> Integer
my_length [] = 0
my_length (_:xs) = my_length xs + 1実際に使ってみよう。
> my_length [1,2,3,4]
4つまり再帰部は、再帰のこころに従って以下のように考える。
- my_foo xs ができているとする。my_foo xs を使うと、my_foo (x:xs) はどうなる？
my_length の場合、my_length xs の長さが分かっているとするなら、my_length (_:xs) の長さは、それに 1 を加えれば得られる。(x は利用しないので、捨てている。)
###演習
入力として Integer のリストを取り、要素すべてを足した結果を返す関数 my_sum を実装しなさい。
my_sum :: [Integer] -> Integer
my_sum = undefined入力として Integer のリストを取り、要素すべてを掛けた結果を返す関数 my_product を実装しなさい。
my_product :: [Integer] -> Integer
my_product = undefined##末尾再帰
my_length のように、リストを最後まで走査する(途中で離脱しない)再帰関数は、簡単に末尾再帰の形に直せる。
my_length_iter :: [a] -> Integer
my_length_iter as = iter as 0
where
iter :: [a] -> Integer -> Integer
iter [] n = n
iter (_:xs) n = iter xs (n + 1)###演習
my_sum を末尾再帰の形に直しなさい。
my_sum_iter :: [Integer] -> Integer
my_sum_iter as = iter as undefined
where
iter = undefinedmy_product を末尾再帰の形に直しなさい。
my_product_iter :: [Integer] -> Integer
my_product_iter as = iter as undefined
where
iter = undefined##再帰を信じろ
比較できる要素を持つリストを入力として取り、最大の要素を求めて返す関数を考えたい。リストを一回最後まで走査すれば、最大の要素は求まるはずである。
この関数名を my_maximum とすると、型は以下のようになる。
my_maximum :: Ord a => [a] -> aOrd とは型に対する制約である。
Ord aが付かないaは、制約のない任意の型Ord a => aのaは、Ordという制約を持つ型。Ordとは値の大小を比較できるという制約である。
最大値を求めるには、要素の型がなんでもよいわけではなく、少なくとも比較して大小関係を決定できる必要があるという訳だ。
使用例は以下の通り。
> my_maximum [5,10,2,8,4]
10入力が空リストだった場合は、エラーを返す(これは伝統だが、まじめにやるなら Maybe a を返すべき)。要素が1つのリストの場合、その要素が最大となる。よって、基底部は以下のように定義できる。
my_maximum [] = error "my_maximum"
my_maximum [x] = x問題は、再帰部である。
xs の最大の要素が my_maximum xs で解決されていると信じて、以下の再帰部を完成させよ。
my_maximum :: Ord a => [a] -> a
my_maximum [] = error "my_maximum"
my_maximum [x] = x
my_maximum (x:xs) = undefined同様に、最小の要素を探す関数 my_minimum を定義せよ。
my_minimum :: Ord a => [a] -> a
my_minimum [] = error "my_minimum"
my_minimum [x] = x
my_minimum (x:xs) = undefinedmy_maximum を末尾再帰の形に直せ。
my_maximum_iter :: Ord a => [a] -> a
my_maximum_iter [] = error "my_maximum_iter"
my_maximum_iter (a:as) = iter undefined undefined
where
iter = undefinedmy_minimum を末尾再帰の形に直せ。
my_minimum_iter :: Ord a => [a] -> a
my_minimum_iter [] = error "my_minimum_iter"
my_minimum_iter (a:as) = iter undefined undefined
where
iter = undefined##途中で離脱する再帰
リストの探索を途中で打ち切るタイプの関数がある。
例として、Bool のリストを取り、すべての要素が True であるか検査する関数を考えよう。関数名は my_and とする。使用例は以下の通り。
> my_and [True,True,True]
True
> my_and [True,False,True]
Falseこの関数は、False を発見したら、すぐにリストの走査を打ち切って、False を返すべきである。この関数は以下のように定義できる。
my_and :: [Bool] -> Bool
my_and [] = True
my_and (x:xs) = x && my_and xs再帰部において、x が False の場合、my_and xs は評価されないことに注意。(離脱するためには通常遅延評価が必要となるが、この場合は (&&) を使っているので、正格評価でも同じ。) 基底部がなぜ True となるのかは、自分で考えること。
これを単純に末尾再帰の形に直してみよう。
my_and_bad_iter :: [Bool] -> Bool
my_and_bad_iter as = iter as True
where
iter [] acc = acc
iter (x:xs) acc = iter xs (x && acc)my_and と my_and_bad_iter は、同じ入力に対して同じ結果を返すが、同等ではない。my_and_bad_iter は、必ずリストを最後まで走査してしまうからである。途中で離脱するためには、工夫が必要である。
また、返り値は Bool であるので、値は蓄積する必要がない。これらを考慮すると、以下のような末尾再帰の形に直せる。
my_and_iter :: [Bool] -> Bool
my_and_iter [] = True
my_and_iter (x:xs)
| x = my_and_iter xs
| otherwise = False###演習
Boolのリストを取り、要素が一つでも True であれば True を、すべてが False なら False を返す関数を実装しなさい。
my_or :: [Bool] -> Bool
my_or = undefinedこれを末尾再帰の形に直せ。
my_or_iter :: [Bool] -> Bool
my_or_iter = undefined第一引数として判定関数、第二引数にリストを取り、すべての要素が判定関数で True となるか検査する関数を定義しなさい。
my_all :: (a -> Bool) -> [a] -> Bool
my_all = undefinedこれを末尾再帰の形に直せ。
my_all_iter :: (a -> Bool) -> [a] -> Bool
my_all_iter = undefined##検索
指定された値がリストの中にあるか判定する関数は、以下のように定義できる。
my_elem :: Eq a => a -> [a] -> Bool
my_elem _ [] = False
my_elem k (x:xs)
| k == x = True
| otherwise = my_elem k xs値があればリストの走査を止めていること、値を集約する必要がないため末尾再帰の形になっていることに注意。
実際に使ってみよう。
> my_elem 3 [1,2,3,4]
True
> my_elem 5 [1,2,3,4]
False###演習
判定関数が True を返すような値がリストの中にあるか判定する関数を定義せよ。
my_find :: (a -> Bool) -> [a] -> Maybe a
my_find = undefined指定された値が、連想リストのキーとして存在すれば、その対となるバリューを Just にくるんで返し、存在しなければ Nothing を返す関数を実装せよ。
my_lookup :: Eq k => k -> [(k,v)] -> Maybe v
my_lookup = undefined##畳み込み
ある演算子を使いリストの要素を集約することを「畳み込む」という。畳み込みには、右からの畳込みと左からの畳込みがある。
###右からの畳み込み
たとえば、[1,2,3,4] というリストがあって、二項演算子 "+" を使い、初期値 0 で右から畳み込むと以下のようになる。
1 + (2 + (3 + (4 + 0)))
右からの畳込みを実現する my_foldl を実装せよ。
my_foldr :: (a -> b -> b) -> b -> [a] -> b
my_foldr _ ini [] = ini
my_foldr f ini (x:xs) = undefined難しいかもしれないが、型が実装を導いてくれるはずである。
ヒント：右からの畳み込みは、途中で離脱できる。
使用例は以下の通り：
> my_foldr (+) 0 [1,2,3,4]
10###左からの畳み込み
たとえば、[1,2,3,4] というリストがあって、二項演算子 "+" を使い、初期値 0 で左から畳み込むと以下のようになる。
(((0 + 1) + 2) + 3) + 4
左からの畳込みを実現する my_foldl を実装せよ。
my_foldl :: (a -> b -> a) -> a -> [b] -> a
my_foldl _ acc [] = acc
my_foldl f acc (x:xs) = undefined難しいかもしれないが、型が実装を導いてくれるはずである。
ヒント：左からの畳み込みは、途中で離脱できない。
> my_foldl (+) 0 [1,2,3,4]
10