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 の後で紹介する）。
なお、これらの識別子の定義は直接記述されているものもあれば、
import Data.Maybe
import GHC.Base
import GHC.Num (Num(..))
import GHC.Integer (Integer)
でインポートしたモジュール内に記述されているものもある。
map
map :: (a -> b) -> [a] -> [b]
map _ [] = []
map f (x:xs) = f x : map f xs
リストのそれぞれの要素に関数を適用したリストを返す。
Haskell のリストは連結リストなので、「先頭要素と残りのリスト」（(先頭要素:[残りのリスト])）という組み合わせになっている。そこでこの場合は、「先頭要素に関数 f を適用した要素と、残りのリストに map 関数を適用したリスト」を返すと定義してやることで、再帰的に「残りのリスト」が空になるまで全ての要素に f が適用されたリストが返る。
例
Prelude> map (* 2) [1..10]
[2,4,6,8,10,12,14,16,18,20]
Prelude> map succ "genius" -- succ で文字コードを1つ増やし、1文字進めている
"hfojvt"
++
infixr 5 ++
(++) :: [a] -> [a] -> [a]
(++) [] ys = ys
(++) (x:xs) ys = x : xs ++ ys
リストとリストを結合させる。優先度5の右結合の（右側が先に処理される）二項演算子である（演算子については http://walk.northcol.org/haskell/operators/ が詳しい）。
ysの方を無限長リストにすることもできる。
例
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
filter :: (a -> Bool) -> [a] -> [a]
filter _pred [] = []
filter pred (x:xs)
| pred x = x : filter pred xs
| otherwise = filter pred xs
リストのうち条件を満たす要素のみ残したリストを返す。 再帰的に書かれている。
例
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
errorEmptyList :: String -> a
errorEmptyList fun =
errorWithoutStackTrace (prel_list_str ++ fun ++ ": empty list")
prel_list_str :: String
prel_list_str = "Prelude."
リストが空だった際にエラー処理をする。これから登場する関数で利用される。
head
head :: [a] -> a
head (x:_) = x
head [] = badHead
badHead :: a
badHead = errorEmptyList "head"
「先頭要素と残りのリスト」から「先頭要素」のみ取り出す。 パターンマッチを使っている。
例
Prelude> head [3, 4, 5]
3
Prelude> head "genius"
'g'
Prelude> head []
*** Exception: Prelude.head: empty list
tail
tail :: [a] -> [a]
tail (_:xs) = xs
tail [] = errorEmptyList "tail"
「先頭要素と残りのリスト」から「残りのリスト」のみ取り出す。 head と同様にパターンマッチを使っている。
例
Prelude> tail [3, 4, 5]
[4,5]
Prelude> tail "genius"
"enius"
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というのが謎だが、この記事によると、#if defined(USE_REPORT_PRELUDE)は定義通りの実装であり、通常はこちらは使われることはなく、#else以下が行われるということらしい。
今回の場合、再帰的に要素を見て最後の一個になったら空のリストを返す、という点で両者は変わりないが、#else以下の実装だとよりシンプルに書けるという点で軍配があるということだろうか。
例
Prelude> init [3, 4, 5]
[3,4]
Prelude> init "genius"
"geniu"
uncons
uncons :: [a] -> Maybe (a, [a])
uncons [] = Nothing
uncons (x:xs) = Just (x, xs)
リストを先頭要素と末尾のリストに分解し、タプルで返す。 リストが空の場合と空でない場合の双方の処理をくるめたMaybeモナドが実装されている。
例
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
null :: [a] -> Bool
null [] = True
null (_:_) = False
リストが空ならTrueを、そうでないならFalseを返す。
length
length :: [a] -> Int
length xs = lenAcc xs 0
lenAcc :: [a] -> Int -> Int
lenAcc [] n = n
lenAcc (_:ys) n = lenAcc ys (n+1)
リストの長さを返す。
lenAcc (まだ数えていないリスト) (既に数え終わったリストの長さ) という関数を利用している。
例
Prelude> length "genius"
6
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が代入され、その結果が演算子に代入され ... という形で処理が行われる。
例
Prelude> foldr (-) 10 [3, 3, 4] -- 3 - ( 3 - ( 4 - 10 ))) = -6
-6
Prelude> foldr (-) 10 []
10
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の代わりにリストの右端の値を初期値として使うので、そもそもリストが空の場合エラーになる。
例
Prelude> foldr1 (-) [3, 3, 4] -- 3 - (3 - 4) = 4
4
Prelude> foldr1 (-) []
*** Exception: Prelude.foldr1: empty list
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 にそれらしき記述があるが何をやっているかは不明。詳しい方いたらコメントで教えてください）
例
Prelude> foldl (-) 10 [3, 3, 4] -- (((10 - 3) - 3) - 4) = 0
0
Prelude> foldl (-) 10 []
10
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
foldl1 :: (a -> a -> a) -> [a] -> a
foldl1 f (x:xs) = foldl f x xs
foldl1 _ [] = errorEmptyList "foldl1"
左から関数を畳み込んでいく（ただし演算子に代入する初期値を持たない）。 foldr1 と同様である。
例
Prelude> foldl1 (-) [3, 3, 4] -- ((3 - 3) - 4) = -4
-4
Prelude> foldl1 (-) []
*** Exception: Prelude.foldl1: empty list
foldl1'
foldl1' :: (a -> a -> a) -> [a] -> a
foldl1' f (x:xs) = foldl' f x xs
foldl1' _ [] = errorEmptyList "foldl1'"
左から関数を畳み込んでいく（ただし演算子に代入する初期値を持たない、先行評価を強制）。 foldl'をそのまま利用して実装している。返す値自体はfoldl1と変わらない。
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
右から関数を畳み込んでいく際の結果を順々にまとめたリストを返す。
例
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
scanr1 :: (a -> a -> a) -> [a] -> [a]
scanr1 _ [] = []
scanr1 _ [x] = [x]
scanr1 f (x:xs) = f x q : qs
where qs@(q:_) = scanr1 f xs
右から関数を畳み込んでいく際の結果を順々にまとめたリストを返す（ただし演算子に代入する初期値を持たない）。
例
Prelude> scanr1 (*) [3, 3, 4]
[36,12,4]
Prelude> scanr1 (*) []
[]
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)
左から関数を畳み込んでいく際の結果を順々にまとめたリストを返す。 パターンマッチで再帰させている。
例
Prelude> scanl (*) 5 [3, 3, 4]
[5,15,45,180]
Prelude> scanl (*) 5 []
[5]
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
scanl1 :: (a -> a -> a) -> [a] -> [a]
scanl1 f (x:xs) = scanl f x xs
scanl1 _ [] = []
左から関数を畳み込んでいく際の結果を順々にまとめたリストを返す（ただし演算子に代入する初期値を持たない）。
例
Prelude> scanl1 (*) [3, 3, 4]
[3,9,36]
Prelude> scanl1 (*) []
[]
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をちゃんと返してくれるというのが面白い。
例
Prelude> last [3, 4, 5]
5
Prelude> last "genius"
's'
Prelude> last []
*** Exception: Prelude.last: empty list
!!
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 初心者にとっては難しいポイントでもあった。
負のインデックスをエラーで弾く部分は良いとして
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を返すという一種の演算子とみなすところが難しい。これはどういう型変数を持つのかというと、
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を返す演算子なのである。
例
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の場合、
[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
iterate :: (a -> a) -> a -> [a]
iterate f x = x : iterate f (f x)
関数を順々に適用した無限長リストを返す。
例
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'
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
repeat :: a -> [a]
repeat x = xs where xs = x : xs
単一要素から成る無限長リストを返す。
例
Prelude> repeat "hoge"
["hoge","hoge","hoge","hoge","hoge","hoge","hoge", ...
cycle
cycle :: [a] -> [a]
cycle [] = errorEmptyList "cycle"
cycle xs = xs' where xs' = xs ++ xs'
単一リストを繰り返し結合させた無限長リストを返す。
例
Prelude> cycle "hoge"
"hogehogehogehogehogehogehogehogehogehogehogehogehoge ...
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でわざわざ正格性フラグを付けているのは余分ではないのか？詳しい方いたらコメントで教えてください。
例
Prelude> take (-2) "genius"
""
Prelude> take 2 "genius"
"ge"
Prelude> take 5 "genius"
"geniu"
Prelude> take 10 "genius"
"genius"
Prelude> take 10 ""
""
replicate
replicate :: Int -> a -> [a]
replicate n x = take n (repeat x)
指定された長さの単一要素から成るリストを返す。
例
Prelude> replicate 3 "Fuwa"
["Fuwa","Fuwa","Fuwa"]
Prelude> replicate (-2) "Fuwa"
[]
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と似通っている。
Prelude> drop (-2) "genius"
"genius"
Prelude> drop 2 "genius"
"nius"
Prelude> drop 5 "genius"
"s"
Prelude> drop 10 "genius"
""
Prelude> drop 10 ""
""
sum
sum :: (Num a) => [a] -> a
sum = foldl (+) 0
リストの要素の和を返す。足し算を左からたたみ込んでいるだけ。
例
Prelude> sum (take 15 (iterate (*3) 1))
7174453 -- 1 + 3 + 9 + ... + (3^(14))
product
product :: (Num a) => [a] -> a
product = foldl (*) 1
リストの要素の積を返す。掛け算を左からたたみ込んでいるだけ。
例
Prelude> product [1..10]
3628800 -- 10!
maximum
maximum :: (Ord a) => [a] -> a
maximum [] = errorEmptyList "maximum"
maximum xs = foldl1 max xs
リストの要素の最大値を返す。
2つの引数のうち大きいものを返すmax自体はOrd型クラス（大小比較のためのクラス）のメソッドとして定義されていて、これをOrd型クラスで型制約されている型の要素から成るリストにおいて、左からたたみ込んでいる。
例
Prelude> maximum "maximum"
'x' -- 文字コードが最大の文字が返される
minimum
minimum :: (Ord a) => [a] -> a
minimum [] = errorEmptyList "minimum"
minimum xs = foldl1 min xs
リストの要素の最小値を返す。 maximumと同様。
例
Prelude> minimum "minimum"
'i' -- 文字コードが最小の文字が返される
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'') 〜という書き方が必要になることがわかる。
例
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
takeWhile :: (a -> Bool) -> [a] -> [a]
takeWhile _ [] = []
takeWhile p (x:xs)
| p x = x : takeWhile p xs
| otherwise = []
リストのうち条件を満たす要素からなる先頭列を返す。
filterとそっくりだが、otherwise以下が異なる。filterではotherwiseでも再帰させているのに対して、takeWhileではotherwiseで再帰が止まる。
例
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
dropWhile :: (a -> Bool) -> [a] -> [a]
dropWhile _ [] = []
dropWhile p xs@(x:xs')
| p x = dropWhile p xs'
| otherwise = xs
リストのうち条件を満たす要素からなる先頭列を取り除いたリストを返す。
takeに対するdropの関係とtakeWhileに対するdropWhileの関係は同じである。
例
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
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の関係は同じである。
例
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
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の場合でひっくり返すことによって実装している。
例
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
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つとる関数の引数の順番を入れ替える関数である。例えば
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という関数を作ってしまうか、の差であろう。
例
Prelude> reverse [3, 3, 4]
[4,3,3]
Prelude> reverse "genius"
"suineg"
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の方では左から参照しているため無限長リストに対応できる部分がポイントである。
例
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
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の方では左から参照しているため無限長リストに対応できる部分がポイントである。
例
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
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の合成関数。
例
Prelude> all (> 4) [1..7]
False
Prelude> all (> 0) [1..7]
True
Prelude> all (< 10000000000000000000) (iterate (* 3) 3)
False
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の合成関数。
例
Prelude> any (< 4) [1..7]
True
Prelude> any (< 0) [1..7]
False
Prelude> any (> 10000000000000000000) (iterate (* 3) 3)
True
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で表現できる。
例
Prelude> 'e' `elem` "genius"
True
Prelude> 'a' `elem` "genius"
False
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で表現できる。
例
Prelude> 'e' `notElem` "genius"
False
Prelude> 'a' `notElem` "genius"
True
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モナドで返される。
例
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
concat :: [[a]] -> [a]
concat = foldr (++) []
複数のリストを一つのリストにまとめる。
例
Prelude> concat ["Encouragement", " ", "of", " ", "Climb"]
"Encouragement of Climb"
concatMap
concatMap :: (a -> [b]) -> [a] -> [b]
concatMap f = foldr ((++) . f) []
リストの要素それぞれに関数を作用させて、できた複数のリストを一つのリストにまとめる。
例
Prelude> concatMap (replicate 5) [1, 2, 3]
[1,1,1,1,1,2,2,2,2,2,3,3,3,3,3]
zip
zip :: [a] -> [b] -> [(a,b)]
zip [] _bs = []
zip _as [] = []
zip (a:as) (b:bs) = (a,b) : zip as bs
2つのリストをまとめ、1つのタプルから成るリストにする。実装から分かる通り、2つのうち長い方の余った部分は削除される。
例
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
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)のような形式で表示できなくなった場合、すなわちリストが空になった場合である。
例
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
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つずつそれぞれ値を取得し関数を作用させて、結果をまとめたリストを返す。
例
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
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つずつそれぞれ値を取得し関数を作用させて、結果をまとめたリストを返す。
例
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
unzip :: [(a,b)] -> ([a],[b])
unzip = foldr (\(a,b) ~(as,bs) -> (a:as,b:bs)) ([],[])
タプルから成るリストを2つのリストに分解する。
~というのは左右が同じ型であることをチェックするのに役立つらしい。そうしないとa:as,b:bsの部分で初めてaとas, bとbsが同じ型であることをチェックするということになるのだろうか。
例
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
unzip3 :: [(a,b,c)] -> ([a],[b],[c])
unzip3 = foldr (\(a,b,c) ~(as,bs,cs) -> (a:as,b:bs,c:cs))
([],[],[])
タプルから成るリストを3つのリストに分解する。
例
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])