実例によるPureScript

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

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

目次に戻る

第6章 型クラス

6.1 章の目標

この章では、PureScriptの型システムによって可能になる強力な抽象化の手法である、型クラスを導入します。

この章ではデータ構造をハッシュするためのライブラリを題材に説明していきます。データ自身の構造について直接考えることなく複雑な構造のデータのハッシュ値を求めるために、型クラスの仕組みがどのようにして働くのかを見ていきます。

また、PureScriptのPreludeや標準ライブラリに含まれる、標準的な型クラスも見ていきます。PureScriptのコードは概念を簡潔に表現するために型クラスの強力さに大きく依存しているので、これらのクラスに慣れておくと役に立つでしょう。

6.2 プロジェクトの準備

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

このプロジェクトには以下のBower依存関係があります。

モジュール Data.Hashableでは、これらのBowerパッケージによって提供されるモジュールのいくつかをインポートしています。

module Data.Hashable where

import Data.Maybe
import Data.Tuple
import Data.Either
import Data.String
import Data.Function

6.3 見せてください！(Show Me!)

型クラスの最初に扱う例は、すでに何回か見たことがある関数と関係しています。 showは、何らかの値を取り、それを文字列として表示する関数です。

showは Preludeモジュールの Showと呼ばれる型クラスで次のように定義されています。

class Show a where
  show :: a -> String

このコードでは、型変数 aでパラメータ化された、 Showという新しい型クラス(type class)を宣言しています。

型クラスインスタンスには、型クラスで定義された関数の、その型に特殊化された実装が含まれています。

例えば、Preludeにある Boolean値に対する Show型クラスインスタンスの定義は次のとおりです。

instance showBoolean :: Show Boolean where
  show true = "true"
  show false = "false"

このコードは showBool​​eanという名前の型クラスのインスタンスを宣言します。

PureScriptでは、生成されたJavaScriptの可読性を良くするために、型クラスインスタンスに名前をつけます。このとき、Boolean型は Show型クラスに属しているといいます。

PSCiで、いろいろな型の値をShow型クラスを利用して表示してみましょう。

> import Prelude
> show true
"true"

> show 1.0
"1.0"

> show "Hello World"
"\"Hello World\""

この例ではさまざまなプリミティブ型の値を showしましたが、もっと複雑な型を持つ値を showすることもできます。

> import Data.Tuple

> show (Tuple 1 true)
"(Tuple 1 true)"

> import Data.Maybe

> show (Just "testing")
"(Just \"testing\")"

型 Data.Eitherの値を表示しようとすると、興味深いエラーメッセージが表示されます。

> import Data.Either
> show (Left 10)

The inferred type

    forall a. Show a => String

has type variables which are not mentioned in the body of the type.
Consider adding a type annotation.

ここでの問題は showしようとしている型に対する Showインスタンスが存在しないということではなく、 PSCiがこの型を推論できなかったということです。このエラーメッセージで未知の型aと表示されているのがそれです。

::演算子を使って式に対して型注釈を加えると、 PSCiが正しい型クラスインスタンスを選ぶことができるようになります。

> show (Left 10 :: Either Int String)
"(Left 10)"

Showインスタンスをまったく持っていない型もあります。関数の型 ->がその一例です。 Intから Intへの関数を showしようとすると、型検証器によってその通りのエラーメッセージが表示されます。

> import Prelude
> show $ \n -> n + 1

No type class instance was found for

  Data.Show.Show (Int -> Int)

演習

  1. (簡単)前章の showShape関数を使って、 Shape型に対しての Showインスタンスを定義してみましょう。

6.4 標準的な型クラス

この節では、Preludeや標準ライブラリで定義されている標準的な型クラスをいくつか見ていきましょう。これらの型クラスはPureScript特有の抽象化の基礎としてあちこちで使われているので、これらの関数の基本についてよく理解しておくことを強くお勧めします。

Eq型クラス

Eq型クラスは、2つの値が等しいかどうかを調べるeq関数を定義しています。等値演算子(==)はeqの別名にすぎません。

class Eq a where
  eq :: a -> a -> Boolean

