Yet Another Haskell Tutorial (和訳): 3.3 リスト

3.3 リスト

タプルのおもな制約は、ペアは2つ、3つ組は3つなど、決められた数の要素しか保持できない点である。任意の数の要素を保持できるデータ構造がリストである。リストは、括弧の代わりにカギ括弧を使う点以外はタプルとよく似た形をしている。リストは以下のように定義できる。

Prelude> [1,2]
[1,2]
Prelude> [1,2,3]
[1,2,3]

リストには要素がなくてもかまわない。空のリストは、単に[]である。
タプルとは異なり、コロン演算子を用いればごく簡単にリストの先頭に要素を追加できる。このコロンを「コンス」(cons) 演算子といい、要素を追加する処理を「コンスする」という。この語の語源は、追加する要素と古いリストから新しいリストをconstruct (構築) することから来ている。コンス演算子の動作は以下の例でわかる。

Prelude> 0:[1,2]
[0,1,2]
Prelude> 5:[1,2,3,4]
[5,1,2,3,4]

実際、コンス演算子 (コロン) と空リストを使えば任意のリストを構築できる。

Prelude> 5:1:2:3:4:[]
[5,1,2,3,4]

実は、[5,1,2,3,4]という構文は、コンス演算子と空リストを明示的に使った式の「構文糖」である。[5,1,2,3,4]という表記法を使って書くと、コンパイラは:と[]を使った表現に単純に置き換える。

■注■ 一般に、「構文糖」という言語機能は厳密には必要がない。これは構文をよりよくするために追加されたものである。

リストとタプルのもう1つの相違点は、タプルが異なる型の要素から成るのに対し、リストは型が同一でなければならないことだ (homogeneous)。つまり、整数と文字列の両方を含むリストは作れない。もし作ろうとすると、型エラーとなる。
もちろん、リストが含むことができるのは整数や文字列だけではない。リストはタプルを含むこともできるし、他のリストを含むことすらできる。タプルも同様に、リストや他のタプルを含むことができる。以下に挙げるものをいくつか試してみよう。

Prelude> [(1,1),(2,4),(3,9),(4,16)]
[(1,1),(2,4),(3,9),(4,16)]
Prelude> ([1,2,3,4],[5,6,7])
([1,2,3,4],[5,6,7])

基本的なリスト関数には、headとtailの2つがある。関数headは (空でない) リストの最初の要素を返し、関数tailは (空でない) リストの最初の要素以外のすべてを返す。
リストの長さを得るには、関数lengthを使う。

Prelude> length [1,2,3,4,10]
5
Prelude> head [1,2,3,4,10]
1
Prelude> length (tail [1,2,3,4,10])
4

3.3.1 文字列

Haskellでは、Stringは単なるCharのリストである。したがって、文字列 "Hello" は以下のように生成できる。

Prelude> ’H’:’e’:’l’:’l’:’o’:[]
"Hello"

リスト (および、もちろん文字列) は、++演算子を使って連結できる。

Prelude> "Hello " ++ "World"
"Hello World"

さらに、関数showを使うと文字列でない値を文字列に変換でき、関数readを使うと文字列を文字列以外の値に変換できる。もちろん、不正な値を読もうとするとエラーとなる (なお、これはコンパイル時エラーではなく、ランタイムエラーである)。

Prelude> "Five squared is " ++ show (5*5)
"Five squared is 25"
Prelude> read "5" + 3
8
Prelude> read "Hello" + 3
Program error: Prelude.read: no parse

上の例で、正確なエラーメッセージは実装に依存する。しかし、インタープリタが暗に述べているのは、何かに3を加えようとしたということだ。つまり、read "Hello" を実行したら数値が返されることが期待されている。しかし、"Hello" が数値と解釈できないのでエラーとなるのだ。

3.3.2 簡単なリスト関数

Haskellプログラムの計算の多くはリストを処理して行われる。リストの処理関数にはおもに3つある。map、filter、foldr (およびfoldl) である。
関数mapは、値のリストと、各値に適用する関数を引数にとる。たとえば、Char.toUpperという組み込み関数がある。これはCharを入力値にとり、もとの引数を大文字にする。したがって、文字列 (単なる文字のリスト) 全体を大文字に変換するには、リスト全体に関数toUpperをマップすればよい。

Prelude> map Char.toUpper "Hello World"
"HELLO WORLD"

■警告■ Hugsユーザーの場合: HugsではChar.toUpperのような修飾付きの名前は好まれない。Hugsでは、単にtoUpperを使う。

リスト全体にマップしてもリストの長さは決して変化せず、リスト内の個々の値のみが変化する。
リストから要素を削除するには、関数filterを使う。この関数を使うと、その値に応じてリストから要素を取り除くことができる。ただし、コンテキストに応じた要素の削除はできない。たとえば、関数Char.isLowerは、与えられた文字が小文字かどうかを返す。これを使うと、小文字以外の文字を取り除くことができる。

Prelude> filter Char.isLower "Hello World"
"elloorld"

関数foldrにはちょっとした慣れが必要だ。foldrは、関数、初期値、リストの3つの引数をとる。foldrとは、リストのコンス演算子 (:) をパラメータに指定した関数で置き換え、空リスト生成子 ([]) を初期値で置き換えたものであると考えるのが一番わかりやすい。したがって、リスト
   3 : 8 : 12 : 5 : []
