リストの操作

(2008.8.18 新規作成。)

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

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

Haskell
[POPUP]
  1. import Data.Tree
  2. t :: Tree Int
  3. t = Node 1 [Node 2 [Node 3 [], Node 4 []], Node 5 []]
  4. main = print $ flatten t
  5. -- [1,2,3,4,5] ノードそのものが先で、子はその後ろ。

リスト操作の主な関数

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 の図がイメージしやすいと思います。

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

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

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

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"