実例によるPureScript

ウェブのための関数型プログラミング

Phil Freeman, "PureScript by Example - Functional Programming for the Web"

5 パターン照合

5.1 この章の目標

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

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

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

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

5.2 プロジェクトの準備

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

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

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

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

module Data.Picture where

import Data.Foldable

5.3 単純なパターン照合

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

gcd :: Number -> Number -> Number
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という名前とmという名前の両方、またはどちらか一方に、入力された値を束縛しています。これより、入力の引数から名前を選ぶためのさまざまな方法に対応した、さまざまな種類のパターンを見ていくことになります。

5.4 単純なパターン

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

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

ここではこれらの単純なパターンを使用した、さらに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のときの2つに分岐するためにif .. then .. else式を使っていました。こういうときには他にガード(guard)を使うという選択肢もあります。

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

gcd :: Number -> Number -> Number
gcd n 0 = n
gcd 0 n = n
gcd n m | n > m = gcd (n - m) m 
gcd n m         = gcd n (m - n)

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

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

演習

  1. (簡単)パターン照合を使用して階乗関数を書いてみましょう。ヒント:入力がゼロのときとゼロでないときの2つの場合を考えてみましょう。

  2. (やや難しい)二項係数を計算するためのパスカルの公式(Pascal's Rule、パスカルの三角形を参照のこと)について調べてみてください。パスカルの公式を利用し、パターン照合を使って二項係数を計算する関数を記述してください。

5.6 配列のパターン照合

パターンを使って配列を照合する方法を見ていきましょう。配列リテラルパターンとConsパターンという2種類のパターンがあります。

5.6.1 配列リテラルパターン

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

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

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

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

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

> let takeFive [0, 1, a, b, _] = a * b
      takeFive _ = 0
  
> takeFive [0, 1, 2, 3, 4]
6

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

> takeFive []
0

5.6.2 Consパターン

Consパターンは空でない配列を照合するのに使います。配列の先頭の要素(head)と、配列から先頭を取り除いた残りの配列(tail)へと、配列を分離する方法を提供します。

Consパターンは、コロン(:)で区切られた、先頭に対応するパターンと残りに対応するパターンによって構成されています。数の配列の、それぞれの要素の平方を合計する関数は次のようになります。

sumOfSquares :: [Number] -> Number
sumOfSquares [] = 0
sumOfSquares (n : ns) = n * n + sumOfSquares ns

この関数は入力を空の配列と空でない配列の2つの場合に分けて扱っています。配列が空の場合、平方の和はゼロです。そうでない場合は、Consパターンを使用して配列の先頭と残り​​を分離し、先頭の要素を平方し、残りの平方の和に加算しています。

別の例も見てみましょう。次の関数は、数のリスト内のすべての隣接する数の積の合計を求めます。

sumOfProducts :: [Number] -> Number
sumOfProducts [] = 0
sumOfProducts [_] = 0
sumOfProducts (n : m : ns) = n * m + sumOfProducts (m : ns)

この関数は入力をゼロ要素、1要素、2要素以上の3つの場合に分けています。最後の場合では、最初の2つの要素を乗算し、残りの部分について再帰します。

演習

  1. (簡単)真偽値の配列のすべての要素が trueに等しいかどうかを決定する関数allTrueを書いてみてください。

  2. (やや難しい)数の配列がソートされているかどうかを調べる関数 isSortedを書いてください。

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

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

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

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

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

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

> let showPerson { first = x, last = y } = y ++ ", " ++ x

> :t 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であるようなフィールドfirstlastがレコードに少なくとも含まれていれば、関数適用は正しく型付けされます。しかし、フィールドが不足していると、showPersonの呼び出しは不正となります。

> showPerson { first: "Phil" }

Object does not have property last

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

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

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

> let showPerson p = p.last ++ ", " ++ p.first

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

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

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

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

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

type Person = { height :: Number }

totalHeight :: [Person] -> Number
totalHeight [] = 0
totalHeight ({ height = h } : ps) = h + totalHeight ps

5.9 名前付きパターン

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

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

dup :: forall a. [a] -> [a]
dup arr@(x : _) = x : arr
dup [] = []

その結果、dupは空でない配列の先頭の要素を複製します。

> dup [1, 2, 3]
[1, 1, 2, 3]

演習

  1. (簡単)レコードパターンを使って、その人の市町村を探す関数 getCity を定義してみましょう。PersonAddress型のaddressフィールドを含むレコードとして表現し、Addresscityフィールドを含まなければなりません。

  2. (やや難しい)行多相を考慮すると、getCity関数の最も一般的な型は何でしょうか?先ほど定義したtotalHeight関数についてはどうでしょうか?

  3. (やや難しい)パターンと連結演算子(++)だけを使って、配列の配列を平坦化するflatten関数を書いてみましょう。ヒント: この関数はforall a. [[a]] -> [a].という型を持っていなければなりません。

5.10 Case式

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

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

lzs :: [Number] -> [Number]
lzs [] = []
lzs xs@(_ : t) = case sum xs of
  0 -> xs
  _ -> lzs t

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

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

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

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

5.11 パターン照合の失敗

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

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

patternFailure :: Number -> Number
patternFailure 0 = 0

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

> patternFailure 10

Failed pattern match

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

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

戻り値の型としてMaybe Numberを使うよう書き直したpatternFailure関数は次のようになります。

patternFailure :: Number -> Maybe Number
patternFailure 0 = Just 0
patternFailure _ = Nothing

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データ型は、興味深い点をいくつか示しています。

この宣言ではいくつかの構築子の和としてShapeを定義しており、各構築子に含まれたデータはそれぞれ区別されます。Shapeは、中央Pointと半径を持つCircleか、RectangleLineTextのいずれかです。他には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の2つ目のフィールドでデータ型 List aを使用しており、再帰的なデータ型になっていることに注目してください。

5.13 代数的データ型の使用

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

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

exampleLine :: Shape
exampleLine = Line origin origin
  where
  origin :: Point
  origin = Point { x: 0, y: 0 }

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

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

例を見てみましょう。ShapeStringに変換したいとしましょう。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 (Circle loc text) = ...

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

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

演習

  1. (簡単)半径10で中心が原点にある円を表すShapeの値を構築してください。

  2. (やや難しい)引数のShapeを原点を中心として2倍に拡大する、ShapeからShapeへの関数を書いてみましょう。

  3. (やや難しい) Shapeからテキストを抽出する関数を書いてください。この関数はMaybe Stringを返さなければならず、もし入力がTextを使用して構築されたのでなければ、返り値にはNothing構築子を使ってください。

5.14 newtype宣言

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

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

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

newtype Pixels = Pixels Number
newtype Inches = Inches Number

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

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

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

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

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

type Picture = [Shape]

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

showPicture :: Picture -> String
showPicture picture = "[" ++ go picture ++ "]"
  where
  go :: Picture -> String
  go [] = ""
  go [x] = showShape x
  go (x : xs) = showShape x ++ ", " ++ go xs

再帰が whereブロックで定義された補助関数を使用して処理されていることに注目してください。この関数goは関数showPictureの内部でのみ参照可能で、モジュールの使用者が参照することはできません。

goは、空の配列、1要素の配列、それ以外の、3つの場合を扱います。この方針だと、文字列の末尾に余分なコンマ文字が出力されるのを避けることができます。

試してみましょう。gruntでこのモジュールをコンパイルし、psciで開きます。

$ grunt
$ psci

> :i Data.Picture

> showPicture [Line (Point { x: 0, y: 0 }) (Point { x: 1, y: 1 })]

"[Line [start: (0, 0), end: (1, 1)]]"

5.16 外接矩形の算出

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

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

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

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

bounds :: Picture -> Bounds
bounds = foldl combine emptyBounds
  where
  combine :: Bounds -> Shape -> Bounds
  combine b shape = shapeBounds shape \/ b

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

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

演習

  1. (やや難しい) ベクターグラフィックライブラリを拡張し、Shapeの面積を計算する新しい操作areaを追加してください。この演習では、テキストの面積は0であるものとしてください。

  2. (難しい) Shapeを拡張し、新しいデータ構築子Clippedを追加してください。Clippedは他のPictureを矩形に切り抜き出ます。切り抜かれたPictureの境界を計算できるよう、shapeBounds関数を拡張してください。これはShapeを再帰的なデータ型にすることに注意してください。

5.17 まとめ

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

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

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

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