GHC.List を読んで Haskell のリスト操作をまとめた

Haskell に用意されているリスト操作関数が内部でどのようなことを行なっているのか確認するために、ドキュメントを読んだ。

http://hackage.haskell.org/package/base-4.11.1.0/docs/src/GHC.List.html

```haskell
module GHC.List (
   -- [] (..),          -- built-in syntax; can't be used in export list

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

 ) where
```

以上が List モジュールの識別子である。以下、これらについて見ていくが、必ずしもこの順番通りには紹介しない（例えば `concat` は内部で `foldr` を用いているので `foldr` の後で紹介する）。  
なお、これらの識別子の定義は直接記述されているものもあれば、

```haskell
import Data.Maybe
import GHC.Base
import GHC.Num (Num(..))
import GHC.Integer (Integer)
```

でインポートしたモジュール内に記述されているものもある。

# map

```haskell:map
map :: (a -> b) -> [a] -> [b]
map _ []     = []
map f (x:xs) = f x : map f xs
```

**リストのそれぞれの要素に関数を適用したリストを返す。**
Haskell のリストは連結リストなので、「先頭要素と残りのリスト」（`(先頭要素:[残りのリスト])`）という組み合わせになっている。そこでこの場合は、「先頭要素に関数 f を適用した要素と、残りのリストに map 関数を適用したリスト」を返すと定義してやることで、再帰的に「残りのリスト」が空になるまで全ての要素に f が適用されたリストが返る。

例

```haskell
Prelude> map (* 2) [1..10]
[2,4,6,8,10,12,14,16,18,20]
Prelude> map succ "genius" -- succ で文字コードを1つ増やし、1文字進めている
"hfojvt"
```

# ++

```haskell:++
infixr 5  ++

(++) :: [a] -> [a] -> [a]
(++) []     ys = ys
(++) (x:xs) ys = x : xs ++ ys
```

**リストとリストを結合させる。**優先度5の右結合の（右側が先に処理される）二項演算子である（演算子については http://walk.northcol.org/haskell/operators/ が詳しい）。
``ys``の方を無限長リストにすることもできる。

例

```haskell
Prelude> [1..5] ++ [9..12]
[1,2,3,4,5,9,10,11,12]
Prelude> [1..5] ++ (repeat 9)
[1,2,3,4,5,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9, ...
```

# filter

```haskell:filter
filter :: (a -> Bool) -> [a] -> [a]
filter _pred []    = []
filter pred (x:xs)
  | pred x         = x : filter pred xs
  | otherwise      = filter pred xs
```

**リストのうち条件を満たす要素のみ残したリストを返す。** 再帰的に書かれている。

例

```haskell
Prelude> filter (\n -> n `mod` 3 == 0) [5, 55, 555, 5555, 55555, 555555]
[555,555555]
Prelude> filter (\x -> x `elem` ['i' .. 't']) "I'm stupid." -- iからtまでに含まれるものだけ抜き出す
"mstpi"
```

# errorEmptyList

```haskell:errorEmptyList
errorEmptyList :: String -> a
errorEmptyList fun =
  errorWithoutStackTrace (prel_list_str ++ fun ++ ": empty list")

prel_list_str :: String
prel_list_str = "Prelude."
```

**リストが空だった際にエラー処理をする。**これから登場する関数で利用される。

# head

```haskell:head
head                    :: [a] -> a
head (x:_)              =  x
head []                 =  badHead

badHead :: a
badHead = errorEmptyList "head"
```

**「先頭要素と残りのリスト」から「先頭要素」のみ取り出す。** パターンマッチを使っている。

例

```haskell
Prelude> head [3, 4, 5]
3
Prelude> head "genius"
'g'
Prelude> head []
*** Exception: Prelude.head: empty list
```

# tail

```haskell:tail
tail                    :: [a] -> [a]
tail (_:xs)             =  xs
tail []                 =  errorEmptyList "tail"
```

**「先頭要素と残りのリスト」から「残りのリスト」のみ取り出す。** `head` と同様にパターンマッチを使っている。

例

```haskell
Prelude> tail [3, 4, 5]
[4,5]
Prelude> tail "genius"
"enius"
```

# init

```haskell:init
init                    :: [a] -> [a]
#if defined(USE_REPORT_PRELUDE)
init [x]                =  []
init (x:xs)             =  x : init xs
init []                 =  errorEmptyList "init"
#else
-- eliminate repeated cases
init []                 =  errorEmptyList "init"
init (x:xs)             =  init' x xs
  where init' _ []     = []
        init' y (z:zs) = y : init' z zs
#endif
```

**リストから末尾の要素のみ削除する。**
``#if defined(USE_REPORT_PRELUDE) 〜 #else``というのが謎だが、[この記事](https://ezoeryou.github.io/blog/article/2017-12-26-haskell-coding.html)によると、``#if defined(USE_REPORT_PRELUDE)``は定義通りの実装であり、通常はこちらは使われることはなく、``#else``以下が行われるということらしい。
今回の場合、再帰的に要素を見て最後の一個になったら空のリストを返す、という点で両者は変わりないが、``#else``以下の実装だとよりシンプルに書けるという点で軍配があるということだろうか。

例

```haskell
Prelude> init [3, 4, 5]
[3,4]
Prelude> init "genius"
"geniu"
```

# uncons

```haskell:uncons
uncons                  :: [a] -> Maybe (a, [a])
uncons []               = Nothing
uncons (x:xs)           = Just (x, xs)
```

**リストを先頭要素と末尾のリストに分解し、タプルで返す。** リストが空の場合と空でない場合の双方の処理をくるめた``Maybe``モナドが実装されている。

例

```haskell
Prelude GHC.List> uncons [1 .. 5]
Just (1,[2,3,4,5])
Prelude GHC.List> uncons [1]
Just (1,[])
Prelude GHC.List> uncons []
Nothing

Prelude GHC.List> f x = fmap (fst) (uncons x) -- fst はタプルの先頭要素を取り出す
Prelude GHC.List> f "supernova"
Just 's'
Prelude GHC.List> f ""
Nothing

Prelude GHC.List> g x = maybe "EMPTY LIST!!!" show (f x)
Prelude GHC.List> g [15, 16, 17]
"15"
Prelude GHC.List> g []
"EMPTY LIST!!!"
```