異なる型の2つの値を比較しても意味がありませんから、いずれの演算子も2つの引数が同じ型を持つ必要があることに注意してください。

PSCiで Eq型クラスを試してみましょう。

> 1 == 2
false

> "Test" == "Test"
true

Ord型クラス

Ord型クラスは順序付け可能な型に対して2つの値を比較する compare関数を定義します。 compare関数が定義されていると、比較演算子 <、 >と、その仲間 <=、 >=も定義されます。

data Ordering = LT | EQ | GT

class Eq a <= Ord a where
  compare :: a -> a -> Ordering

compare関数は2つの値を比較して Orderingの3つの値のうちいずれかを返します。

compare関数についても PSCiで試してみましょう。

> compare 1 2
LT

> compare "A" "Z"
LT

Num型クラス

Field型クラスは加算、減算、乗算、除算などの数値演算子を使用可能な型を示します。必要に応じて再利用できるように、これらの演算子を抽象化するわけです。

注意: 関数呼び出しが型クラスの実装に基いて呼び出されるのとは対照的に、型クラス Eqや Ordのクラスと同様に、 Field型のクラスはPureScriptでは特別に扱われ、 1 + 2 * 3のような単純な式は単純なJavaScriptへと変換されます。

class EuclideanRing a <= Field a

Field型クラスは、いくつかのより抽象的な上位クラス(Super Class)が組み合わさってできています。これは、その型はField型クラスの操作をすべてを提供しているわけではないが、その一部を提供する、というように抽象的に説明することができます。この型クラスは抽象的なすべてではないいくつかの数値演算子をサポートしています。例えば、自然数の型は加算および乗算については閉じていますが、減算については閉じていないため、この型はSemiringクラス(これはNumの上位クラスです)のインスタンスですが、RingやFieldのインスタンスではありません。

上位クラスについては、この章の後半で詳しく説明します。しかし、すべての数値型クラスの階層について述べるのはこの章の目的から外れているため、この内容に興味のある読者はpurescript-prelude内の Fieldに関するドキュメントを参照してください。

半群とモノイド

Semigroup(半群)型クラスは、連結演算子 appendを提供する型を示します。

class Semigroup a where
  append :: a -> a -> a

普通の文字列連結について文字列は半群をなし、同様に配列も半群をなします。その他の標準的なインスタンスの幾つかは、 purescript-monoidパッケージで提供されています。

以前に見た <>連結演算子は、 appendの別名として提供されています。

purescript-monoidパッケージで提供されている Monoid型クラスは、 memptyと呼ばれる空の値の概念で Semigroup型クラスを拡張します。

class Semigroup m <= Monoid m where
  mempty :: m

文字列や配列はモノイドの簡単な例になっています。

Monoid型クラスインスタンスでは、「空」の値から始めて新たな値を合成していき、その型で累積した結果を返すにはどうするかを記述する型クラスです。例えば、畳み込みを使っていくつかのモノイドの値の配列を連結する関数を書くことができます。 PSCiで試すと次のようになります。

> import Data.Monoid
> import Data.Foldable

> foldl append mempty ["Hello", " ", "World"]  
"Hello World"

> foldl append mempty [[1, 2, 3], [4, 5], [6]]
[1,2,3,4,5,6]

purescript-monoidパッケージにはモノイドと半群の多くの例を提供しており、これらを本書で扱っていきます。

Foldable型クラス

Monoid型クラスは畳み込みの結果になるような型を示しますが、 Foldable型クラスは、畳み込みの元のデータとして使えるような型構築子を示しています。

また、 Foldable型クラスは、配列や Maybeなどのいくつかの標準的なコンテナのインスタンスを含む purescript-foldable-traversableパッケージで提供されています。

Foldableクラスに属する関数の型シグネチャは、これまで見てきたものよりも少し複雑です。

class Foldable f where
  foldr :: forall a b. (a -> b -> b) -> b -> f a -> b
  foldl :: forall a b. (b -> a -> b) -> b -> f a -> b
  foldMap :: forall a m. Monoid m => (a -> m) -> f a -> m

この定義は fを配列の型構築子だと特殊化して考えてみるとわかりやすくなります。この場合、すべての aについて f aを Array aに置き換える事ができますが、 foldlと foldrの型が、最初に見た配列に対する畳み込みの型になるとわかります。

