[Haskell]Data.Listの関数まとめ

# Haskell の Data.List 関数まとめ

Haskell の標準ライブラリの Data.List の[ページ](https://hackage.haskell.org/package/base-4.12.0.0/docs/Data-List.html)にある関数(117 個)がかなり便利だったのでまとめてみました。

## 注意点

- この記事はとても長いです。
- 自分もまだまだ Haskell を書くのは上手ではないので、誤りなどあれば教えていただければ幸いです。

この記事を書くのに使用した環境は以下の通りです。

- GHC: v8.6.5
- GHCi: v8.6.5

ここに載っている関数は以下の操作で使うことができます。

- ソースファイル: `import Data.List`
- GHCi: `:module +Data.List`

ただし、以下の関数は`Prelude`に含まれているのでインポートする必要はありません。

```haskell

(++), head, tail, last, init, null, length, map, reverse, foldl, foldl1, foldr, foldr1, concat, concatMap, and, or, any, all, sum, product, maximum, minimum, scanl, scanl1, scanr, scanr1, iterate, repeat, replicate, cycle, take, drop, splitAt, dropWhile, span, break, elem, notElem, lookup, filter, (!!), zip, zip3, zipWith, zipWith3, unzip, unzip3, lines, unlines, words, unwords
```

関数名の後には型注釈をつけています。

## 基本の関数

### (++)

```haskell
(++) :: [a] -> [a] -> [a] infixr 5
```

リストを 2 つとり、1 つ目のリストの末尾に 2 つ目のリストを結合します。(注意:この関数は`:`よりもはるかに遅いので、リストから新しいリストを構築する際は`:`をお勧めします。)

例:

```haskell
ghci> [1, 2, 3] ++ [4, 5, 6]
[1, 2, 3, 4, 5, 6]
ghci> "Hello, " ++ "world"
"Hello, world"
```

### head

```haskell
head :: [a] -> a
```

- リストの先頭の要素を返します。

例:

```haskell
ghci> head [1,2,3,4]
1
ghci> head "apple"
'a'
```

### last

```haskell
last :: [a] -> a
```

- リストの末尾の要素を返します。

例:

```haskell
ghci> last [4,3,2,1]
1
```

### tail

```haskell
tail :: [a] -> [a]
```

- リストから先頭の要素を除いたリストを返します。`head ls : tail ls`は`ls`と同値です。

例:

```haskell
ghci> tail [1,2,3,4,5]
[2,3,4,5]
ghci> tail [1,2]
[2]
```

### init

```haskell
init :: [a] -> [a]
```

- リストの末尾の要素を取り除いたリストを返します。

例:

```haskell
ghci> init [1,2,3,4,5,6]
[1,2,3,4,5]
```

### uncons

```haskell
uncons :: [a] -> Maybe (a, [a])
```

- `cons`演算子(`:`)と逆の操作です。リストの先頭の要素と、残りのリストを含む`Maybe a`型のタプルを返します。要素が 1 つのリストなら要素と空リストのタプル、空リストなら`Nothing`を返します。

例:

```haskell
ghci> uncons [1,2,3,4,5]
Just (1, [2,3,4,5])
ghci> uncons [3,4]
Just (3, [4])
ghci> uncons [1]
Just (1, [])
ghci> uncons []
Nothing
```

### null

```haskell
null :: Foldable t => t a -> Bool
```

- リストを 1 つとり、それが空(要素がない)なら`True`、そうでなければ`False`を返します。

例:

```haskell
ghci> null [53]
False
ghci> null []
True
```

### length

```haskell
length :: Foldable t => t a -> Int
```

- リストを 1 つとり、その長さ(要素数)を返します。

例:

```haskell
ghci> length [7,5,3]
3
ghci> length []
0
```

## リストの変形

### map

```haskell
map :: (a -> b) -> [a] -> [b]
```

- `map f xs`は、`xs`の各要素に`f`を適用したリストを返します。(`f`は関数)

例:

```haskell
ghci> map negate [1,2,3,4,5]
[-1,-2,-3,-4,-5]
ghci> map (^2) [1,2,3,4,5]
[1,4,9,16,25]
```

### reverse

```haskell
reverse :: [a] -> [a]
```

- リストを一つとり、その順番を逆にしたリストを返します。(大小は関係ありません。)

例:

```haskell
ghci> reverse [65,23,125,42]
[42,125,23,65]
ghci> reverse [5]
[5]
ghci> reverse []
[]
```

### intersperse

```haskell
intersperse :: a -> [a] -> [a]
```

- 要素とリストを 1 つづつとり、リストの各要素の間に引数の要素を挟んだリストを返します。

例:

```haskell
ghci> intersperse 6 [4,3,2,1]
[4,6,3,6,2,6,1]
ghci> intersperse ',' "abcde"
"a,b,c,d,e"
```

### intercalate

```haskell
intercalate :: [a] -> [[a]] -> [a]
```

- リスト`xs`とリスト`yss1, yss2, yss3, ...`を含むリスト`ys`をとり、`yss1, yss2, yss3, ...`の間に`xs`を挟んだリストを返します。

例:

```haskell
ghci> intercalate ", " ["John", "Bill", "Sam"]
"John, Bill, Sam"
ghci> intercalate [2] [[1,2,3],[4,5,6],[7,8,9]]
[1,2,3,2,4,5,6,2,7,8,9]
ghci> intercalate [1..4] [[1..5],[6..10],[11..15]]
[1,2,3,4,5,1,2,3,4,6,7,8,9,10,1,2,3,4,11,12,13,14,15]
```

### transpose

```haskell
transpose :: [[a]] -> [[a]]
```

この関数は文章だけでは少し説明しづらいので、図を使います。

次のような**リストを含むリスト**があるとき、

```haskell
[
[1,2,3,4]
[1]
[1,2,3,4,5]
]
```

`transpose`は次のように変換します。

```haskell
[
[1,1,1]
[2,2]
[3,3]
[4,4]
[5]
]
```

リストを縦から見て、先頭から同じ位置にある要素を抜き出してリストにします。

例:

```haskell
ghci> transpose [[1,2,3],[1,2],[1],[1,2,3,4,5]]
[[1,1,1,1],[2,2,2],[3,3],[4],[5]]
ghci> transpose [[1,2,3],[4,5,6]]
[[1,2],[3,4],[5,6]]
```

### subsequences

```haskell
subsequences :: [a] -> [[a]]
```

- *subsequence*とは、数学の用語で「部分列」のことらしいです。部分列とは、「与えられた列から項の一部を取り出し、もとの列の順に並べ替えた列」です。(ジーニアス英和大辞典より)

- `subsequences`はリストを 1 つ取り、そのリストから 0~要素数までの「元のリストに含まれるリストを含んだリスト」を返します。重複するリストがあってもそのまま返します。

例:

```haskell
ghci> subsequences "a"
["", "a"]
ghci> subsequences "aa"
["", "a", "a", "aa"]
ghci> subsequences "abc"
["","a","b","ab","c","ac","bc","abc"]
ghci> subsequences [1,2,3,4]
[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3],[4],[1,4],[2,4],[1,2,4],[3,4],[1,3,4],[2,3,4],[1,2,3,4]]
```

### permutations

```haskell
permutations :: [a] -> [[a]]
```

- *permutations*とは、数学で「順列」のことを指すらしいです。「順序も含めた組み合わせ」のことです。

- `permutations`はリストを 1 つ取り、そのリストの要素をすべて使ってできるリストをすべて返します。要はリストの要素の並べ替えです。長さ`x`のリスト`xs`を引数にとった`ys`の要素数は`x`の階乗です。

$$
x!\\
= x(x-1)(x-2)(x-3)...1
$$

例えば、長さが 5 のリスト`ls`があるとき、`permutation ls`の要素数は、

$$
5(5-1)(5-2)(5-3)(5-4)\\
=5\times4\times3\times2\times1 = 120
$$

なので、`permutation ls`の要素数は 120 個です。

例:

```haskell
ghci> permutations [1,2,3]
[[1,2,3],[2,1,3],[3,2,1],[2,3,1],[3,1,2],[1,3,2]]
ghci> permutations "abcd"
["abcd","bacd","cbad","bcad","cabd","acbd","dcba","cdba","cbda","dbca","bdca","bcda","dabc","adbc","abdc","dbac","bdac","badc","dacb","adcb","acdb","dcab","cdab","cadb"]
```

## リストの畳み込み

### 畳み込みとは

リストを右もしくは左から関数を適用して結合させ、最終的に 1 つの値にする操作です。例えば、`[1,2,3,4,5]`というリストを`+`という演算子で左から畳み込むとき、

```haskell
(1 + 2)+ 3 + 4 + 5
    (3 + 3)+ 4 + 5
        (6 + 4)+ 5
            (10 +5)
                15
```

という風に畳み込みます。最初の要素と 2 番目の要素を足し合わせ、その結果と 3 番目の要素を足し合わせ、その結果と 4 番目の要素を足し合わせ…という操作を繰り返します。

### foldl

```haskell
foldl :: Foldable t => (b -> a -> b) -> b -> t a -> b
```

- `foldl`は 2 引数の関数`f`、アキュムレータ`z`とリストを 1 つとります。アキュムレータとは「畳み込みの初期値」で、[Hackage の説明](https://hackage.haskell.org/package/base-4.12.0.0/docs/Data-List.html#g:3)では

```haskell
foldl f z [x1, x2, ..., xn] == (...((z `f` x1) `f` x2) `f`...) `f` xn
```

とあります。上の例で 1 にあたる要素で、そこから畳み込みが始まります。

例:

```haskell
ghci> foldl (*) 1 [1,2,3,4,5] -- !5
120
ghci> foldl (^) 2 [3,4,5] -- 2^3^4^5
1152921504606846976
```

### foldl'

```haskell
foldl' :: Foldable t => (b -> a -> b) -> b -> t a -> b
```

- `foldl'`は`foldl`の正格評価バージョンです。`foldl`は計算を遅延させるので、大きなデータを処理させると計算が引き伸ばされすぎてスタックオーバーフローエラーが発生します。`foldl'`はすぐに評価されるのでエラーは発生しません。
- 基本的な使い方は`foldl`と同じです。

### foldl1

```haskell
foldl1 :: Foldable t => (a -> a -> a) -> t a -> a
```

- `foldl`はアキュムレータを引数にとりますが、`foldl1`ではその必要はありません。引数に取ったリストの先頭の要素をアキュムレータとして畳み込みます。

例:

```haskell
ghci> foldl1 (+) [10..100]
5005
```

### foldl1'

```haskell
foldl1' :: (a -> a -> a) -> [a] -> a
```

- `foldl1`の正格評価バージョンです。使い方は`foldl1`と同じです。

### foldr

```haskell
foldr :: Foldable t => (a -> b -> b) -> b -> t a -> b
```

- `foldl`はリストを左から畳み込むのに対し、`foldr`は右から畳み込むように見えます。畳み込みの展開はリストの末尾から行いますが、実際の計算は左からです。左右の畳み込みの違いについては、[こちらの記事](C)が非常にわかりやすかったので参照してください。

例:

```haskell
ghci> foldr (-) 0 [1..10]
-5
```

### foldr1

```haskell
foldr1 :: Foldable t => (a -> a -> a) -> t a -> a
```

- `foldr`のアキュムレータをとらないバージョンです。`foldl1`と同じくアキュムレータは引数のリストの先頭からとります。

## 特別な畳み込み

### concat

```haskell
concat :: Foldable t => t [a] -> [a]
```

- リストを含むリストをとり、それぞれを結合したリストを返します。

例:

```haskell
ghci> concat ["abc", "def", "ghi"]
"abcdefghi"
ghci> concat [[1,2,3,4],[5,6,7,8]]
[1,2,3,4,5,6,7,8]
```

### concatMap

```haskell
concatMap :: Foldable t => (a -> [b]) -> t a -> [b]
```

- 関数 1 つとリストを含んだリスト 1 つをとり、リスト内の各リストに関数をマップしたリストを結合したリスト 1 つを返します。

例:

```haskell
ghci> concatMap (3:) [[1,2],[3,4],[5,6]]
[3,1,2,3,3,4,3,5,6]
ghci> concatMap (++"aa") ["a", "b", "c"]
"aaabaacaa"
```

### and

```haskell
and :: Foldable t => t Bool -> Bool
```

- `Bool`型の要素のリストをとり、全ての要素が`True`ならば`True`、そうでなければ`False`を返します。

例:

```haskell
ghci> and [True, True, False]
False
ghci> and [True, True, True]
True
```

### or

```haskell
or :: Foldable t => t Bool -> Bool
```

- `Bool`型の要素のリストをとり、全て`False`ならば`False`、そうでなければ`True`を返します。

例:

```haskell
ghci> or [True, False, False]
True
ghci> or [False, False]
False
```

### any

```haskell
any :: Foldable t => (a -> Bool) -> t a -> Bool
```

- リストと、`Bool`型の値を返す関数をとり、リストのうち「関数に適用して`True`になる要素(条件をみたす要素)」が一つでもあれば`True`、そうでなければ`False`を返します。

例:

```haskell
ghci> any (>5) [1..10]
True
ghci> any (>'x') "bananas"
False
```

### all

```haskell
all :: Foldable t => (a -> Bool) -> t a -> Bool
```

- リストと、`Bool`型の値を返す関数をとり、リストのうち全ての要素が「関数に適用して`True`になる要素(条件をみたす要素)」ならば`True`、そうでなければ`False`を返します。

例:

```haskell
ghci> all (<11) [1..10]
True
ghci> all (=='g') "orange"
False
```

### sum

```haskell
sum :: (Foldable t, Num a) => t a -> a
```

- `Num`型の値のリストをとり、全ての要素の和を返します。

例:

```haskell
ghci> sum [1..100]
5050
```

### product

```haskell
product :: (Foldable t, Num a) => t a -> a
```

- `Num`型の値のリストをとり、全ての要素の籍を返します。

例:

```haskell
ghci> product [1..10]
3628800
```

## リストの構築

### スキャン

スキャンとは、アキュムレータの中間状態のリストです。例えば、

```haskell
foldl (+) 0 [1..5]
```

を評価するとき、アキュムレータの`0`は次のように変化します。

```txt
0
1
3
6
10
15
```

これをリストとして表現したのが`[0,1,3,6,10,15]`で、`scanl (+) 0 [1..5]`の値です。

### scanl

```haskell
scanl :: (b -> a -> b) -> b -> [a] -> [b]
```

- 2 引数の関数、アキュムレータ、リストをとり、`foldl`で畳み込んだ際のアキュムレータの中間状態のリストを返します。

例:

```haskell
ghci> scanl (*) 1 [1..5]
[1,1,2,6,24,120]
ghci> scanl (+) 0 [20..30]
[0,20,41,63,86,110,135,161,188,216,245,275]
```

### scanl'

```haskell
scanl' :: (b -> a -> b) -> b -> [a] -> [b]
```

- `scanl`も`foldl`と同じく遅延評価で計算を引き伸ばすので、大きなリストを走査させるとエラーが起きます。なので、エラーを避けるために`foldl'`のような正格評価の`scanl`があります。基本的な使い方は`scanl`と同じです。

### scanl1

```haskell
scanl1 :: (a -> a -> a) -> [a] -> [a]
```

- `foldl`に対する`foldl1`に当たります。`fold1`のように引数にとったリストの先頭をアキュムレータとして使いスキャンします。

例:

```haskell
ghci> scanl1 (+) [4..19]
[4,9,15,22,30,39,49,60,72,85,99,114,130,147,165,184]
```

### scanr

```haskell
scanr :: (a -> b -> b) -> b -> [a] -> [b]
```

- 関数、アキュムレータ、リストをとり、`foldr`で畳み込んだ際のスキャンを返します。

```haskell
ghci> scanr (*) 1 [1..10]
[3628800,3628800,1814400,604800,151200,30240,5040,720,90,10,1]
```

### scanr1

```haskell
scanr1 :: (a -> a -> a) -> [a] -> [a]
```

- `scanr`のアキュムレータをとらないバージョンです。基本的な使い方は`scanr`と同じです。

## マップの蓄積

### mapAccumL

```haskell
mapAccumL :: Traversable t => (a -> b -> (a, c)) -> a -> t b -> (a, t c)
```

- `mapAccumL`は「2 引数をとってペアを返す関数」`\x y -> (n m)`とアキュムレータ`a`、リスト`xs`をとります。そして、「`x`に`a`を渡してアキュムレータ`a`と`n`で`xs`を畳み込んだ値」、「`y`に`a`をとった時の関数を`xs`に`map`したリスト」のペアを返します。とてもわかりにくい説明だと思いますが、まず例を見てください。

```haskell
ghci>  mapAccumL (\a b -> (a+b, a*b))  1 [1..5]
(16,[1,4,12,28,55])
```

初めこれを見たとき、`16`が`foldl (+) 1 [1..5]`だというのはわかったのですが、`[1,4,12,28,55]`がよくわからなかったので次のようにしてみました。

```haskell
ghci> mapAccumL (\a b -> (concat ["(",a,"+",b,")"], concat ["(",a,"*",b,")"])) "1" ["1"
,"2","3","4","5"]
("(((((1+1)+2)+3)+4)+5)",["(1*1)","((1+1)*2)","(((1+1)+2)*3)","((((1+1)+2)+3)*4)","(((((1+1)+2)+3)+4)*5)"])
```

つまり`[1,4,12,28,55]`は、`scanl (+) 1 [1..5]`に`(*([1..5]の各要素))`を順にマップしたものです。

例:

```haskell
ghci> mapAccumL (\a b -> (a*b, a+b) 2 [1..5]
(240,[3,4,7,16,53])
ghci> mapAccumL (\a b -> (concat ["(",a,",",b,")"],concat ["(",a,",",b,")"])) "x" ["a","b","c","d"]
("((((x,a),b),c),d)",["(x,a)","((x,a),b)","(((x,a),b),c)","((((x,a),b),c),d)"])
```

### mapAccumR

- `mapAccumL`の`foldl`を`foldr`、`scanl`を`scanr`として処理するのが`mapAccumR`です。畳み込み、スキャンした際に順序が`mapAccumL`の逆になります。

## 無限リスト

### iterate

```haskell
iterate :: (a -> a) -> a -> [a]
```

- `iterate`は関数`f`と任意の値`x`をとり、次のようなリストを返します。`[x, f x, f (f x), ...]`
- 無限リストを生成するので、コードを書く際は無限リストを評価しないように注意してください。

例:

```haskell
ghci> take 4 (iterate (*2) 4)
[4,8,16,32]
ghci> take 5 (iterate (++".") "hello")
["hello","hello.","hello..","hello...","hello...."]
```

### iterate'

```haskell
iterate' :: (a -> a) -> a -> [a]
```

- `foldl`の時のように、`iterate`は遅延評価なので大きなリストを与えるとエラーが発生します。そのため、正格評価の`iterate`があります。
- 基本的な使い方は`iterate`と同じです。

### repeat

```haskell
repeat :: a -> [a]
```

- `repeat x`は無限リスト`[x,x,x,...]`を生成します。

例:

```haskell
ghci> take 3 $ repeat 1
[1,1,1]
ghci> take 3 $ repeat 'A'
"AAAA"
```

### replicate

```haskell
replicate :: Int -> a -> [a]
```

- `replicate n x`は長さ`n`の`x`で構成された要素を返します。

例:

```haskell
ghci> replicate 4 3
[3,3,3,3]
ghci> replicate 5 'o'
"ooooo"
```

### cycle

```haskell
cycle :: [a] -> [a]
```

- `cycle`はリストを 1 つとり、そのリストが繰り返される無限リストを生成します。

例:

```haskell
ghci> take 6 $ cycle "ha"
"hahaha"
ghci> take 7 $ cycle [1,2,3]
[1,2,3,1,2,3,1]
```

## 畳み込みの逆(Unfolding)

## unfoldr

```haskell
unfoldr :: (b -> Maybe (a, b)) -> b -> [a]
```

- `unfoldr`は`foldr`の逆の操作をします。例えば、`iterate f`は`unfoldr (\x -> Just (x, f x))`として表現できます。この操作は次のように行われます。

```haskell
iterate f =
[(x, f x)]
[x, (f x, f (f x))]
[x, f x, (f (f x), f (f (f x)))]
[x, f x, f (f x), f (f (f x)), ...]
```

リストの最初の要素の`x`がラムダ式に与えられ、`(x, f x)`が生成されます。次に、`f x`がラムダ式に与えられ、`(f x, f (f x))`が生成されます。そして次は`f (f x)`…というふうに次々に多重適用が行われていきます。

例:

```haskell
ghci> unfoldr (\a -> if a<10 then Nothing else Just (a, a-1)) 30
[30,29,28,27,26,25,24,23,22,21,20,19,18,17,16,15,14,13,12,11,10]
```

## 二次的なリスト

### 二次リストの算出

### take

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

- `take n xs`は`xs`の先頭から`n`個の要素のリストを返します。

例:１

```haskell
ghci> take 5 "abcdefg"
"abcde"
ghci> take 6 $ filter even [1..20]
[2,4,6,8,10,12]
```

### drop

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

- `drop n xs`は`xs`の先頭から`n`個取り除いたリストを返します。

例:

```haskell
ghci> drop 3 [1..10]
[4,5,6,7,8,9,10]
ghci> drop 0 "aaa"
"aaa"
```

### splitAt

```haskell
splitAt :: Int -> [a] -> ([a], [a])
```

- `splitAt n xs`は`xs`の先頭から`n`個目の要素で分割したリストのタプルを返します。

例:

```haskell
ghci> splitAt 4 [1..10]
([1,2,3,4],[5,6,7,8,9,10])
```

### takeWhile

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

- リストの先頭から要素を調べ、関数の結果が`False`になった時点で操作を終了します。

例:

```haskell
ghci> takeWhile (<7) $ cycle [1..10]
[1,2,3,4,5,6]
```

### dropWhile

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

- リストの最初から要素のうち関数の結果が`False`になるまで`drop`します。

例:

```haskell
 ghci> dropWhile (<5) [1..10]
 [6,7,8,9,10]
```

### dropWhileEnd

```haskell
dropWhileEnd :: (a -> Bool) -> [a] -> [a]
```

- `dropWhile`をリストの末尾から適用します。引数は`dropWhile`と同じです。

### span

```haskell
span :: (a -> Bool) -> [a] -> ([a], [a])
```

- リストの先頭から、引数の関数に要素を適用した結果が`False`になった部分で分割して、そのタプルを返します。

例:

```haskell
ghci> span (/=5) [1..10]
([1,2,3,4],[5,6,7,8,9,10])
```

### break

```haskell
break :: (a -> Bool) -> [a] -> ([a], [a])
```

- リストの先頭から、引数の関数に要素を適用した結果が`True`になった部分で分割して、そのタプルを返します。

例:

```haskell
ghci> break (>5) [1..10]
([1,2,3,4,5],[6,7,8,9,10])
```

### stripPrefix

```haskell
stripPrefix :: Eq a => [a] -> [a] -> Maybe [a]
```

- リストを 2 つとり、2 つ目のリストが 1 つ目のリストから始まっていれば「2 つ目のリストから 1 つ目のリストを取り除いたリスト」を`Just`でラップして返し、そうでなければを`Nothing`返します。

例:

```haskell
ghci> stripPrefix "a" "abc"
Just "bc"
ghci> stripPrefix "aa" "abc"
Nothing
```

### group

```haskell
group :: Eq a => [a] -> [[a]]
```

- リストをとり、続いている同じ要素をまとめたリストとしてリストに包んで返します。

```haskell
ghci> group "bananas"
["b","a","n","a","n","a","s"]
ghci> group "essentially"
["e","ss","e","n","t","i","a","ll","y"]
```

### inits

```haskell
inits :: [a] -> [[a]]
```

- リストをとり、リストの先頭から順序通りにリストの要素から構築できるリストを包んだリストを返します。

例:

```haskell
ghci> inits "apple"
["","a","ap","app","appl","apple"]
```

### tails

```haskell
tails :: [a] -> [[a]]
```

- リストをとり、リストの先頭から順序通りにリストの要素から構築できるリストを包んだリストを返します。

例:

```haskell
ghci> tails "apple"
["apple","pple","ple","le","e",""]
```

## 述語

### isPrefixOf

```haskell
isPrefixOf :: Eq a => [a] -> [a] -> Bool
```

- リストを 2 つとり、2 つ目のリストが 1 つ目のリストから始まっていれば`True`、そうでなければ`False`を返します。

例:

```haskell
ghci> "Ha" `isPrefixOf` "Haskell"
True
ghci> "Ha" `isPrefixOf` "leksah"
False
```

### isSuffixOf

```haskell
isSuffixOf :: Eq a => [a] -> [a] -> Bool
```

- リストを 2 つとり、2 つ目のリストが 1 つ目のリストで終わっていれば`True`、そうでなければ`False`を返します。

```haskell
ghci> "ell" `isSuffixOf` "Haskell"
True
ghci> "ell" `isSuffixOf` "leksah"
False
```

### isInfixOf

```haskell
isInfixOf :: Eq a => [a] -> [a] -> Bool
```

- リストを 2 つとり、1 つ目のリストが 2 つ目のリストに含まれていれば`True`、そうでなければ`False`を返します。

```haskell
ghci> "ask" `isInfixOf` "Haskell"
True
ghci> "say" `isInfixOf` "Haskell"
False
```

### isSubsequenceOf

```haskell
isSubsequenceOf :: Eq a => [a] -> [a] -> Bool
```

- 2 つリストをとり、1 つ目のリストが 2 つ目のリストの`subsequences`に含まれていれば`True`、そうでなければ`False`を返します。

例:

```haskell
ghci> isSubsequenceOf [1,2,3] [1..4]
True
ghci> isSubsequenceOf "aaa" "Haskell"
False
```

## リストの探索

### 等しいものを探す

### elem

```haskell
elem :: (Foldable t, Eq a) => a -> t a -> Bool infix 4
```

- 要素 1 つとリスト 1 つをとり、要素がリストに含まれていれば`True`、そうでなければ`False`を返します。
    例:

```haskell
ghci> "a" `elem` "Pascal"
True
ghci> "k" `elem` "Pascal"
False
```

### notElem

```haskell
notElem :: (Foldable t, Eq a) => a -> t a -> Bool infix 4
```

- 要素 1 つとリスト 1 つをとり、要素がリストに含まれていなければ`True`、そうでなければ`False`を返します。
- 操作は`elem`の逆です。

### lookup

```haskell
lookup :: Eq a => a -> [(a, b)] -> Maybe b
```

- 探したいリストと`[(key1, value1), (key2, value2), ...]`という構造の関連付けリストをとり、キー(`key`)に探したいリストがあれば`Just`でラップした値(`value`)を返し、なければ`Nothing`を返します。

例:

```haskell
ghci> let phonebook = [("Andre", "0627"), ("Bob", "1129"), ("Charlie", "0611")]
ghci> lookup "Bob" phonebook
Just "1129"
ghci> lookup "Sam" phonebook
Nothing
```

### 述語から探す

### find

```haskell
find :: Foldable t => (a -> Bool) -> t a -> Maybe a
```

- リストと`Bool`型の値を返す関数をと、`True`になる要素が見つかったら`Just`でラップしてそれを返し、なければ`Nothing`を返します。
    例:

```haskell
ghci> find (>5) [1..10]
Just 6
ghci> find (<5) [10..15]
Nothing
```

### filter

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

- `find`は条件をみたす要素を見つけた時点でそれを返して終わりますが、`filter`は条件をみたす要素全てをリストとして返します。条件をみたす要素がなければ空リストを返します。
    例:

```haskell
ghci> filter even [1..20]
[2,4,6,8,10,12,14,16,18,20]
ghci> filter (<1) [1..20]
[]
```

### patition

```haskell
partition :: (a -> Bool) -> [a] -> ([a], [a])
```

- 引数のリストを、条件を満たす要素と満たさない要素のそれぞれのリストに分割してタプルで包んで返します。
    例:

```haskell
ghci> partition (<'r') "astronaut"
("aona","strut")
ghci> partition (<3) [4..10]
([],[3,4,5,6,7,8,9,10])
```

## リストのインデックス

### (!!)

```haskell
(!!) :: [a] -> Int -> a infixl 9
```

- リストと 0~要素数-1 までの`Int`型の値をとり、リストの先頭から 0 から数えて引数の値に当たる要素を返します。
    例:

```haskell
ghci> "haskell" !! 4
'e'
ghci> filter odd [1..20] !! 5
11
```

### elemIndex

```haskell
elemIndex :: Eq a => a -> [a] -> Maybe Int
```

- 要素とリストをとり、要素と等しい値が見つかったら`Just`でラップしてその要素のインデックスを返し、なければ`Nothing`を返します。
    例:

```haskell
ghci> elemIndex 10 $ filter even [1..]
4
ghci> elemIndex 2 [1,3,5,7,9]
Nothing
```

### elemIndices

```haskell
elemIndices :: Eq a => a -> [a] -> [Int]
```

- 要素とリストを１つずつとり、リスト内でマッチした要素のインデックスのリストを返します。

```haskell
ghci> elemIndices 'n' "bananas"
[2,4]
ghci> elemIndices 'n' "haskell"
[s]
```

### findIndex

```haskell
findIndex :: (a -> Bool) -> [a] -> Maybe Int
```

- リストと述語をとり、マッチする要素があれば`Just`でラップしたインデックスを返し、なければを`Nothing`を返します。
    例:

```haskell
ghci> findIndex (>'o') "haskell"
Just 2
ghci> findIndex (>'t') "haskell"
Nothing
```

### findIndices

```haskell
findIndices :: (a -> Bool) -> [a] -> [Int]
```

- 述語のうち、リスト内でマッチした要素のインデックスのリストを返します。
    例:

```haskell
ghci> findIndices (`elem` "aeiou") "orange"
[0,2,5]
ghci> findIndices (`elem` "aeiou") "zsh"
[]
```

## リストの Zip と Unzip

### zip

```haskell
zip :: [a] -> [b] -> [(a, b)]
```

- リストを 2 つ受け取り、先頭から同じインデックスにある要素をタプルで包みます。そして、全体のリストを返します。どちらかのリストが短かった場合は、短い方のリストの要素数だけタプルが生成されます。

```haskell
[x1, x2, x3, ...]
[y1, y2, y3, ...]

[(x1,y1),(x2,y2),(x3,y3),...]
```

例:

```haskell
ghci> 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)]
ghci> zip "zippingandunzipping" [1..]
[('z',1),('i',2),('p',3),('p',4),('i',5),('n',6),('g',7),('a',8),('n',9),('d',10),('u',11),('n',12),
('z',13),('i',14),('p',15),('p',16),('i',17),('n',18),('g',19)]
```

### zip3, zip4, zip5, zip6, zip7

```haskell
zip3 :: [a] -> [b] -> [c] -> [(a, b, c)]
zip4 :: [a] -> [b] -> [c] -> [d] -> [(a, b, c, d)]
zip5 :: [a] -> [b] -> [c] -> [d] -> [e] -> [(a, b, c, d, e)]
zip6 :: [a] -> [b] -> [c] -> [d] -> [e] -> [f] -> [(a, b, c, d, e, f)]
zip7 :: [a] -> [b] -> [c] -> [d] -> [e] -> [f] -> [g] -> [(a, b, c, d, e, f, g)]
```

- `zip`の引数のリストが 3 つ、4 つ、5 つ、6 つ、7 つのバージョンです。基本的な操作は`zip`と同じです。

### zipWith

```haskell
zipWith :: (a -> b -> c) -> [a] -> [b] -> [c]
```

- 2 引数の関数を 1 つ、リストを 2 つ受け取り、各リストの先頭から同じインデックスにある要素に関数を適用して`zip`します。

```haskell
[x1, x2, x3, ...]
[y1, y2, y3, ...]

[(f x1 y1),(f x2 y2),(f x3 y3),...]
```

例:

```haskell
ghci> zipWith (*) [1..10] [11..20]
[11,24,39,56,75,96,119,144,171,200]
ghci> zipWith (zipWith (+)) [[1,4,2],[2,6,2],[7,2,5]] [[5,3,5],[6,1,5],[7,9,8]]
[[6,7,7],[8,7,7],[14,11,13]]
```

### zipWith3, zipWith4, zipWith5, zipWith6, zipWith7

```haskell
zipWith3 :: (a -> b -> c -> d) -> [a] -> [b] -> [c] -> [d]
zipWith4 :: (a -> b -> c -> d -> e) -> [a] -> [b] -> [c] -> [d] -> [e]
zipWith5 :: (a -> b -> c -> d -> e -> f) -> [a] -> [b] -> [c] -> [d] -> [e] -> [f]
zipWith6 :: (a -> b -> c -> d -> e -> f -> g) -> [a] -> [b] -> [c] -> [d] -> [e] -> [f] -> [g]
zipWith7 :: (a -> b -> c -> d -> e -> f -> g -> h) -> [a] -> [b] -> [c] -> [d] -> [e] -> [f] -> [g] -> [h]
```

- `zipWith`の引数のリストが 3 つ、4 つ、5 つ、6 つ、7 つのバージョンです。基本的な操作は`zipWith`と同じです。

### unzip

```haskell
unzip :: [(a, b)] -> ([a], [b])
```

- `Zip`と逆の操作を行います。引数のタプルのリストを先頭から分解して、`zip`する前のリストのタプルを生成します。

```haskell
[(x1,y1),(x2,y2),(x3,y3),]

([x1,x2,x3,...],[y1,y2,y3,...])
```

例:

```haskell
ghci> let profiles = [("Alice","0415"),("Bob","1220"),("Chris","0718")]
ghci> unzip profiles
(["Alice","Bob","Chris"],["1121","0315","0829"])
```

### unzip3, unzip4, unzip5, unzip6, unzip7

```haskell
unzip3 :: [(a, b, c)] -> ([a], [b], [c])
unzip4 :: [(a, b, c, d)] -> ([a], [b], [c], [d])
unzip5 :: [(a, b, c, d, e)] -> ([a], [b], [c], [d], [e])
unzip6 :: [(a, b, c, d, e, f)] -> ([a], [b], [c], [d], [e], [f])
unzip7 :: [(a, b, c, d, e, f, g)] -> ([a], [b], [c], [d], [e], [f], [g])
```

- `unzip`の引数のリストのタプル内の要素が 3 つ、4 つ、5 つ、6 つ、7 つのバージョンです。

## 特殊なリスト

### 文字列の関数

### lines

```haskell
lines :: String -> [String]
```

- 文字列を受け取り、改行文字`"\n"`で分割したリストをリストで包んで返します。
    例:

```haskell
ghci> lines "a\nbc\nd"
["a","bc","d"]
ghci> lines "a\\nb"
["a\\nb"]
```

### words

```haskell
words :: String -> [String]
```

- 文字列を受け取り、改行文字(`"\n"`)、空白(`" "`)、キャリッジ・リターン(`"\r"`)、タブ(`"\t"`)、改ページ(`"\f"`)、垂直タブ(`"\v"`)で文字列を分割し、リストで包んで返します。
    例:

```haskell
ghci> words "a\nb\tc d\re\vf\fg"
["a","b","c","d","e","f","g"]
```

### unlines

```haskell
unlines :: [String] -> String
```

- 文字列のリストを受け取り、改行文字で結合させた文字列を返します。
    例:

```haskell
ghci> unlines ["hello,","world"]
"hello\nworld"
```

### unwords

```haskell
unwords :: [String] -> String
```

- 文字列のリストを受け取り、空白で結合した文字列を返します。
    例:

```haskell
ghci> unwords ["hello,", "world"]
"hello, world"
```

## 集合の操作

### 集合とは

[集合](https://ja.wikipedia.org/wiki/%E9%9B%86%E5%90%88)は数学の概念の一つで、ある集合にはいくつかの要素が含まれます。集合を扱う集合論は、ある集合にある要素が含まれるか否か、2 つの集合の間で共通する要素はあるかなどを扱う学問です。例えば、「林檎は果物に含まれるか」「バナナはおやつに入るか(冗談です)」といった事柄です。

### nub

```haskell
nub :: Eq a => [a] -> [a]
```

- リストを受け取り、重複する要素を削除したリストを返します。
    例:

```haskell
ghci> nub [1,3,4,5,1,8,3,3,6,8,2,2,5,7,3,9,7,5,3,2,6,5]
[1,3,4,5,8,6,2,7,9]
```

### delete

```haskell
delete :: Eq a => a -> [a] -> [a]
```

- 要素とリストを一つづつ受け取り、リストの先頭から受け取った要素と同じ要素を 1 つ削除します。
    例:

```haskell
ghci> delete 'p' "apple"
"aple"
```

### (\\\\)

```haskell
(\\) :: Eq a => [a] -> [a] -> [a] infix 5
```

- s リストを 2 つ受け取り、1 つ目のリストと 2 つ目のリストで対応する要素を先頭から削除します。
    例:

```haskell
ghci> "stringoperation" \\ "aeiou"
"strngprtion"
```

### union

```haskell
union :: Eq a => [a] -> [a] -> [a]
```

- リストを 2 つ受け取り、重複した要素を削除して結合します。
    例:

```haskell
ghci> union "apple" "bananas"
"applebns"
```

### intersect

```haskell
intersect :: Eq a => [a] -> [a] -> [a]
```

- リストを 2 つ受け取り、重複した要素をリストとして返します。
    例:

```haskell
ghci> intersect [1,4,5,3,5,6,7,4,1] [9,6,4,2,5,6,4,2]
[4,5,5,6,4]
```

## リストの順序

### sort

```haskell
sort :: Ord a => [a] -> [a]
```

- リストを受け取り、数値ならば小さい順、文字なら A~Z、`Maybe`ならば`Nothing`が先頭でその後は先の順番に並べ替えたリストを返します。
    例:

```haskell
ghci> sort "orderedlists"
"ddeeilorrsst"
ghci> sort [7,4123,432,4,124,32,14,2,76,58,35]
[2,4,7,14,32,35,58,76,124,432,4123]
ghci> sort [Just 4, Just 6, Nothing]
[Nothing,Just 4,Just 6]
```

### sortOn

```haskell
sortOn :: Ord b => (a -> b) -> [a] -> [a]
```

- 2 引数の関数とペアのリストを受け取り、各タプルに関数を適用した値をもとにソートします。
    例:

```haskell
ghci> sortOn fst [(4,"a"),(1,"c"),(3,"b"),(2,"d")]
[(1,"c"),(2,"d"),(3,"b"),(4,"a")]
ghci> sortOn snd [(4,"a"),(1,"c"),(3,"b"),(2,"d")]
[(4,"a"),(3,"b"),(1,"c"),(2,"d")]
```

一つめの`sortOn`は`fst`を引数にとっているので、タプルの 1 つ目の要素である`4,1,3,2`をもとにソートされます。同じく、2 つ目では`snd`でタプルの 2 つ目の要素の`"a","c","b","d"`を使ってソートされています。

### insert

```haskell
insert :: Ord a => a -> [a] -> [a]
```

- 要素とリストを受け取り、リストの先頭から`sort`の順序になるように要素が差し込まれます。
    例:

```haskell
ghci> insert 5 [8,4,3,2,5]
[5,8,4,3,2,5]
ghci> insert 'r' "quicksort"
"qruicksort"
```

## 一般化された関数

### "By" の処理

### ユーザ提供の等値性の関数

### nubBy

```haskell
nubBy :: (a -> a -> Bool) -> [a] -> [a]
```

- 「2 引数をとって`Bool`型の値を返す関数」とリストをとり、関数が`True`になる値のみをリストとして返します。
    例:

```haskell
ghci> nubBy (\x y -> mod x 5 == mod y 3) [1..10]
[1,2,3,6,9]
```

### deleteBy

```haskell
deleteBy :: (a -> a -> Bool) -> a -> [a] -> [a]
```

- `delete`の条件部を関数として渡して処理できます。
    例:

```haskell
ghci> deleteBy (>=) 'e' "deleteby"
"eleteby"
```

### deleteFirstsBy

```haskell
deleteFirstsBy :: (a -> a -> Bool) -> [a] -> [a] -> [a]
```

- `deleteBy`の要素の部分をリストにして渡すことができます。
    例:

```haskell
ghci> deleteFirstsBy (==) "deletefirstsby" "aeiou"
"dletefrstsby"
```

### unionBy

```haskell
unionBy :: (a -> a -> Bool) -> [a] -> [a] -> [a]
```

- `union`の条件部を 2 引数の関数で指定して、`True`になる要素を削除したリストを取り出せます。
    例:

```haskell
ghci> unionBy (\x y -> x*3==y) [1..5] [6..10]
[1,2,3,4,5,7,8,10]
```

### intersectBy

```haskell
intersectBy :: (a -> a -> Bool) -> [a] -> [a] -> [a]
```

- `intersect`の条件部を 2 引数の関数で指定して、`True`になる要素だけをリストで取り出せます。
    例:

```haskell
ghci> intersectBy (\x y -> x*3==y) [1..10] [1..20]
[1,2,3,4,5,6]
```

### groupBy

```haskell
groupBy :: (a -> a -> Bool) -> [a] -> [[a]]
```

- `group`の条件部を 2 引数の関数の関数に置き換えて分類します。リストの最初の要素と次の要素、2 番目の要素と 3 番目の要素というふうに隣り合った要素が評価されます。
    例:

```haskell
ghci> groupBy (\x y -> x > y) [1,6,4,4,4,5,5,52,32,3,3,42,4,8,7,5,4,3]
[[1],[6,4,4,4,5,5],[52,32,3,3,42,4,8,7,5,4,3]]
```

### ユーザ提供の比較の関数

### sortBy

```haskell
sortBy :: (a -> a -> Ordering) -> [a] -> [a]
```

- `sort`の条件部を 2 引数の関数で指定してソートします。
    例:

```haskell
ghci> sortBy (\(a,_) (b,_) -> compare a b) [(2, "d"), (4, "b"), (1, "a")]
[(1,"a"),(2,"d"),(4,"b")]
```

### insertBy

```haskell
insertBy :: (a -> a -> Ordering) -> a -> [a] -> [a]
```

- `insert`の条件部を 2 引数の関数で指定して要素を差し込むことができます。
    例:

```haskell
ghci> insertBy (\x y -> compare  x y) 4 [7,4,3,5,4,27,5,8,2]
[4,7,4,3,5,4,27,5,8,2]
```

### maximumBy

```haskell
maximumBy :: Foldable t => (a -> a -> Ordering) -> t a -> a
```

- `maximum`の条件部を 2 引数の関数で指定して条件に合う要素を取り出すことができます。
例:

```haskell
ghci> maximumBy (\x y -> compare x y) [6,4,2,5,3,5,2,9]
9
```

### mininumBy

```haskell
minimumBy :: Foldable t => (a -> a -> Ordering) -> t a -> a
```

- `minimum`の条件部を 2 引数の関数で指定して条件に合う要素を取り出すことができます。
例:

```haskell
ghci> minimumBy (\x y -> compare x y) [9,5,4,3,7,3,8,1,7]
1
```

## 「ジェネリックな」処理

`Prelude`内の関数を一般化した関数群です。

### genericLength

```haskell
genericLength :: Num i => [a] -> i
```

- `length`との違いは、`length`の返り値は`Int`型だけど`genericLength`の返り値は`Num`型クラスのインスタンスだという点です。`length`では扱えない大きいリストを扱えます。ただ、`length`と動作は変わりませんが、`length`の方が効率は良いです。

### genericTake

```haskell
genericTake :: Integral i => i -> [a] -> [a]
```

- `take`の一般化バージョンです。`take`の引数は`Int`型ですが、`genericTake`の引数は`Integral`型クラスのインスタンスを指定できます。動作は`take`と同じです。

### genericDrop

```haskell
genericDrop :: Integral i => i -> [a] -> [a]
```

- `drop`の引数は`Int`型ですが、`genericDrop`の引数は`Integral`型クラスのインスタンスです。動作は`drop`と同じです。

### genericSplitAt

```haskell
genericSplitAt :: Integral i => i -> [a] -> ([a], [a])
```

`splitAt`の引数は`Int`型ですが、`genericSplitAt`の第 1 引数は`Integral`型クラスのインスタンスです。動作は`drop`と同じです。

### genericIndex

```haskell
genericIndex :: Integral i => [a] -> i -> a
```

- `!!`の一般化バージョンです。`!!`の第 2 引数は`Int`型ですが`genericIndex`の第 1 引数は`Integral`型クラスのインスタンスです。動作は中置関数では**ない**ことを除いて`!!`と同じです。

### genericReplicate

```haskell
genericReplicate :: Integral i => i -> a -> [a]
```

`replicate`の引数は`Int`型ですが、`genericReplicate`の第 1 引数は`Integral`型クラスのインスタンスです。動作は`replicate`と同じです。

## 感想

2日かけて書いた記事は、気づけば 30000 字に近づいていました。長すぎる記事になってしまいました。[Hackage の公式ページ](https://hackage.haskell.org/package/base-4.12.0.0/docs/Data-List.html)を見ている気持ちで眺めていただければ嬉しいです。面白そうな関数がたくさん並んでいるのを見たときはとても満たされた気持ちになりますね。途中、Hackage にもコード例が載っていない関数があったので、ググったり、GHCi に叱られまくったりしました。でも、知らない関数にデータを与えてその挙動を推測するのはとても興味深いものでした。こういった素晴らしいライブラリを提供してくれている GHC、Haskell に感謝です。

## 参考文献

- [Hackage - Data.List](https://hackage.haskell.org/package/base-4.12.0.0/docs/Data-List.html)
- [畳込関数 fold：foldr と foldl の違い (あるいは fold_right, fold_left）](http://succzerohatenablog.com/entry/2013/12/07/234808)