# null

```haskell:null

null                    :: [a] -> Bool
null []                 =  True
null (_:_)              =  False
```

**リストが空ならTrueを、そうでないならFalseを返す。**

# length

```haskell:length
length                  :: [a] -> Int
length xs               = lenAcc xs 0

lenAcc          :: [a] -> Int -> Int
lenAcc []     n = n
lenAcc (_:ys) n = lenAcc ys (n+1)
```

**リストの長さを返す。**
``lenAcc (まだ数えていないリスト) (既に数え終わったリストの長さ)`` という関数を利用している。

例

```haskell
Prelude> length "genius"
6
```

# foldr

```haskell:foldr
foldr            :: (a -> b -> b) -> b -> [a] -> b
foldr k z = go
          where
            go []     = z
            go (y:ys) = y `k` go ys
```
**右から関数を畳み込んでいく。**
``foldr k z (リスト) = go (リスト)``という形に書き換えることで、``(リスト)``の部分に行う処理を定義している。再帰的に書かれており、最終的に``z``に行き着くので、順番としては最初に演算子に``z``が代入され、その結果が演算子に代入され ... という形で処理が行われる。

例

```haskell
Prelude> foldr (-) 10 [3, 3, 4] -- 3 - ( 3 - ( 4 - 10 ))) = -6
-6
Prelude> foldr (-) 10 []
10
```

# foldr1

```haskell:foldr1
foldr1                  :: (a -> a -> a) -> [a] -> a
foldr1 f = go
  where go [x]            =  x
        go (x:xs)         =  f x (go xs)
        go []             =  errorEmptyList "foldr1"
```
**右から関数を畳み込んでいく（ただし演算子に代入する初期値を持たない）。** 基本的に``foldr``とやることは同じだが、``foldr``の``z``の代わりにリストの右端の値を初期値として使うので、そもそもリストが空の場合エラーになる。

例

```haskell
Prelude> foldr1 (-) [3, 3, 4] -- 3 - (3 - 4) = 4
4
Prelude> foldr1 (-) []
*** Exception: Prelude.foldr1: empty list
```

# foldl

```haskell:foldl
foldl :: forall a b. (b -> a -> b) -> b -> [a] -> b
foldl k z0 xs =
  foldr (\(v::a) (fn::b->b) -> oneShot (\(z::b) -> fn (k z v))) (id :: b -> b) xs z0
```
**左から関数を畳み込んでいく。**
この実装が何をやっているのか本当に謎。書籍や様々なサイトを巡回したところ、以下のような状況は見えてきた。

- Haskell は lazy な言語である。すなわち、使われない式は評価されないまま、必要な時になるまで実行されない（``take 5 [無限長のリスト]``で`[無限長のリスト]`のうち最初の 5 つをとるということができるのも`[無限長のリスト]`自体を評価しないからである）。遅延性には様々なメリットがある一方で、未評価な式がたまりやすく、メモリの浪費（スペースリーク）が起こってしまうというデメリットもある。``foldl``も左端から順々に関数をあてはめるので未評価な式がたまってしまう。
- そこで、``oneShot``なる関数を用いてリークしないような工夫がなされている。（https://ghc.haskell.org/trac/ghc/wiki/OneShot にそれらしき記述があるが何をやっているかは不明。詳しい方いたらコメントで教えてください）


例

```haskell
Prelude> foldl (-) 10 [3, 3, 4] -- (((10 - 3) - 3) - 4) = 0
0
Prelude> foldl (-) 10 []
10
```

# foldl'

```haskell:foldl'
foldl'           :: forall a b . (b -> a -> b) -> b -> [a] -> b
foldl' k z0 xs =
  foldr (\(v::a) (fn::b->b) -> oneShot (\(z::b) -> z `seq` fn (k z v))) (id :: b -> b) xs z0
```

**左から関数を畳み込んでいく（ただし先行評価を強制）。**
引数を2つ受け取り、第一引数を評価してから第二引数をそのまま返す関数`seq`を用いることで、上記で述べた`foldl`の遅延評価の問題を解決している。返す値自体は`foldl`と変わらない。

# foldl1

```haskell:foldl1
foldl1                  :: (a -> a -> a) -> [a] -> a
foldl1 f (x:xs)         =  foldl f x xs
foldl1 _ []             =  errorEmptyList "foldl1"
```
**左から関数を畳み込んでいく（ただし演算子に代入する初期値を持たない）。** ``foldr1`` と同様である。

例

```haskell
Prelude> foldl1 (-) [3, 3, 4] -- ((3 - 3) - 4) = -4
-4
Prelude> foldl1 (-) []
*** Exception: Prelude.foldl1: empty list
```

# foldl1'

```haskell:foldl1'
foldl1'                  :: (a -> a -> a) -> [a] -> a
foldl1' f (x:xs)         =  foldl' f x xs
foldl1' _ []             =  errorEmptyList "foldl1'"
```

**左から関数を畳み込んでいく（ただし演算子に代入する初期値を持たない、先行評価を強制）。** ``foldl'``をそのまま利用して実装している。返す値自体は`foldl1`と変わらない。

# scanr

```haskell:scanr
scanr                   :: (a -> b -> b) -> b -> [a] -> [b]
scanr _ q0 []           =  [q0]
scanr f q0 (x:xs)       =  f x q : qs
                           where qs@(q:_) = scanr f q0 xs
```
**右から関数を畳み込んでいく際の結果を順々にまとめたリストを返す。**

例

```haskell
Prelude> scanr (*) 5 [3, 3, 4]
[180,60,20,5] 
Prelude> scanr (*) 5 []
[5]
```

実装はアズパターン`@`を用いていて複雑だが、こういうことになる。