foldMapについてはどうでしょうか？これは forall a m. Monoid m => (a -> m) -> Array a -> mになります。この型シグネチャは、型 mが Monoid型クラスのインスタンスであればどんな型でも返り値の型として選ぶことができると言っています。配列の要素をそのモノイドの値へと変換する関数を提供すれば、そのモノイドの構造を利用して配列を畳み込み、ひとつの値にして返すことができます。

それでは PSCiで foldMapを試してみましょう。

> import Data.Foldable

> foldMap show [1, 2, 3, 4, 5]
"12345"

ここではモノイドとして文字列を選び、 Intを文字列として表示する show関数を使いました。それから、数の配列を渡し、それぞれの数を showしてひとつの文字列へと連結した結果出力されました。

畳み込み可能な型は配列だけではありません。 purescript-foldable-traversableでは Maybeや Tupleのような型の Foldableインスタンスが定義されており、 purescript-listsのような他のライブラリでは、そのライブラリのそれぞれのデータ型に対して Foldableインスタンスが定義されています。 Foldableは順序付きコンテナ(ordered container)の概念を抽象化するのです。

関手と型クラス則

PureScriptで副作用を伴う関数型プログラミングのスタイルを可能にするための Functorと Applicative、 Monadといった型クラスがPreludeでは定義されています。これらの抽象については本書で後ほど扱いますが、まずは「持ち上げ演算子」 mapの形ですでに見てきた Functor型クラスの定義を見てみましょう。

class Functor f where
  map :: forall a b. (a -> b) -> f a -> f b

演算子 map関数（別名<$>）は関数をそのデータ構造まで「持ち上げる」(lift)ことができます。ここで「持ち上げ」という言葉の具体的な定義は問題のデータ構造に依りますが、すでにいくつかの単純な型についてその動作を見てきました。

> import Prelude

> map (\n -> n < 3) [1, 2, 3, 4, 5]
[true, true, false, false, false]

> import Data.Maybe
> import Data.String (length)

> map length (Just "testing")
(Just 7)

map演算子は様々な構造の上でそれぞれ異なる振る舞いをしますが、 map演算子の意味はどのように理解すればいいのでしょうか。

直感的には、 map演算子はコンテナのそれぞれの要素へ関数を適用し、その結果から元のデータと同じ形状を持った新しいコンテナを構築するのだというように理解することができます。しかし、この概念を厳密にするにはどうしたらいいでしょうか？

Functorの型クラスのインスタンスは、関手則(functor laws)と呼ばれる法則を順守するものと期待されています。

最初の法則は恒等射律(identity law)です。これは、恒等関数をその構造まで持ち上げると、元の構造をそのまま返す恒等射になるということと言っています。恒等関数は入力を変更しませんから、これは理にかなっています。

第二の法則は合成律(composition law)です。構造をひとつの関数で写してから２つめの関数で写すのは、２つの関数の合成で構造を写すのと同じだ、と言っています。

「持ち上げ」の一般的な意味が何であれ、データ構造に対する持ち上げ関数の正しい定義はこれらの法則に従っていなければなりません。

標準の型クラスの多くには、このような法則が付随しています。一般に、型クラスに与えられた法則は、型クラスの関数に構造を与え、インスタンスについて調べられるようにします。興味のある読者は、すでに見てきた標準の型クラスに属する法則について調べてみてもよいでしょう。

演習

  1. (簡単)次のnewtypeは複素数を表します。

    newtype Complex = Complex 
    { real :: Number
    , imaginary :: Number 
    }

    Complexについて、 Showと Eqのインスタンスを定義してください。

6.5 型注釈

型クラスを使うと、関数の型に制約を加えることができます。例を示しましょう。 Eq型クラスのインスタンスで定義された等値性を使って、３つの値が等しいかどうかを調べる関数を書きたいとします。

threeAreEqual :: forall a. Eq a => a -> a -> a -> Boolean
threeAreEqual a1 a2 a3 = a1 == a2 && a2 == a3

