Haskellの勉強 (4) - リスト (1)
基本的なリスト処理関数はPreludeListの中にある.Haskell 98 Reportに実装のサンプルが記述されている.
http://www.haskell.org/onlinereport/standard-prelude.html
head, tail, last, init, null
head :: [a] -> a head (x:_) = x head [] = error "Prelude.head: empty list" tail :: [a] -> [a] tail (_:xs) = xs tail [] = error "Prelude.tail: empty list" last :: [a] -> a last [x] = x last (_:xs) = last xs last [] = error "Prelude.last: empty list" init :: [a] -> [a] init [x] = [] init (x:xs) = x : init xs init [] = error "Prelude.init: empty list" null :: [a] -> Bool null [] = True null (_:_) = False
headとtailはそれぞれリストの最初の要素と残りのリストを取得する.schemeでいうcarとcdr.
Prelude> head [1, 2, 3] 1 Prelude> head [] *** Exception: Prelude.head: empty list Prelude> tail [1, 2, 3] [2,3] Prelude> tail [] *** Exception: Prelude.tail: empty list
headの定義
head :: [a] -> a head (x:_) = x head [] = error "Prelude.head: empty list"
の_はワイルドカードパターンであり,どんなものにもマッチする.また,errorは処理を中断して文字列を標準出力に出力する関数である.headなどに空リストが与えられると,エラーを出力する.
headとtailが最初の要素と後半のリストに分割しているのに対して,lastとinitは最後の要素と前半のリストに分割している.
Prelude> last [1, 2, 3] 3 Prelude> last [] *** Exception: Prelude.last: empty list Prelude> init [1, 2, 3] [1,2] Prelude> init [] *** Exception: Prelude.init: empty list
nullは空リストかどうかを判定する
Prelude> null [] True Prelude> null [1] False
length
length :: [a] -> Int length [] = 0 length (_:l) = 1 + length l
lengthはリストの長さを求める
Prelude> length [1, 2, 3] 3
インデクシング (!!)
(!!) :: [a] -> Int -> a xs !! n | n < 0 = error "Prelude.!!: negative index" [] !! _ = error "Prelude.!!: index too large" (x:_) !! 0 = x (_:xs) !! n = xs !! (n-1)
!!はリストのインデクシングを行う.
Prelude> "Haskell" !! 2 's'
インデックスが負であったり,リストの最後のインデックスを越えていたらエラーを出すようになっている.
Prelude> "Haskell" !! 8 *** Exception: Prelude.(!!): index too large Prelude> "Haskell" !! (-1) *** Exception: Prelude.(!!): negative index
take, drop, splitAt
take :: Int -> [a] -> [a] take n _ | n <= 0 = [] take _ [] = [] take n (x:xs) = x : take (n-1) xs drop :: Int -> [a] -> [a] drop n xs | n <= 0 = xs drop _ [] = [] drop n (_:xs) = drop (n-1) xs splitAt :: Int -> [a] -> ([a],[a]) splitAt n xs = (take n xs, drop n xs)
takeはリストから最初のn個の要素を抽出したリストを返し,dropはリストから最初のn個の要素を除去したリストを返す.
Prelude> take 2 [1, 2, 3, 4, 5] [1,2] Prelude> drop 2 [1, 2, 3, 4, 5] [3,4,5]
nがリストの長さを超えた場合,takeは全リストを返し,dropは空リストを返す.
Prelude> take 6 [1, 2, 3, 4, 5] [1,2,3,4,5] Prelude> drop 6 [1, 2, 3, 4, 5] []
逆にnが負の場合,takeは空リストを返し,dropは全リストを返す.
Prelude> take (-1) [1, 2, 3, 4, 5] [] Prelude> drop (-1) [1, 2, 3, 4, 5] [1,2,3,4,5]
splitAtはtakeとdropのタプルを作る.そうすると,n番目で分割したタプルが返される.
Prelude> splitAt 2 [1, 2, 3, 4, 5] ([1,2],[3,4,5]) Prelude> splitAt 6 [1, 2, 3, 4, 5] ([1,2,3,4,5],[]) Prelude> splitAt (-1) [1, 2, 3, 4, 5] ([],[1,2,3,4,5])
splitAtの定義
splitAt :: Int -> [a] -> ([a],[a]) splitAt n xs = (take n xs, drop n xs)
はリストを2回走査するので少し非効率的な気がする.これをtakeやdropを用いずに書いてみると,
splitAt :: Int -> [a] -> ([a], [a]) splitAt n xs | n <= 0 = ([], xs) splitAt _ [] = ([], []) splitAt n (x:xs) = (x:ys, zs) where (ys, zs) = splitAt (n - 1) xs
のようになる.
等差数列 (Arithmetic Sequence)
..はperlの範囲演算子のようにある範囲のリストを生成する.これは公差1の等差数列とみなすことができる.
Prelude> [0..9] [0,1,2,3,4,5,6,7,8,9] Prelude> [-5..5] [-5,-4,-3,-2,-1,0,1,2,3,4,5]
公差は1である必要はない.[a,b..c]は公差b-aでcを越えない等差数列を生成する.
Prelude> [0,2..10] [0,2,4,6,8,10] Prelude> [0,3..10] [0,3,6,9] Prelude> [10,9..1] [10,9,8,7,6,5,4,3,2,1]
無限リスト
上限を設定しないと無限リストを生成できる.例えば[0..]は任意の自然数のリストを表し,[0,2..]任意の正の偶数のリストを表す.これをそのままghciで評価すると無限に出力してしまうので,takeなどを用いて一部を切り出す.
Prelude> take 10 [0..] [0,1,2,3,4,5,6,7,8,9] Prelude> take 10 [0,2..] [0,2,4,6,8,10,12,14,16,18]
リスト内包表記 (List Comprehension)
集合の定義のようなものを用いてリストを表現することができる.例えば
Prelude> [(x, y) | x <- [1..3], y <- [1..3]] [(1,1),(1,2),(1,3),(2,1),(2,2),(2,3),(3,1),(3,2),(3,3)]
x <- [1..3]はxは集合(1, 2, 3)に属すという意味である.また,その他の条件式も記述することができる.よくある例の一つがquicksortである.quicksortは以下のように記述できる.
quicksort [] = [] quicksort (x:xs) = quicksort [y | y <- xs, y<x ] ++ [x] ++ quicksort [y | y <- xs, y>=x]
これは,先頭の要素を軸として,軸より小さいもの,軸,軸より大きいものに分割して連結する.ということを行っている.
*Main> quicksort [3, 2, 5, 4, 1] [1,2,3,4,5]
map
map :: (a -> b) -> [a] -> [b] map f [] = [] map f (x:xs) = f x : map f xs
mapはリストの各要素に関数を適用したリストを返す.例えばリストの要素の平方をとる場合は,以下のようになる.
Prelude> map (\x -> x * x) [0..10] [0,1,4,9,16,25,36,49,64,81,100]
連結演算子 (++)
(++) :: [a] -> [a] -> [a] [] ++ ys = ys (x:xs) ++ ys = x : (xs ++ ys)
(++)はリストを連結する
Prelude> "Ha" ++ "skell" "Haskell"
filter
filter :: (a -> Bool) -> [a] -> [a] filter p [] = [] filter p (x:xs) | p x = x : filter p xs | otherwise = filter p xs
filter リストの各要素に対して述語pが真となる要素のみからなるリストを返す.Perlのgrepにあたる.
リストから偶数の要素のみを抽出する場合は以下の式を用いる
Prelude> filter (\x -> x `mod` 2 == 0) [0..10] [0,2,4,6,8,10]
fold[lr]1?, scan[lr]1?
foldl :: (a -> b -> a) -> a -> [b] -> a foldl f z [] = z foldl f z (x:xs) = foldl f (f z x) xs foldl1 :: (a -> a -> a) -> [a] -> a foldl1 f (x:xs) = foldl f x xs foldl1 _ [] = error "Prelude.foldl1: empty list" scanl :: (a -> b -> a) -> a -> [b] -> [a] scanl f q xs = q : (case xs of [] -> [] x:xs -> scanl f (f q x) xs) scanl1 :: (a -> a -> a) -> [a] -> [a] scanl1 f (x:xs) = scanl f x xs scanl1 _ [] = [] foldr :: (a -> b -> b) -> b -> [a] -> b foldr f z [] = z foldr f z (x:xs) = f x (foldr f z xs) foldr1 :: (a -> a -> a) -> [a] -> a foldr1 f [x] = x foldr1 f (x:xs) = f x (foldr1 f xs) foldr1 _ [] = error "Prelude.foldr1: empty list" scanr :: (a -> b -> b) -> b -> [a] -> [b] scanr f q0 [] = [q0] scanr f q0 (x:xs) = f x q : qs where qs@(q:_) = scanr f q0 xs scanr1 :: (a -> a -> a) -> [a] -> [a] scanr1 f [] = [] scanr1 f [x] = [x] scanr1 f (x:xs) = f x q : qs where qs@(q:_) = scanr1 f xs
foldlはリストに2項演算子を以下のように適用して値を返す関数である.
foldl f z [x1, x2, ..., xn] = (...((z `f` x1) `f` x2)... `f` xn)
例えばリストの要素の和や積は以下のように計算される
Prelude> foldl (+) 0 [1..10] 55 Prelude> foldl (*) 1 [1..10] 3628800
初期値はリストの最初の要素にしたものがfoldl1である.
Prelude> foldl1 (+) [1..10] 55 Prelude> foldl1 (*) [1..10] 3628800
scanlは以下のようなリストを返す.
scanl f z [x1, x2, ..., xn] = [z, (z `f` x1), ((z `f` x1) `f` x2), ..., (z `f` x1), (((z `f` x1) `f` x2) ... `f` xn)]
例えば,
Prelude> scanl (+) 0 [1..10] [0,1,3,6,10,15,21,28,36,45,55]
のようになる.
foldl1のように初期値をリストの最初の要素としたものがscanl1である.scanl1は空リストの場合は空リストを返す.
Prelude> take 10 (scanl1 (+) [1..]) [1,3,6,10,15,21,28,36,45,55] Prelude> take 10 (scanl1 (+) [1,3..]) [1,4,9,16,25,36,49,64,81,100]
これまで紹介した4つ関数は2項演算子を左結合で用いていたが,右結合で用いるたものがそれぞれfoldr, foldr1, scanr, scanr1となる.
foldr f z [x1, x2, ,..., xn] = (f xn ... (f x2 (f x1 z))) scanr f q [x1, x2, ,..., xn] = [(f xn ... (f x2 (f x1 z))),..., (f x2 (f x1 z)), (f x1 z)]
foldlとfoldrでは関数の型が異なる.
foldl :: (a -> b -> a) -> a -> [b] -> a foldr :: (a -> b -> b) -> b -> [a] -> b
foldlは左結合であり,2項演算子の左項と戻り値が同じでなければならない.逆にfoldrは右結合であるため2項演算子の右項と戻り値が同じでなければならない.そのため,上記のような型になる.
scanrの定義では@を使っている.var@apatはvarにapatをバインドするというような意味らしい.この場合qs=(q:_)=scanr f q0 xsであり,それをf x qの後ろに連結している.
sum, product
sum, product :: (Num a) => [a] -> a sum = foldl (+) 0 product = foldl (*) 1
sum(product)はリストの要素の和(積)を求める関数である.
Prelude> sum [1..10] 55 Prelude> product [1..10] 3628800
maximum minimum
maximum, minimum :: (Ord a) => [a] -> a maximum [] = error "Prelude.maximum: empty list" maximum xs = foldl1 max xs minimum [] = error "Prelude.minimum: empty list" minimum xs = foldl1 min xs
maximum(minimum)はリストの要素の最大値(最小値)を求める関数である.定義に用いているmax(min)は2つの引数のうち大きい(小さい)方を返す関数である.
Prelude> max 1 2 2 Prelude> min 1 2 1 Prelude> maximum [2, 1, 3] 3 Prelude> minimum [2, 1, 3] 1