- `scanr (*) 5 [] = [5]`である。
- その先頭`5`と全体`[5]`がアズパターンで捕捉され、`scanr (*) 5 [4] = scanr (*) 5 (4:[]) = (*) 4 5 : [5] = [20, 5]`
- その先頭`20`と全体`[20, 5]`がアズパターンで捕捉され、`scanr (*) 5 [3, 4] = scanr (*) 5 (3:[4]) = (*) 3 20 : [20, 5] = [60, 20, 5]`
- その先頭`60`と全体`[60, 20, 5]`がアズパターンで捕捉され、`scanr (*) 5 [3, 3, 4] = scanr (*) 5 (3:[3, 4]) = (*) 3 60 : [60, 20, 5] = [180, 60, 20, 5]`

# scanr1

```haskell:scanr1
scanr1                  :: (a -> a -> a) -> [a] -> [a]
scanr1 _ []             =  []
scanr1 _ [x]            =  [x]
scanr1 f (x:xs)         =  f x q : qs
                           where qs@(q:_) = scanr1 f xs
```

**右から関数を畳み込んでいく際の結果を順々にまとめたリストを返す（ただし演算子に代入する初期値を持たない）。**

例

```haskell
Prelude> scanr1 (*) [3, 3, 4]
[36,12,4]
Prelude> scanr1 (*) []
[]
```

# scanl

```haskell:scanl
scanl                   :: (b -> a -> b) -> b -> [a] -> [b]
scanl                   = scanlGo
  where
    scanlGo           :: (b -> a -> b) -> b -> [a] -> [b]
    scanlGo f q ls    = q : (case ls of
                               []   -> []
                               x:xs -> scanlGo f (f q x) xs)
```

**左から関数を畳み込んでいく際の結果を順々にまとめたリストを返す。** パターンマッチで再帰させている。

例

```haskell
Prelude> scanl (*) 5 [3, 3, 4]
[5,15,45,180]
Prelude> scanl (*) 5 []
[5]
```

# scanl'

```haskell:scanl'
scanl'           :: (b -> a -> b) -> b -> [a] -> [b]
scanl' = scanlGo'
  where
    scanlGo'           :: (b -> a -> b) -> b -> [a] -> [b]
    scanlGo' f !q ls    = q : (case ls of
                            []   -> []
                            x:xs -> scanlGo' f (f q x) xs)
```

**左から関数を畳み込んでいく際の結果を順々にまとめたリストを返す（ただし先行評価を強制）。** `scanl`とほぼ全く同じ実装だが、`!q`という風に、`q`に正格性フラグ`!`をつけることで、遅延評価によるスペースリークの問題を解決している。

# scanl1

```haskell:scanl1
scanl1                  :: (a -> a -> a) -> [a] -> [a]
scanl1 f (x:xs)         =  scanl f x xs
scanl1 _ []             =  []
```

**左から関数を畳み込んでいく際の結果を順々にまとめたリストを返す（ただし演算子に代入する初期値を持たない）。** 

例

```haskell
Prelude> scanl1 (*) [3, 3, 4]
[3,9,36]
Prelude> scanl1 (*) []
[]
```

# last

```haskell:last
last                    :: [a] -> a
#if defined(USE_REPORT_PRELUDE)
last [x]                =  x
last (_:xs)             =  last xs
last []                 =  errorEmptyList "last"
#else
-- Use foldl to make last a good consumer.
-- This will compile to good code for the actual GHC.List.last.
-- (At least as long it is eta-expaned, otherwise it does not, #10260.)
last xs = foldl (\_ x -> x) lastError xs
lastError :: a
lastError = errorEmptyList "last"
#endif
```

**リストの末尾の要素を抜き出す。**
`#if defined(USE_REPORT_PRELUDE)`の実装はいたってシンプルで、リストの要素が0個ならエラーを返し、1個ならその要素を返し、2個以上なら後の要素だけ取得することを繰り返して再帰的に1個の場合に帰着する。
`#else`の方は分かりづらいが、`\_ x -> x`という後の要素だけ取得する無名関数を、`foldl`を使って順々に畳み込んでいる。畳み込みで最初に行われるのが`(初期値であるlastError) (リストの先頭の要素) -> (リストの先頭の要素)`だが、`foldl`で見たように、リストが空の場合には演算子に代入する初期値のみ返るので、この場合も初期値`lastError`をちゃんと返してくれるというのが面白い。

例

```haskell
Prelude> last [3, 4, 5]
5
Prelude> last "genius"
's'
Prelude> last []
*** Exception: Prelude.last: empty list
```

# !!

```haskell:!!
infixl 9  !!

(!!)                    :: [a] -> Int -> a
#if defined(USE_REPORT_PRELUDE)
xs     !! n | n < 0 =  errorWithoutStackTrace "Prelude.!!: negative index"
[]     !! _         =  errorWithoutStackTrace "Prelude.!!: index too large"
(x:_)  !! 0         =  x
(_:xs) !! n         =  xs !! (n-1)
#else

-- We don't really want the errors to inline with (!!).
-- We may want to fuss around a bit with NOINLINE, and
-- if so we should be careful not to trip up known-bottom
-- optimizations.
tooLarge :: Int -> a
tooLarge _ = errorWithoutStackTrace (prel_list_str ++ "!!: index too large")

negIndex :: a
negIndex = errorWithoutStackTrace $ prel_list_str ++ "!!: negative index"

xs !! n
  | n < 0     = negIndex
  | otherwise = foldr (\x r k -> case k of
                                   0 -> x
                                   _ -> r (k-1)) tooLarge xs n
#endif
```