この型宣言は forallを使って定義された通常の多相型のようにも見えます。しかし、太い矢印 =>で型の残りの部分から区切られた、型クラス制約(type class constraint)Eq aがあります。

インポートされたモジュールのどれかに aに対する Eqインスタンスが存在するなら、どんな型 aを選んでも threeAsEqualを呼び出すことができる、とこの型は言っています。

制約された型には複数の型クラスインスタンスを含めることができますし、インスタンスの型は単純な型変数に限定されません。 Ordと Showのインスタンスを使って2つの値を比較する例を次に示します。

showCompare :: forall a. Ord a => Show a => a -> a -> String
showCompare a1 a2 | a1 < a2 =
  show a1 <> " is less than " <> show a2
showCompare a1 a2 | a1 > a2 =
  show a1 <> " is greater than " <> show a2
showCompare a1 a2 =
  show a1 <> " is equal to " <> show a2

=>シンボルを複数回使って複数の制約を指定できることに注意してください。複数の引数のカリー化された関数を定義するのと同様です。しかし、2つの記号を混同しないように注意してください。

PureScriptコンパイラは、型の注釈が提供されていない場合、制約付き型を推測しようとします。これは、関数に対して可能な最も一般的な型を使用したい場合に便利です。

PSCiで Semiringのような標準の型クラスのいずれかを使って、このことを試してみましょう。

> import Prelude

> :type \x -> x + x
forall a. Semiring a => a -> a

ここで、この関数にはInt -> IntまたはNumber -> Numberと注釈を付けることが考えられますが、最も一般的な型がSemiringで動作するため、PSCiではIntと Numberの両方で関数を実行させることができます。

6.6 インスタンスの重複

PureScriptには型クラスのインスタンスに関する重複インスタンス規則(Overlapping instances rule)という規則があります。型クラスのインスタンスが関数呼び出しのところで必要とされるときはいつでも、PureScriptは正しいインスタンスを選択するために型検証器によって推論された情報を使用します。そのとき、その型の適切なインスタンスがちょうどひとつだけ存在しなければなりません。

これを実証するために、適当な型に対して2つの異なる型クラスのインスタンスを作成してみましょう。次のコードでは、型 Tの2つの重複する Showインスタンスを作成しています。

module Overlapped where
import Prelude
data T = T

instance showT1 :: Show T where
  show _ = "Instance 1"
  
instance showT2 :: Show T where
  show _ = "Instance 2"

このモジュールはエラーなくコンパイルされます。 PSCiを起動し、型 Tの Showインスタンスを見つけようとすると、重複インスタンス規則が適用され、エラーになります。

Overlapping instances found for Prelude.Show T

重複インスタンスルールが適用されるのは、型クラスのインスタンスの自動選択が予測可能な処理であるようにするためです。もし型に対してふたつの型クラスインスタンスを許し、モジュールインポートの順序に従ってどちらかを選ぶようにすると、実行時のプログラムの振る舞いが予測できなくなってしまい好ましくありません。

適切な法則を満たすふたつ妥当な型クラスインスタンスが存在しうるなら、既存の型を包むnewtypeを定義するのが一般的な方法です。重複インスタンスのルールの下でも、異なるnewtypeなら異なる型クラスインスタンスを持つことが許されるので、問題はなくなります。この手法はPureScriptの標準ライブラリでも使われており、例えば purescript-monoidでは、 Maybe a型は Monoid型クラスの妥当なインスタンスを複数持っています。

6.7 インスタンスの依存関係

制約された型を使うと関数の実装が型クラスインスタンスに依存できるように、型クラスインスタンスの実装は他の型クラスインスタンスに依存することができます。これにより、型を使ってプログラムの実装を推論するという、プログラム推論の強力な形式を提供します。

Show型クラスを例に考えてみましょう。要素を showする方法があるとき、その要素の配列を showする型クラスインスタンスを書くことができます。

instance showArray :: Show a => Show (Array a) where
  ...

型クラスインスタンスが複数の他のインスタンスに依存する場合、括弧で囲んでそれらのインスタンスをコンマで区切り、それを=>シンボルの左側に置く必要があります。

instance showEither :: (Show a, Show b) => Show (Either a b) where
  ...

