Haskellで16進数の表示とShowS - 型だけで全てが分かるわけじゃないって話

括弧の中に書いてあることは基本的に戯言です。

##16進数を表示したいだけならここを見れば十分

Haskellで16進数を表示したいときには`Numeric`モジュールにある`showHex`関数を使うんだけど、その型がちょっとややこしい。
こんな風になってる。

```hs
showHex :: (Integral a, Show a) => a -> ShowS
```

`(Integral a, Show a) => a`までは普通に、整数で表示できる型を受け取るってことだから難しくはない。問題はその後の、`-> ShowS`の部分だ。
じゃあ、この`ShowS`って何だろう？

調べてみると、ただの型シノニムだったりする。

```hs
type ShowS = String -> String
```

この型だけでは、何がしたいのか理解することは難しいと思う。(これだけじゃ文字列専用の恒等関数にしか見えませんし)

まあ、文字列を渡すと文字列を返してくれるんだから、とりあえず空文字列でも食わしておけ、って具合にすれば、16進数を表示することはできるんだけどね。

```hs
import Numeric (showHex)

main = print $ showHex 255 "" -- ffと表示
```

##`ShowS`が現われるまでのあまりに長い道程

というわけで、とりあえず、二つの文字列結合することを考えてみる。
(要するに、`(++)`関数なんだけど……)あえて実装すると、こんな風になる。

```hs
-- 二つの文字列を結合する関数
addStr :: String -> String -> String
addStr "" ys = ys
addStr (x:xs) ys = x : addStr xs ys
```

この`addStr`は、前の文字の長さだ再帰することはすぐに分かると思う。

次に思い切って、整数値を16進数の文字列にする関数を考えてみる。

```hs
-- 数値を16進数に変換
intToHex :: (Integral a) => a -> String
intToHex 0 = "0"
intToHex n
  |n < 0     = '-' : intToHex (negate n)
  |otherwise = intToHex' n ""
  where
  intToHex' 0 s = s
  intToHex' n s = intToHex' (n `div` 16) $ intToChar (n `mod` 16) : s
  intToChar = ("0123456789abcdef" !!) . fromIntegral
```

(この関数の負数の表現の仕方は賛否両論あると思うけど深く気にしないでください)

で、次に「数値を受け取って、その数値の16進表現の最後に`"H"`を追加する(≒アセンブラの16進数風にする)」関数を考えてみます。

```hs
-- 数値をアセンブラの16進数風の文字列に変換
asmHex :: (Integral a) => a -> String
asmHex = (`addStr` "H") . intToHex
```

まあ、今まで作った関数を組み合わせるだけですね。関数型言語万歳！って感じです。

ですが、考えてみてください。
この関数、あまり効率がよろしくないです。

前述のとおり、`addStr`は前の文字列の長さだけ再帰します。そして、`asmHex`において前の文字列とは、`intToHex`で返される文字列のことです。
しかし、`asmHex`の中で`addStr`がしたいことは`"H"`の一文字を追加すること。
たった一文字のために何度も再帰するなんて馬鹿馬鹿しくありませんか？

と、ここで`intToHex`が16進数の文字列を作る過程に注目してみます。具体的には、`intToHex'`とその呼び出しの部分。

> ```hs
  |otherwise = intToHex' n ""
  where
  intToHex' 0 s = s
  intToHex' n s = intToHex' (n `div` 16) $ intToChar (n `mod` 16) : s
```

この`|otherwise = intToHex' n ""`の部分で渡している、`""`(空文字列)が16進数の文字列の後ろの文字列になっていることが確認できます。
なので、ここに後ろに追加したい文字列を指定することができれば、`addStr`を用いずに`asmHex`を実装することができます。

というわけで書き直した`intToHex`がこちら。

```hs
intToHexWith ::(Integral a) => a -> String -> String
intToHexWith 0 s = '0' : s
intToHexWith n s
  |n < 0     = '-' : intToHexWith (negate n) s
  |otherwise = intToHex' n s
  where
  intToHex' 0 s = s
  intToHex' n s = intToHex' (n `div` 16) $ intToChar (n `mod` 16) : s
  intToChar = ("0123456789abcdef" !!) . fromIntegral
```

`intToHexWith`という名前になりました。あと、`where`以下は`intToHex`と全く同じだったりします。

さて、型を見てみます。

> ```hs
intToHexWith ::(Integral a) => a -> String -> String
```

さらに、`ShowS`は`String -> String`であることを思い出すと、こう書けることが分かります。

```hs
intToHexWith ::(Integral a) => a -> ShowS
```

この型は`showHex`の型と(型制約が若干違いますが)ほぼ同一になっていますね。

##結論。`ShowS`とは何だったのか

`ShowS`は型シノニムで、その実態は`String -> String`という関数の型になっている。
ということまではGHCiでちゃちゃっと`:t`コマンドと`:i`コマンドを駆使すれば分かることなんだけど、そこから先の、これは効率化のためにある、っていうことを理解するのに約2KB程のテキストが必要になった。

結論からすればこの記事では、よくHaskellなんかの関数型言語では、型を見ればその関数の大抵のことは分かるっていうけれど(本当か？)、こういう風に効率のために回りくどいことをしている関数では、中々そうはいかないこともあるんだっていうことを伝えたかったわけです。

理想としては「型が全て」であって欲しいんですけど、現実は厳しいもので。

(最近は型族とかあるから大抵のことは型の上で表現できるはずだし、`ShowS`は努力が足りないだけかもしれないけど。`ShowS`の中に前の文字列が隠れてて、後ろの文字列を適用することで取り出せる、っていうのは何か米田っぽいな、とか思わなくもないし。パラメトリックじゃないけど)

ちなみに、他に`ShowS`を返す関数が`Numeric`モジュールにはいくつか定義されています。興味のある人は見てみてください。

##おまけ。`unfoldr`を使った`intToHex`の実装

説明上都合が悪いから使わなかったけど、`intToHex`は`Data.List`で定義されている`unfoldr`を使った方が絶対に綺麗に書ける。

```hs
import Control.Monad (guard)
import Control.Applicative (($>))
import Control.Arrow ((>>>))
import Data.List (unfoldr)

intToHex :: (Integral a) => a -> String
intToHex 0 = "0"
intToHex n
  |n < 0     = '-' : intToHex (negate n)
  |otherwise = f n
  where
  f = unfoldr (\n-> swap (n `divMod` 16) <$ guard (n /= 0))
    >>> map (("0123456789abcdef" !!) . fromIntegral)
    >>> reverse
```

- - -

###TODO

 * 参考資料を貼る。
 * 使用したモジュールや関数へリンクがあると良さそう。

気が向いたらやる。