**リストのインデックスに対応する要素を取得する。**優先度9の左結合の二項演算子である。
`#if defined(USE_REPORT_PRELUDE)`から解読しよう。例えば``[3, 3, 4]``だったら、まず``[3, 3, 4] !! (-2)``のような負のインデックスは論外で最初にエラーで弾く。``[3, 3, 4] !! 0``で最初の要素`3`が取れる。``[3, 3, 4] !! 1 = [3, 4] !! 0``で2番目の要素`3`が取れる。``[3, 3, 4] !! 2 = [3, 4] !! 1 = [4] !! 0``で3番目の要素`4`が取れる。それ以上大きい数を``!!``の後に付けると、再帰的に``= [] !! _``となってエラーパターンに引っかかる。このようにインデックスが大きすぎたということでもちゃんとエラーになってくれる。

`#else`の方はもう少し複雑で、自分のような Haskell 初心者にとっては難しいポイントでもあった。
負のインデックスをエラーで弾く部分は良いとして

```haskell
foldr (\x r k -> case k of
                  0 -> x
                  _ -> r (k-1)) tooLarge xs n
```

これは何をやっているのだろうか。
まず、`foldr` は先ほど見たように

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

という型変数を持つのであった。より一般的には、リストは``Foldable``型クラスのサブクラスであるので、3つ目の引数は``[a]``に限らず、

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

と``Foldable``型クラスで型制約させた`t a`なら何でもOKなのだが、今はリストに限った話をすればよいだろう。
さて、`foldr`以下の`\x r k -> ...`, `tooLarge`, `xs`を、それぞれの引数の型`a -> b -> b`, `b`, `[a]`に対応させてみると、`foldr` は最終的には2つ目の引数`b`と同じ型`b`をとることから、`foldr (\x r k -> ...) tooLarge xs` は `tooLarge :: Int -> a`と同じ`Int -> a`を返す。これに、末尾の`n :: Int`が反応して、答えの `a` が返ってくるというカラクリなのだ。

`\x r k -> ...` を、`a` と `b` から `b`を返すという一種の演算子とみなすところが難しい。これはどういう型変数を持つのかというと、

```haskell
Prelude> :{
Prelude| f x r k = case k of
Prelude|                0     -> x
Prelude|                _     -> r (k-1)
Prelude| :}
Prelude> :t f
f :: (Eq t, Num t) => p -> (t -> p) -> t -> p
```

型変数`t`が`Eq`型クラスと`Num`型クラスで型制約を受けていて、今回は`Int`のことにあたる。したがって、この演算子はリストの要素と`Int -> a`を受け取って、新しく`Int -> a`を返す演算子なのである。

例

```haskell
Prelude> [3, 3, 4] !! (-1)
*** Exception: Prelude.!!: negative index
Prelude> [3, 3, 4] !! 0
3
Prelude> [3, 3, 4] !! 1
3
Prelude> [3, 3, 4] !! 2
4
Prelude> [3, 3, 4] !! 3
*** Exception: Prelude.!!: index too large
```

改めてこの例で考えてみよう。先ほど `\x r k -> ...` を `f` で置き換えたのも活用すると、``n >= 0``の場合、

```haskell
[3, 3, 4] !! n = foldr f tooLarge [3, 3, 4] n
               = f 3 (f 3 (f 4 tooLarge) n
```

である。

- `n　=　0`の場合、`f 3 (f 3 (f 4 tooLarge)) 0`で、`f 3 (f 4 tooLarge)`が何だかよく分からないが、`f`の仕組みを考えると`f 3 (何だかよく分からないもの) 0`は`3`となり、これが一つ目の要素にあたる。
- `n　=　1`の場合、`f`の仕組みから`f 3 (f 3 (f 4 tooLarge)) 1 = f 3 (f 4 tooLarge) 0`で、`f 4 tooLarge`が何だかよく分からないが、`f`の仕組みを考えると`f 3 (何だかよく分からないもの) 0`は`3`となり、これが二つ目の要素にあたる。
- `n　=　2`の場合、`f`の仕組みから`f 3 (f 3 (f 4 tooLarge)) 2 = f 3 (f 4 tooLarge) 1 = f 4 tooLarge 0`は`4`となり、これが三つ目の要素にあたる。
- `n　=　3`の場合、`f`の仕組みから`f 3 (f 3 (f 4 tooLarge)) 3 = f 3 (f 4 tooLarge) 2 = f 4 tooLarge 1 = tooLarge 0`で、エラーになる。`n`がそれ以上の場合も同様。

こうやって「何だかよく分からないもの」とみなして処理しない、ということができるのは、ひとえに Haskell の遅延評価のおかげである。

# iterate

```haskell:iterate
iterate :: (a -> a) -> a -> [a]
iterate f x =  x : iterate f (f x)
```

**関数を順々に適用した無限長リストを返す。**

例

```haskell
Prelude> iterate (*2) 1
[1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536 ...
Prelude> data Week = Mon | Tue | Wed | Thu | Fri | Sat | Sun deriving (Enum, Show)
Prelude> :{
Prelude| f x = case x of Sun      -> Mon
Prelude|                 n        -> succ n
Prelude| :}
Prelude> iterate f Mon
[Mon,Tue,Wed,Thu,Fri,Sat,Sun,Mon,Tue,Wed,Thu,Fri,Sat,Sun,Mon,Tue, ...
```

# iterate'

```haskell:iterate'
iterate' :: (a -> a) -> a -> [a]
iterate' f x =
    let x' = f x
    in x' `seq` (x : iterate' f x')
```

**関数を順々に適用した無限長リストを返す（ただし先行評価を強制）。**
`iterate`にも`scanl`や`foldl`などと同様、遅延評価によるスペースリークの問題がある。`[1,2,4,8,16,32,64,128, ... `とまとめておけば良いものを、いつまでたっても`[1,2*1,2*2*1,2*2*2*1,2*2*2*2*1,2*2*2*2*2*1,2*2*2*2*2*2*1,2*2*2*2*2*2*2*1, ... `の状態で保管してしまうということである。そこで、`foldl'`の実装と同様、第一引数を評価してから第二引数をそのまま返す関数`seq`を用いる。

# repeat

```haskell:repeat
repeat :: a -> [a]
repeat x = xs where xs = x : xs
```

**単一要素から成る無限長リストを返す。**

例