これらの2つの型クラスインスタンスは purescript-preludeライブラリにあります。

プログラムがコンパイルされると、 Showの正しい型クラスのインスタンスは showの引数の推論された型に基づいて選ばれますが、このあたりの複雑さに開発者が関与することはありません。

演習

  1. (簡単)次は型 aの要素の空でない配列の型を定義しています。

    data NonEmpty a = NonEmpty a (Array a)

`Eq a`と `Eq (Array a)`のインスタンスを再利用して、型 `NonEmpty a`に対する `Eq`インスタンスを書いてみましょう。
  1. (やや難しい)Semigroupインスタンスを Arrayに再利用して NonEmpty aの Semigroupインスタンスを作成しましょう。
  1. (やや難しい)NonEmptyの Functorインスタンスを書いてみましょう。
  1. (やや難しい)Ordのインスタンスを持つ型 aがあれば、他の値より大きい新しい 無限の値を追加することができます。
```haskell
data Extended a = Finite a | Infinite
```

`a`の `Ord`インスタンスを再利用して、 `Extended a`の `Ord`インスタンスを書いてみましょう。
  1. (難しい)NonEmptyの Foldableインスタンスを書いてみましょう。ヒント：配列の Foldableインスタンスを再利用してみましょう。

  1. (難しい)　順序付きコンテナを定義する(そして Foldableのインスタンスを持っている)ような型構築子 fが与えられたとき、追加の要素を先頭に含めるような新たなコンテナ型を作ることができます。

    data OneMore f a = OneMore a (f a)

    このコンテナ OneMore fもまた順序を持っています。ここで、新しい要素は任意の fの要素よりも前にきます。この OneMore fの Foldableインスタンスを書いてみましょう。

    instance foldableOneMore :: Foldable f => Foldable (OneMore f) where

6.8 多変数型クラス

型クラスは必ずしもひとつの型だけを型変数としてとるわけではありません。型変数がひとつだけなのが最も一般的ですが、実際には型クラスはゼロ個以上の型変数を持つことができます。

それでは2つの型引数を持つ型クラスの例を見てみましょう。

module Stream where

import Data.Array as Array
import Data.Maybe (Maybe)
import Data.String as String

class Stream stream element where
  uncons :: stream -> Maybe { head :: element, tail :: stream }

instance streamArray :: Stream (Array a) a where
  uncons = Array.uncons

instance streamString :: Stream String Char where
  uncons = String.uncons

この Streamモジュールでは、 uncons関数を使ってストリームの先頭から要素を取り出すことができる、要素のストリームのような型を示すクラス Streamが定義されています。

Stream型クラスは、ストリーム自身の型だけでなくその要素の型も型変数として持っていることに注意してください。これによって、ストリームの型が同じでも要素の型について異なる型クラスインスタンスを定義することができます。

このモジュールでは、 unconsがパターン照合で配列の先頭の要素を取り除くような配列のインスタンスと、文字列から最初の文字を取り除くような文字列のインスタンスという、２つの型クラスインスタンスが定義されています。

任意のストリーム上で動作する関数を記述することができます。例えば、ストリームの要素に基づいて Monoidに結果を累積する関数は次のようになります。

import Prelude
import Data.Maybe (Maybe(..))
import Data.Monoid (class Monoid, mempty)

foldStream :: forall l e m. Stream l e => Monoid m => (e -> m) -> l -> m
foldStream f list =
  case uncons list of
    Nothing -> mempty
    Just cons -> f cons.head <> foldStream f cons.tail

PSCiで使って、異なる Streamの型や異なる Monoidの型について foldStreamを呼び出してみましょう。

6.9 関数従属性

多変数型クラスは非常に便利ですが、混乱しやすい型や型推論の問題にもつながります。簡単な例として、上記の Streamクラスを使って genericTail関数をストリームに書くことを考えてみましょう。

genericTail xs = map _.tail (uncons xs)

これはやや複雑なエラーメッセージを出力します。

The inferred type

  forall stream a. Stream stream a => stream -> Maybe stream

has type variables which are not mentioned in the body of the type.
Consider adding a type annotation.

