Haskell: リストの操作

(2008.8.18 新規作成。)

操作と言っても、Haskell のオブジェクトは immutable なので、関数がリストを返す場合、それは新しいリストです。

Haskell は lazy evaluation ですから、例えば、木構造のデータをリストに変換して、リストとして操作するようにプログラムを書いたりしても, 実際に必要な部分しか評価されませんから, 効率の問題はありません。

●TODO: リストの例を追加する。

リスト操作の主な関数

map :: (a -> b) -> [a] -> [b] 	-- Defined in `GHC.Base'

関数とリストを引数に取り, リストの各要素に関数を適用し、その結果のリストを作る。無限リストを渡したときは、mapの戻り値も無限リスト。

Prelude> map (* 2) [1, 2, 3]
[2,4,6]

●擬似コード??
map f [x1, x2, ...] == [f x1, f x2, ...]

(++) :: [a] -> [a] -> [a]

二つのリストを連結する。最初のリストが無限リストのときは単に最初のリストを返す。そりゃそうだ。

filter :: (a -> Bool) -> [a] -> [a]

リストの各要素に第1引数の関数を適用してみて、戻り値が真となる要素だけで新しいリストを作る。

リストの内包記法で次のように書くのと同じ。

filter p xs = [ x | x <- xs, p x]

head :: [a] -> a

リストの最初の要素を取り出す。空リストのときは, 関数の型は純粋にもかかわらずエラー (例外) 発生。

n 個の要素を取り出すときは take を使う。

tail :: [a] -> [a]

2番目以降のリストを得る。head した残り。tail という語感がピンとこない。

(!!) :: [a] -> Int -> a

リストのn番目の要素を得る。nは0開始の整数。

take :: Int -> [a] -> [a]

先頭のn個の要素からなる新しいリストを作る。

drop :: Int -> [a] -> [a]

先頭のn個以外のリストを作る。take した残り。

takeWhile :: (a -> Bool) -> [a] -> [a]

takeWhile p xs は、関数 p をリストxsの各要素に適用してみて、戻り値が真の間の要素を取り出す。p が偽を返した時点で打ち切る。

takeWhile (< 3) [1,2,3,4,1,2,3,4] == [1,2]

dropWhile :: (a -> Bool) -> [a] -> [a]

takeWhile した残り。関数が真の間だけ要素を捨てる。

dropWhile (< 3) [1,2,3,4,5,1,2,3] == [3,4,5,1,2,3]

reverse :: [a] -> [a]

リストをひっくり返す。リストは有限でなければならない。無限リストを渡すと返ってこない。

リストを調べる

null :: [a] -> Bool

リストが空のとき真。Bool を返す関数は is... という名前が多いが、これはそうなっていない。

length :: [a] -> Int

リストの長さを返す。無限リストのときは返ってこない。あれ？

any :: (a -> Bool) -> [a] -> Bool

xsのいずれかの要素について真ならば、Trueを返す。

all :: (a -> Bool) -> [a] -> Bool

すべてが真のとき True を返す。

elem :: Eq a => a -> [a] -> Bool 	-- Defined in `GHC.List'
infix 4 `elem`

リストが第1引数の要素を含むときTrue.

elem 1 [1,2,3]   -- True
elem 1 [2,3,4]   -- False

中置きで書くこともできます。

Prelude> 5 `elem` [1,2,3]
False

次と同じ。

elem x xs    = any (== x) xs
notElem x xs = all (/= x) xs

Data.List.find :: (a -> Bool) -> [a] -> Maybe a

find f xs は、リストxsの要素のうち、関数fが真となる最初の要素のMaybeモナドを返す。 そのような要素が見つからなかったときは Nothing を返す。

Prelude> Data.List.find (== 1) [1, 2, 3]
Just 1
Prelude> Data.List.find (== 3) [2, 4, 6]
Nothing

集約

リストに関数を適用し、集約します。

sum :: Num a => [a] -> a

リストの要素をすべて足しあげる。空リストのときは 0 を返す。foldl で次のように書くのと同じです。

sum xs =  foldl (+) 0 xs

product :: Num a => [a] -> a

リストの要素を掛け合わせる。空リストのときは、エラーではなく、1 を返す。次と同じ。

product xs = foldl (*) 1 xs

汎用の畳み込み演算として、foldl, foldr があります。

Wikipedia の図がイメージしやすいと思います。Fold (higher-order function) - Wikipedia, the free encyclopedia

Rubyだと、Enumerable#inject() -- 別名 Enumerable#reduce() -- が foldl に相当します。inject() に引数を渡さなければ foldl1 になります。

[1,2.3].inject(10) {|prev, item| prev - item} 
            #=> 10 - 1 - 2 - 3 = 4

ややマニアックな解説は、例えば、

• foldr と foldl の違い - 言語ゲーム

foldl :: (a -> b -> a) -> a -> [b] -> a 	-- Defined in `GHC.List'

リストの左に値を並べて、左の要素から順に関数を適用して畳み込みます。無限リストを渡すと終わりません。

foldl (-) 1 [2, 3, 4] = ((1 - 2) - 3) - 4 == -8

定義は次のようになっています。

foldl f z []     =  z
foldl f z (x:xs) =  foldl f (f z x) xs

foldr :: (a -> b -> b) -> b -> [a] -> b

foldr の r は right の r です。リストの右に値を置いて、右から順に関数を適用して畳み込みます。

定義はこうです。

foldr f z []     =  z
foldr f z (x:xs) =  f x (foldr f z xs)

foldl1 :: (a -> a -> a) -> [a] -> a

リストの左の要素から順に関数を適用して畳み込みます。空リストのときはエラーです。

foldl1 f (x:xs)         =  foldl f x xs
foldl1 _ []             =  errorEmptyList "foldl1"

foldr1 :: (a -> a -> a) -> [a] -> a

foldr1 _ [x]            =  x
foldr1 f (x:xs)         =  f x (foldr1 f xs)
foldr1 _ []             =  errorEmptyList "foldr1"