Symbolのすごく簡単な具体例をひとつ（＋解説）

# はじめに

[前回](https://qiita.com/matoruru/items/b1aa529eec22e266c91f)はRowToListについての簡単記事を書きました。続きというわけではないですが、同じような構成の記事を書いてみます。

# 目的

**Symbolの文字列（5文字）を逆順にしたい**("ABCDE"から"EDCBA"、など)。

今回は簡単な具体例ということで、文字列の長さは5文字固定にします。こういうものには再帰を使った例が多い気がするのですが、ここでは再帰を使っていません。再帰を使わない本記事の方法では文字数の固定やコード量の増加など不都合なことは多いですが、今回はあくまでSymbolの例として分かりやすいことを重視しているので、気にせず！(記事の最後におまけとして再帰を使った改善例を載せています)

# 基礎知識

ここは飛ばしてもいいかもしれません。興味がある方はぜひ読んでみてください！

Symbolはtype(型)ではなくkind(種)なので、そのまま型として使うことができません。

型は`Int`や`String`、`Array a`、`Maybe a`などで（ここで`Array`と`Maybe`は型をもらって型を返す型コンストラクタです。`Array Int`など。）、関数や値の型を明示するときに「::」の右側に書くことのできるものです。

```haskell
func1 :: Int -> Int
func1 a = a

func2 :: Array Int -> String
func2 _ = "atai wo mushi shitemasu."

func3 :: Maybe Int -> Int
func3 (Just v) = (v :: Int)  -- 書く必要ない 
func3 Nothing  = (0 :: Int)  -- ですが、一例です
```

対して、種であるSymbolでは例えば、以下のようなことができません。

```haskell
func :: "This is a symbol" -> Int
func _ = 1

-- こんなエラーが出ます
-- [PureScript Kinds DoNotUnify] [E]  Could not match kind
--
--    Type
--  with kind
--    Symbol
```

型が書かれるべき場所に種を書いてしまったので、エラーになってしまいました。`Int`に対する`1`、`Array String`に対する`["a", "b"]`、`Maybe Int`に対する`Just 2`、などのように、その型に属する値を作ることが種の場合はできません。

ここで、代数的データ型の宣言方法を見てみましょう。

```haskell
-- MyType1型の値としてNeko、Hello、Oyatsu、Matoruruが存在する
data MyType1 = Neko | Hello | Oyatsu | Matoruru

-- MyType2 a型の値としてInu a、Dog、B aが存在する
data MyType2 a = Inu a | Dog | B a
```

これらはこんなふうに使えます。

```haskell
func1 :: MyType1
func1 = Neko

func2 :: MyType1 -> MyType2 Int
func2 _ = Inu 2

func3 :: MyType1 -> MyType2 String
func3 _ = Dog

func4 :: MyType2 String
func4 = func3 $ Oyatsu
```

結構重要なのが`MyType2 a`型の`Dog`ですが、これは`MyType2 Int`型でも`MyType2 String`型でも`MyTpe2 (Array Int)`型でも、見た目は同じ`Dog`として型情報を隠し持っています。`Maybe a`型の`Nothing`とか、`Array a`型の`[]`とかもそれです。

```haskell
func1 :: MyType2 String
func1 = Dog

func2 :: MyType2 (Array Int)
func2 = Dog

func3 :: MyType2 String
func3 = func1

func4 :: MyType2 String
func4 = func2 -- 見た目は同じDogなのに、これはできない！
```

見た目は同じでも、型情報を持つことができるということです。同じような宣言方法で、代数的データ型は種であるSymbolを受け取って型を作ることができます。

```haskell
data MyType3 (sym :: Symbol) = Meow

-- symは型ではないので、これはできない
data MyType4 (sym :: Symbol) = Meoww sym
```

さっきの`MyType2`の例と同じようなことをしてみましょう。

```haskell
func1 :: MyType3 "ohayo!"
func1 = Meow

func2 :: MyType3 "hajimemashite"
func2 = Meow

func3 :: MyType3 "ohayo!"
func3 = func1

func4 :: MyType3 "ohayo!"
func4 = func2 -- 見た目は同じMeowなのに、これはできない！
```

つまり、そのままでは型の世界に存在できない種の情報を持ち、型引数を通して種を受け渡しできる値が作れたということです。

このような型と値はよくProxyという名前で使われます。種SymbolのProxyは`SProxy`、種NatのProxyは`NProxy`とか、そのような名付け方をされます。

以下のように書きます。

```haskell
data SProxy (sym :: Symbol) = SProxy
```

先程の例で出した`MyType3`型と同じ形式ですね。

せっかく作りましたが、`SProxy`は既に[Pursuit](https://pursuit.purescript.org/packages/purescript-prelude/4.1.1/docs/Data.Symbol#t:SProxy)にあります。

本題に戻ります。

# 具体例

```haskell:Main.purs
module Main where

import Prim.Symbol as Symbol
import Type.Prelude (SProxy(..))

class Cons5
  (s1 :: Symbol)
  (s2 :: Symbol)
  (s3 :: Symbol)
  (s4 :: Symbol)
  (s5 :: Symbol)
  (sym :: Symbol)
  | s1 s2 s3 s4 s5 -> sym
  , sym -> s1 s2 s3 s4 s5

instance cons5 ::
  ( Symbol.Cons s1 t1 sym
  , Symbol.Cons s2 t2 t1
  , Symbol.Cons s3 t3 t2
  , Symbol.Cons s4 t4 t3
  , Symbol.Cons s5 t5 t4
  ) => Cons5 s1 s2 s3 s4 s5 sym

class Reverse (original :: Symbol) (reversed :: Symbol) | original -> reversed

instance reverse ::
  ( Cons5 s1 s2 s3 s4 s5 original
  , Cons5 s5 s4 s3 s2 s1 reversed
  ) => Reverse original reversed

test1 :: SProxy "EDCBA"
test1 = SProxy :: forall output. Reverse "ABCDE" output => SProxy output

test2 :: SProxy "ABCDE"
test2 = SProxy :: forall output. Reverse "EDCBA" output => SProxy output

test3 :: SProxy "NEKO!"
test3 = SProxy :: forall output. Reverse "!OKEN" output => SProxy output
```

`test1`、`test2`、`test3`では目的の型(元のSymbol文字列が逆順になっているもの)がうまく導出されたかどうかを確かめています。

型クラス`Reverse`と`Cons5`は、Symbolを変換する関数のように動作します。

`Reverse`は、型引数`original`として受け取ったSymbolを逆順に並べ替え、それを型引数`reversed`にします。内部で`Cons5`を使います。

`Cons5`には2つの役割があり、1つ目は`sym`として受け取ったSymbolを`s1`、`s2`、`s3`、`s4`、`s5`に分解すること、2つ目はその逆で`s1`、`s2`、`s3`、`s4`、`s5`として受け取ったSymbolを結合して`sym`にすることです。

# 順番に見る＋解説

少しずつ増やしながら見ていきます。

### 1. Symbolを分解する型クラス`Cons5`を用意する

`Cons`型クラスは、`Cons a b c`のとき、`c`に受け取ったSymbolの1文字目を`a`、それ以降を`b`にします。また逆に、`a`に受け取った1文字と`b`に受け取った数文字を結合したものを`c`にすることもできます。例えば、`Cons "N" "eko" "Neko"`です。`Cons a b "Neko"`のとき、`a`は`"N"`、`b`は`"eko"`になります。

この知識で、以下の`Cons5`型クラスとインスタンスの宣言が読めます。

```haskell
class Cons5
  (s1 :: Symbol)
  (s2 :: Symbol)
  (s3 :: Symbol)
  (s4 :: Symbol)
  (s5 :: Symbol)
  (sym :: Symbol)
  | s1 s2 s3 s4 s5 -> sym
  , sym -> s1 s2 s3 s4 s5

instance cons5 ::
  ( Symbol.Cons s1 t1 sym
  , Symbol.Cons s2 t2 t1
  , Symbol.Cons s3 t3 t2
  , Symbol.Cons s4 t4 t3
  , Symbol.Cons s5 t5 t4
  ) => Cons5 s1 s2 s3 s4 s5 sym
```

`Cons5`は、6個の型引数を持ち、受け取った5つのSymbolを結合して`sym`にするか、`sym`を5つに分解することができます。実際の動作はインスタンスの型制約に書いてあります。

まず、`sym`に`"Hello"`を受け取ったとして、分解の方から見ていきます。

1. `sym`が`"Hello"`なので、`Cons`により`s1`が`"H"`、`t1`が`"ello"`だとわかる。
2. `t1`が`"ello"`なので、`Cons`により`s2`が`"e"`、`t2`が`"llo"`だとわかる。
3. `t2`が`"llo"`なので、`Cons`により`s3`が`"l"`、`t3`が`"lo"`だとわかる。
4. `t3`が`"lo"`なので、`Cons`により`s4`が`"l"`、`t4`が`"o"`だとわかる。
5. `t4`が`"o"`なので、`Cons`により`s5`が`"o"`、`t5`が`""`だとわかる。
6. 以上をまとめて、`Cons5 s1 s2 s3 s4 s5 sym`は`Cons5 "H" "e" "l" "l" "o" "Hello"`だとわかる。

結合ではこの逆のことが行われます。この場合は`Symbol.Cons s5 t5 t4`の`t5`がわからないままですが、最終的にはつじつま合わせで空白だったことにしてくれます。つじつま合わせのために、型注釈が必要になります。型注釈が間違っている場合は型エラーを出して知らせてくれます(正しくするまでコンパイルできない)。

### 2. Symbolを逆順にする型クラス`Reverse`を用意する

```haskell
class Cons5
  (s1 :: Symbol)
  (s2 :: Symbol)
  (s3 :: Symbol)
  (s4 :: Symbol)
  (s5 :: Symbol)
  (sym :: Symbol)
  | s1 s2 s3 s4 s5 -> sym
  , sym -> s1 s2 s3 s4 s5

instance cons5 ::
  ( Symbol.Cons s1 t1 sym
  , Symbol.Cons s2 t2 t1
  , Symbol.Cons s3 t3 t2
  , Symbol.Cons s4 t4 t3
  , Symbol.Cons s5 t5 t4
  ) => Cons5 s1 s2 s3 s4 s5 sym

class Reverse (original :: Symbol) (reversed :: Symbol) | original -> reversed

instance reverse ::
  ( Cons5 s1 s2 s3 s4 s5 original
  , Cons5 s5 s4 s3 s2 s1 reversed
  ) => Reverse original reversed
```

`Reverse`型クラスのインスタンスの中で、1. で用意した`Cons5`を使っています。`Reverse`は`|`の横に書かれた関数従属性(functional dependency)`original -> reversed`により、`original`から`reversed`を導出できることがわかります。

`forall output. Reverse "Hello" output`のように型クラスが使われた場面を考えます。

1. `Reverse "Hello" reversed`として型引数`original`のSymbolが決まる。
2. `original`が`"Hello"`であることがわかっているので、`Cons5 s1 s2 s3 s4 s5 original`は`Cons5 s1 s2 s3 s4 s5 "Hello"`になることがわかる。
3. `Cons5`型クラスは`sym`に渡されたSymbolを`s1`、`s2`、`s3`、`s4`、`s5`に分解できるので、`Cons5 s1 s2 s3 s4 s5 "Hello"`は`Cons5 "H" "e" "l" "l" "o" "Hello"`になることがわかる。
4. 次の`Cons5`では`s5`〜`s1`はわかっているので、5文字を結合して`reversed`を導出できる。上の`Cons5`と下の`Cons5`では分解された各Symbolを逆順に並べているので、`Cons5 "o" "l" "l" "e" "H" reversed`となる。ここから、`Cons5 "o" "l" "l" "e" "H" "olleH"`と、`reversed`が`"olleH"`であることがわかる。
5. `Reverse "Hello" reversed`は`Reverse "Hello" "olleH"`であることがわかった。
6. `forall output. Reverse "Hello" output`の`output`が`"olleH"`になることがわかる。

ここまでで、ある5文字のSymbol文字列から逆順を導出できるようになりました！

### 型クラス`Reverse`を試してみる

実際に`test1`関数の中で、`Reverse`で導出された逆順のSymbolを`SProxy`に渡して型を作ってみます。

```haskell
class Cons5
  (s1 :: Symbol)
  (s2 :: Symbol)
  (s3 :: Symbol)
  (s4 :: Symbol)
  (s5 :: Symbol)
  (sym :: Symbol)
  | s1 s2 s3 s4 s5 -> sym
  , sym -> s1 s2 s3 s4 s5

instance cons5 ::
  ( Symbol.Cons s1 t1 sym
  , Symbol.Cons s2 t2 t1
  , Symbol.Cons s3 t3 t2
  , Symbol.Cons s4 t4 t3
  , Symbol.Cons s5 t5 t4
  ) => Cons5 s1 s2 s3 s4 s5 sym

class Reverse (original :: Symbol) (reversed :: Symbol) | original -> reversed

instance reverse ::
  ( Cons5 s1 s2 s3 s4 s5 original
  , Cons5 s5 s4 s3 s2 s1 reversed
  ) => Reverse original reversed

test1 :: SProxy "EDCBA"
test1 = SProxy :: forall output. Reverse "ABCDE" output => SProxy output
```

2. の説明に従うと、`forall output. Reverse "ABCDE" output`の`output`は`EDCBA`になることがわかります。ここで求めた逆順のSymbolをSProxyに渡したものをSProxyの型注釈に書きます。

```haskell
test1 = SProxy :: forall output. Reverse "ABCDE" output => SProxy output
```

の部分です。型注釈をまとめると、`SProxy :: SProxy output`が`SProxy :: SProxy "EDCBA"`になるので、`test1`関数の型定義には`test1 :: SProxy "EDCBA"`と書けます。

次の例でも同じです。

```haskell
test2 :: SProxy "ABCDE"
test2 = SProxy :: forall output. Reverse "EDCBA" output => SProxy output

test3 :: SProxy "NEKO!"
test3 = SProxy :: forall output. Reverse "!OKEN" output => SProxy output
```

# おまけ

簡単な例として再帰を使わないものを見せたかったので上記のようにしていましたが、拡張性を考えると再帰定義を使って簡潔にしたほうがいいです。Symbolの文字数制限もありません(長すぎると再帰の途中でコンパイラが諦めてしまうため実際には制限なしとはいきませんが…)。

以下のようにするとうまくできます。

```haskell
module Main where

import Prim.Symbol as Symbol
import Type.Prelude (SProxy(..))

class Reverse (original :: Symbol) (reversed :: Symbol) | original -> reversed
                                                        , reversed -> original

instance reverseNil :: Reverse "" ""

else instance reverse ::
  ( Symbol.Cons s t original
  , Reverse t r
  , Symbol.Append r s reversed
  ) => Reverse original reversed


test1 :: SProxy "EDCBA"
test1 = SProxy :: forall output. Reverse "ABCDE" output => SProxy output

test2 :: SProxy "ABCDE"
test2 = SProxy :: forall output. Reverse "EDCBA" output => SProxy output

test3 :: SProxy "NEKO!"
test3 = SProxy :: forall output. Reverse "!OKEN" output => SProxy output
```

`Cons`ではなく`Append`を使っているところがありますが、これは結合するときに先頭のSymbolが1文字であるとは限らないからです(`Cons`では先頭のSymbolは1文字でなければなりません)。

この例では、各テスト関数の型定義を`_`(ワイルドカード)にしても、エラーにならず、導出結果の逆順のSymbolを教えてくれます。