```haskell
Prelude> repeat "hoge"
["hoge","hoge","hoge","hoge","hoge","hoge","hoge", ...
```

# cycle

```haskell:cycle
cycle                   :: [a] -> [a]
cycle []                = errorEmptyList "cycle"
cycle xs                = xs' where xs' = xs ++ xs'
```

**単一リストを繰り返し結合させた無限長リストを返す。**

例

```haskell 
Prelude> cycle "hoge"
"hogehogehogehogehogehogehogehogehogehogehogehogehoge ...
```

# take

```haskell:take
take                   :: Int -> [a] -> [a]
#if defined(USE_REPORT_PRELUDE)
take n _      | n <= 0 =  []
take _ []              =  []
take n (x:xs)          =  x : take (n-1) xs
#else

take n xs | 0 < n     = unsafeTake n xs
          | otherwise = []

-- A version of take that takes the whole list if it's given an argument less
-- than 1.

unsafeTake :: Int -> [a] -> [a]
unsafeTake !_  []     = []
unsafeTake 1   (x: _) = [x]
unsafeTake m   (x:xs) = x : unsafeTake (m - 1) xs
#endif
```

**リストを指定された長さだけ前から抜き出す。**
1つ目の引数が`Int`で、2つ目の引数がリストだが、`Int`が0以下になるかリストが空になるまで再帰的に処理を行っている。
~~`#else`の方も`unsafeTake`という関数を新たに持ち出しているが、1つ目の引数を0ではなく1になるところで止めているという微妙な違いしかないようだ。むしろ、`unsafeTake !_  [] `と正格性フラグをつけることで、``take (3 `div` 0) []``のような場合に`[]`ではなくエラーをきちんと返してくれるところが目新しいか。~~
↑
最初に`n`の値でパターンマッチさせているので、`n`がボトムであればボトムが返ってくるという正格性を有しているはずであり、`unsafeTake`でわざわざ正格性フラグを付けているのは余分ではないのか？詳しい方いたらコメントで教えてください。

例

```haskell
Prelude> take (-2) "genius"
""
Prelude> take 2 "genius"
"ge"
Prelude> take 5 "genius"
"geniu"
Prelude> take 10 "genius"
"genius"
Prelude> take 10 ""
""
```

# replicate

```haskell:replicate
replicate               :: Int -> a -> [a]
replicate n x           =  take n (repeat x)
```

**指定された長さの単一要素から成るリストを返す。**

例

```haskell
Prelude> replicate 3 "Fuwa"
["Fuwa","Fuwa","Fuwa"]
Prelude> replicate (-2) "Fuwa"
[]
```

# drop

```haskell:drop
drop                   :: Int -> [a] -> [a]
#if defined(USE_REPORT_PRELUDE)
drop n xs     | n <= 0 =  xs
drop _ []              =  []
drop n (_:xs)          =  drop (n-1) xs
#else /* hack away */

drop n ls
  | n <= 0     = ls
  | otherwise  = unsafeDrop n ls
  where
    -- A version of drop that drops the whole list if given an argument
    -- less than 1
    unsafeDrop :: Int -> [a] -> [a]
    unsafeDrop !_ []     = []
    unsafeDrop 1  (_:xs) = xs
    unsafeDrop m  (_:xs) = unsafeDrop (m - 1) xs
#endif
```

**リストを指定された長さだけ前から削除する。** ちょうど`take`で取得されたリストの残りの部分を指しており、実装も`take`と似通っている。

```haskell
Prelude> drop (-2) "genius"
"genius"
Prelude> drop 2 "genius"
"nius"
Prelude> drop 5 "genius"
"s"
Prelude> drop 10 "genius"
""
Prelude> drop 10 ""
""
```

# sum

```haskell:sum
sum                     :: (Num a) => [a] -> a
sum                     =  foldl (+) 0
```

**リストの要素の和を返す。**足し算を左からたたみ込んでいるだけ。

例

```haskell
Prelude> sum (take 15 (iterate (*3) 1))
7174453 -- 1 + 3 + 9 + ... + (3^(14))
```

# product

```haskell:product
product                 :: (Num a) => [a] -> a
product                 =  foldl (*) 1
```

**リストの要素の積を返す。**掛け算を左からたたみ込んでいるだけ。

例

```haskell
Prelude> product [1..10]
3628800 -- 10!
```

# maximum

```haskell:maximum
maximum                 :: (Ord a) => [a] -> a
maximum []              =  errorEmptyList "maximum"
maximum xs              =  foldl1 max xs
```

**リストの要素の最大値を返す。**
2つの引数のうち大きいものを返す`max`自体は`Ord`型クラス（大小比較のためのクラス）のメソッドとして定義されていて、これを`Ord`型クラスで型制約されている型の要素から成るリストにおいて、左からたたみ込んでいる。

例

```haskell
Prelude> maximum "maximum"
'x' -- 文字コードが最大の文字が返される
```

# minimum

```haskell:minimum
minimum                 :: (Ord a) => [a] -> a
minimum []              =  errorEmptyList "minimum"
minimum xs              =  foldl1 min xs
```

**リストの要素の最小値を返す。** `maximum`と同様。

例

```haskell
Prelude> minimum "minimum"
'i' -- 文字コードが最小の文字が返される
```

# splitAt

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

