top page > computer > haskell > web_lecture > for_programmer > list_pattern_match.html
更新日:
文責: 重城良国

リストのパターンマッチ

リストの構造

リストの先頭に要素を追加

演算子(:)はリストの先頭に要素を追加する。

% ghci
Prelude> 8 : [3, 5, 7]
[8,3,5,7]
Prelude> 'H' : "ello"
"Hello"

空リスト

Prelude> []
[]

リストの構造

リストは追加演算子(:)と空リストだけで作れる。

Prelude> 8 : (3 : (5 : (7 : [])))
[8,3,5,7]

空リストに次々と値を追加して[8,3,5,7]というリストを作成したように見える。しかし8 : (3 : (5 : (7 : [])))のほうがリストの本当の姿だ。[8,3,5,7]という表記は対話環境が読みやすく表示しただけだ。リストは本質的にx : (y : ... : (z : [])..)という構造のデータだ。

構文糖

[x, y, ... ,z]の形は構文糖だ。x : (y : ... : (z : [])..)として解釈される。演算子(:)は右結合だ。丸括弧を省略しx : y : ... : z : []とも書ける。

再帰的

リストとは「リストの先頭に要素を加えたもの、または空リスト」だ。再帰的な定義だ。疑似コードを示す。

[a] = (a : [a]) or []

Maybe a型の値がJust aまたはNothingなのと同じように[a]型の値はa : [a]または[]だ。

リストへのパターンマッチ

リストは次の2つのどちらかだ。

2つのパターンでパターンマッチする。

対象となるリストが空リストでなければx : xsにマッチしリストの先頭の要素がxを束縛しリストの残りの部分がxsを束縛する。「先頭の要素」と「残りの要素から成るリスト」がとりだせる。空リストは[]にマッチする。

構文糖

パターンマッチにも構文糖が使える。

f [x] = ...
g [x, y, z] = ...

それぞれ以下のように解釈される。

f (x : []) = ...
g (x : y : z : []) = ...

関数head

関数headはリストの先頭を取り出す。

Prelude> head [3, 4, 5]
3
Prelude> head "Hello"
'H'

myHead :: [a] -> a
myHead (x : _) = x

関数tail

関数tailはリストの残りの部分を取り出す。

Prelude> tail [3, 4, 5]
[4,5]
Prelude> tail "Hello"
"ello"

myTail :: [a] -> [a]
myTail (_ : xs) = xs

試してみる

myHeadTail.hs

% ghci myHeadTail.hs
*Main> myHead [3, 4, 5]
3
*Main> myTail [3, 4, 5]
[4,5]
*Main> myHead []
*** Exception: myHeadTail.hs:2:1-18: Non-exhaustive patterns in function myHead

*Main> myTail []
*** Exception: myHeadTail.hs:5:1-20: Non-exhaustive patterns in function myTail

空リストに対しては「パターンが存在しないよ」というエラーが発生する。

全域関数と部分関数

関数はある集合から別の集合に値を対応づける。逆数を求める関数は2を0.5に4を0.25に対応づける。逆数関数では0に対応する値がない。対応する値のない値がもとの集合にある関数は「全域関数ではない部分関数」だ。headやtailは空リストに対して定義されないので全域関数ではない。このような関数は慎重に使わないと予期せぬエラーの原因となる。

エラー値

パターンマッチを書かないとNon-exhaustive patternsというエラーメッセージとなる。より明示的にエラー値を返せる。定義済みのエラー値として値undefinedと関数errorとがある。

*Main> undefined
*** Exception: Prelude.undefined
*Main> error "Beep! Beep!"
*** Exception: Beep! Beep!

undefinedはコーディング中にスタブとして使う。関数errorを使うと自分の好きなエラーメッセージが表示できる。関数errorは本来は「起こり得ない場合」に使うことが望ましい。

myHeadのエラーメッセージをユーザーフレンドリーにしてみよう。

myHead (x : _) = x
myHead _ = error "Bonehead!"

関数null

関数nullはリストが空かどうかをチェックする。

*Main> null [1, 2, 3]
False
*Main> null []
True
*Main> null "hello"
False
*Main> null ""
True

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

これは「空リストなら真、リストに要素をひとつ足したリストなら偽」だ。ワイルドカードを使っても良い。

myNull [] = True
myNull _ = False

「空リストなら真、そうでないなら偽」だ。

まとめ

リストは再帰的に「リストの先頭に要素を足したものまたは空リスト」と定義される。空でないリストはx : xsの形で保存される。空リストは[]だ。x : xsと[]でパターンマッチする。[x, y, ..., z]のような表記は構文糖だ。リストはパターンマッチで先頭とそれ以外に分けられる。

fun (x : xs) = [xやxsを使った式]
fun [] = [空リストの場合の式]

[]のかわりにワイルドカードが使える。

fun (x : xs) = [xやxsを使った式]
fun _ = [空リストの場合の式]

空リストへのマッチを先にしても良い。

fun [] = [空リストの場合の式]
fun (x : xs) = [xやxsを使った式]

課題

  1. 与えられたリストの要素が複数であることを確認する関数pluralを定義せよ

「二分樹を下へたどる」へもどる 「リストの要素の総和」へ

正当なCSSです! HTML5 Powered with CSS3 / styling, and Semantics