目次に戻る

第5章 パターン照合

5.1 この章の目標

この章では、代数的データ型とパターン照合という、ふたつの新しい概念を導入します。また、行多相というPureScriptの型システムの興味深い機能についても簡単に取り扱います。

パターン照合(Pattern matching)は関数​​型プログラミングにおける一般的な手法で、複数の場合に実装を分解することにより、開発者は潜在的に複雑な動作の関数を簡潔に書くことができます。

代数的データ型はPureScriptの型システムの機能で、パターン照合とも密接に関連しています。

この章の目的は、代数的データ型やパターン照合を使用して、単純なベクターグラフィックスを描画し操作するためのライブラリを書くことです。

5.2 プロジェクトの準備

この章のソースコードはファイル src/Data/Picture.pursで定義されています。

このプロジェクトでは、これまで見てきたBowerパッケージを引き続き使用しますが、それに加えて次の新しい依存関係が追加されます。

• purescript-globals: 一般的なJavaScriptの値や関数の取り扱いを可能にします。
• purescript-math: JavaScriptの Mathオブジェクトの関数群を利用可能にします。

Data.Pictureモジュールは、簡単な図形を表すデータ型 Shapeや、図形の集合である型 Picture、及びこれらの型を扱うための関数を定義しています。

このモジュールでは、データ構造の畳込みを行う関数を提供する Data.Foldableモジュールもインポートします。

module Data.Picture where

import Prelude
import Data.Foldable (foldl)

Data.Pictureモジュールでは、 Globalと Mathモジュールもインポートするため asキーワードを使用します。

import Global as Global
import Math as Math

これは型や関数をモジュール内で使用できるようにしますが、Global.infinityやMath.maxといった修飾名でのみ使用にできるようにします。これは重複したインポートをさけ、使用するモジュールを明確にするのに有効な方法です。

注意：同じモジュール名を修飾名に使用する場合には不要な作業です。一般的にはimport Math as Mなどの短い名前がよく使われています。

5.3 単純なパターン照合

それではコード例を見ることから始めましょう。パターン照合を使用して2つの整数の最大公約数を計算する関数は、次のようになります。

gcd :: Int -> Int -> Int
gcd n 0 = n
gcd 0 m = m
gcd n m = if n > m
            then gcd (n - m) m
            else gcd n (m - n)

このアルゴリズムはユークリッドの互除法と呼ばれています。その定義をオンラインで検索すると、おそらく上記のコードによく似た数学の方程式が見つかるでしょう。パターン照合の利点のひとつは、上記のようにコードを場合分けして定義することができ、数学関数の定義と似たような簡潔で宣言型なコードを書くことができることです。

パターン照合を使用して書かれた関数は、条件と結果の組み合わせによって動作します。この定義の各行は選択肢(alternative)や場合(case)と呼ばれています。等号の左辺の式はパターンと呼ばれており、それぞれの場合は空白で区切られた1つ以上のパターンで構成されています。等号の右側の式が評価され値が返される前に引数が満たさなければならない条件について、これらの場合は説明しています。それぞれの場合は上からこの順番に試されていき、最初に入力に適合した場合が返り値を決定します。

たとえば、 gcd関数は次の手順で評価されます。

• まず最初の場合が試されます。第２引数がゼロの場合、関数は n（最初の引数）を返します。
• そうでなければ、2番目の場合が試されます。最初の引数がゼロの場合、関数は m（第２引数）を返します。
• それ以外の場合、関数は最後の行の式を評価して返します。

パターンは値を名前に束縛することができることに注意してください。この例の各行では nという名前と mという名前の両方、またはどちらか一方に、入力された値を束縛しています。これより、入力の引数から名前を選ぶためのさまざまな方法に対応した、さまざまな種類のパターンを見ていくことになります。

5.4 単純なパターン

上記のコード例では、2種類のパターンを示しました。

• Int型の値が正確に一致する場合にのみ適合する、数値リテラルパターン
• 引数を名前に束縛する、変数パターン

単純なパターンには他にも種類があります。

• 文字列リテラルと真偽リテラル
• どんな引数とも適合するが名前に束縛はしない、アンダースコア（ _）で表されるワイルドカードパターン

