2009年6月21日日曜日

Haskell でデータコンストラクタによるパターンマッチ

0. 目次

  1. let 式でパターンマッチを利用
  2. パターンマッチは、代数的データ型の値を分解して、値を取り出す
  3. パターンを利用できる場面は 6 つある
  4. case 式におけるパターンマッチ
  5. パターン束縛におけるパターンマッチ
  6. ラムダ抽象におけるパターンマッチ
  7. リスト内包表記におけるパターンマッチ
  8. do 式におけるパターンマッチ

 

1. let 式でパターンマッチを利用

パターン束縛とは,左辺がfun x ... のような関数ではなく,Just xや(x,y)などのようなパターンになる等式のことです。パターン束縛はトップレベルで定義するよりもlet式などで利用することのほうが多いと思うので,…

(第8回 遅延評価の仕組み:ITpro より、太字は引用者による)

ん? (@_@) let 式でもパターンって使えたんだ。

let 式 と言えば、

*Main> let x = 100; y = 200 in x + y
300

のように変数を値に束縛するだけだと思っていた。

 

リストで試してみる

早速試してみる。

*Main> let (x:xs) = [0..5] in xs
[1,2,3,4,5]

ちなみに、リストは Haskell において特別扱いされている。

定義を見ると以下の通り。

*Main> :i []
data [] a = [] | a : [a] 	-- Defined in GHC.Types

上記パターンマッチは、データコンストラクタを利用したものだということ。

 

2. パターンマッチは、代数的データ型の値を分解して、値を取り出す

Haskell (programming language) – WikipediaFeatures and extensions によると、

Characteristic features of Haskell include lazy evaluation, pattern matching, currying, list comprehensions [7], guards, definable operators, and single assignment.

「パターンマッチ」は、Haskell の特徴の一つとして挙げられる。

代数的データ型 – Wikipedia によると、

代数的データ型(…)とはプログラミングにおけるデータ型の一種で、他のデータ型を当該代数的データ型のコンストラクタで包んだデータをとする。この包まれたデータはコンストラクタの引数である。他のデータ型と異なり、コンストラクタが実行されることはなく、データを操作するにはパターンマッチを使ってコンストラクタからデータを抜き出さねばならない。

(太字は引用者による)

つまり、代数的データ型の値を分解して中身の値を取得するために用いると。

 

3. パターンを利用できる場面は 6 つある

では、パターンマッチは、上記の let 式以外にどのような場面で利用できるのだろう?

すぐに思い出すのは関数の定義におけるパターンマッチ。

Haskell 98 Report: 式3.17 パターン照合 によると、

パターンは、ラムダ抽象、関数定義、パターン束縛、リスト内包 表記、do 式、case 式に出現する。しかしながら、これらのうち、最初の5つ は最終的には、case 式に変換される

(太字は引用者による)

頭に入れておくために、整理しておく。

  1. ラムダ抽象
  2. 関数定義
  3. パターン束縛
  4. リスト内包表記
  5. do 式
  6. case 式

 

4. case 式におけるパターンマッチ

ところで、一番肝心な case 式で使えることを忘れていた。(+_+)

以前に、文字列を分割する split 関数で、

によりスッキリと書けるのを見たのを思い出す。

復習をしておく。何をするわけでもない適当な hoge 関数を定義。 case 式におけるリストのデータコンストラクによるパターンの利用例。

hoge xs = case xs of
           [] -> []
           (0:_) -> [0]
           (_:xs) -> xs

例えば、

*Main> hoge []
[]
*Main> hoge [0..5]
[0]
*Main> hoge [1..5]
[2,3,4,5]

 

5. パターン束縛におけるパターンマッチ

上記で引用した「3.17 パターン照合」には、let 式が挙げられていない。代わりに

「パターン束縛」

という用語が書かれている。これは冒頭に引用した文章の冒頭にも出てきた。

The Haskell 98 Report: 宣言 によると、

パターン束縛は変数を値に束縛する。単純パターン束縛は p = e という形式である。

「パターン束縛」の前項の説明「4.4.3.1 関数束縛」を読んでみたが、よくわからなかった。 (@_@;)

