配列と違って注意しないといけないのは，リストは "n 番目の要素を取り出す" みたいな処理が不得意という点です．配列ではこの操作は一瞬ですが，リストの場合には，列を先頭から順番に辿っていかなければならないため，時間がかかります．ただし，Haskell ではインデックスを指定して要素を取り出す操作はあまり書かないため，このことはそれほど問題になりません．

2. Haskell のリスト

Haskell では，次の 2 通りの方法でリストを書けます．構文上はまるで見た目が違いますが，どちらも同一のリストを表します．

1 : 2 : 3 : []   -- cons 構成子による書き方
[1, 2, 3]        -- リストリテラルによる書き方

ここで，記号 (:) :: a -> [a] -> [a] は "cons 構成子" と呼ばれます． x : xs と書くと，これは先頭要素が x で，先頭を除いた部分のリストが xs であるリストを表します．なお，: は右結合なので，1 : 2 : 3 : [] は 1 : (2 : (3 : [])) と同じ意味です．

要素数 0 のリスト（空リスト）は [] と書きます．

Haskell で扱うリストは，同一の型の要素のみで構成されるリストです．型が a である要素から構成されるリストの型を [a] と書きます．あまり見かけないですが，たまに [] a とも書きます．

[]                 -- [a] 型 （空リスト）
[1, 2, 3]          -- [Int] 型
['a', 'b', 'c']    -- [Char] 型
"abc"              -- [Char] 型
[[1, 2], [3], []]  -- [[Int]] 型

Haskell が採用しているような，すべて同じデータ型の要素からなるリストは，等質的 (homogeneous) なリストとよばれます．

3. リストを扱う関数

リストを扱う基本的な関数として，次のようなものがあります．

head [1, 2, 3]      -- 値: 1         （先頭要素を返す）
tail [1, 2, 3]      -- 値: [2, 3]    （先頭要素を除いたリストを返す）
[1] ++ [2, 3]       -- 値: [1, 2, 3] （リストを連結する）
length [1, 2, 3]    -- 値: 3         （リストの長さを返す）
map (2*) [1, 2, 3]  -- 値: [2, 4, 6] （各要素に関数を適用する）

リストを扱う関数は，基本的にはパターンマッチングを利用した再帰関数として定義するのがふつうです．例として，map 関数を定義してみましょう．次のプログラムは，map 関数を自前で定義した例です．

import Prelude hiding (map)  -- 標準関数の map を隠すおまじない

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

main = do
  print $ map id [1, 2, 3, 4, 5]             -- 出力: [1, 2, 3, 4, 5]
  print $ map succ [1, 2, 3, 4, 5]           -- 出力: [2, 3, 4, 5, 6]
  print $ map (\x -> x * x) [1, 2, 3, 4, 5]  -- 出力: [1, 4, 9, 16, 25]

標準で定義されているリスト用関数には，以下のようなものがあります（筆者が勝手に 5 つに分類していますが，特に深い意味はありません）．これらの関数の定義を自分で書いてみると，再帰関数を書くよい練習になります（筆者もそうしていました）．

3.1. 操作系

関数	型	説明
head xs	[a] -> a	先頭要素を返す
tail xs	[a] -> [a]	先頭要素を除去する
last xs	[a] -> a	最終要素を返す
init xs	[a] -> [a]	最終要素を除去する
take n xs	Int -> [a] -> [a]	先頭から長さ n の部分リストを返す
drop n xs	Int -> [a] -> [a]	先頭から n 要素目までを除去する
xs !! n	[a] -> Int -> a	先頭から n 番目の要素を返す
map f xs	(a -> b) -> [a] -> [b]	リストの各要素に関数 f を適用する
filter p xs	(a -> Bool) -> [a] -> [a]	述語 p を満たす要素を残す
reverse xs	[a] -> [a]	要素の並びを逆にする

3.2. 合成系

関数	型	説明
xs ++ ys	[a] -> [a] -> [a]	2 つのリストを連結する
concat xs	[[a]] -> [a]	リストのリストの要素を連結する
zip xs ys	[a] -> [b] -> [(a, b)]	2 つのリストを合成したタプルのリストを返す
zipWith f xs ys	(a -> b -> c) -> [a] -> [b] -> [c]	2 つのリストを関数で合成したリストを返す

3.3. 判定系

関数	型	説明
null xs	[a] -> Bool	空リストであれば True
length xs	[a] -> Int	リストの長さを返す
elem x xs	Eq a => a -> [a] -> Bool	要素に x が含まれていれば True
all p xs	(a -> Bool) -> [a] -> Bool	すべての要素が述語 p を満たせば True
any p xs	(a -> Bool) -> [a] -> Bool	いずれかの要素が述語 p を満たせば True

