Haskell Tips (文字列編)

この記事はHaskell Advent 2012のための記事です。(遅れてすいません(ヽ´ω`))

Haskellで実際にプログラムを書く上では、様々なパッケージにある型や関数を利用するのが不可避になります。 そういった便利ツールのうち文字列まわりについて調べたところを、Haskell最近始めたって人に紹介するのがこの記事の目的です。Haskell詳しい方には新しい発見は無いかもしれません。ごめんなさい。

この記事では、主に文字列に焦点を当てていますが、そのうちまた別のテーマでも書こうと思っています。

なお、前提としてるバージョンはHaskell Platform 2012.4.0.0と、それに付随するGHCやパッケージです。 OSも、Mac OS XやLinuxなどUNIX系の環境を想定しています。Windowsは持ってませんのでわかりません。ごめんなさい。

文字列

Haskellでは文字列の表現も色々あって、Haskellを始めたばかりの人はきっと混乱するでしょう。 自分も大混乱しましたよ。

Haskellで文字列を扱うのによく使われる型は大きく分けて以下の３つです。

• String
• ByteString
  • Strict
  • Lazy
• Text
  • Strict
  • Lazy

ByteString型はbytestringパッケージで、Textはtextパッケージから提供されてます。 どちらもHaskell Platformに同封されてます。

ひとまず確認して行きましょう。

String

あんまり説明は要らないと思いますが、Stringはただの文字型Charのリストです。 なのでlengthやmapなどのリスト操作関数はそのまんま使えて便利ですし、自然な発想です。

Stringでは一文字で５ワードも占めるので、 メモリを喰いますし、速度もイマイチです。

でもStringはマルチバイト文字を扱えます。 以下のようなものはランタイムのロケールを考慮して、正しく出力されるはずです。

putStrLn "鬼"

そうそう、入出力のエンコーディングなどのロケール情報は、GHC.IO.Encodingモジュールの getLocaleEncodingã‚„getLocaleFileSystemEncodingで取得できます。

import GHC.IO.Encoding

sample1 :: IO ()
sample1 = print =<< getLocaleEncoding

出力

UTF-8

他にもGHC.IO.Encodingにはエンコーディングを設定する機能などがあるようなので、この機能も必要があるかもしれません。

---

ByteString

「すごいHaskell」や「Read World Haskell」などを読まれた方はおなじみかと思います。bytestringパッケージで提供されているByteString型と関数で、効率良く文字列（というよりバイト列）を扱うことができます。

ByteStringが実際に収めているデータはWord8(8bitの符号なし整数)型なので、それより大きい要素を収めようとすると問題があります。マルチバイト文字など8bitに収まらないデータがそうです。

ByteStringには、実は同名の２つの型があります。 ひとつはData.ByteString.Internalモジュールで定義されている正格評価のByteStringで、 もうひとつはData.ByteString.Lazy.Internalモジュールにある遅延評価のByteStringです。 内部的には、Lazyな方のByteStringは、StrictのByteStringをリストにしているだけです。

-- LazyなByteStringの定義
import qualified Data.ByteString.Internal as S
data ByteString = Empty | Chunk {-# UNPACK #-} !S.ByteString ByteString

正格と遅延の型を字面だけ見て組み合わせようとしても、型エラーが出るので気をつけましょう(｀･ω･´) 外部のライブラリを使うときは、ByteStringとだけ書いてあってもどちらか分からないので、ソースを読むなり、HTML版のHaddockのリンク先を確認するなりしないといけませんね。

じゃあ、これらの型の相互変換はどうするのかというと、bytestringパッケージのバージョン0.10.0.1では、 toStrictとfromStrictが、LazyとStrictを相互変換するための関数が定義されています。 それ以前のバージョンでは、これらの関数は自作することになります。 このへんの話は以下のリンクを参考にして下さい。

• Convert a Lazy ByteString to a strict ByteString
• Proposal: Add {to,from}Strict conversion functions between strict and lazy ByteStrings

他に、Data.ByteStringにはモジュール名の末尾にChar8がつくData.ByteString.Char8とData.ByteString.Lazy.Char8もありますが、これらはByteStringが内部でもつWord8のデータとCharの相互変換をしてくれる関数を間にかませているだけなので、本質的には何も変わりません。変換の分のオーバーヘッドはありそうですが。

このへんの挙動をちょっと見てみましょう。

下のコードの頭にあるOverloadedStringsは、文字列リテラルをIsString型クラスのインスタンスへと自動的に変換してくれます。 ですので、文字列リテラルに関しては、bytestringã‚„textパッケージで用意されているpack関数を明示的に呼ぶ必要はありません。

コメントでは文字に対応する文字符号化形式のコードを書いています。

{-# LANGUAGE OverloadedStrings #-}

import qualified Data.ByteString.Char8 as B8

sample :: IO ()
sample = do
    -- '鬼':
    --   UTF-16: 9B3C
    --   UTF-8:  E9ACBC
    -- '<':
    --   ASCII: 3C
    B8.putStrLn (B8.singleton '鬼')

    -- 'å¹³':
    --   UTF-16: 5E73
    --   UTF-8:  E5B9B3
    -- 's':
    --   ASCII: 73
    B8.putStrLn (B8.singleton 'å¹³')

    B8.putStrLn (B8.pack "鬼平")
    B8.putStrLn "鬼平"      -- OverloadedStringsがなければ、この書き方は型エラー

出力

<
s
<s
<s

漢字などマルチバイト文字は、Char型としての文字リテラルではUTF-16でエンコードされている様子です。 しかし、ByteStringは内部的にはWord8(8bit)単位でしか扱えないので、 ByteStringに変換する際に、CharのデータはWord8(8bit)に切り詰められてるのが分かると思います。

文字列リテラルで指定されたマルチバイト文字を無理やりByteStringで扱おうとすると、特にエラーも出さず間違った結果を返すので注意が必要ですね。 なので、ByteStringは文字列というよりは、生のバイト列を収めるデータ型と思ったほうが良いと思います。

IOを介すなどして外部から与えられたマルチバイト文字は、 エンコーディングなど考慮されずにそのままバイト列として扱えます。 なので、以下のようにユーザーの入力を受け取る場合は、入力がマルチバイト文字を含んでいても問題ありません。入力をそのまま吐いてるだけです。

sample :: IO ()
sample = do
    putStrLn "What is your name?"
    putStr "> "
    name <- B8.getLine
    B8.putStrLn $ "Hello, " `B8.append` name
    putStrLn $ (show $ B8.length name) ++ "-byte"

出力

What is your name?
> 鬼平
Hello, 鬼平
6-byte

バイト数がUTF-8でエンコードしたときにあたる6バイトになっちゃってますね。 これでは文字数は正しく数えられませんし、文字境界も分からないのでgrepのようなことも出来ません。

---

Text

じゃぁこういったマルチバイト文字をバイト列でなく、ちゃんと文字列として扱うにはどうすればいいのかと言うと、textというパッケージがありまして、こいつを使うというわけです。

ちゃんと文字列として扱うとは、文字列の長さが正しく数えられるとか、特定の文字を探せるとかそういう話です。

textパッケージでは、文字列操作のためのモジュールとIOのためのモジュールが別のモジュール(Data.Text.IO)にあります。下のように、同じTという別名をつけてimportすると楽ちんです。

{-# LANGUAGE OverloadedStrings #-}

import qualified Data.Text    as T
import qualified Data.Text.IO as T

sample :: IO ()
sample = do
    T.putStrLn (T.singleton '鬼')
    T.putStrLn (T.singleton 'å¹³')

    T.putStrLn (T.pack "鬼平")
    T.putStrLn "鬼平"       -- これもOverloadedStringsが必要

出力

鬼
å¹³
鬼平
鬼平

良い感じですね(´ω｀) Data.Text.IOではロケールを考慮してくれています。

先ほどのByteStringのときと同じサンプルも、Textなら大丈夫です。

sample :: IO ()
sample = do
    putStrLn "What is your name?"
    putStr "> "
    name <- T.getLine
    T.putStrLn $ "Hello, " `T.append` name
    putStrLn $ (show $ T.length name) ++ "-letter"

出力

What is your name?
> 鬼平
Hello, 鬼平
2-letter

ちゃんと文字数を数えています。バイト数じゃなくって。 でも、Textのlength関数の計算量はO(n)です(´・ω・｀)

Data.Text.IOには他にファイルやHandleとText型のデータをやり取りする関数も用意されてます。

TextはByteStringとの相互変換も可能ですし、Lazyなバージョンもあります。 相互変換に必要な関数はData.Text.Encodingモジュールにあります。

利用できるエンコーディングは以下の３つです。

• UTF-8
• UTF-16
• UTF-32

下の例では、マルチバイト文字をByteStringで表現して、decode系の関数がそのByteStringをバリバリ喰ってTextにガガッと変換してくれます。

ちなみに、任意のバイト列を作成したい時は、 以下の様に文字列リテラルの中でバックスラッシュ()と16進数を表すxで指定することができます。 10進数では、xは要りません。

{-# LANGUAGE OverloadedStrings #-}

import qualified Data.ByteString          as B
import qualified Data.Text                as T
import qualified Data.Text.IO             as T
import qualified Data.Text.Encoding       as T
import qualified Data.Text.Encoding.Error as T

sample :: IO ()
sample = do
    -- '鬼':
    --   UTF-8:  E9ACBC
    --   UTF-16: 9B3C
    let oniUTF8    = "\xE9\xAC\xBC" :: B.ByteString
        oniUTF16BE = "\x9B\x3C"     :: B.ByteString -- ビッグエンディアン
        oniUTF16LE = "\x3C\x9B"     :: B.ByteString -- リトリエンディアン

    T.putStrLn $ T.decodeUtf8    oniUTF8     -- Output: 鬼
    T.putStrLn $ T.decodeUtf16BE oniUTF16BE  -- Output: 鬼
    T.putStrLn $ T.decodeUtf16LE oniUTF16LE  -- Output: 鬼

    -- エンディアンの間違い!!
    T.putStrLn $ T.decodeUtf16LE oniUTF16BE  -- Output: ã²›

UTF-8ではバイトオーダーの指定は不要なのですが、 UTF-16では必要で、バイトオーダーを間違えると別の文字として認識されていしまいます。 外部から受け取ったUTF-16でエンコードされているはずのByteStringなどを、Text型に変換する際はバイトオーダーに気をつけましょう。

あと、外部から受け取ったデータなどをText型に落としこむ際には気をつけなければならないことがあります。

以下の例は例外を投げてしまいます。

T.decodeUtf16BE "\xD8\x00"

出力

"*** Exception: Cannot decode input: Data.Text.Encoding.Fusion.streamUtf16BE: Invalid UTF-16BE stream

これは、Text型が内部的にはUTF-16を利用していることが原因です。 UnicodeではU+D800~U+DBFFとU+DC00~U+DFFFの範囲の16bitをペア(サロゲートペア)にして、16bitだけでは表現しきれない文字を表現しています。 この範囲はUTF-16では表現しきれないので、decodeUtf16BEなどでは例外を投げます。 外部から与えられたByteStringをデコードするときは、この挙動に注意して例外を拾うか、 decodeUtf16BEWith関数など、デコードのエラーが生じた時の挙動を明示する関数を使うといいでしょう。

lenientDecodeを使うと、デコードできないものはコードポイントU+FFFDに置き換えられます。

T.putStrLn $ T.decodeUtf16BEWith T.lenientDecode "\xD8\x00"

他にもUTF-8に限ればutf8-stringというパッケージがあるようですが、使ったことはありませんので分かりません(ヽ´ω`)

blaze-builder

チャンクのサイズが...

ByteStringの説明のところで、LazyなByteStringはStrictなByteStringのリストだと説明しました。 だとすると、細かく作ったStrictなByteStringをたくさんつなげばLazyなByteStringを作る場合、結局細かいByteStringが連なったリストが出来上がりそうです。

下の例では、5バイトのByteStringを10個連結して、50バイトのLazyなByteStringを作っています。 それをまたチャンクに分解して、それぞれの長さを調べると、確かに5バイトのチャンクが10個連なってます。

{-# LANGUAGE OverloadedStrings #-}

import Control.Monad
import Data.Monoid
import Blaze.ByteString.Builder           as B
import qualified Data.ByteString.Lazy     as BL
import qualified Data.ByteString.Char8    as BS


chunkSizes :: BL.ByteString -> [Int]
chunkSizes = map BS.length . BL.toChunks

concatByteString :: Int -> BS.ByteString -> BL.ByteString
concatByteString n = BL.fromChunks . replicate n

main = print . chunkSizes $ concatByteString 10 "xxxxx"

出力

[5,5,5,5,5,5,5,5,5,5]

5バイトずつのチャンクになって、これじゃァCharのリストだったStringと大して変わらんってことで、 ひとつひとつのチャンクサイズを広げて、うまいことLazyなバイトストリングを作ってくれるのがblaze-builderです。

blaze-builderではBuilder型を介して文字列の結合をO(1)で行い、LazyなByteStringを吐き出すときに大きなチャンクを提供してくれます。

blaze-builderで文字列連結をするため、blazeConcatByteString関数を加えた例が以下のコードです。

{-# LANGUAGE OverloadedStrings #-}

import Control.Monad
import Data.Monoid
import Blaze.ByteString.Builder        as B
import qualified Data.ByteString.Lazy  as BL
import qualified Data.ByteString.Char8 as BS


byteN :: Int -> BS.ByteString
byteN n = BS.concat $ replicate n "x"

chunkSizes :: BL.ByteString -> [Int]
chunkSizes = map BS.length . BL.toChunks

concatByteString :: Int -> BS.ByteString -> BL.ByteString
concatByteString n = BL.fromChunks . replicate n

blazeConcatByteString :: Int -> BS.ByteString -> BL.ByteString
blazeConcatByteString n = B.toLazyByteString . mconcat . map B.fromByteString . replicate n

main =
    forM_ [1, 10, 100, 1000, 5000, 10000] $ \x -> do
        let bs = byteN x
        putStrLn $ show x ++ "-byte:"
        putStr "no-blaze "
        print . chunkSizes $ concatByteString      10 bs
        putStr "blaze    "
        print . chunkSizes $ blazeConcatByteString 10 bs
        putStr "\n"

出力

1-byte:
no-blaze [1,1,1,1,1,1,1,1,1,1]
blaze    [10]

10-byte:
no-blaze [10,10,10,10,10,10,10,10,10,10]
blaze    [100]

100-byte:
no-blaze [100,100,100,100,100,100,100,100,100,100]
blaze    [1000]

1000-byte:
no-blaze [1000,1000,1000,1000,1000,1000,1000,1000,1000,1000]
blaze    [4080,5920]

5000-byte:
no-blaze [5000,5000,5000,5000,5000,5000,5000,5000,5000,5000]
blaze    [4080,32752,13168]

10000-byte:
no-blaze [10000,10000,10000,10000,10000,10000,10000,10000,10000,10000]
blaze    [10000,10000,10000,10000,10000,10000,10000,10000,10000,10000]

blaze-builderを使ってつなげたほうが、チャンクのサイズが大きくなって、連結リストの長さが短くなってますね。 こうしてチャンクのサイズを大きくすることで、キャッシュの利用を効率化したり、入出力に関わるシステムコールのオーバーヘッドを低減しているようです。

詳しいバッファ利用の戦略などについては、blaze-builderのhaddockや作者のブログ記事を参考にして下さい。

これを利用して、HTMLやSVGなどを高速に構築するblaze-htmlやblaze-svgといったパッケージがあります。 WebアプリケーションフレームワークのYesodなどでも使われていますね。

ベンチマーク

最後に、blaze-builderがどれくらい効くのが、ベンチマークをカジュアルに取ってみましょう！

ベンチマークにはcriterionを使ってます。Haskellのベンチマークが簡単に取れて、ブラウザで見られる出力も得られます。

blazeを使用しない元々の連結操作と、blazeを利用した連結との両方の方針で文字列片をつなげて、ファイルに出力しています。 ついでに、Textに関してもByteStringと同様にベンチマークを取ってみました。

{-# LANGUAGE OverloadedStrings #-}

import Data.Monoid
import Blaze.ByteString.Builder           as B
import Blaze.ByteString.Builder.Char.Utf8 as BT
import qualified Data.ByteString.Lazy     as BL
import qualified Data.ByteString.Char8    as BS
import qualified Data.Text                as T
import qualified Data.Text.Lazy           as TL
import qualified Data.Text.Lazy.IO        as TL
import qualified Data.Text.Encoding       as T
import qualified Data.Text.Lazy.Builder   as T
import Criterion.Main
import System.IO (openTempFile)
import System.Directory (removeFile)


-- N-byteのByteStringを作る
byteN :: Int -> BS.ByteString
byteN n = BS.concat $ replicate n "x"

concatByteString :: Int -> BS.ByteString -> BL.ByteString
concatByteString n = BL.fromChunks . replicate n

blazeConcatByteString :: Int -> BS.ByteString -> BL.ByteString
blazeConcatByteString n = B.toLazyByteString . mconcat . map B.fromByteString . replicate n


-- N-文字のTextを作る
textN :: Int -> T.Text
textN n = T.concat $ replicate n "鬼"

concatText :: Int -> T.Text -> TL.Text
concatText n = TL.fromChunks . replicate n

blazeConcatText :: Int -> T.Text -> TL.Text
blazeConcatText n = T.toLazyText . mconcat . map T.fromText . replicate n


main :: IO ()
main = do
    -- 出力用の一時ファイル
    (tmpfile, tmph) <- openTempFile "/tmp" "bench_blaze"

    -- 1, 10, 50の大きさの単語を、10000個つなげる
    let samples = [1,5,10,50]
        wc      = 10000

    defaultMain $
        [ bgroup ("[bytestring] " ++ show x ++ "-byte words") [
              bench "no-blaze" $ BL.hPut tmph $ concatByteString      wc (byteN x)
            , bench "blaze"    $ BL.hPut tmph $ blazeConcatByteString wc (byteN x)
            ]
        | x <- samples ]
        ++
        [ bgroup ("[text] " ++ show x ++ "-letter words") [
              bench "no-blaze" $ TL.hPutStr tmph $ concatText      wc (textN x)
            , bench "blaze"    $ TL.hPutStr tmph $ blazeConcatText wc (textN x)
            ]
        | x <- samples ]

    removeFile tmpfile

上半分がByteStringで、下半分がTextです。

ちっちゃい文字列片ほど、効果が大きいようですね。

ベンチマークの実行は以下の様な感じです。

% ghc -O2 bench_blaze.hs
% ./bench_blaze -o bench_blaze.html

出力は分かりやすさのため一部削ってます。

出力

warming up
estimating clock resolution...
mean is 1.488974 us (640001 iterations)
found 4828 outliers among 639999 samples (0.8%)
  3539 (0.6%) high severe
estimating cost of a clock call...
mean is 58.44394 ns (8 iterations)
found 1 outliers among 8 samples (12.5%)
  1 (12.5%) high severe

benchmarking [bytestring] 1-byte words/no-blaze
mean: 1.221033 ms, lb 1.214946 ms, ub 1.228679 ms, ci 0.950
std dev: 34.94729 us, lb 29.31052 us, ub 43.71415 us, ci 0.950

benchmarking [bytestring] 1-byte words/blaze
mean: 136.0696 us, lb 125.3679 us, ub 144.9379 us, ci 0.950
std dev: 49.58111 us, lb 39.05003 us, ub 60.22993 us, ci 0.950

benchmarking [bytestring] 5-byte words/no-blaze
mean: 1.321834 ms, lb 1.310183 ms, ub 1.337639 ms, ci 0.950
std dev: 68.97484 us, lb 54.09187 us, ub 95.68489 us, ci 0.950

benchmarking [bytestring] 5-byte words/blaze
mean: 743.6934 us, lb 709.6834 us, ub 775.6366 us, ci 0.950
std dev: 169.3327 us, lb 132.2535 us, ub 223.0841 us, ci 0.950

benchmarking [bytestring] 10-byte words/no-blaze
mean: 1.396986 ms, lb 1.387786 ms, ub 1.408378 ms, ci 0.950
std dev: 52.24961 us, lb 42.96288 us, ub 63.49543 us, ci 0.950

benchmarking [bytestring] 10-byte words/blaze
mean: 1.448711 ms, lb 1.383338 ms, ub 1.513390 ms, ci 0.950
std dev: 331.6004 us, lb 294.9020 us, ub 414.8301 us, ci 0.950

benchmarking [bytestring] 50-byte words/no-blaze
mean: 6.478227 ms, lb 5.424632 ms, ub 7.761446 ms, ci 0.950
std dev: 5.944880 ms, lb 5.028813 ms, ub 7.670362 ms, ci 0.950

benchmarking [bytestring] 50-byte words/blaze
mean: 7.454674 ms, lb 7.041077 ms, ub 8.173508 ms, ci 0.950
std dev: 2.719382 ms, lb 1.760055 ms, ub 5.017425 ms, ci 0.950

benchmarking [text] 1-letter words/no-blaze
mean: 3.269654 ms, lb 3.259670 ms, ub 3.282536 ms, ci 0.950
std dev: 58.06780 us, lb 46.70660 us, ub 75.66644 us, ci 0.950

benchmarking [text] 1-letter words/blaze
mean: 306.1035 us, lb 304.2076 us, ub 308.4018 us, ci 0.950
std dev: 10.65997 us, lb 9.045305 us, ub 12.66282 us, ci 0.950

benchmarking [text] 5-letter words/no-blaze
mean: 4.930164 ms, lb 4.542772 ms, ub 6.752361 ms, ci 0.950
std dev: 3.662762 ms, lb 177.2833 us, ub 8.698922 ms, ci 0.950

benchmarking [text] 5-letter words/blaze
mean: 1.524795 ms, lb 1.515778 ms, ub 1.535984 ms, ci 0.950
std dev: 51.46477 us, lb 43.33059 us, ub 64.69094 us, ci 0.950

benchmarking [text] 10-letter words/no-blaze
mean: 5.897089 ms, lb 5.879782 ms, ub 5.917257 ms, ci 0.950
std dev: 95.94202 us, lb 82.75690 us, ub 114.9103 us, ci 0.950

benchmarking [text] 10-letter words/blaze
mean: 3.982748 ms, lb 3.591212 ms, ub 4.620310 ms, ci 0.950
std dev: 2.510847 ms, lb 1.805720 ms, ub 3.784512 ms, ci 0.950

benchmarking [text] 50-letter words/no-blaze
mean: 21.43716 ms, lb 19.98548 ms, ub 27.01497 ms, ci 0.950
std dev: 13.20911 ms, lb 2.446692 ms, ub 31.00659 ms, ci 0.950

benchmarking [text] 50-letter words/blaze
mean: 21.46007 ms, lb 20.58942 ms, ub 22.80350 ms, ci 0.950
std dev: 5.445815 ms, lb 3.780456 ms, ub 8.059161 ms, ci 0.950

ところで、最新のbytestring-0.10.2.0のパッケージを見ると、Builder関係のパッケージがbytestringから提供されてますね。 ドキュメントも、サンプルコードなどがあり充実してます。 textでは既にBuilderが入ってきてます。

まとめ

３種の文字列型と連結ライブラリのblaze-builderを見てきました。

• Stringはマルチバイト文字も扱えてカジュアルに使えるけど長い文字列には向かない。
• ByteStringは文字列というよりバイト列で、各種データをシリアライズするには便利。blaze-builderもあるし。
• TextはStringのようにマルチバイト文字も扱えて、ByteStringのように効率のいい処理ができて嬉しい。

これらの実装もHaskellで書かれているので、ソースを読んでみればきっと面白い発見があると思いますよ(・ω<)。

何か間違いなどありましたら、Twitter宛@brain_appleかコメント欄などで教えて頂けるとありがたいです。