Haskellのリスト操作関数に関する覚書です.
注意: この記事の内容は2014/07/28時点のものです。 最新の情報についてはHaskellの公式リファレンスを参照してください。
Haskellのまとまったリファレンスは, Haskell Wiki なのですが, サイト内の見通しがあまりよくないというか, 目的の記事に行くまでに時間がかかってしまいます. Pythonのドキュメントや. Clojureのチートシート, SchemeのR5RS(R7RS)のように, 全体を概観しにくいです.
そんなHaskellにもちゃんと, 言語仕様書があり, 以下のページでHaskellの仕様が説明されています.
本文はほとんどが英文ですが, 各セクションのタイトルは日本語化されているので, 多少, 読みやすいドキュメントかと思われます.
この記事は, 上記の報告書のセクション20 Data.Listを見ながら書いた, リスト操作関数の一覧です.
- Haskellには, Data.Listに含まれるリスト操作関数とPreludeListにデフォルトで含まれているリスト操作関数があります. この記事にかかれているものは, PreludeListではなく, Data.Listに含まれている関数です. Preludeで使えないものは, import Data.Listを追記すれば, 動きます.
- 一応, 動作は確認していますが, 間違いやスペルミスが含まれるかもしれません. (Haskell 2010 Language Report(上記)の記述の方が正確です)
- ()で型が定義されているものは演算子です.
基本関数
2つのリストを結合する
(++) :: [a] -> [a] -> [a]
>> [1..10]++[10..15]
[1,2,3,4,5,6,7,8,9,10,10,11,12,13,14,15]
リストの先頭を返す
head :: [a] -> a
>> head [1..10]
1
リストの二番目以降の要素を返す(consセルの後ろ側を返す)
tail :: [a] -> [a]
>> tail [1..10]
[2,3,4,5,6,7,8,9,10]
リストの最後の要素を返す
last :: [a] -> [a]
>> last [1..10]
10
リストの最後の要素を除いたリストを返す
init :: [a] -> [a]
>> init [1..10]
[1,2,3,4,5,6,7,8,9]
リストが空かどうか判定
null :: [a] -> Bool
>> null [1..10]
False
>> null []
True
リストの長さを返す
length :: [a] -> Int
>> length [1..10]
10
リストの変換
リストのそれぞれの要素にf(与えられた関数)を適用する(map関数)
map :: (a -> b) -> [a] -> [b]
関数型言語といえば, コレです.
>> map (1 +) [1..10]
[2,3,4,5,6,7,8,9,10,11]
リストを反転させる関数
reverse :: [a] -> [a]
>> reverse [1..10]
[10,9,8,7,6,5,4,3,2,1]
リストの各要素の間にある要素を挿入(はさみこませる)
intersperse :: a -> [a] -> [a]
>> intersperse 0 [1..10]
[1,0,2,0,3,0,4,0,5,0,6,0,7,0,8,0,9,0,10]
リストの各要素(各リスト)の間にある要素(リスト)を挿入して結合
intercalate :: [a] -> [[a]] -> [a]
利用するシチュエーションのイメージが浮かびませんが, intersperseとconcat(後述)を合成したような関数のようです.
>> intercalate [1..2] [[3..4],[5..6],[7..8]]
[3,4,1,2,5,6,1,2,7,8]
(行列でいうところの)転置の処理
transpose :: [[a]] -> [[a]]
>> transpose [[1,2],[3,4]]
[[1,3],[2,4]]
与えられたリストの部分リストを返す
subsequences :: [[a]] -> [[a]]
部分集合と読み替えてもいいかもしれません.
>> subsequences [1..3]
[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
permutation(順列)を返す.
permutations :: [a] -> [[a]]
>> permutations [1..3]
[[1,2,3],[2,1,3],[3,2,1],[2,3,1],[3,1,2],[1,3,2]]
リストの畳み込み(fold系)
関数型言語のリスト処理の定番といえば, map&reduce(fold)ですが, Haskellでは, fold用関数が何種類も用意されています.
リストを左側から畳み込む
foldl :: (a -> b -> a) -> a -> [b] -> a
左側から, foldl (+) 0 [1..]の時, ((0 + 1) + 2) ...と計算していきます.
>> foldl (-) 1 [1..10]
-54
foldlの正格評価関数version
foldl' :: (a -> b -> a) -> a -> [b] -> a
計算結果は, foldlと同じ.
foldlの初期値無しversion
foldl1 :: (a -> a -> a) -> [a] -> a
リストが空リストでない場合(要素１個でもOK)のfoldl.
>> foldl1 (-) [1..10]
-53
foldlの初期値無し/正格評価version
foldl1' :: (a -> a -> a) -> [a] -> a
リストを右側から畳み込む
foldr :: (a -> b -> b) -> b -> [a] -> b
右側から, foldr (+) 0 [1..10]の時, ... 9 + (10 + 0)と計算していきます. (必ず正格評価になります)
>> foldr (-) 0 [1..10]
-5
foldrの初期値無しversion
foldr1 :: (a -> a -> a) -> [a] -> a
リストが空リストでない場合(要素１個でもOK)のfoldr.
foldrの双対となる関数
unfoldr :: (b -> Maybe (a, b)) -> b -> [a]
unfoldrは, foldrの双対として定義される関数で, foldrにおけるfの逆関数f'とfoldrの計算結果を引数にとり, foldrによって計算されたリストを戻り値として返す関数です. 計算が失敗する可能性もあるので, Maybeモナドを用います.
以下の例では, (+) (和を計算する関数)と (\x-> (1 , x - 1))それを分解する関数について考えます.
>> let f = (+)
>> let f' = (\x-> if x < 1 then Nothing else Just (1, x - 1))
>> unfoldr f' 10
[1,1,1,1,1,1,1,1,1,1]
>> let ls = replicate 10 1
>> (unfoldr f' (foldr f 0 ls)) == ls
True
リストの畳み込み(その他)
リストのリストを一つのリストへ結合
concat :: [[a]] -> [a]
>> concat [[1],[2],[3]]
[1,2,3]
リストの各要素からそれぞれリストを作り, 結合
concatMap :: (a -> [b]) -> [a] -> [b]
>> concatMap (\x->[0,x]) [1..5]
[0,1,0,2,0,3,0,4,0,5]
リストの要素すべてでand
and :: [Bool] -> Bool
>> and [True, True, False]
False
リストの要素すべてでor
or :: [Bool] -> Bool
>> or [True, True, False]
True
リストにmap関数を適用して[Bool]を作りor
any :: (a -> Bool) -> [a] -> Bool
>> any odd [1..3]
True
リストにmap関数を適用して[Bool]を作りand
all :: (a -> Bool) -> [a] -> Bool
>> all odd [1..3]
False
総和
sum :: Num a => [a] -> a
>> sum [1..10]
55
総乗
product :: Num a => [a] -> a
>> product [1..10]
3628800
最大値
maximum :: Ord a => [a] -> a
>> maximum [1..10]
10
最小値
minimum :: Ord a => [a] -> a
>> minimum [1..10]
1
スキャン
foldlの途中経過のリストを生成
scanl :: (a -> b -> a) -> a -> [b] -> [a]
うまい言い方が無いですが, リストのn番目の要素がfoldlの結果となるようなリストです.
scanl f i [x1, x2 ...] = [foldl f i [], foldl f i [x1], foldl f i [x1,x2], ...]
>> scanl (+) 0 [1..10]
[0,1,3,6,10,15,21,28,36,45,55]
scanl1の初期値なしversion
scanl1 :: (a -> a -> a) -> [a] -> [a]
scanlを右側から
scanr :: (a -> b -> b) -> b -> [a] -> [b]
scanrの初期値なし
scanr1 :: (a -> a -> a) -> [a] -> [a]
累積写像
mapとfoldlの処理を両方実行, 結果をタプルで保存
mapAccumL :: (acc -> x -> (acc, y)) -> acc -> [x] -> (acc, [y])
mapAccumLに渡される関数の一番目の引数(acc)が「状態」を表し, 二番目の引数がリストの各要素(each element)を表します. (acc -> x -> (acc, y))の関数が返すタプルは, 「状態」とリストの各要素の計算結果のペアです.
詳しい解説は,
http://zvon.org/other/haskell/Outputlist/mapAccumL_f.html
上手な使い方はすぐに思い浮かびませんが, 使いどころはありそうな関数です.
>> mapAccumL (\x y -> (x * y, x + y)) 1 [1..5]
(120,[2,3,5,10,29])
>> mapAccumL (\x y -> (x * y, y + 1)) 1 [1..5]
(120,[2,3,4,5,6])
scanl mapAccumLを右側から
mapAccumR :: (acc -> x -> (acc, y)) -> acc -> [x] -> (acc, [y])
リスト生成
初期値にn回関数を適用した値がn番目の要素になるリスト
iterate :: (a -> a) -> a -> [a]
>> take 5 (iterate (1 +) 1)
[1,2,3,4,5]
与えられた要素を繰り返すリスト
repeat :: a -> [a]
>> take 5 (repeat 1)
[1,1,1,1,1]
長さnの与えられた要素を繰り返すリスト
replicate :: Int -> a -> [a]
>> replicate 5 1
[1,1,1,1,1]
リストの要素を繰り返す
cycle :: [a] -> [a]
>> take 11 (cycle [1..5])
[1,2,3,4,5,1,2,3,4,5,1]
部分リストの操作
リストの先頭からn個を取り出す
take :: Int -> [a] -> [a]
>> take 4 [1..10]
[1,2,3,4]
リストの先頭からn個を取り除く
drop :: Int -> [a] -> [a]
>> drop 4 [1..10]
[5,6,7,8,9,10]
先頭から調べ, 条件を満たし続けるまで値を取り出す
takeWhile :: (a -> Bool) -> [a] -> [a]
>> takeWhile (< 4) [1..10]
[1,2,3]
先頭から調べ, 条件を満たし続けるまで値を取り除く
dropWhile :: (a -> Bool) -> [a] -> [a]
>> dropWhile (< 4) [1..10]
[4,5,6,7,8,9,10]
リストをn番目で2つに分ける
splitAt :: Int -> [a] -> ([a], [a])
>> splitAt 3 [1..10]
([1,2,3],[4,5,6,7,8,9,10])
先頭から調べ, 条件を満たさなくなった要素で2つに分ける
span :: (a -> Bool) -> [a] -> ([a], [a])
>> span (< 4) [1..10] ([1,2,3],[4,5,6,7,8,9,10])
先頭から調べ, 条件を満たすようになった要素で2つに分ける
break :: (a -> Bool) -> [a] -> ([a], [a])
>> break (4 <) [1..10] ([1,2,3,4],[5,6,7,8,9,10])
接頭辞(先頭の要素列)を取り除く
stripPrefix :: Eq a => [a] -> [a] -> Maybe [a]
>> stripPrefix [1..3] [1..10]
Just [4,5,6,7,8,9,10]
同じ要素が続いた箇所をグループにする
group :: Eq a => [a] -> [[a]]
>> group [1,1,3,4,5,5,5,6]
[[1,1],[3],[4],[5,5,5],[6]]
先頭から与えられたリストの部分リストのリストを作る
inits :: [a] -> [[a]]
>> inits [1..5]
[[],[1],[1,2],[1,2,3],[1,2,3,4],[1,2,3,4,5]]
後ろから与えられたリストの部分リストのリストを作る
tails :: [a] -> [[a]]
>> tails [1..5]
[[1,2,3,4,5],[2,3,4,5],[3,4,5],[4,5],[5],[]]
述語系
リストの接頭辞(先頭の要素列)が与えられたリストに一致するか判定
isPrefixOf :: Eq a => [a] -> [a] -> Bool
>> isPrefixOf [1..4] [1..10]
True
リストの接尾辞(後尾の要素列)が与えられたリストに一致するか判定
isSuffixOf :: Eq a => [a] -> [a] -> Bool
>> isSuffixOf [1..4] [1..10]
False
リストの部分列が与えられたリストに一致するか判定
isInfixOf :: Eq a => [a] -> [a] -> Bool
>> isInfixOf [1..4] [1..10]
True
検索系
リストが与えられた要素を含むかどうか判定
elem :: Eq a => a -> [a] -> Bool
>> elem 3 [1..10]
True
リストが与えられた要素を含まないかどうか判定
notElem :: Eq a => a -> [a] -> Bool
>> notElem 3 [1..10]
False
keyとvalueからなるタプルのリストからkeyを指定して検索
lookup :: Eq a => a -> [(a, b)] -> Maybe b
>> lookup 3 [(1,2),(3,4)]
Just 4
与えられた述語が真となる要素を返す
find :: (a -> Bool) -> [a] -> Maybe a
>> find odd [1..5]
Just 1
与えられた述語が真となる要素のリスト, フィルター関数
filter :: (a -> Bool) -> [a] -> [a]
>> filter odd [1..10]
[1,3,5,7,9]
与えられた述語が真となるものと偽となるもので分割
partition :: (a -> Bool) -> [a] -> ([a], [a])
>> partition odd [1..10]
([1,3,5,7,9],[2,4,6,8,10])
インデックスによるリストの操作
リストの要素をインデックスで指定
(!!) :: [a] -> Int -> a
>> [1..10] !! 3
4
与えられた要素と一致する最初の要素のインデックスを返す
elemIndex :: Eq a => a -> [a] -> Maybe Int
>> elemIndex 3 [1..10]
Just 2
与えられた要素と一致する要素のインデックスのリストを返す
elemIndices :: Eq a => a -> [a] -> [Int]
>> elemIndices 3 [1..10]
[2]
述語が真を返す最初のインデックスを返す
findIndex :: (a -> Bool) -> [a] -> Maybe Int
>> findIndex odd [1..10]
Just 0
述語が真を返すインデックスのリストを返す
findIndices :: (a -> Bool) -> [a] -> [Int]
>> findIndices odd [1..10]
[0,2,4,6,8]
リストの結合と分解
2つのリストを各要素でタプル(2組)にしたリストにまとめる, zip関数
zip :: [a] -> [b] -> [(a, b)]
3つのリストを用いて三組にしたい場合は, zip3を使います. zip関数は, zip7まであり, zip7は,七組のタプルのリストを生成します.
>> zip [1..10] [11..20]
[(1,11),(2,12),(3,13),(4,14),(5,15),(6,16),(7,17),(8,18),(9,19),(10,20)]
2つのリストについてmapする関数
zipWith :: (a -> b -> c) -> [a] -> [b] -> [c]
2つのリスト[a], [b]から各要素を取り出し, 与えられた関数(a -> b -> c)の引数とし, その関数が返す結果のリスト[c]を返します.
私が一番好きなHaskellの関数です.
zipWithもzipと同様, zipWith7まであります.
>> zipWith (+) [1..10] [11..20]
[12,14,16,18,20,22,24,26,28,30]
zipされたリストを元の2つのリストへ還元する
unzip :: [(a, b)] -> ([a], [b])
unzipにもzip同様, unzip7まであります.
>> unzip (zip [1..10] [11..20])
([1,2,3,4,5,6,7,8,9,10],[11,12,13,14,15,16,17,18,19,20])
文字列用の関数
文字列を改行で分割
lines :: String -> [String]
>> lines "abc\ndef"
["abc","def"]
文字列を空白で分割
words :: String -> [String]
>> words "this is a pen."
["this","is","a","pen."]
文字列のリストを改行で結合
unlines :: [String] -> String
>> unlines ["abc","def"]
"abc\ndef\n"
文字列を空白で結合
unwords :: [String] -> String
>> unwords ["this","is","a","pen."]
"this is a pen."
集合演算
リストの重複する要素を取り除く
nub :: Eq a => [a] -> [a]
>> nub [1,2,3,1,2,4,5,4]
[1,2,3,4,5]
最初に登場する引数に与えられた要素を取り除く
delete :: Eq a => a -> [a] -> [a]
>> delete 2 [1,2,3,1,2,4,5,4]
[1,3,1,2,4,5,4]
リストの差のリストを求める
(\\) :: Eq a => [a] -> [a] -> [a]
>> [1,2,3,1,2,4,5,4] \\ [3..5]
[1,2,1,2,4]
直和を返す
union :: Eq a => [a] -> [a] -> [a]
>> union [1..5] [3..7]
[1,2,3,4,5,6,7]
積を返す
intersect :: Eq a => [a] -> [a] -> [a]
>> intersect [1..5] [3..7]
[3,4,5]
※コメントを受けて修正しました。(2017/11/24)
順序づけられたリスト操作
リストのソート(並び替え)
sort :: Ord a => [a] -> [a]
昇順で並び替えます.
>> sort [5,6,9,2,3]
[2,3,5,6,9]
ソート済み(と仮定した)のリストに挿入する, 挿入ソートの挿入処理
insert :: Ord a => a -> [a] -> [a]
>> insert 1 [5,6,9,2,3]
[1,5,6,9,2,3]
>> insert 1 [3..9]
[1,3,4,5,6,7,8,9]
セクション20.10以降の一般化された関数は省略します. かなりの数がありますが, 汎用性の高い関数ばかりでした. Haskellでは, 文字列は, char型のリストなので, 文字列の操作にもここにある関数が使えます.