エラーは、 genericTail関数が Stream型クラスの定義で言及された element型を使用しないので、その型は未解決のままであることを指しています。

さらに、特定の型のストリームに genericTailを適用することができません。

> map _.tail (uncons "testing")

The inferred type

  forall a. Stream String a => Maybe String

has type variables which are not mentioned in the body of the type.
Consider adding a type annotation.

ここでは、コンパイラが streamStringインスタンスを選択することを期待しています。結局のところ、 Stringは Charのストリームであり、他の型のストリームであってはなりません。

コンパイラは自動的にその排除を行うことはできず、 streamStringインスタンスに引き渡すことはできません。しかし、型クラス定義にヒントを追加すると、コンパイラを助けることができます。

class Stream stream element | stream -> element where
  uncons :: stream -> Maybe { head :: element, tail :: stream }

ここで、 stream -> elementは関数従属性(functional dependency)と呼ばれます。関数従属性は、多変数型クラスの型引数間の関数関係を宣言します。この関数の依存関係は、ストリーム型から（一意の）要素型への関数があることをコンパイラに伝えるので、コンパイラがストリーム型を知っていれば要素型へ適用できます。

このヒントは、コンパイラが上記の genericTail関数の正しい型を推論するのに十分です。

> :type genericTail
forall stream element. Stream stream element => stream -> Maybe stream

> genericTail "testing"
(Just "esting")

多種の型のクラスを使用して特定のAPIを設計する場合、関数従属性は非常に有用です。

6.10 型変数のない型クラス

ゼロ個の型変数を持つ型クラスを定義することもできます！これらは関数に対するコンパイル時のアサーションに対応しており、型システム内のコードの大域的な性質を追跡することができます。

たとえば、型システムを使って部分関数の使用を追跡したいとしましょう。すでに Data.Array.Partialで定義されている headと tailの部分関数を確認します。

head :: forall a. Partial => Array a -> a

tail :: forall a. Partial => Array a -> Array a

Partialモジュールの Partial型クラスのインスタンスを定義していないことに注意してください。こうすると目的を達成できます。このままの定義では head関数を使用しようとすると型エラーになるのです。

> head [1, 2, 3]

No type class instance was found for

  Prim.Partial

代わりに、これらの部分関数を利用するすべての関数で Partial制約を再発行する方法ができます。

secondElement :: forall a. Partial => Array a -> a
secondElement xs = head (tail xs)

前章で見た unsafePartial関数を使用し、部分関数を通常の関数（unsafely）として扱うことができます。 この関数は Partial.Unsafeモジュールで定義されています。

unsafePartial :: forall a. (Partial => a) -> a

Partial制約は関数の矢印の左側の括弧の中に現れますが、外側の forallでは現れません。 つまり、 unsafePartialは部分的な値から通常の値への関数です。

6.11 上位クラス

インスタンスを別のインスタンスに依存させることによって型クラスのインスタンス間の関係を表現することができるように、いわゆる上位クラス(superclass)を使って型クラス間の関係を表現することができます。

あるクラスのどんなインスタンスも、その他のあるクラスのインスタンスで必要とされているとき、前者の型クラスは後者の型クラスの上位クラスであるといい、クラス定義で逆向きの太い矢印(<=)を使い上位クラス関係を示します。

すでに上位クラスの関係の一例について見ています。 Eqクラスは Ordの上位クラスです。 Ordクラスのすべての型クラスインスタンスについて、その同じ型に対応する Eqインスタンスが存在しなければなりません。 compare関数が2つの値が比較できないと報告した時は、それらが実は同値であるかどうかを決定するために Eqクラスを使いたくなることが多いでしょうから、これは理にかなっています。

一般に、下位クラスの法則が上位クラスのメンバに言及しているとき、上位クラス関係を定義するのは理にかなっています。例えば、 Ordと Eqのインスタンスのどんな組についても、もしふたつの値が Eqインスタンスのもとで同値であるなら、 compare関数は EQを返すはずだとみなすのは妥当です。言い換えれば、 a == bならば compare a b == EQです。法則の階層上のこの関係は、 Eqと Ordの間の上位クラス関係を説明します。

