リスト

このページでは,複数のデータを扱う際に中心的な役割を果たす,リストについて説明します.

リストとは

リスト (list) は,複数のデータを一列に並べたデータ構造のひとつです. Haskell では,複数のデータを扱う際には,配列よりもリストがよく使われます.

リストの概念図

これは,リスト [1, 2, 3] の概念的な構造を表した図です. リストはこの図のように,値をもつ単位(LISP ではこれを「cons セル」とよぶ)を一列に並べた構造となっています. 最後は空リスト (nil) で終ります.

Haskell では,この構造が(次のページで説明する)「代数的データ型」で自然に表せることから,配列よりもリストが好んで使われます.

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

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) なリストとよばれます.

リストを扱う関数

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

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 つに分類していますが,特に深い意味はありません.

操作系

関数説明
head xs[a] -> a先頭要素を返す
tail xs[a] -> [a]先頭要素を除去する
last xs[a] -> a最終要素を返す
init xs[a] -> [a]最終要素を除去する
take n xsInt -> [a] -> [a]先頭から長さ n の部分リストを返す
drop n xsInt -> [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]要素の並びを逆にする

合成系

関数説明
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 つのリストを関数で合成したリストを返す

判定系

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

畳込み系

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

生成系

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

*     *     *

ぜひ,ここまでに挙げた関数の定義を自分で書いてみることに挑戦してみてください. 再帰関数を書くよい練習になります.

リストの畳込み

上の表に挙げた関数 foldrfoldl は割と重要なので,ここで少し説明します.

関数 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 関数は : を二項演算子に,[] をシード値に置き換えるだけのシンプルな関数だということが理解できます.

一方,左からリストを畳み込む 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

数列表記

リストを [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 は遅延評価を採用しているため,このような無限リストが自然に扱えます.

リスト内包表記

次のようなリストの表現は,リスト内包表記 (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 つがあります.

リスト内包表記を用いると,関数 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]