Haskellの文字列型：分類と特徴

# Haskellの文字列型について

Haskellの文字列型には色々あります。標準の `String` のほかに `Text` や `ByteString` があり、`Text` と `ByteString` はそれぞれstrictとlazyの2種類ずつあります。

Haskellを学びたての方はこれを知ると「なんでこんなに色々あるんだ？Haskellはクソなのか？」と思われるかもしれません。

ですが、それぞれの文字列型にはちゃんと存在意義があります ~~（まあ `String` は標準であること以外取り柄のないクソですが……）~~。この記事ではそれぞれの型の特徴と使いどころを解説します。

ここで説明する対象は、主に以下の型です。

* `String`
* `Text` 系
    * strict `Text` ([textパッケージ](https://hackage.haskell.org/package/text))
    * lazy `Text` (同上)
    * `ShortText` （[text-shortパッケージ](https://hackage.haskell.org/package/text-short)）
* `ByteString` 系（[bytestringパッケージ](https://hackage.haskell.org/package/bytestring)）
    * strict `ByteString`
    * lazy `ByteString`
    * `ShortByteString`

その他、Builder系（`Data.ByteString.Builder`, `Data.Text.Lazy.Builder`）の型や、FFIで使う型を適宜扱います。

この記事では、各種の文字列型の分類や比較に重点を置きます。個々の文字列型の使い方は、それぞれのドキュメントを読んでください。

単に `Text` 型、 `ByteString` 型といった場合にはstrictな方を指します。

# まずは確認

いくつか用語の確認をしておきます。

## 文字列とは

「文字」や「文字列」について真面目に考えると大変なので、ここでは「Unicode文字列」と「バイト文字列」を考えます。

まず、Unicodeに関する用語をいくつか確認しておきます。
https://www.unicode.org/glossary/
<dl>
<dt>コードポイント (code point)</dt>
<dd>0以上0x10FFFF以下の整数のことです。$2^{20}+2^{16}$通りあります。21ビットの整数で表現できます。</dd>
<dt>Unicodeスカラー値 (Unicode scalar value)</dt>
<dd>Unicodeコードポイントであって、0xD800以上0xDFFF以下の範囲にないもののことです。Unicodeスカラー値の集合を数学っぽく書くと {0,1,…,0xD7FF,0xE000,…,0x10FFFF} となります。</dd>
<dt>コードユニット (code unit)</dt>
<dd>Unicode文字列をUTF-8やUTF-16等の符号化方式で表す時に使う、8ビット整数や16ビット整数のことです。Haskellで広く使われているUnicode文字列型はこの辺をうまく隠蔽しているため、（JavaScript等と違って）Haskellでコードユニットを意識することは少ないです。</dd>
</dl>

その上で、この記事の中で「Unicode文字列」は、**UnicodeコードポイントあるいはUnicodeスカラー値の列**である、と約束します（Unicode標準での「Unicode string」の定義とはちょっと違います）。

「バイト文字列」は、バイト列を何らかの方法で文字列とみなしたもの、ということにします。

## 文字型 `Char`

GHCにおいて `Char` 型の値はUnicode **コードポイント** を表します。つまり「0以上0x10FFFF以下の整数」です。サロゲートコードポイントも含みます。`Char` 型の定義（架空）を書くと、次のようになります：

```haskell
data Char = '\0' | '\1' | ... | '\x10FFFF'
```

`Int` との相互変換には、 `Enum` クラスの

```haskell
toEnum :: Enum a => Int -> a
fromEnum :: Enum a => a -> Int
```

や `Data.Char` モジュールの

```haskell:Data.Char
chr :: Int -> Char
ord :: Char -> Int
```

を使います。

例：

```haskell:GHCi
λ> import Data.Char
λ> chr 0x3042 == 'あ'
True
λ> chr 0xD800 -- エラーにはならない
'\55296'
λ> chr (-1) -- エラー
*** Exception: Prelude.chr: bad argument: (-1)
λ> chr 0x110000 -- エラー
*** Exception: Prelude.chr: bad argument: 1114112
```

# 表すものに着目した分類

Haskellの文字列型の最も重要な分類として、表すものが**Unicode文字列**か**バイト文字列**かというのがあります。表にまとめると次のようになります。

| Unicode文字列 | バイト文字列 |
|:--:|:--:|
| `String` (= `[Char]`) | `[Word8]` |
| (strict/lazy) `Text` | (strict/lazy) `ByteString` |
| `ShortText` | `ShortByteString` |

## Unicode文字列

`String` 型と `Text` 系の型は、**Unicode文字列**を表します。

`String` 型と `Text` 系の型の最も大きな違いは、**効率**です。Haskellの `String` は連結リストで実装されており、非効率ということで悪名高いです。これに対し、 `Text` 系の型はUnicode文字列をより効率的に表すことができます。

他の違いとして、それぞれが**表すもの**が微妙に違います。

Haskellの `String` 型は `Char` のリスト、すなわち `[Char]` の別名です。つまり、 `String` 型が表すものは**Unicodeコードポイントの列**です。長さは有限かもしれませんし、無限かもしれません。

一方、 `Text` 型が表すものは**Unicodeスカラー値の列**です。strict `Text` 型であれば長さは有限、lazy `Text` 型は長さは有限もしくは無限です。

つまり、 `"\xD800"` は正当な `String` ですが、これと同じ中身を持つ `Text` は構築できません（構築しようとすると変換エラーになるか、黙って `U+FFFD` 等に置き換えられます）。

他の言語だと「文字列型が表すものはただのバイト列（または16ビット整数列）。ただし標準の関数がUTF-8（UTF-16）として解釈してくれることが多い」みたいな世界観だったりしますが、Haskellの `Text` は真っ当なUnicode文字列であることが型の不変条件として保証されているわけです。

## バイト文字列

`ByteString` 系の型は**バイト列**を表します。言うなれば `[Word8]` の亜種です。型には文字コードの情報は含まれません。

Unicodeが世界のコンピューティング環境を支配した今、Unicode文字列ではなくあえてバイト文字列（バイト列で表される文字列）を使いたい状況は何でしょうか。いくつか挙げてみます。

* ASCII文字のみ、あるいはISO 8859-1 (Latin-1) のみで構成される文字列ならば `ByteString` を使うのが消費メモリ的に有利でしょう。
    * （Unicode文字列のメモリ上の表現がUTF-8ならASCII文字も1文字1バイトで済みますが、現状の `Text` 系の型はUTF-16で表されている場合があります。）
* ファイルの中身（あるいはパイプやソケット等のストリーム）は、バイト列です。アプリケーションが読み書きしたいのがUnicode文字列であったとしても、ディスクに近い側ではUTF-8やUTF-16などの方法でバイト列に変換した上で読み書きすることになります。
* C言語の `char *` は結局のところバイト列なので、C言語と文字列をやり取りする場合はバイト列を扱う必要があります。
* HTTPヘッダーに直接指定できるのは、ASCIIだかISO 8859-1だかです（合ってる？）。Unicode文字列を指定する際は、ヘッダーの種類に応じた方法でエンコードする必要があります。なので、「具体的な種類が不明なヘッダー」を扱うデータ型や関数では、Unicode文字列型ではなくバイト文字列型を使うべきです。
    * 実際、[http-types パッケージの `Header` 型](https://hackage.haskell.org/package/http-types-0.12.3/docs/Network-HTTP-Types-Header.html#t:Header)の定義では `ByteString` が使われています。
    * 一方、[scottyではヘッダーの型が `Text` になっています](https://hackage.haskell.org/package/scotty-0.11.5/docs/Web-Scotty-Trans.html#v:header)。これは筆者に言わせれば不適切な型です。[関連issue](https://github.com/scotty-web/scotty/issues/42)

**Unicode文字列とバイト文字列を相互変換するための、万人が納得する標準的な方法はありません。** Unicode文字列とバイト文字列を変換するには、なんらかのエンコーディングを固定する必要があります。また、エンコーディングの他に、「エラー処理をどうするか（例：UTF-8として不正なバイト列をどう扱うか）」という問題を意識する必要があります。

# 用途・特性による文字列型の分類

値の列を表すデータ構造には、リストやArray, Vector, Sequenceなど、色々あります。これらは、要素の参照や連結など、各種操作に対する向き不向きがあります。文字列についても同様で、特性によって分類することができます。

このセクションの内容をざっくり表にまとめると次のようになります：

| | 要素の参照 | スライス | ストリーム | 構築 |
|:-:|:-:|:-:|:-:|:-:|
| `String` | O(n) | | ○ | |
| strict `Text` | O(n) | ○ | | |
| lazy `Text` | O(n) | ○ | ○ | |
| `ShortText` | O(n) | | | |
| strict `ByteString` | O(1) | ○ | | |
| lazy `ByteString` | O(c) | ○ | ○ | |
| `ShortByteString` | O(1) | | | |
| `ShowS` | 不可 | | | ○ |
| Text `Builder` | 不可 | | | ○ |
| ByteString `Builder` | 不可 | | | ○ |

## 要素の参照

文字列というのは文字の列ですから、その要素である「文字」を取得できて然るべきです。ただ、「n番目の文字をピンポイントで取得したい」という場合にかかる計算時間は型によって違います。

`String` は連結リストですから、n番目の文字を `!!` で参照すると O(n) の時間がかかることはご存知の方も多いでしょう。

`Text` 系の型も内部表現の都合上、n番目の文字の参照には O(n) の時間がかかります。何らかの事情によりUnicode文字列のn番目の文字を高速に参照（ランダムアクセス）したいのであれば、事前に `Vector Char` に変換しておくと良いでしょう。

これに対し `ByteString` や `ShortByteString` は、定数時間でn番目の文字にアクセスできます。ただ、lazy `ByteString` に関しては内部表現の都合上、「チャンク」の個数に比例した時間がかかります。

後述しますが、Builder系の型は構築中の文字列の中身を参照できません。筆者としては文字を参照できない型を「文字列型」と呼ぶのには抵抗があるので、この記事で単に「文字列型」といった場合にはBuilder系の型は含みません。

## 共有とスライス

`Text` 型や `ByteString` 型は部分文字列を効率的に（データをコピーすることなく）表すことができます（**スライス**）。

具体的には、以下の型がスライスに対応しています。

* (strict/lazy) `Text`
* (strict/lazy) `ByteString`

これに対して、以下の型はスライスになりません（ただし、 `String` に関しては「先頭から何文字か除く」系の操作はコピーなしでできます）。

* `String`
* `ShortText`
* `ShortByteString`

スライスに対応した文字列型の方が便利な気もしますが、ある種の状況ではスライスが作られない方が便利なことがあります。例えば、でかい文字列の一部分だけが必要な場合、スライスで表すとでかい文字列の全体がメモリに乗ったままになってしまいます。

`ShortText` と `ShortByteString` は、そのほかに「細かい文字列を大量に扱う際に必要とするメモリが少ない」という利点もあります。

## 逐次処理（ストリーム）

巨大なファイルや長さがわからない文字列（あるいはバイト列）を逐次的に処理したいことがあります。lazy `Text` や lazy `ByteString` はそのための型です。`String` もそういう使い方ができます。

* `String`
* lazy `Text`
* lazy `ByteString`

メモリに全体が納まらないような巨大なデータを扱うことを考慮して、lazy `Text` と lazy `ByteString` は長さやオフセットが `Int` ではなく `Int64` となっています。つまり、32ビット環境でも2GiB超えのデータを扱うことができます。

## 文字列の構築：ビルダー

細々とした文字列をつなぎ合わせて一つの文字列を作ることを考えます。

普通に連結演算子 `<>` を使って連結すると、その都度コピーが発生します。例えば `("abc" <> "def") <> "gh"` を計算すると

```haskell
("abc" <> "def") <> "gh"
--> "abcdef" <> "gh"
--> "abcdefgh"
```

と言う風に、途中で `"abcdef"` という文字列を構築してすぐに捨てることになります。無駄になる文字列が少なければ良いのですが、大量の文字列を連結する場合はこれは無視できません。

このような不要な文字列構築を減らすには、連結の際に文字列そのものではなく「メモリ領域に文字列を書き出す」という操作を連結することにします。そうすると実際に連続したメモリ領域に書き込むのは最後の1回だけとなり、無駄な文字列構築を避けられます。それをやってくれるのが **ビルダー** と呼ばれるやつです。

こういう話（文字列連結の効率化）はHaskellに限った話ではなく、他の言語でも細切れの文字列をつなげるために `StringBuilder` などの専用の型が用意されていることがあるかと思います。あるいは、そういう専用の型がない言語の場合は、文字列のリストを作ってそれを一括でjoin、みたいなテクニックを使ったりしますね。

ちなみに、 `String` のようなイミュータブルなリストの場合は、効率よく構築する方法として**差分リスト**と呼ばれる手法があります。Haskellでは `ShowS` がそれの例です。

まとめると、以下の型は文字列を効率よく構築（連結）するための型、ということになります。

* `Data.ByteString.Builder`
* `Data.Text.Lazy.Builder`
* `ShowS` (= `String -> String`)

ちなみに、ByteString BuilderやText Builderからは直接（長さの確定した）`ByteString` や `Text` 型に変換することはできません。一旦、lazy系の文字列を経由する必要があります。

また、すでに述べたように、文字列型を経由せずに `Builder` 等の中身を見る（例：先頭の文字を取得する）ことはできません。

（ちなみに、ByteString Builderに関してはもっと効率の良い代替物があるようです。→[fast-builderパッケージ](https://hackage.haskell.org/package/fast-builder), [masonパッケージ](https://hackage.haskell.org/package/mason)（[最強にして最速のビルダー、mason - モナドとわたしとコモナド](http://fumieval.hatenablog.com/entry/2019/12/05/191010)））

# ByteString と UTF-8

`ByteString` にUTF-8エンコードされた文字列を入れて色々操作しようという場合は、いくつか注意点があります。というか、推奨しません。

どこかから受け取ったUTF-8な `ByteString` をUnicode文字列として扱いたい場合は、細かい操作の前に `Text` 系の型に変換するべきでしょう。

## 文字列リテラル

`OverloadedStrings` 拡張で `ByteString` のリテラルを書く場合、非ASCII文字は書いてはいけません。`ByteString` の `IsString` インスタンスはUnicodeコードポイントの下位8ビットを切り出すという挙動をするからです。

```haskell
λ> import qualified Data.ByteString as BS
λ> :set -XOverloadedStrings
λ> "猫" :: BS.ByteString
"+"
λ> "にゃーん" :: BS.ByteString
"k\131\252\147"
λ> "ねはなどぢちにづ" :: Data.ByteString.ByteString
"mojibake"
```

これは `Data.ByteString.UTF8` からimportした `ByteString` 型であっても同じことです。`Data.ByteString.UTF8` がexportする `ByteString` 型は `Data.ByteString` のそれと同一の型（再export）であり、 `IsString` のインスタンスも共有しているからです。**UTF-8用の `ByteString` 型なんてものはありません。 `ByteString` の中身をUTF-8だと思って処理してくれる関数があるだけ**なのです。

## ByteString 用の関数

`ByteString` 用の関数でUTF-8文字列を操作しようとすると罠にはまる場合があります。以下のコードの挙動を説明できない人は「`ByteString` でUnicode文字列を表そう」などとは考えずに素直に `Text` を使っておくべきです。

```haskell
import qualified Data.ByteString.Char8 as BS -- from bytestring
import qualified Data.ByteString.UTF8 as BS.UTF8 -- from utf8-string

main = do
  let s = BS.UTF8.fromString "猫だよ" -- U+732B U+3060 U+3088
  print $ s == BS.pack "\xE7\x8C\xAB\xE3\x81\xA0\xE3\x82\x88" -- True
  print $ length $ BS.words s -- s は空白文字を含まないので「1」となって欲しいが…？
```

# ファイルの読み書きとUTF-8

ファイルの内容はバイト列です。`readFile` 等の関数でファイルの内容を `Text` や `String` 等のUnicode文字列型として読み取った場合は、何らかの方法でバイト列からUnicode文字列への変換が行われるはずです。

今の時代、ファイルの内容もUTF-8として扱って欲しいところですが、GHCのデフォルトでは**ファイルの読み書き時のエンコーディングはシステムの設定に依存**します。詳しくは次の記事を読んでください：

* [Haskell with UTF-8](https://serokell.io/blog/haskell-with-utf8)

結論だけ書くと、システムの設定に依存せずにファイルの内容をUTF-8で読み書きしたい場合は以下のいずれかの措置を取る必要があります：

* プログラムの起動時に [`GHC.IO.Encoding.setLocaleEncoding`](https://hackage.haskell.org/package/base-4.12.0.0/docs/GHC-IO-Encoding.html#v:setLocaleEncoding) でデフォルトのエンコーディングを [`utf8`](https://hackage.haskell.org/package/base-4.12.0.0/docs/GHC-IO-Encoding.html#v:utf8) に設定する
* 開いた `Handle` のエンコーディング設定を [`hSetEncoding`](https://hackage.haskell.org/package/base-4.12.0.0/docs/System-IO.html#v:hSetEncoding) で変更する
* [with-utf8 パッケージ](https://hackage.haskell.org/package/with-utf8) を使う（上記ブログ記事を参照）
* ファイルの内容は `ByteString` で読み書きして、 `Text` との変換時にUTF-8で変換する

# 雑多な話

## FFIで使う文字列型

*このセクションはHaskellで完結するコードを書く際は必要のない話です。興味のない方は読み飛ばしてください。*

C言語とやりとりする際には、それ用の文字列型が必要になります。`Foreign.C.String` ではそういう文字列型がいくつか定義されています。実態はただのポインターなので、メモリ管理は手動で行うことになります。

* `CString` (= `Ptr CChar`)
* `CWString` (= `Ptr CWchar`)
* `CStringLen` (= `(Ptr CChar, Int)`)
* `CWStringLen` (= `(Ptr CWchar, Int)`)

| Haskellでの型 | C言語の対応物 | 要素 | 表すもの |
|:-:|:-:|:-:|:-:|
| `CString` | `char *`（NUL終端） | `CChar` （NULを除く） | バイト文字列（NUL終端） |
| `CStringLen` | `char *` と `int` | `CChar` | バイト文字列 |
| `CWString` | `wchar_t *`（NUL終端） | `CWchar` （NULを除く） | ワイド文字列（NUL終端） |
| `CWStringLen` | `wchar_t *` と `int` | `CWchar` | ワイド文字列 |

C言語の `char` は8ビット整数なので、 `CString`(`Len`) は先述の分類では**バイト文字列**ということになります。

### ワイド文字列

C言語には `char *` で表される文字列の他に、 `wchar_t *` で表される**ワイド文字列**もあります。

Unicodeが世界を支配した今、「ワイド文字列」という概念はほぼ過去の遺物ですが、CとのFFIのためにHaskellにも対応する型が一応用意されています。Windows APIを使う際にお世話になるかもしれません。

Unicode文字列の要素はUnicodeコードポイント（もしくはスカラー値）、バイト文字列の要素は8ビット整数でした。これに対し、ワイド文字列の要素は**ワイド文字**です。

ワイド文字の実態は、

* Windowsでは16ビット整数で UTF-16 の code unit を表す
* Unix系では32ビット整数で UTF-32 の code unit を表す

ことが多いですが、例外もあります[^non-unicode-wchar]。

[^non-unicode-wchar]: BSD系のlibcで8ビットなロケールを使うと、コード値がそのまま `wchar_t` に格納されたりします。

GHCではワイド文字列は UTF-16 または UTF-32 であると仮定するようです。詳しくは [Foreign.C.String のドキュメント](https://hackage.haskell.org/package/base-4.12.0.0/docs/Foreign-C-String.html#g:4) を参照してください。

## `Text` の内部エンコード

現状（2020年4月現在）、text パッケージの `Text` 型は内部UTF-16です。ですがこれはユーザーが意識しなくて良い実装の詳細であり、普通の使い方をしている限りでは `Text` 型はUnicodeスカラー値の列にしか見えません。（JavaScriptの文字列型がUTF-16 code unitの列に見えるのとは対照的です）

それでも「時代はUTF-8なんや！俺のHaskellアプリも内部UTF-8にするんや！」と思った貴方には以下の選択肢があります。

1. [text-utf8 パッケージ](https://hackage.haskell.org/package/text-utf8)を使う
2. text-short パッケージの `ShortText` 型を使う
3. `ByteString` で保持する

先に述べた理由により3.はお勧めしません。 

まあ、内部UTF-8を検討するのは、内部UTF-16では遅いとわかってからでも良いと思います。その際は [text-utf8](https://github.com/text-utf8/META/issues) の方にベンチマーク結果等を報告すると喜ばれるかもしれません。

## メモリ管理とかの細かい話

`ByteString` はメモリ領域がピン留めされるので、その気になれば内容をコピーすることなくFFIで使用できます（`Data.ByteString.Unsafe` 参照）。一方このピン留めについては、「ヒープの断片化に繋がる」「compact regionに入れることができない」などのデメリットもあります。

一方、 `ShortByteString` はピン留めされていない通常のメモリに確保されます。

ちなみに、 `ShortText` は `ShortByteString` のnewtypeなので、ゼロコストで変換できます（`ShortText` → `ShortByteString` はゼロコスト、`ShortByteString` → `ShortText` はUTF-8としての検査を省略する危険を冒すのであればゼロコスト）。

# 文字列同士の変換

~~変換についてはまた長くなるので、別の記事に書きます。~~ →書きました。

[Haskellの文字列型：変換時の心構えと変換方法まとめ](https://qiita.com/mod_poppo/items/88a6e876efbf7183209a)

# まとめ

各文字列型を一言で表現するなら、こんな感じでしょうか：

- `String`: 古き良き（良くない）Unicode文字列。Unicodeコードポイントの列。
- `Text`: 効率の良いUnicode文字列。Unicodeスカラー値の列。
- lazy `Text`: Unicode文字列のストリーム。
- `ByteString`: バイト列。
- lazy `ByteString`: バイト列のストリーム。
- `ShortText`: 「短い」Unicode文字列を格納するのに向いたやつ。
- `ShortByteString`: 「短い」バイト列を格納するのに向いたやつ。
- Text `Builder`: Unicode文字列を構築するのに使うやつ。
- ByteString `Builder`: バイト列を構築するのに使うやつ。
- `CString`, `CStringLen`: C FFIで使うやつ。`char *`。
- `CWString`, `CWStringLen`: C FFIで使うやつ。`wchar_t *`。実質Windowsでしか使わないかも。

用途に応じてうまく使い分けましょう！