#if defined(USE_REPORT_PRELUDE)
splitAt n xs           =  (take n xs, drop n xs)
#else
splitAt n ls
  | n <= 0 = ([], ls)
  | otherwise          = splitAt' n ls
    where
        splitAt' :: Int -> [a] -> ([a], [a])
        splitAt' _  []     = ([], [])
        splitAt' 1  (x:xs) = ([x], xs)
        splitAt' m  (x:xs) = (x:xs', xs'')
          where
            (xs', xs'') = splitAt' (m - 1) xs
#endif /* USE_REPORT_PRELUDE */
```

**リストを指定された長さで分割し、タプルで返す。**
定義通りの実装である`#if defined(USE_REPORT_PRELUDE)`の方を見れば、これが`take`と`drop`を両方やっているだけだというのが一目瞭然である。
`#else`の方では、タプルの左側と右側の両方の要素を再帰的にいじるので、`where (xs', xs'') 〜`という書き方が必要になることがわかる。

例

```haskell
Prelude> splitAt (-2) "genius"
("","genius")
Prelude> splitAt 2 "genius"
("ge","nius")
Prelude> splitAt 5 "genius"
("geniu","s")
Prelude> splitAt 10 "genius"
("genius","")
Prelude> splitAt 10 ""
("","")
``` 

# takeWhile

```haskell:takeWhile
takeWhile               :: (a -> Bool) -> [a] -> [a]
takeWhile _ []          =  []
takeWhile p (x:xs)
            | p x       =  x : takeWhile p xs
            | otherwise =  []
```

**リストのうち条件を満たす要素からなる先頭列を返す。**
``filter``とそっくりだが、`otherwise`以下が異なる。`filter`では`otherwise`でも再帰させているのに対して、`takeWhile`では`otherwise`で再帰が止まる。

例

```haskell
Prelude> takeWhile (\n -> n `mod` 3 == 0) [5, 55, 555, 5555, 55555, 555555]
[]
Prelude> takeWhile (\n -> n `mod` 3 == 0) [555555, 555, 5]
[555555,555]
Prelude> takeWhile (< 10000000000000000000) (iterate (* 3) 3)
[3,9,27,81,243,729,2187,6561,19683,59049,177147,531441,1594323,4782969,14348907,43046721,129140163,387420489,1162261467,3486784401,10460353203,31381059609,94143178827,282429536481,847288609443,2541865828329,7625597484987,22876792454961,68630377364883,205891132094649,617673396283947,1853020188851841,5559060566555523,16677181699666569,50031545098999707,150094635296999121,450283905890997363,1350851717672992089,4052555153018976267]
-- 3の階乗のうち、10000000000000000000未満のもの
```

# dropWhile

```haskell:dropWhile
dropWhile               :: (a -> Bool) -> [a] -> [a]
dropWhile _ []          =  []
dropWhile p xs@(x:xs')
            | p x       =  dropWhile p xs'
            | otherwise =  xs
```

**リストのうち条件を満たす要素からなる先頭列を取り除いたリストを返す。**
`take`に対する`drop`の関係と`takeWhile`に対する`dropWhile`の関係は同じである。

例

```haskell
Prelude> dropWhile (\n -> n `mod` 3 == 0) [5, 55, 555, 5555, 55555, 555555]
[5,55,555,5555,55555,555555]
Prelude> dropWhile (\n -> n `mod` 3 == 0) [555555, 555, 5]
[5]
Prelude> dropWhile (< 10000000000000000000) (iterate (* 3) 3)
[12157665459056928801,36472996377170786403,109418989131512359209, ...
-- 3の階乗のうち、10000000000000000000以上のもの
```

# span

```haskell:span
span                    :: (a -> Bool) -> [a] -> ([a],[a])
span _ xs@[]            =  (xs, xs)
span p xs@(x:xs')
         | p x          =  let (ys,zs) = span p xs' in (x:ys,zs)
         | otherwise    =  ([],xs)
```

**リストを、リストのうち条件を満たす要素からなる先頭列とその残りからなるタプルとして返す。**
`take, drop`に対する`splitAt`の関係と`takeWhile, dropWhile`に対する`span`の関係は同じである。

例

```haskell
Prelude> span (\n -> n `mod` 3 == 0) [5, 55, 555, 5555, 55555, 555555]
([],[5,55,555,5555,55555,555555])
Prelude> span (\n -> n `mod` 3 == 0) [555555, 555, 5]
([555555,555],[5])
Prelude> span (< 10000000000000000000) (iterate (* 3) 3)
([3,9,27,81,243,729,2187,6561,19683,59049,177147,531441,1594323,4782969,14348907,43046721,129140163,387420489,1162261467,3486784401,10460353203,31381059609,94143178827,282429536481,847288609443,2541865828329,7625597484987,22876792454961,68630377364883,205891132094649,617673396283947,1853020188851841,5559060566555523,16677181699666569,50031545098999707,150094635296999121,450283905890997363,1350851717672992089,4052555153018976267],[12157665459056928801,36472996377170786403,109418989131512359209, ...
Prelude> span (> 10) []
([],[])
```

# break

```haskell:break
break                   :: (a -> Bool) -> [a] -> ([a],[a])
#if defined(USE_REPORT_PRELUDE)
break p                 =  span (not . p)
#else
-- HBC version (stolen)
break _ xs@[]           =  (xs, xs)
break p xs@(x:xs')
           | p x        =  ([],xs)
           | otherwise  =  let (ys,zs) = break p xs' in (x:ys,zs)
#endif
```
**リストを、リストのうち条件を満たさない要素からなる先頭列とその残りからなるタプルとして返す。**
`not`はその名の通り`True`なら`False`を、`False`なら`True`を返す`Bool -> Bool`という型の関数で、`#if defined(USE_REPORT_PRELUDE)`では与えられた条件式`p`との合成関数として用いられ、`span`に代入されている。
`#else`の方では、`span`のパターンマッチの式を`p x`の場合と`otherwise`の場合でひっくり返すことによって実装している。

例

```haskell
Prelude> break (\n -> n `mod` 3 == 0) [5, 55, 555, 5555, 55555, 555555]
([5,55],[555,5555,55555,555555])
Prelude> break (\n -> n `mod` 3 == 0) [555555, 555, 5]
([],[555555,555,5])
Prelude> break (>= 10000000000000000000) (iterate (* 3) 3)
([3,9,27,81,243,729,2187,6561,19683,59049,177147,531441,1594323,4782969,14348907,43046721,129140163,387420489,1162261467,3486784401,10460353203,31381059609,94143178827,282429536481,847288609443,2541865828329,7625597484987,22876792454961,68630377364883,205891132094649,617673396283947,1853020188851841,5559060566555523,16677181699666569,50031545098999707,150094635296999121,450283905890997363,1350851717672992089,4052555153018976267],[12157665459056928801,36472996377170786403,109418989131512359209, ...
Prelude> break (> 10) []
([],[])
```

# reverse

```haskell:reverse
reverse                 :: [a] -> [a]
#if defined(USE_REPORT_PRELUDE)
reverse                 =  foldl (flip (:)) []
#else
reverse l =  rev l []
  where
    rev []     a = a
    rev (x:xs) a = rev xs (x:a)
#endif
```

**リストを逆向きに並び替える。**
``#if defined(USE_REPORT_PRELUDE)``では`flip`という関数を用いている。これは`GHC.base`で定義されていて、引数を2つとる関数の引数の順番を入れ替える関数である。例えば

```haskell
Prelude> (/) 5 2 -- 5 / 2
2.5
Prelude> flip (/) 5 2 -- 2 / 5 
0.4
Prelude> (++) "konni" "chiwa"
"konnichiwa"
Prelude> flip (++) "konni" "chiwa"
"chiwakonni"
```

である。
これを用いると、`flip (:) [すでに作ったリスト] 新しく取得するリストの要素 = 新しく取得するリストの要素 : [すでに作ったリスト]`　が次に作られるリストになるので、これを元のリストの要素に前から適用すると、逆向きのリストが完成する。
`#else`の場合は、`reverse [1, 2, 3] = rev [1, 2, 3] [] = rev [2, 3] [1] = rev [3] [2, 1] = rev [] [3, 2, 1] = [3, 2, 1]`という要領だ。
`flip`という既存の入れ替え関数をうまく応用するか、新しく`rev`という関数を作ってしまうか、の差であろう。

例

```haskell
Prelude> reverse [3, 3, 4]
[4,3,3]
Prelude> reverse "genius"
"suineg"
```

# and

```haskell:and
and                     :: [Bool] -> Bool
#if defined(USE_REPORT_PRELUDE)
and                     =  foldr (&&) True
#else
and []          =  True
and (x:xs)      =  x && and xs

#endif
```

**リストの要素が全てTrueの場合のみTrueを返す。一つでもFalseがあればFalseを返す。**
`#if defined(USE_REPORT_PRELUDE)`の方では`foldr`を使っているため無限長リストには対応できないが、`#else`の方では左から参照しているため無限長リストに対応できる部分がポイントである。

例

```haskell
Prelude> map (> 4) [1..7]
[False,False,False,False,True,True,True]
Prelude> and (map (> 4) [1..7])
False
Prelude> map (> 0) [1..7]
[True,True,True,True,True,True,True]
Prelude> and (map (> 0) [1..7])
True
Prelude> and (map (< 10000000000000000000) (iterate (* 3) 3))
False -- 3　の階乗もいつかは10000000000000000000を超えるので
```

# or

```haskell:or
or                      :: [Bool] -> Bool
#if defined(USE_REPORT_PRELUDE)
or                      =  foldr (||) False
#else
or []           =  False
or (x:xs)       =  x || or xs

#endif
```

**リストの要素が全てFalseの場合のみFalseを返す。一つでもTrueがあればTrueを返す。**
`#if defined(USE_REPORT_PRELUDE)`の方では`foldr`を使っているため無限長リストには対応できないが、`#else`の方では左から参照しているため無限長リストに対応できる部分がポイントである。

例

```haskell
Prelude> map (< 4) [1..7]
[True,True,True,False,False,False,False]
Prelude> or (map (< 4) [1..7])
True
Prelude> map (< 0) [1..7]
[False,False,False,False,False,False,False]
Prelude> or (map (< 0) [1..7])
False
Prelude> or (map (> 10000000000000000000) (iterate (* 3) 3))
True -- 3　の階乗もいつかは10000000000000000000を超えるので
```

# all

```haskell:all
all                     :: (a -> Bool) -> [a] -> Bool
#if defined(USE_REPORT_PRELUDE)
all p                   =  and . map p
#else
all _ []        =  True
all p (x:xs)    =  p x && all p xs

#endif
```

**リストの要素が全て条件式を満たす場合のみTrueを返す。一つでも満たさない要素があればFalseを返す。**
`and`と`map`の合成関数。

例

```haskell
Prelude> all (> 4) [1..7]
False
Prelude> all (> 0) [1..7]
True
Prelude> all (< 10000000000000000000) (iterate (* 3) 3)
False
```

# any 

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

#if defined(USE_REPORT_PRELUDE)
any p                   =  or . map p
#else
any _ []        = False
any p (x:xs)    = p x || any p xs

#endif
```

**リストの要素が全て条件式を満たさない場合のみFalseを返す。一つでも満たす要素があればTrueを返す。**
`or`と`map`の合成関数。

例

```haskell:any
Prelude> any (< 4) [1..7]
True
Prelude> any (< 0) [1..7]
False
Prelude> any (> 10000000000000000000) (iterate (* 3) 3)
True
```

# elem

```haskell:elem
infix  4 `elem`

elem                    :: (Eq a) => a -> [a] -> Bool
#if defined(USE_REPORT_PRELUDE)
elem x                  =  any (== x)
#else
elem _ []       = False
elem x (y:ys)   = x==y || elem x ys

#endif
```

**与えられた要素がリストに含まれていればTrueを返し、そうでなければFalseを返す。**優先度4の非結合の二項演算子。
「含まれているかどうか」というのを`any`で表現できる。

例

```haskell
Prelude> 'e' `elem` "genius"
True
Prelude> 'a' `elem` "genius"
False
```

# notElem

```haskell:notElem
infix  4 `notElem`

notElem                 :: (Eq a) => a -> [a] -> Bool
#if defined(USE_REPORT_PRELUDE)
notElem x               =  all (/= x)
#else
notElem _ []    =  True
notElem x (y:ys)=  x /= y && notElem x ys

#endif
```
**与えられた要素がリストに含まれていなければTrueを返し、そうでなければFalseを返す。**優先度4の非結合の二項演算子。
「含まれていないかどうか」というのを`all`で表現できる。

例

```haskell
Prelude> 'e' `notElem` "genius"
False
Prelude> 'a' `notElem` "genius"
True
```

# lookup

```haskell:lookup
lookup                  :: (Eq a) => a -> [(a,b)] -> Maybe b
lookup _key []          =  Nothing
lookup  key ((x,y):xys)
    | key == x          =  Just y
    | otherwise         =  lookup key xys
```

**連想配列で、指定されたキーに対応する値を返す。**`Maybe`モナドで返される。

例

```haskell
Prelude> ageList = [("Aoi", 15), ("Hinata", 15), ("Kaede", 16), ("Kokona", 13)] 
Prelude> lookup "Aoi" ageList
Just 15
Prelude> lookup "Honoka" ageList
Nothing
Prelude> f name = maybe "unknown" show (lookup name ageList)
Prelude> f "Kokona"
"13"
Prelude> f "Yuka"
"unknown"
```

# concat

```haskell:concat
concat :: [[a]] -> [a]
concat = foldr (++) []
```

**複数のリストを一つのリストにまとめる。**

例

```haskell
Prelude> concat ["Encouragement", " ", "of", " ", "Climb"]
"Encouragement of Climb"
```

# concatMap

```haskell:concatMap
concatMap               :: (a -> [b]) -> [a] -> [b]
concatMap f             =  foldr ((++) . f) []
```

**リストの要素それぞれに関数を作用させて、できた複数のリストを一つのリストにまとめる。**

例

```haskell
Prelude> concatMap (replicate 5) [1, 2, 3]
[1,1,1,1,1,2,2,2,2,2,3,3,3,3,3]
```

# zip

```haskell:zip
zip :: [a] -> [b] -> [(a,b)]
zip []     _bs    = []
zip _as    []     = []
zip (a:as) (b:bs) = (a,b) : zip as bs
```

**2つのリストをまとめ、1つのタプルから成るリストにする。**実装から分かる通り、2つのうち長い方の余った部分は削除される。

例

```haskell
Prelude> zip ['a'..'g'] [1..3]
[('a',1),('b',2),('c',3)]
Prelude> zip ['a'..'g'] [1..7]
[('a',1),('b',2),('c',3),('d',4),('e',5),('f',6),('g',7)]
Prelude> zip ['a'..'g'] [1..10]
[('a',1),('b',2),('c',3),('d',4),('e',5),('f',6),('g',7)]
```

# zip3

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

zip3 (a:as) (b:bs) (c:cs) = (a,b,c) : zip3 as bs cs
zip3 _      _      _      = []
```
**3つのリストをまとめ、1つのタプルから成るリストにする。**
ワイルドカードを使っているが、これは3つのうち少なくとも1つが`(a:as)`のような形式で表示できなくなった場合、すなわちリストが空になった場合である。

例

```haskell
Prelude> zip3 ['a'..'g'] [1..3] (iterate (*2) 2)
[('a',1,2),('b',2,4),('c',3,8)]
Prelude> zip3 ['a'..'g'] [1..7] (iterate (*2) 2)
[('a',1,2),('b',2,4),('c',3,8),('d',4,16),('e',5,32),('f',6,64),('g',7,128)]
Prelude> zip3 ['a'..'z'] [1..100] (iterate (*2) 2)
[('a',1,2),('b',2,4),('c',3,8), ... ,('z',26,67108864)]
```

# zipWith

```haskell:zipWith
zipWith :: (a->b->c) -> [a]->[b]->[c]
zipWith f = go
  where
    go [] _ = []
    go _ [] = []
    go (x:xs) (y:ys) = f x y : go xs ys
```

**2つのリストの要素から1つずつそれぞれ値を取得し関数を作用させて、結果をまとめたリストを返す。**

例

```haskell
Prelude> zipWith (*) [3, 4, 5] [8, 9, 10]
[24,36,50]
Prelude> zipWith (+) [1..10] (iterate (* 0.1) 0.1)
[1.1,2.01,3.001,4.0001,5.00001,6.000001,7.0000001,8.00000001,9.000000001,10.0000000001]
```

# zipWith3

```haskell:zipWith3
zipWith3                :: (a->b->c->d) -> [a]->[b]->[c]->[d]
zipWith3 z = go
  where
    go (a:as) (b:bs) (c:cs) = z a b c : go as bs cs
    go _ _ _                = []
```

**3つのリストの要素から1つずつそれぞれ値を取得し関数を作用させて、結果をまとめたリストを返す。**

例

```haskell
Prelude> f a b c = a * b + c
Prelude> zipWith3 f [1..10] [11..20] (iterate (* 0.1) 0.1)
[11.1,24.01,39.001,56.0001,75.00001,96.000001,119.0000001,144.00000001,171.000000001,200.0000000001]
```

# unzip

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

unzip    =  foldr (\(a,b) ~(as,bs) -> (a:as,b:bs)) ([],[])
```

**タプルから成るリストを2つのリストに分解する。**
`~`というのは左右が同じ型であることをチェックするのに役立つらしい。そうしないと`a:as,b:bs`の部分で初めて`a`と`as`, `b`と`bs`が同じ型であることをチェックするということになるのだろうか。

例

```haskell
Prelude> unzip [('a',1),('b',2),('c',3),('d',4),('e',5),('f',6),('g',7)]
("abcdefg",[1,2,3,4,5,6,7])
```

# unzip3

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

unzip3   =  foldr (\(a,b,c) ~(as,bs,cs) -> (a:as,b:bs,c:cs))
                  ([],[],[])
```

**タプルから成るリストを3つのリストに分解する。**

例

```haskell
Prelude> unzip3 [('a',1,2),('b',2,4),('c',3,8),('d',4,16),('e',5,32),('f',6,64),('g',7,128)]
("abcdefg",[1,2,3,4,5,6,7],[2,4,8,16,32,64,128])
```