3.4. 畳込み系

関数	型	説明
foldl f z xs	(a -> b -> a) -> a -> [b] -> a	左から右へリストを畳み込む
foldr f z xs	(a -> b -> b) -> b -> [a] -> b	右から左へリストを畳み込む
sum xs	Num a => [a] -> a	要素の和を返す
product xs	Num a => [a] -> a	要素の積を返す

3.5. 生成系

関数	型	説明
repeat x	a -> [a]	無限リスト [x, x, ...] を返す
iterate f x	(a -> a) -> a -> [a]	無限リスト [x, f x, f (f x), ...] を返す

4. リストの畳込み

上の表に挙げた関数 foldr と foldl は割と重要なので，ここで少し説明します．

関数 foldr は，二項演算子を使って右からリストを畳み込む関数です．例えば，式 foldr (+) 0 [1, 2, 3] は，1 + (2 + (3 + 0)) と展開されます．

foldr (+) 0 [1, 2, 3]  -- 1 + (2 + (3 + 0)) = 6
foldr (-) 0 [1, 2, 3]  -- 1 - (2 - (3 - 0)) = 2

リスト [1, 2, 3] が 1 : (2 : (3 : [])) という構造だったことを思い起こすと，foldr 関数は : を二項演算子に，[] をシード値に置き換えるだけのシンプルな関数だということが理解できます．

            [1, 2, 3] = 1 : (2 : (3 : []))
foldr (+) 0 [1, 2, 3] = 1 + (2 + (3 + 0 ))

一方，左からリストを畳み込む foldl という関数もあります．例えば，式 foldl (+) 0 [1, 2, 3] は，((0 + 1) + 2) + 3 と展開されます．

foldl (+) 0 [1, 2, 3]  -- ((0 + 1) + 2) + 3 = 6
foldl (-) 0 [1, 2, 3]  -- ((0 - 1) - 2) - 3 = -6

これらの畳込み関数はかなり万能な関数であり，リストを扱う関数の多くがこれで書けてしまいます．次のプログラムは，いろんな関数を foldr で書いてみた例です．

sum' = foldr (+) 0
map' f = foldr (\x a -> f x : a) []
all' p = foldr (\x a -> p x && a) True

main = do
    print $ sum' [1, 2, 3, 4, 5]        -- 出力: 15
    print $ map' (^2) [1, 2, 3, 4 ,5]   -- 出力: [1, 4, 9, 16, 25]
    print $ all' even [2, 4, 6, 8, 10]  -- 出力: True

5. 数列表記

リストを [m..n] と書くことで，リスト [m, m+1, …, n-1, n] を表すことができます．これはリストの数列表記と呼ばれます．

[1..5]        -- 値: [1, 2, 3, 4, 5]
[1, 3..10]    -- 値: [1, 3, 5, 7, 9]
take 5 [1..]  -- 値: [1, 2, 3, 4, 5]

数列表記 [1..] は無限リスト [1, 2, 3, …] を表します． Haskell は遅延評価を採用しているため，このような無限リストが自然に扱えます．

[1..]  -- 値: [1, 2, 3, ...]

6. リスト内包表記

次のようなリストの表現は，リスト内包表記（list comprehension）と呼ばれます．

[x      | x <- [1..10], odd x]         -- 値: [1, 3, 5, 7, 9]
[(x, y) | x <- [1, 2], y <- [3, 4]]    -- 値: [(1,3), (1,4), (2,3), (2,4)]
[(x, y) | x <- [1, 2, 3], let y = 4]   -- 値: [(1,4), (2,4), (3,4)]

一般に，リスト内包表記は次のように書きます．

[ 式 | 限定子1 , ... , 限定子n ]

ここで，限定子には次の 3 つがあります．

ジェネレータ: パターン <- 式と書く．x <- [1, 2] など．
ガード: 条件式を書く．odd x など．
局所宣言: let で始まる宣言を書く．let y = 4 など．

リスト内包表記を用いると，関数 map の定義は次のように書くこともできます．

map f xs = [f x | x <- xs]

リスト内包表記を用いれば，クイックソートを行う関数 qsort は驚くほど簡単に定義できます．

qsort [] = []
qsort (p:xs) = qsort smaller ++ [p] ++ qsort larger
    where smaller = [x | x <- xs, x < p ]
          larger  = [x | x <- xs, x >= p]

main = print $ qsort [3, 2, 4, 1, 5]  -- 出力: [1, 2, 3, 4, 5]

リスト

1. リストとは