ここではこれらの単純なパターンを使用した、さらに2つの例を示します。

fromString :: String -> Boolean
fromString "true" = true
fromString _      = false

toString :: Boolean -> String
toString true  = "true"
toString false = "false"

PSCiでこれらの関数を試してみてください。

5.5 ガード

ユークリッドの互除法の例では、 m > nのときと m <= nのときの２つに分岐するために if .. then .. else式を使っていました。こういうときには他にガード(guard)を使うという選択肢もあります。

ガードは真偽値の式で、パターンによる制約に加えてそのガードが満たされたときに、その場合の結果になります。ガードを使用してユークリッドの互除法を書き直すと、次のようになります。

gcd :: Int -> Int -> Int
gcd n 0 = n
gcd 0 n = n
gcd n m | n > m = gcd (n - m) m
        | otherwise = gcd n (m - n)

３行目ではガードを使用して、最初の引数が第２引数よりも厳密に大きいという条件を付け加えています。

この例が示すように、ガードは等号の左側に現れ、パイプ文字（ |）でパターンのリストと区切られています。

5.6 配列リテラルパターン

配列リテラルパターン(array literal patterns)は、固定長の配列に対して照合を行う方法を提供します。たとえば、空の配列であることを特定する関数 isEmptyを書きたいとします。最初の選択肢に空の配列パターン（ []）を用いるとこれを実現できます。

isEmpty :: forall a. Array a -> Boolean
isEmpty [] = true
isEmpty _ = false

次の関数では、長さ5の配列と適合し、配列の5つの要素をそれぞれ異なった方法で束縛しています。

takeFive :: Array Int -> Int
takeFive [0, 1, a, b, _] = a * b
takeFive _ = 0

最初のパターンは、第１要素と第２要素がそれぞれ0と1であるような、5要素の配列にのみ適合します。その場合、関数は第3要素と第4要素の積を返します。それ以外の場合は、関数は0を返します。 PSCiで試してみると、たとえば次のようになります。

> :paste
… takeFive [0, 1, a, b, _] = a * b
… takeFive _ = 0
… ^D

> takeFive [0, 1, 2, 3, 4]
6

> takeFive [1, 2, 3, 4, 5]
0

> takeFive []
0

配列のリテラルパターンでは、固定長の配列と一致させることはできますが、不特定の長さの配列を照合させる手段を提供していません。PureScriptでは、そのような方法で不変な配列を分解すると、実行速度が低下する可能性があるためです。不特定の長さの配列に対して照合を行うことができるデータ構造が必要な場合は、Data.Listを使うことをお勧めします。そのほかの操作について、より優れた漸近性能を提供するデータ構造も存在します。

5.7 レコードパターンと行多相

レコードパターン(Record patterns)は(ご想像のとおり)レコードに照合します。

レコードパターンはレコードリテラルに見た目が似ていますが、レコードリテラルでラベルと式をコロンで区切るのとは異なり、レコードパターンではラベルとパターンを等号で区切ります。

たとえば、次のパターンは firstと lastと呼ばれるフィールドが含まれた任意のレコードにマッチし、これらのフィールドの値はそれぞれ xと yという名前に束縛されます。

showPerson :: { first :: String, last :: String } -> String
showPerson { first: x, last: y } = y <> ", " <> x

レコードパターンはPureScriptの型システムの興味深い機能である行多相(row polymorphism)の良い例となっています。もし上のshowPersonを型シグネチャなしで定義していたとすると、この型はどのように推論されるのでしょうか？面白いことに、推論される型は上で与えた型とは同じではありません。

> showPerson { first: x, last: y } = y <> ", " <> x

> :type showPerson
forall r. { first :: String, last :: String | r } -> String

この型変数 rとは何でしょうか？PSCiで showPersonを使ってみると、面白いことがわかります。

> showPerson { first: "Phil", last: "Freeman" }
"Freeman, Phil"

> showPerson { first: "Phil", last: "Freeman", location: "Los Angeles" }
"Freeman, Phil"

