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

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

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

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

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

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

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

type ShowS = String -> String

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

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

import Numeric (showHex)

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

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

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

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

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

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

-- 数値を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進数風にする)」関数を考えてみます。

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

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

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

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

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

|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と全く同じだったりします。

さて、型を見てみます。

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を使った方が絶対に綺麗に書ける。

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

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

気が向いたらやる。