トップ > 技術メモ (ソフトウェア開発) > はすけるで遊ぶ >
リストの操作
(2008.8.18 新規作成。)
操作と言っても、Haskell のオブジェクトは immutable なので、関数がリストを返す場合、それは新しいリストです。
Haskell は lazy evaluation ですから、例えば、木構造のデータをリストに変換して、リストとして操作するようにプログラムを書いたりしても効率の問題はありません。
- import Data.Tree
- t :: Tree Int
- t = Node 1 [Node 2 [Node 3 [], Node 4 []], Node 5 []]
- main = print $ flatten t
- -- [1,2,3,4,5] ノードそのものが先で、子はその後ろ。
- map :: (a -> b) -> [a] -> [b]
- リストの各要素に関数を適用し、その結果のリストを作る。無限リストを渡したときは、mapの戻り値も無限リスト。
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
- リストが第1引数の要素を含むときTrue.
elem 1 [1,2,3] == True elem 1 [2,3,4] == 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 を返す。
集約
リストに関数を適用し、集約します。
- 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
- リストの左に値を並べて、左の要素から順に関数を適用して畳み込みます。無限リストを渡すと終わりません。
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"
トップ > 技術メモ (ソフトウェア開発) > はすけるで遊ぶ > リストの操作
Netsphere Laboratories http://www.nslabs.jp/
[PR]
[PR]