この場合に上位クラス関係を定義する別の考え方としては、この２つのクラスの間には明らかに"is-a"の関係があることです。下位クラスのすべてのメンバは、上位クラスのメンバでもあるということです。

演習

  1. (やや難しい) 整数の空でない配列の最大値を求める部分関数を定義します。あなたの関数の型は Partial => Array Int - > Intでなければなりません。 unsafePartialを使ってPSCiであなたの関数をテストしてください。 ヒント：Data.Foldableの maximum関数を使います。

  1. (やや難しい) 次の Actionクラスは、ある型の動作(action)を定義する、多変数型クラスです。

    class Monoid m <= Action m a where
  act :: m -> a -> a

    actはモノイドがどうやって他の型の値を変更するのに使われるのかを説明する関数です。この動作が　モノイドの連結演算子に従っていると期待しましょう。

    • act mempty a = a
    • act (m1 <> m2) a = act m1 (act m2 a)

    この動作は Monoidクラスによって定義された操作を順守します。

    たとえば、乗算を持つ自然数のモノイドを形成します。

    newtype Multiply = Multiply Int

instance semigroupMultiply :: Semigroup Multiply where
  append (Multiply n) (Multiply m) = Multiply (n * m)

instance monoidMultiply :: Monoid Multiply where
  mempty = Multiply 1

    このモノイドは、文字列の何度かの繰り返しとして文字列に対して動作します。このアクションを実装するインスタンスを作成します。

    instance repeatAction :: Action Multiply String

    このインスタンスが上記の法則を満たしているか確かめましょう。

  2. (やや難しい) インスタンス Action m a => Action m（Array a）を書いてみましょう。ここで、 配列上の動作は要素の順序で実行されるように定義されるものとします。

  3. (難しい) 以下のnewtypeが与えられたとき、 Action m (Self m)のインスタンスを書いてみましょう。ここで、モノイド mは連結によって自身に作用するものとします。

    newtype Self m = Self m

1.（難しい）多変数型のクラス Actionの引数は、いくつかの関数従属性によって関連づけられるべきですか。それはなぜでしょうか。

6.12 ハッシュの型クラス

この最後の節では、章の残りを費やしてデータ構造をハッシュするライブラリを作ります。

このライブラリの目的は説明だけであり、堅牢なハッシングの仕組みの提供を目的としていないことに注意してください。

ハッシュ関数に期待される性質とはどのようなものでしょうか？

最初の性質はまさに型クラスの法則のように見える一方で、２番目の性質はもっとぼんやりとした規約に従っていて、PureScriptの型システムによって確実に強制できるようなものではなさそうです。しかし、これは型クラスについて次のような直感的理解を与えるはずです。

newtype HashCode = HashCode Int

hashCode :: Int -> HashCode
hashCode h = HashCode (h `mod` 65535)

class Eq a <= Hashable a where
  hash :: a -> HashCode

これに、 a == bならば hash a == hash bという関係性の法則が付随しています。

この節の残りの部分を費やして、 Hashable型クラスに関連付けられているインスタンスと関数のライブラリを構築していきます。

決定的な方法でハッシュ値を結合する方法が必要になります。

combineHashes :: HashCode -> HashCode -> HashCode
combineHashes (HashCode h1) (HashCode h2) = hashCode (73 * h1 + 51 * h2)

combineHashes関数は、２つのハッシュ値を混ぜて結果を0-65535の間に分布します。

それでは、入力の種類を制限する Hashable制約を使う関数を書いてみましょう。ハッシュ関数を必要とするよくある目的としては、2つの値が同じハッシュ値にハッシュされるかどうかを決定することです。 hashEqual関係はそのような機能を提供します。

hashEqual :: forall a. Hashable a => a -> a -> Boolean
hashEqual = eq `on` hash

この関数はハッシュ同値性を定義するために Data.Functionの on関数を使っていますが、このハッシュ同値性の定義は『それぞれの値が hash関数に渡されたあとで２つの値が等しいなら、それらの値は「ハッシュ同値」である』というように宣言的に読めるはずです。