があったとして、これに foldr (+) 0 を適用すると、
   3 + 8 + 12 + 5 + 0
が得られ、合計値が計算される。これは、以下のようにして確かめられる。

Prelude> foldr (+) 0 [3,8,12,5]
28

同様の処理で、リスト内の全要素の積を計算できる。

Prelude> foldr (*) 1 [4,8,5]
160

折りたたみ関数は、(:) を特定の関数に置き換え、([]) を初期値に置き換えるようなものだと述べた。では、指定した関数が結合的でない場合は何が起きるだろうか (a · (b · c) = (a · b) · c なら、関数 (·) は結合的である)。4 · 8 · 5 · 1と書いたとき、括弧を置く場所を指定する必要がある。つまり、((4 · 8) · 5) · 1 と 4 · (8 · ((5 · 1)) のどちらを意味するだろうか？foldrは、関数が右結合的であるとみなす (つまり、後者の括弧のつけかたが正しい)。ゆえに、(減算のような) 非結合的関数でこれを使うと以下のような結果になる。

Prelude> foldr (-) 1 [4,8,5]
0

正確には、以下のように導かれる。
    foldr (-) 1 [4,8,5]
==> 4 - (foldr (-) 1 [8,5])
==> 4 - (8 - foldr (-) 1 [5])
==> 4 - (8 - (5 - foldr (-) 1 []))
==> 4 - (8 - (5 - 1))
==> 4 - (8 - 4)
==> 4 - 4
==> 0
関数foldlは反対の動作をし、逆から括弧をつける。適用のしかたはfoldlも同じなので、foldlでもまったく同じように合計を出すことができる。

Prelude> foldl (+) 0 [3,8,12,5]
28

しかし、非結合的関数である減算を使用すると結果が異なる。

Prelude> foldl (-) 1 [4,8,5]
-16

それは、foldlは括弧のつけかたが逆だからである。本質的には、リストをくだっていって実行する。つまり、最後の要素を取り出し、与えられた関数で初期値と結びつける。得られた値に、リストの最後から2番目の要素を取り出して結びつける。リストに何も残らなくなるまでこれが行われる。
このようにして、逆のやり方で導かれていく。
    foldl (-) 1 [4,8,5]
==> foldl (-) (1 - 4) [8,5]
==> foldl (-) ((1 - 4) - 8) [5]
==> foldl (-) (((1 - 4) - 8) - 5) []
==> ((1 - 4) - 8) - 5
==> ((-3) - 8) - 5
==> (-11) - 5
==> -16
ここで注意しておきたいのは、foldlを取り去った状態がfoldrとまったく逆の括弧付けになっていることだ。

■注■ 7.8節で述べる理由から、foldrよりもfoldlのほうが効果的であることが多い。しかし、foldrは無限リストでも動作するが、foldlは動作しない。なぜなら、foldlは何をするにも必ずリストの最後で行わねばならないからだ。一方で、foldrは出力の生成をすぐに開始する。たとえば、foldr (:) [] [1,2,3,4,5] は、単純に同じリストを返す。無限リストであっても出力は生成される。同様の関数にfoldlを使用すると出力の生成は失敗する。

折りたたみ関数に関するこういった議論がまだよくわからなくても問題はない。これについては、7.8節で詳しく述べる。

演習

演習3.3 mapを使用して、文字列をもとのリストの各要素が小文字かどうかを表すbooleanのリストに変換せよ。つまり、文字列 "aBCde" を受けたら [True,False,False,True,True] を返すようにする。

演習3.4 この節で述べた関数を使い (2つ必要だろう)、文字列内の小文字の数を計算せよ。たとえば、"aBCde" なら 3 を返すようにする。

演習3.5 折りたたみ関数を使って合計や積を計算する方法を学んだ。関数maxが2つの数の最大値を返すとした場合、折りたたみを使ってリストの最大値 (リストが空なら0) を返す関数を書け。つまり、[5,10,2,8,1] が与えられたら、10を返す。なお、リストの値はつねに0以上とする。また、それが動作する理由を自分自身に説明せよ。

演習3.6 長さ2以上のペアのリストに対し、リストの2つめの要素の最初の成分を返す関数を書け。つまり、[(5,’b’),(1,’c’),(6,’a’)] が与えられたら1を返す。

---

前ページ「3.2 タプル」
次ページ「3.4 ソースコードファイル」

---

表紙

目次

1 はじめに

2 スタートガイド

3 Haskell言語の基礎

4 型の基礎

5 Basic Input/Output

6 Modules

7 Advanced Features

8 Advanced Types

9 Monads

10 Advanced Techniques

A Brief Complexity Theory

B Recursion and Induction

C Solutions To Exercises

---

これは、Haskell (ハスケル) のチュートリアル "Yet Another Haskell Tutorial" を日本語に翻訳したものです。
オリジナルのドキュメントは、
http://www.cs.utah.edu/~hal/docs/daume02yaht.pdf
などから入手できます。
日本語訳に関するご指摘は、コメントとしてお寄せください。