※この記事は「型クラスで見るPureSciript」の連載記事です。
うしろの正面だぁれ？
前回は、Ord型クラスのサブクラスであるBounded型クラスについて学びました。今回は、Ord型クラスのもう１つのサブクラスであるEnum型クラスについて学んでみます。
Enum型クラスは__直後__と__直前__を定義する型クラスです。C言語に影響を受けた言語の多くには、インクリメントとデクリメントという計算がありますが、Enum型クラスはそれとよく似た計算をPureScriotのデータ型に導入します。
もっとも、PureScriptの言語構造上、手続き型言語で多く見られるようなカウンタを使ったロジックには不向きではありますが、初期値から順に一定範囲のデータ値を順次生成していく用途にEnum型クラスは利用することができるでしょう。
それでは、早速、はじめましょう。
直後と直前
この節の内容は筆者による見解を含みます。
あるデータ値が別のデータ値の__直後__や__直前__であるということは、数学的にはどのように表されるのでしょう？ 残念ながら、私が調べた限りでは、直後と直前に関する数学的定義を見つけることはできませんでした。
しかしながら、これまで学んだことと、Enum型クラスが要求している関数の性質を考慮すれば、__直後__と__直前__に関して、独自の定義をすることはできそうです。
私は数学者ではないので、考慮不足があるかもしれませんし、もしかすると、私が知らないだけで数学の世界で一般的な定義が他にあるかもしれません。もし、知っている方がいましたら、教えていただけると嬉しいです。
直後
では、まずは__直後__の定義からしてみましょう。私なりに__直後__を定義してみると、次のようになります。
データ値 $a$ の__直後__の値が $b$ であるとは、$a$ と $b$ が次の条件を満たすことを言う。
- 順序関係 $a<=b$ が成り立つ
- データ値 $c$ に対して、順序関係 $a<=c<=b$ が成り立つならば、$a==c;\text{or};c==b$ である。
- $a$ と $b$ は同値ではない。すなわち、$\newcommand{\noteq}{\mathbin{,\mathrel/,=}} a \noteq b$ である。
若干冗長な気もしますが、こんな感じでしょうか？
１番と３番は当たり前ですね。２つ合わせれば、$a$ の直後の値は、$a$ 自身ではなく、$a$より大きいこ値であることを意味します。２番はちょっと分かりにくいですが、$a$ と $b$ の間に別の値は存在しないということです。
直前
__直前__の定義も順序関係を反転させるだけで、ほとんど一緒の定義ができますね。一応書いておきましょう。
データ値 $a$ の__直前__の値が $b$ であるとは、$a$ と $b$ が次の条件を満たすことを言う。
- 順序関係 $a>=b$ が成り立つ
- データ値 $c$ に対して、順序関係 $a>=c>=b$ が成り立つならば、$a==c;\text{or};c==b$ である。
- $a$ と $b$ は同値ではない。すなわち、$a \noteq b$ である。
__直後__について理解できていれば、解説するまでもありません。
Enum型クラス
それでは、Enum型クラスについて見てみましょう。Enum型クラスは次のように定義されています。
class Ord a <= Enum a where
succ :: a -> Maybe a
pred :: a -> Maybe a
ここで、関数succは「successor（後継者）」の略で、関数predは「predecessor（前任者）」の略です。それぞれ、あるデータ型の値の__直後__と__直前__の値を返却する関数です。Intデータ型で試すと、次のようになります。
> succ 5
(Just 6)
> pred 5
(Just 4)
このように、関数succと関数predの返却値はMaybeデータ型で包まれてます。これは、関数succと関数predは失敗する可能性がある、即ち、直後の値や直前の値が存在しない可能性がるということです。これも、Intデータ型について簡単に試すことができます。
> succ (top::Int)
Nothing
> pred (top::Int)
(Just 2147483646)
> succ (bottom::Int)
(Just -2147483647)
> pred (bottom::Int)
Nothing
簡単に分かることですが、最大値の__直後__や最小値の__直前__を表す値を表現することはできません。なので、それぞれの関数の結果はNothing、即ち、失敗します。
Enum型クラスの挙動は理解できたでしょうか？ それでは、これまでのようにEnum型クラスの例を考えてみましょう。
Enum型クラスの例１
前回作成したSeasonデータ型に、Enum型クラスを実装すると次のようになります。
instance enumSeason :: Enum Season where
succ s = case s of
Spring -> Just Summer
Summer -> Just Autumn
Autumn -> Just Winter
Winter -> Nothing
pred s = case s of
Spring -> Nothing
Summer -> Just Spring
Autumn -> Just Summer
Winter -> Just Autumn
結果は分かりきっているとは思いますが、一応PSCIで試しておきましょう。
> map succ [Spring,Summer,Autumn,Winter]
[(Just Summer),(Just Autumn),(Just Winter),Nothing]
> map pred [Spring,Summer,Autumn,Winter]
[Nothing,(Just Spring),(Just Summer),(Just Autumn)]
Enum型クラスの性質
Enum型クラスの性質については、論理的に考えるよりも、直感的に理解した方が早いです。なので、今回は、先に具体例を理解することを優先してみました。しかし、それだけでは理解が深まらないと思うので、Enum型クラスの性質について論理的な視点からも見直してみましょう。
Puresuiteを見てやると、Enum型クラスの満たすべき性質について、６つの式が書かれています。これらは、それぞれ２つずつの組み合せで３種類に分類できます。それぞれ、下記のように呼ぶことにしましょう。
- 順序ルール
- 撤回ルール
- ノンスキップルール
ここでは、これらのルールについて１つずつ解釈していきたいと思います。
順序ルール
順序ルールは関数succやpredを適用した結果と元の値との間の大小関係に関するルールです。最初の方で__直後__と__直前__の数学的定義をした際の、１番目と３番目を合わせたものに相当します。Puresuiteには次のように書かれています。
- Successor: all (a < _) (succ a)
- Predecessor: all (_ < a) (pred a)
ここで、allというのはData.Foldableモジュールで定義されている関数で、第１引数の関数を第２引数の中身全てに適用した結果が、全てtrueである時にtrueを返却する関数です。
succやpredの結果はMaybe型で包まれるので、a < (succ a)のような書き方ができません。そのため、Maybeの中身と比較するために関数allを使っています。ややこしい書き方ですが、感覚的にはa < (succ a)や(pred a) < aを表現したいだけだと解釈すれば十分でしょう。（Nothingを考慮するとanyとの使い分けが実は重要だったりします。）
つまり、「$a$の直後は$a$より大きい。$a$の直前は$a$より小さい。」ということです。当たり前のことを言っているだけですね。
撤回ルール
次に撤回ルールです。このルールは、簡単に言えば「関数succと関数predは互いに打ち消し合う性質を持っている」ということです。Pursuiteでは、次のように書かれています。
- Succ retracts pred:
pred >=> succ >=> pred=pred - Pred retracts succ:
succ >=> pred >=> succ=succ
見慣れない演算子>=>が出てきましたが、これはKleisli合成と呼ばれている演算子で、合成演算子>>>とバインド演算子>>=の中間のようなイメージの演算子です。
気持ちとしては>>>を使って表現したいのですが、関数の演算結果がMaybeデータ型で包まれてしまうので、代わりに>=>を使って合成していると思えば十分です。
見慣れない演算子に惑わされましたが、ルールの内容について見てみましょう。
ルールの１つ目は、最初のpredの結果が次のsuccによって打ち消されて、最後のpredだけが有効な演算として生き残るという意味です。別の言い方をすると、関数predの結果に対してsuccを適用することで、先に適用したpredの演算を撤回することができるということです。
ルール２つ目はその逆ですね。最初のsuccの結果が次のpredによって打ち消されて、最後のsuccだけが有効な演算になります。
撤回ルールは、__直後__と__直前__の定義から導き出すことができます。興味がある方は証明してみてください。
ノンスキップルール
最後にノンスキップルールです。このルールは関数succや関数predを適用した際に、跳ばされる値が存在しないと言う意味です。__直後__と__直前__の定義をした際の、２番目の条件に相当します。
最大値と最小値が定義されている場合は、別の言い方をすることができます。その場合は、最小値から順にsuccを適用したり、最大値から順にpredを適用したりすれば、そのデータ型で表現される全ての値を走査することができるとも言えます。
このルールは、Pursuiteには次のように書かれています。
- Non-skipping succ:
b <= a || any (_ <= b) (succ a) - Non-skipping pred:
a <= b || any (b <= _) (pred a)
このままだと、ちょっと理解しにくいですね。１つ目の式を例にして、分解しながら少しずつ考えてみましょう。
||
まず、この式の真ん中にある||はOR演算子です。つまり、||に対して左辺と右辺のうち少なくとも一方は必ずtrueになるという意味です。なので、左辺と右辺に分けて考えれば良いことがわかります。
a <= b
左辺は簡単で、aはb以上であることを意味します。__左辺が成り立つ時__は右辺の結果に関わらず全体がtrueになるので__右辺を考える必要がありません。__すなわち、__右辺が重要な意味を持つのは左辺がfalseの時__であることが分かります。
左辺が成り立たない時、言い直すと、aがbより小さい時に右辺が重要な意味を持ちます。つまり、このルールが本当に言わんとしていることは、「aがbより小さい時に右辺が成り立つようにせよ」ということなのです。
any
右辺を見てやると、何やらanyという関数が現れています。関数anyはData.Foldableモジュールで定義されている関数で、第１引数の関数を、第２引数の中に包まれている各値に適用していき、１つでもtrueであれば、trueを返却する関数です。
(_ <= b)
その次の(_ <= b)はラムダ式です。引数が_で表されていますが、書き換えると(\x -> x <= b)と一緒です。 あまり詳しくないですが、イータ変換とか呼ぶやつですかね？ 本題からそれるので、あまり気にしないでおきましょう。
この式は__trueになる条件を考えるよりも、falseにならない条件を考える__方がわかりやすいです。
第１引数の結果がfalseになる条件は、乱暴な言い方をすると、(succ a)の結果がbより大きくなることです。falseになる条件にイコールが含まれないことが重要です。
これを否定形にすれば、falseにならない条件の出来上がりです。即ち、「指定された条件下では、(succ a)の結果がbより大きくならないようにせよ」という事を意味します。
b <= a || any (_ <= b) (succ a)
ここまで来れば、あとは分解した式を、再度組み立てるだけです。
この条件式が言いたかったのは「bより小さなどんなデータ値aに対して関数succを適用しても、その結果がbより大きくなることはないようにせよ」ということです。
特に、a < bを満たすような最大の値をaに選んだ場合でも、(succ a)の結果はbとイコールになることはあっても、__bを跳び越えるようなことはない__ということが重要です。
２つ目の条件式も同じようなことを言っています。すぐに分からない方は、同じように分解して意味を確かめてみてください。
Enum型クラスの例２
Enum型クラスの満たすべき性質を理解したので、先ほど作成したSeasonデータ型が、Enum型クラスの性質を満たすように実装できていることを確かめましょう。
まずは、順序ルールです。全ての結果がtrueになることを確かめてください。
> (\a -> (all (a < _) (succ a))) <$> [Spring,Summer,Autumn,Winter]
[true,true,true,true]
> (\a -> (all (_ < a) (pred a))) <$> [Spring,Summer,Autumn,Winter]
[true,true,true,true]
次に、撤回ルールです。それぞれ、単独のpredやsuccを適用した結果と同じになることを確かめます。
> (pred >=> succ >=> pred) <$> [Spring,Summer,Autumn,Winter]
[Nothing,(Just Spring),(Just Summer),(Just Autumn)]
> (succ >=> pred >=> succ) <$> [Spring,Summer,Autumn,Winter]
[(Just Summer),(Just Autumn),(Just Winter),Nothing]
最後に、ノンスキップルールです。入力が長くて煩わしいのでPSCIのpasteコマンドを使って複数行に分けて入力しました。
> :p
… (\a b -> (b <= a || any (_ <= b) (succ a)))
… <$> [Spring,Summer,Autumn,Winter]
… <*> [Spring,Summer,Autumn,Winter]
… ␄
[true,true,true,true,true,true,true,true,true,true,true,true,true,true,true,true]
> :p
… (\a b -> (a <= b || any (b <= _) (pred a)))
… <$> [Spring,Summer,Autumn,Winter]
… <*> [Spring,Summer,Autumn,Winter]
… ␄
[true,true,true,true,true,true,true,true,true,true,true,true,true,true,true,true]
※上記で、:pコマンドの最後にある伝送終了␄はCtrl+dで入力します。（実際には文字は表示されません。）
これでEnum型クラスの満たすべき性質が成り立つことを確認できました。
Enum型クラスの関数
次に、Enum型クラスの関数を幾つか見ていきましょう。Enum型クラスは値を列挙することが得意な型クラスです。ここでは代表的な３つの関数についてお話しします。
enumFromTo
関数enumFromToは範囲の上限と下限を指定して、その範囲に含まれる全ての値をUnfoldable型クラスのデータ型に格納する関数です。
言葉で説明してもよく分からないと思うので実行して見ましょう。この関数の返却値はUnfolable型クラスであれば何でもよいので、実行する時は返却値の型を明記して記述します。
> (enumFromTo Spring Winter)::(Array Season)
[Spring,Summer,Autumn,Winter]
> (enumFromTo Winter Spring)::(Array Season)
[]
upFrom
関数upFromはenumFromToとよく似ていますが、範囲の下限値を指定して、それより大きい値を全て列挙します。境界値自身は返却値に含まれないことに注意です。
> (upFrom Spring)::(Array Season)
[Summer,Autumn,Winter]
downFrom
関数downFromはupFromの逆バージョンです。範囲の上限値を指定します。上から列挙していくので順序が逆さまになります。これも上限値自身は結果に含まれません。
> (downFrom Winter)::(Array Season)
[Autumn,Summer,Spring]
Enum型クラスの例２
ところで、Enum型クラスはOrd型クラスのサブクラスなのですが、同じくOrd型クラスのサブクラスであるBounded型クラスとは別の枝に分かれています。即ち、Bounded型クラスを実装できない場合でも、Enum型クラスを実装できる可能性があるということです。
最後に、そんな少し変わった例を紹介して今回の締め括りとしましょう。
まず、前回作成したAstrsデータ型を思い出して見ましょう。このデータ型はOrd型クラスは実装できるがBounded型クラスを実装できない例として導入しました。
実は、このAstrsデータ型にはEnum型クラスを問題なく実装することができます。Enum型クラスの実装は次のようになります。
instance enumAstrs :: Enum Astrs where
succ a = Just(a ++ Astr)
pred Astr = Nothing
pred a = Just(genAstrs (countAstr a - 1))
注目するべきは関数succがNothingを返却する場合が無いということでしょう。前回お話しした通りAstrsデータ型は最小値は存在しても最大値は存在しないデータ型でした。そのため、関数succはメモリの許す限り、いつまでたってもJustを返却し続けます。
３歩進んで２歩退がる
今回はEnum型クラスについて学んでみました。Enum型クラスは、その名の通り、列挙型のような構造のデータ型を扱うのに適した型クラスです。
ところが、列挙メンバの数が増えてくるとEnum型クラスの実装は非常に面倒なものとなってきます。特に、Enum型クラスの前提となるOrd型クラスは、値の組み合わせが $\mathcal{O}(n^2)$ で増えていくので厄介です。他の言語だと、列挙型は整数の実行時表現を持っていたりするので解決策もありそうですが、PureScriptの列挙型データ構造は値の数だけコンストラクタを定義するのが主流なので、厄介です。
次回ご紹介するBoundedEnum型クラスは、そんなEnum型クラスを実装する際の面倒臭さを解決してくれる型クラスです。物事に行き詰まった時は、一旦来た道を引き返して、別の道からアプローチし直してみると簡単に解決できることがよくあります。次回はそんな話をする予定です。それでは、また次回。
演習問題
- Bounded型クラスの回で導入したドリンクサイズを表すデータ型
DrinkSizeにEnum型クラスを実装してみてください。 - $a$の直後の値を$b$とし、$b$の直前の値を$c$としたとき、$a==c$となることを、__直前__と__直後__の定義から証明して下さい。
- Astrsデータ型がEnum型クラスの性質を満たしていることを確認してください。
参考資料
Enum型クラスについては下記のページを参考にしました。