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)
はリストを２回走査するので少し非効率的な気がする．これを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 xsfilter リストの各要素に対して述語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はリストに２項演算子を以下のように適用して値を返す関数である．
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]
これまで紹介した４つ関数は２項演算子を左結合で用いていたが，右結合で用いるたものがそれぞれ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は左結合であり，２項演算子の左項と戻り値が同じでなければならない．逆にfoldrは右結合であるため２項演算子の右項と戻り値が同じでなければならない．そのため，上記のような型になる．
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)は２つの引数のうち大きい(小さい)方を返す関数である．
Prelude> max 1 2 2 Prelude> min 1 2 1 Prelude> maximum [2, 1, 3] 3 Prelude> minimum [2, 1, 3] 1