レコードにそれ以外のフィールドが追加されていても、 showPerson関数はそのまま動作するのです。型が Stringであるようなフィールド firstと lastがレコードに少なくとも含まれていれば、関数適用は正しく型付けされます。しかし、フィールドが不足していると、 showPersonの呼び出しは不正となります。

> showPerson { first: "Phil" }

Type of expression lacks required label "last"

showPersonの推論された型シグネチャは、 Stringであるような firstと lastというフィールドと、それ以外の任意のフィールドを持った任意のレコードを引数に取り、 Stringを返す、というように読むことができます。

この関数はレコードフィールドの行 rについて多相的なので、行多相と呼ばれるわけです。

次のように書くことができることにも注意してください。

> showPerson p = p.last <> ", " <> p.first

この場合も、 PSCiは先ほどと同じ型を推論するでしょう。

後ほど拡張可能作用(Extensible effects)について議論するときに、再び行多相について見ていくことになります。

5.8 入れ子になったパターン

配列パターンとレコードパターンはどちらも小さなパターンを組み合わせることで大きなパターンを構成しています。これまでの例では配列パターンとレコードパターンの内部に単純なパターンを使用していましたが、パターンが自由に入れ子にすることができることも知っておくのが大切です。入れ子になったパターンを使うと、潜在的に複雑なデータ型に対して関数が条件分岐できるようになります。

たとえば、次のコードでは、レコードパターンと配列パターンを組み合わせて、レコードの配列と照合させています。

type Address = { street :: String, city :: String }

type Person = { name :: String, address :: Address }

livesInLA :: Person -> Boolean
livesInLA { address: { city: "Los Angeles" } } = true
livesInLA _ = false

5.9 名前付きパターン

パターンには名前を付けることができ、入れ子になったパターンを使うときにスコープに追加の名前を導入することができます。任意のパターンに名前を付けるには、 @記号を使います。

たとえば、次のコードは1つ以上の要素を持つ任意の配列と適合しますが、配列の先頭を xという名前、配列全体を arrという名前に束縛します。

sortPair :: Array Int -> Array Int
sortPair arr@[x, y]
  | x <= y = arr
  | otherwise = [y, x]
sortPair arr = arr

その結果、ペアがすでにソートされている場合は、新しい配列を複製する必要がありません。

5.10 Case式

パターンはソースコードの最上位にある関数だけに現れるわけではありません。 case式を使用すると計算の途中の値に対してパターン照合を使うことができます。case式には無名関数に似た種類の便利さがあります。関数に名前を与えることがいつも望ましいわけではありません。パターン照合を使いたいためだけで関数に名前をつけるようなことを避けられるようになります。

例を示しましょう。次の関数は、配列の"longest zero suffix"(和がゼロであるような、最も長い配列の末尾)を計算します。

import Data.Array.Partial (tail)
import Partial.Unsafe (unsafePartial)

lzs :: Array Int -> Array Int
lzs [] = []
lzs xs = case sum xs of
           0 -> xs
           _ -> lzs (unsafePartial tail xs)

例えば次のようになります。

> lzs [1, 2, 3, 4]
[]

> lzs [1, -1, -2, 3]
[-1, -2, 3]

この関数は場合ごとの分析によって動作します。もし配列が空なら、唯一の選択肢は空の配列を返すことです。配列が空でない場合は、さらに2つの場合に分けるためにまず case式を使用します。配列の合計がゼロであれば、配列全体を返します。そうでなければ、配列の残りに対して再帰します。

5.11 パターン照合の失敗

case式のパターンを順番に照合していって、もし選択肢のいずれの場合も入力が適合しなかった時は何が起こるのでしょうか？この場合、パターン照合失敗によって、case式は実行時に失敗します。

簡単な例でこの動作を見てみましょう。

import Partial.Unsafe (unsafePartial)

partialFunction :: Boolean -> Boolean
partialFunction = unsafePartial \true -> true

この関数はゼロの入力に対してのみ適合する単一の場合を含みます。このファイルをコンパイルして PSCiでそれ以外の値を与えてテストすると、実行時エラーが発生します。

> partialFunction false

Failed pattern match

どんな入力の組み合わせに対しても値を返すような関数は全関数(total function)と呼ばれ、そうでない関数は部分関数(partial function)と呼ばれています。