プリミティブ型の Hashableインスタンスをいくつか書いてみましょう。まずは整数のインスタンスです。 HashCodeは実際には単なるラップされた整数なので、これは簡単です。hashCodeヘルパー関数を使うことができます。

instance hashInt :: Hashable Int where
  hash = hashCode

パターン照合を使うと、Boolean値の単純なインスタンスを定義することもできます。

instance hashBoolean :: Hashable Boolean where
  hash false = hashCode 0
  hash true  = hashCode 1

整数のインスタンスでは、 Data.Charの toCharCode関数を使うとCharをハッシュするインスタンスを作成できます。

instance hashChar :: Hashable Char where
  hash = hash <<< toCharCode

（要素型が Hashableのインスタンスでもあるならば）配列の要素に hash関数を mapしてから、 combineHashes関数の結果を使ってハッシュを左側に畳み込むことで、配列のインスタンスを定義します。

instance hashArray :: Hashable a => Hashable (Array a) where
  hash = foldl combineHashes (hashCode 0) <<< map hash

すでに書いたより単純なインスタンスを使用して新たなインスタンスを構築する方法に注目してください。 StringをCharの配列に変換し、この新たなArrayインスタンスを使ってStringインスタンスを定義しましょう。

instance hashString :: Hashable String where
  hash = hash <<< toCharArray

これらの Hashableインスタンスが先ほどの型クラスの法則を満たしていることを証明するにはどうしたらいいでしょうか。同じ値が等しいハッシュ値を持っていることを確認する必要があります。 Int、 Char、 String、 Booleanの場合は、 Eqの意味では同じ値でも厳密には同じではない、というような型の値は存在しないので簡単です。

もっと面白い型についてはどうでしょうか。この場合、配列の長さに関する帰納を使うと、型クラスの法則を証明することができます。長さゼロの唯一の配列は []です。配列の Eqの定義により、任意の二つの空でない配列は、それらの先頭の要素が同じで配列の残りの部分が等しいとき、その時に限り等しくなります。この帰納的な仮定により、配列の残りの部分は同じハッシュ値を持ちますし、もし Hashable aインスタンスがこの法則を満たすなら、先頭の要素も同じハッシュ値をもつことがわかります。したがって、２つの配列は同じハッシュ値を持ち、 Hashable（Array a）も同様に型クラス法則を満たしています。

この章のソースコードには、 Maybeと Tuple型のインスタンスなど、他にも Hashableインスタンスの例が含まれています。

演習

  1. (簡単)PSCiを使って、各インスタンスのハッシュ関数をテストしてください。

  2. (やや難しい) 同値性の近似として hashEqual関数のハッシュ同値性を使い、配列が重複する要素を持っているかどうかを調べる関数を書いてください。ハッシュ値が一致したペアが見つかった場合は、 ==を使って値の同値性を厳密に検証することを忘れないようにしてください。 ヒント：Data.Arrayの nubBy関数を使用してみてください。

  3. (やや難しい) 型クラスの法則を満たす、次のnewtypeの Hashableインスタンスを書いてください。

    newtype Hour = Hour Int

instance eqHour :: Eq Hour where
  eq (Hour n) (Hour m) = mod n 12 == mod m 12

    newtypeの Hourとその Eqインスタンスは、12進数である型を表します。したがって、1と13は等しいと見なされます。そのインスタンスが型クラスの法則を満たしていることを証明してください。

  4. (難しい)Maybe、 Either、 Tupleの Hashableインスタンスが型クラスの法則を満たしていることを証明してください。

まとめ

この章では、型に基づく抽象化で、コードの再利用のための強力な形式化を可能にする型クラスを導入しました。PureScriptの標準ライブラリから標準の型クラスを幾つか見てきました。また、ハッシュ値を計算する型クラスに基づく独自のライブラリを定義しました。

この章では型クラス法則の考え方を導入するとともに、抽象化のための型クラスを使うコードについて、その性質を証明する手法を導入しました。型クラス法則は等式推論(equational reasoning)と呼ばれる大きな分野の一部であり、プログラミング言語の性質と型システムはプログラムについて論理的な推論をできるようにするために使われています。これは重要な考え方で、本書では今後あらゆる箇所で立ち返る話題となるでしょう。

目次に戻る