Enum型クラス　〜型クラスで見るPureScript〜

<!-- # Enum型クラス -->
※この記事は「[型クラスで見るPureSciript](https://qiita.com/u4da3/items/c1692f7c6e9a53d2d3b5)」の連載記事です。

## うしろの正面だぁれ？
[前回](https://qiita.com/u4da3/items/db1a8b1169f4fa1329b9)は、Ord型クラスのサブクラスであるBounded型クラスについて学びました。今回は、Ord型クラスのもう１つのサブクラスであるEnum型クラスについて学んでみます。

Enum型クラスは__直後__と__直前__を定義する型クラスです。C言語に影響を受けた言語の多くには、インクリメントとデクリメントという計算がありますが、Enum型クラスはそれとよく似た計算をPureScriotのデータ型に導入します。

もっとも、PureScriptの言語構造上、手続き型言語で多く見られるようなカウンタを使ったロジックには不向きではありますが、初期値から順に一定範囲のデータ値を順次生成していく用途にEnum型クラスは利用することができるでしょう。

それでは、早速、はじめましょう。

## 直後と直前
<font color="#80000">この節の内容は筆者による見解を含みます。</font>

あるデータ値が別のデータ値の__直後__や__直前__であるということは、数学的にはどのように表されるのでしょう？ 残念ながら、私が調べた限りでは、直後と直前に関する数学的定義を見つけることはできませんでした。

しかしながら、これまで学んだことと、Enum型クラスが要求している関数の性質を考慮すれば、__直後__と__直前__に関して、独自の定義をすることはできそうです。

私は数学者ではないので、考慮不足があるかもしれませんし、もしかすると、私が知らないだけで数学の世界で一般的な定義が他にあるかもしれません。もし、知っている方がいましたら、教えていただけると嬉しいです。

### 直後
では、まずは__直後__の定義からしてみましょう。私なりに__直後__を定義してみると、次のようになります。

データ値 $a$ の__直後__の値が $b$ であるとは、$a$ と $b$ が次の条件を満たすことを言う。
1. 順序関係 $a<=b$ が成り立つ
2. データ値 $c$ に対して、順序関係 $a<=c<=b$ が成り立つならば、$a==c\;\text{or}\;c==b$ である。
3. $a$ と $b$ は同値ではない。すなわち、$\newcommand{\noteq}{\mathbin{\,\mathrel/\,=}} a \noteq b$ である。

若干冗長な気もしますが、こんな感じでしょうか？

１番と３番は当たり前ですね。２つ合わせれば、$a$ の直後の値は、$a$ 自身ではなく、$a$より大きいこ値であることを意味します。２番はちょっと分かりにくいですが、$a$ と $b$ の間に別の値は存在しないということです。

### 直前
__直前__の定義も順序関係を反転させるだけで、ほとんど一緒の定義ができますね。一応書いておきましょう。

データ値 $a$ の__直前__の値が $b$ であるとは、$a$ と $b$ が次の条件を満たすことを言う。
1. 順序関係 $a>=b$ が成り立つ
2. データ値 $c$ に対して、順序関係 $a>=c>=b$ が成り立つならば、$a==c\;\text{or}\;c==b$ である。
3. $a$ と $b$ は同値ではない。すなわち、$a \noteq b$ である。

__直後__について理解できていれば、解説するまでもありません。

## Enum型クラス
それでは、Enum型クラスについて見てみましょう。Enum型クラスは次のように定義されています。

```haskell
class Ord a <= Enum a where
  succ :: a -> Maybe a
  pred :: a -> Maybe a
```

ここで、関数`succ`は「successor（後継者）」の略で、関数`pred`は「predecessor（前任者）」の略です。それぞれ、あるデータ型の値の__直後__と__直前__の値を返却する関数です。Intデータ型で試すと、次のようになります。

```haskell
> succ 5
(Just 6)

> pred 5
(Just 4)
```

このように、関数`succ`と関数`pred`の返却値はMaybeデータ型で包まれてます。これは、関数`succ`と関数`pred`は失敗する可能性がある、即ち、直後の値や直前の値が存在しない可能性がるということです。これも、Intデータ型について簡単に試すことができます。

```haskell
> succ (top::Int)
Nothing

> pred (top::Int)
(Just 2147483646)

> succ (bottom::Int)
(Just -2147483647)

> pred (bottom::Int)
Nothing
```

簡単に分かることですが、最大値の__直後__や最小値の__直前__を表す値を表現することはできません。なので、それぞれの関数の結果は`Nothing`、即ち、失敗します。

Enum型クラスの挙動は理解できたでしょうか？ それでは、これまでのようにEnum型クラスの例を考えてみましょう。

## Enum型クラスの例１
[前回](https://qiita.com/u4da3/items/db1a8b1169f4fa1329b9)作成したSeasonデータ型に、Enum型クラスを実装すると次のようになります。

```haskell
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で試しておきましょう。

```haskell
> 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](https://pursuit.purescript.org/packages/purescript-enums/3.2.1/docs/Data.Enum)を見てやると、Enum型クラスの満たすべき性質について、６つの式が書かれています。これらは、それぞれ２つずつの組み合せで３種類に分類できます。それぞれ、下記のように呼ぶことにしましょう。

- 順序ルール
- 撤回ルール
- ノンスキップルール

ここでは、これらのルールについて１つずつ解釈していきたいと思います。

### 順序ルール
順序ルールは関数`succ`や`pred`を適用した結果と元の値との間の大小関係に関するルールです。最初の方で__直後__と__直前__の数学的定義をした際の、１番目と３番目を合わせたものに相当します。Puresuiteには次のように書かれています。

- Successor: all (a < _) (succ a)
- Predecessor: all (_ < a) (pred a)

ここで、`all`というのは[Data.Foldableモジュール](https://pursuit.purescript.org/packages/purescript-foldable-traversable/3.4.0/docs/Data.Foldable#v:all)で定義されている関数で、第１引数の関数を第２引数の中身全てに適用した結果が、全て`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合成](https://pursuit.purescript.org/packages/purescript-prelude/3.2.0/docs/Control.Bind#v:composeKleisli)と呼ばれている演算子で、合成演算子`>>>`とバインド演算子`>>=`の中間のようなイメージの演算子です。

気持ちとしては`>>>`を使って表現したいのですが、関数の演算結果が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モジュール](https://pursuit.purescript.org/packages/purescript-foldable-traversable/3.4.0/docs/Data.Foldable#v:any)で定義されている関数で、第１引数の関数を、第２引数の中に包まれている各値に適用していき、１つでも`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`になることを確かめてください。

```haskell
> (\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`を適用した結果と同じになることを確かめます。

```haskell
> (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`コマンドを使って複数行に分けて入力しました。

```haskell
> :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`コマンドの最後にある伝送終了&#9220;は`Ctrl`+`d`で入力します。（実際には文字は表示されません。）

これでEnum型クラスの満たすべき性質が成り立つことを確認できました。

## Enum型クラスの関数
次に、Enum型クラスの関数を幾つか見ていきましょう。Enum型クラスは値を列挙することが得意な型クラスです。ここでは代表的な３つの関数についてお話しします。

### enumFromTo
関数`enumFromTo`は範囲の上限と下限を指定して、その範囲に含まれる全ての値をUnfoldable型クラスのデータ型に格納する関数です。

言葉で説明してもよく分からないと思うので実行して見ましょう。この関数の返却値はUnfolable型クラスであれば何でもよいので、実行する時は返却値の型を明記して記述します。

```haskell
> (enumFromTo Spring Winter)::(Array Season)
[Spring,Summer,Autumn,Winter]

> (enumFromTo Winter Spring)::(Array Season)
[]
```

### upFrom
関数`upFrom`は`enumFromTo`とよく似ていますが、範囲の下限値を指定して、それより大きい値を全て列挙します。境界値自身は返却値に含まれないことに注意です。

```haskell
> (upFrom Spring)::(Array Season)
[Summer,Autumn,Winter]
```

### downFrom
関数`downFrom`は`upFrom`の逆バージョンです。範囲の上限値を指定します。上から列挙していくので順序が逆さまになります。これも上限値自身は結果に含まれません。

```haskell
> (downFrom Winter)::(Array Season)
[Autumn,Summer,Spring]
```

## Enum型クラスの例２
ところで、Enum型クラスはOrd型クラスのサブクラスなのですが、同じくOrd型クラスのサブクラスであるBounded型クラスとは別の枝に分かれています。即ち、Bounded型クラスを実装できない場合でも、Enum型クラスを実装できる可能性があるということです。

最後に、そんな少し変わった例を紹介して今回の締め括りとしましょう。

まず、[前回](https://qiita.com/u4da3/items/db1a8b1169f4fa1329b9)作成したAstrsデータ型を思い出して見ましょう。このデータ型はOrd型クラスは実装できるがBounded型クラスを実装できない例として導入しました。

実は、このAstrsデータ型にはEnum型クラスを問題なく実装することができます。Enum型クラスの実装は次のようになります。

```haskell
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型クラスを実装する際の面倒臭さを解決してくれる型クラスです。物事に行き詰まった時は、一旦来た道を引き返して、別の道からアプローチし直してみると簡単に解決できることがよくあります。次回はそんな話をする予定です。それでは、また[次回](https://qiita.com/u4da3/items/b1b14db510d26a5f60e7)。


## 演習問題
1. Bounded型クラスの回で導入したドリンクサイズを表すデータ型`DrinkSize`にEnum型クラスを実装してみてください。
1. $a$の直後の値を$b$とし、$b$の直前の値を$c$としたとき、$a==c$となることを、__直前__と__直後__の定義から証明して下さい。
1. Astrsデータ型がEnum型クラスの性質を満たしていることを確認してください。

## 参考資料
Enum型クラスについては下記のページを参考にしました。

- https://pursuit.purescript.org/packages/purescript-enums/3.2.1/docs/Data.Enum
- https://github.com/purescript/purescript-enums/blob/v3.2.1/src/Data/Enum.purs