一般的には、可能な限り全関数として定義したほうが良いと考えられています。もしその関数が正しい入力に対して値を返さないことがあるとわかっているなら、大抵は aに対して型 Maybe aの返り値にし、失敗を示すときには Nothingを使うようにしたほうがよいでしょう。この方法なら、型安全な方法で値の有無を示すことができます。

PureScriptコンパイラは、パターンマッチが不完全で関数が全関数ではないことを検出するとエラーを生成します。部分関数が安全である場合、unsafePartial関数を使ってこれらのエラーを抑制することができます(その部分関数が安全だとあなたが言い切れるなら！)。もし上記の unsafePartial関数の呼び出しを取り除くと、コンパイラは次のエラーを生成します。

A case expression could not be determined to cover all inputs.
The following additional cases are required to cover all inputs:

  false

これは値falseが、定義されたどのパターンとも一致しないことを示しています。これらの警告には、複数の不一致のケースが含まれることがあります。

上記の型シグネチャも省略した場合は、次のようになります。

partialFunction true = true

このとき、PSCiは興味深い型を推論します｡

:type partialFunction

Partial => Boolean -> Boolean

本書ではのちに=>記号を含むいろいろな型を見ることができます（これらは型クラスに関連しています）。しかし、今のところは、PureScriptは型システムを使って部分関数を追跡していること、開発者は型検証器にコードが安全であることを明示する必要があることを確認すれば十分です。

コンパイラは、定義されたパターンが冗長であることを検出した場合（すでに定義されたパターンに一致するケースのみ）でも警告を生成します。

redundantCase :: Boolean -> Boolean
redundantCase true = true
redundantCase false = false
redundantCase false = false

このとき、最後のケースは冗長であると正しく検出されます。

Redundant cases have been detected.
The definition has the following redundant cases:

  false

注意：PSCiは警告を表示しないので、この例を再現するには、この関数をファイルとして保存し、 pulp buildを使ってコンパイルします。

5.12 代数的データ型