これについては、関数の話をしよう - @IT を参照。そこでは、同じ計算内容の二つの関数の例が挙げらている。

stdWeight' = \ h -> (h ^ 2) * stdBMI
stdWeight    h      =  (h ^ 2) * stdBMI

下の関数定義の書き方について、次のように解説されている。

この形式は関数束縛という。左辺が関数適用の形になっていて、右辺は関数抽象の本体と同じ形になっている。通常この関数束縛という形式で定義するのが分かりやすい。

なるほど、普通の関数の定義の方法だと認識していたものが「関数束縛」のようだ。

そして、 4.4.3 関数束縛およびパターン束縛 に、次位のように書かれている。

… 左辺が pat0 であるときパターン束縛が出現す る。それ以外の場合には、この束縛は関数束縛と呼ぶ。どちらの束 縛もモジュールのトップレベルあるいは let あるいは where 構成内であらわれる

(太字は引用者による)

 

6. ラムダ抽象におけるパターンマッチ

さて、ラムダ抽象でも、パターンが使えたことに長らく気がつかず。 ^^;

先ほどと同じく適当に hoge’ 関数を定義するなら、

hoge' = \(_:xs) –> xs

使ってみる。

*Main> hoge' [0..5]
[1,2,3,4,5]

先ほどの説明にあったように、これを関数束縛の形式で記述するなら、

hoge'' (_:xs) = xs

関数の定義に引数を書くのと、ラムダ抽象の引数を書くのは親戚みたいなものだから、ラムダ抽象でパターンが利用できるのは当り前か。 ^^; とは言ったものの、

「あれ?ラムダ抽象でもパターンが使えるの!?」

と思ってしまったのは、ラムダ抽象と関数束縛の形式による関数の定義方法が、自分の中で別物のように感じていたから。

先ほどの「4.4.3.1 関数束縛」の説明の中にあったが、

関数束縛には関数の値を中置演算子に束縛する別の構文も用意されている。 たとえば、以下の 2 つの関数定義は同等である。
  plus x y z = x+y+z
  x
`plus` y = \ z -> x+y+z
  (x
`plus` y) z = x+y+z

新ためて、二つは表裏一体だと実感。 (@_@)

 

7. リスト内包表記におけるパターンマッチ

では、リスト内包表記ではどう書くのだろう?

Haskell/Pattern matching – Wikibooks によると、

catMaybes :: [Maybe a] -> [a]
catMaybes ms = [ x | Just x <- ms ]

これを真似て、

*Main> [xs | xs <- [[1,2,3],[4,5,6],[7,8,9]]]
[[1,2,3],[4,5,6],[7,8,9]]
*Main> [x | x:xs <- [[1,2,3],[4,5,6],[7,8,9]]]
[1,4,7]
*Main> [xs | x:xs <- [[1,2,3],[4,5,6],[7,8,9]]]
[[2,3],[5,6],[8,9]]

パターンマッチで利用される、リストのデータコンストラクタは、「与えられたリストの要素に対して、照合が行われる」。

別の例を挙げるなら、

data Person = Person {name :: String, age :: Int}
ps = [Person "Tarou" 30, Person "Hanako" 40, Person "Jiro" 50]
main = do print $ [x | Person x y <- ps]
          print $ [y | Person x y <- ps]

結果は、

*Main> main
["Tarou","Hanako","Jiro"]
[30,40,50]

 

8. do 式におけるパターンマッチ

do式で、リスト内包表記の例と同様のものを考える。

hoge''' xs = do x:xs' <- xs
                return x

使ってみる。

*Main> hoge''' [[1,2,3],[4,5,6],[7,8,9]]
[1,4,7]

do 式は、モナドの (>>=) を書換えたもの。リストモナドの (>>=) は、

m >>= f  = concatMap f m

(List モナド より)

よって、(>>=) を使って書き直すと、

*Main> [[1,2,3],[4,5,6],[7,8,9]] >>= \(x:xs) -> return x
[1,4,7]

ラムダ抽象におけるパターンマッチに対応している。