この節では、PureScriptの型システムでパターン照合に原理的に関係している代数的データ型(Algebraic data type, ADT）と呼ばれる機能を導入します。

しかしまずは、ベクターグラフィックスライブラリの実装というこの章の課題を解決する基礎として、簡単な例を切り口にして考えていきましょう。

直線、矩形、円、テキストなどの単純な図形の種類を表現する型を定義したいとします。オブジェクト指向言語では、おそらくインタフェースもしくは抽象クラス Shapeを定義し、使いたいそれぞれの図形について具体的なサブクラスを定義するでしょう。

しかしながら、この方針は大きな欠点をひとつ抱えています。 Shapeを抽象的に扱うためには、実行したいと思う可能性のあるすべての操作を事前に把握し、 Shapeインタフェースに定義する必要があるのです。このため、モジュール性を壊さずに新しい操作を追加することが難しくなります。

もし図形の種類が事前にわかっているなら、代数的データ型はこうした問題を解決する型安全な方法を提供します。モジュール性のある方法で Shapeに新たな操作を定義し、型安全なまま保守することを可能にします。

代数的データ型として表現された Shapeがどのように記述されるかを次に示します。

data Shape
  = Circle Point Number
  | Rectangle Point Number Number
  | Line Point Point
  | Text Point String

次のように Point型を代数的データ型として定義することもできます。

data Point = Point
  { x :: Number
  , y :: Number
  }

この Pointデータ型は、興味深い点をいくつか示しています。

• 代数的データ型の構築子に格納されるデータは、プリミティブ型に限定されるわけではありません。構築子はレコード、配列、あるいは他の代数的データ型を含めることもできます。
• 代数的データ型は複数の構築子があるデータを記述するのに便利ですが、構築子がひとつだけのときでも便利です。
• 代数的データ型の構築子は、代数的データ型自身と同じ名前の場合もあります。これはごく一般的であり、 Pointデータ構築子と Point型構築子を混同しないようにすることが大切です。これらは異なる名前空間にあります。

この宣言ではいくつかの構築子の和として Shapeを定義しており、各構築子に含まれたデータはそれぞれ区別されます。 Shapeは、中央 Pointと半径を持つ Circleか、 Rectangle、 Line、 Textのいずれかです。他には Shape型の値を構築する方法はありません。

代数的データ型の定義は予約語 dataから始まり、それに新しい型の名前と任意個の型引数が続きます。その型のデータ構築子は等号の後に定義され、パイプ文字（ |）で区切られます。

それではPureScriptの標準ライブラリから別の例を見てみましょう。オプショナルな値を定義するのに使われる Maybe型を本書の冒頭で扱いました。 purescript-maybeパッケージでは Maybeを次のように定義しています。

data Maybe a = Nothing | Just a

この例では型引数 aの使用方法を示しています。パイプ文字を「または」と読むことにすると、この定義は「 Maybe a型の値は、無い(Nothing)、またはただの(Just)型 aの値だ」と英語のように読むことができます。

データ構築子は再帰的なデータ構造を定義するために使用することもできます。更に例を挙げると、要素が型 aの単方向連結リストのデータ型を定義はこのようになります。

data List a = Nil | Cons a (List a)

この例は purescript-listsパッケージから持ってきました。ここで Nil構築子は空のリストを表しており、 Consは先頭となる要素と他の配列から空でないリストを作成するために使われます。 Consの２つ目のフィールドでデータ型 List aを使用しており、再帰的なデータ型になっていることに注目してください。

5.13 代数的データ型の使用

代数的データ型の構築子を使用して値を構築するのはとても簡単です。対応する構築子に含まれるデータに応じた引数を用意し、その構築子を単に関数のように適用するだけです。

例えば、上で定義した Line構築子は２つの Pointを必要としていますので、 Line構築子を使って Shapeを構築するには、型 Pointのふたつの引数を与えなければなりません。

exampleLine :: Shape
exampleLine = Line p1 p2
  where
    p1 :: Point
    p1 = Point { x: 0.0, y: 0.0 }

    p2 :: Point
    p2 = Point { x: 100.0, y: 50.0 }

p1及び p2を構築するため、レコードを引数として Point構築子を適用しています。

代数的データ型で値を構築することは簡単ですが、これをどうやって使ったらよいのでしょうか？ここで代数的データ型とパターン照合との重要な接点が見えてきます。代数的データ型の値がどの構築子から作られたかを調べたり、代数的データ型からフィールドの値を取り出す唯一の方法は、パターン照合を使用することです。

例を見てみましょう。 Shapeを Stringに変換したいとしましょう。 Shapeを構築するのにどの構築子が使用されたかを調べるには、パターン照合を使用しなければなりません。これには次のようにします。

showPoint :: Point -> String
showPoint (Point { x: x, y: y }) =
  "(" <> show x <> ", " <> show y <> ")"

showShape :: Shape -> String
showShape (Circle c r)      = ...
showShape (Rectangle c w h) = ...
showShape (Line start end)  = ...
showShape (Text p text) = ...

各構築子はパターンとして使用することができ、構築子への引数はそのパターンで束縛することができます。 showShapeの最初の場合を考えてみましょう。もし Shapeが Circle構築子適合した場合、２つの変数パターン cと rを使って Circleの引数（中心と半径）がスコープに導入されます。その他の場合も同様です。

showPointは、パターン照合の別の例にもなっています。 showPointはひとつの場合しかありませんが、 Point構築子の中に含まれたレコードのフィールドに適合する、入れ子になったパターンが使われています。

5.14 レコード同名利用

showPoint関数は引数内のレコードと一致し、 xと yプロパティを同じ名前の値に束縛します。 PureScriptでは、このようなパターン一致を次のように単純化できます。

showPoint :: Point -> String
showPoint (Point { x, y }) = ...

ここでは、プロパティの名前のみを指定し、名前に導入したい値を指定する必要はありません。 これはレコード同名利用(record pun)と呼ばれます。

レコード同名利用をレコードの構築に使用することもできます。例えば、スコープ内に xと yという名前の値があれば、 Point {x、y}を使って Pointを作ることができます。

origin :: Point
origin = Point { x, y }
  where
    x = 0.0
    y = 0.0

これは、状況によってはコードの可読性を向上させるのに役立ちます。

5.15 newtype宣言

代数的データ型の特別な場合に、newtypeと呼ばれる重要なものあります。newtypeは予約語 dataの代わりに予約語 newtypeを使用して導入します。

newtype宣言では過不足なくひとつだけの構築子を定義しなければならず、その構築子は過不足なくひとつだけの引数を取る必要があります。つまり、newtype宣言は既存の型に新しい名前を与えるものなのです。実際、newtypeの値は、元の型と同じ実行時表現を持っています。しかし、これらは型システムの観点から区別されます。これは型安全性の追加の層を提供するのです。

例として、ピクセルとインチのような単位を表現するために、 Numberの型レベルの別名を定義したくなる場合があるかもしれません。

newtype Pixels = Pixels Number
newtype Inches = Inches Number

こうすると Inchesを期待している関数に Pixels型の値を渡すことは不可能になりますが、実行時の効率に余計な負荷が加わることはありません。

newtypeは次の章で型クラスを扱う際に重要になります。newtypeは実行時の表現を変更することなく型に異なる振る舞いを与えることを可能にするからです。

5.16 ベクターグラフィックスライブラリ

これまで定義してきたデータ型を使って、ベクターグラフィックスを扱う簡単なライブラリを作成していきましょう。

ただの Shapeの配列であるような、 Pictureという型同義語を定義しておきます。

type Picture = Array Shape

デバッグしていると Pictureを Stringとして表示できるようにしたくなることもあるでしょう。これはパターン照合を使用して定義された showPicture関数で行うことができます。

showPicture :: Picture -> Array String
showPicture = map showShape

それを試してみましょう。 モジュールを pulp buildでコンパイルし、 pulp replでPSCiを開きます。

$ pulp build
$ pulp repl

> import Data.Picture

> :paste
… showPicture
…   [ Line (Point { x: 0.0, y: 0.0 })
…          (Point { x: 1.0, y: 1.0 })
…   ]
… ^D

["Line [start: (0.0, 0.0), end: (1.0, 1.0)]"]

5.17 外接矩形の算出

このモジュールのコード例には、 Pictureの最小外接矩形を計算する関数 boundsが含まれています。

Boundsは外接矩形を定義するデータ型です。また、構築子をひとつだけ持つ代数的データ型として定義されています。

data Bounds = Bounds
  { top    :: Number
  , left   :: Number
  , bottom :: Number
  , right  :: Number
  }

Picture内の Shapeの配列を走査し、最小の外接矩形を累積するため、 boundsは Data.Foldableの foldl関数を使用しています。

bounds :: Picture -> Bounds
bounds = foldl combine emptyBounds
  where
    combine :: Bounds -> Shape -> Bounds
    combine b shape = union (shapeBounds shape) b

畳み込みの初期値として空の Pictureの最小外接矩形を求める必要がありますが、 emptyBoundsで定義される空の外接矩形がその条件を満たしています。

累積関数 combineは whereブロックで定義されています。 combineは foldlの再帰呼び出しで計算された外接矩形と、配列内の次の Shapeを引数にとり、ユーザ定義の演算子 unionを使ってふたつの外接矩形の和を計算しています。 shapeBounds関数は、パターン照合を使用して、単一の図形の外接矩形を計算します。

まとめ

この章では、関数型プログラミングから基本だが強力なテクニックであるパターン照合を扱いました。複雑なデータ構造の部分と照合するために、簡単なパターンだけでなく配列パターンやレコードパターンをどのように使用するかを見てきました。

またこの章では、パターン照合に密接に関連する代数的データ型を導入しました。代数的データ型がデータ構造のわかりやすい記述をどのように可能にするか、新たな操作でデータ型を拡張するためのモジュール性のある方法を提供することを見てきました。

最後に、多くの既存のJavaScript関数に型を与えるために、強力な抽象化である行多相を扱いました。この本の後半ではこれらの概念を再び扱います。

本書では今後も代数的データ型とパターン照合を使用するので、今のうちにこれらに習熟しておくと後で役立つでしょう。これ以外にも独自の代数的データ型を作成し、パターン照合を使用してそれらを使う関数を書くことを試してみてください。

目次に戻る