Traversable API

与えられたConnectionを通じて、指定したKeyに対応するByteStringを取り出すような、シンプルなKey-ValueストアのAPIを考えてみよう。

type Key = ByteString
fetchOne :: Connection -> Key -> IO ByteString

ネットワーク越しにたくさんのデータを取得したいとき、何度もこれを呼び出していては効率が悪い。一度にまとめて取り出せるように拡張するなら、このように書ける。

fetchMany :: Connection -> [Key] -> IO [ByteString]

悪くはないが、この型はたとえば「["foo", "bar"]を要求したのに返ってきたのは[]」のような振る舞いを許してしまうため、使い手に不必要なパターンマッチを強いる。だが、リスト[]にちょっとした一般化を施すだけでそれを防ぐことが可能だ。

fetch :: Traversable t
  => Connection -> t Key -> IO (t ByteString)

リストが任意のTraversableになっているのがミソだ。TraversableはFunctorとFoldableのサブクラスで、各要素に対して作用を伴って関数適用し、元の構造を保ったまま返すような関数、traverseを持つ。パラメトリシティのおかげで、勝手に要素を追加したり減らしたりするような振る舞いは許されない*1。Identity、Maybe、[]のような型はもちろん、data V3 a = V3 a a aのような固定長のコンテナもインスタンスになる。

class (Functor t, Foldable t) => Traversable t where
  traverse :: Applicative f => (a -> f b) -> t a -> f (t b)
  ...

これだけでもfetchOneとfetchManyの一般化になるが、最近流行りのHKD(higher kinded datatype)とのコンボでさらなる力を発揮する。HKDは、パラメータとして与えられた型で各フィールドを包むことによって、同じデータ型に複数の役割を与えられるような手法である。例えばConst Stringで包んで各フィールドの名前を表したり、Parserで各フィールド用のパーサーを定義することができ、Identityなら当然通常のデータ型と同型になる。

data User h = User
  { userId :: h Int
  , userName :: h Text
  }

userFields :: User (Const Key)
userFields = User (Const "userId") (Const "userName")

barbiesのData.Barbie.Containerは、このパラメータがConstな場合にTraversableとして使えるようにする。

newtype Container b a = Container
  { getContainer :: b (Const a) }

userFieldsContainerで包めばfetchに渡せて、形を保ったままByteStringのレコードが返ってくるので、あとは煮るなり焼くなり好きにすればいい。

Container result :: Container User ByteString <- fetch conn $ Container userFields
let user :: Maybe (User Identity)
     user = btraverseC @FromJSON
       (fmap Identity . decode . getConst) result 

リクエストと同じ形のレスポンスが得られるという性質はGraphQLにも通じる。このような関手ライクなインターフェイスは、今後のAPI設計の鍵を握っているかもしれない。

*1:厳密には順番を入れ替えることは可能だが、そのような使い方はまずありえない

楽園へ行きたい

楽園へ行きたい。

森と平原に囲まれた、街のはずれの小屋に住みたい。

朝は、小鳥たちのさえずりと窓から射し込む陽の光で目覚めたい。
昼は、コーヒーと焼き菓子を用意して一服したい。
夜は、天の河の向こうに思いを馳せながら眠りたい。

月曜日は大学に行き、エルフの先生の下で言語学を学びたい。
火曜日は研究室にこもり、ドラゴンの教授と研究に没頭したい。
水、木曜日は道具鍛治と修繕の仕事をしたい。
金曜日は都に向かい、品を売って食材と情報を仕入れたい。
土曜日は酒場に集まり、仲間たちと杯を交わしたい。
日曜日は使い魔を連れ、公園をゆったり散歩したい。

春は、花々を眺めながら、渡り鳥たちにしばしの別れを告げたい。
夏は、祭りの企画に参加し、市民を楽しませたい。
秋は、旬のものでご馳走をたくさん作りたい。
冬は、客を呼んで鍋をつつきながら新年を迎えたい。

そんな楽園で私は暮らしたい。

特級シリアライズライブラリ、winery 1.0解禁

fumieval.hatenablog.com

あれから9ヶ月…wineryバージョン1.0をついにリリースした。

前回までのあらすじ

データの保存や通信に直列化は不可欠の概念である。 binaryなどの直列化ライブラリは、レコードのフィールド名などの情報が欠けており、構造が変わると互換性を持たせることができない。 一方、JSONやCBORなどのフォーマットで愚直にフィールド名などを残すと極めて冗長になり、時間・空間効率が悪い。 コード生成が前提のProtobufなどはHaskell既存のデータ構造との相性がよくない。 そんな現状に殴り込みをかけたのがwineryだ。値を「スキーマ」と「データ」に分割して保存することによって、冗長性を避けつつ、メタデータを保持させることができる。wineryは最強のライブラリとなりうるか…?

特徴と特長

JSON, MessagePack, CBORなど、多くのフォーマットでは値にフィールド名などの情報を付属させる。

[{"id": 0, "name": "Alice"}, {"id": 1, "name": "Bob"}]

wineryが違うのは、それらメタデータをデータ本体から分離し、一箇所にまとめて保存することにある。これにより、冗長性はなくなり、しかも要素がwell-typedであることを保証する。

0402 0402 0269 6410 046e 616d 6514  [{ id :: Integer, name :: Text }]
0200 0541 6c69 6365 0103 426f 62    [(0, "Alice"), (1, "Bob")]

メタデータのおかげでデシリアライザに互換性を持たせることも可能となる。もちろん、目的に応じてメタデータを省き、binaryやcerealと同じように使うこともできる。 整数のエンコードにはVLQを採用しているため、binaryやcerealよりも短くなりやすい。

使い方

まずSerialiseインスタンスを定義する。DerivingViaを使って簡単にインスタンスを導出できる。この導出機構は再帰的なデータ型にも対応している。

{-# LANGUAGE DerivingVia, DeriveGeneric, OverloadedStrings, ApplicativeDo #-}
import Control.Applicative
import Data.Winery
import Data.Text (Text)
import qualified Data.Text as T
import GHC.Generics (Generic)

data User = User
  { first_name :: !Text
  , last_name :: !Text
  , email :: !Text
  } deriving (Show, Generic)
  deriving Serialise via WineryRecord User

WineryRecordはどのようなインスタンスにするか選ぶためのラッパーだ。目的に応じてWineryProduct (フィールド名なし), WineryVariant(コンストラクタ名あり)と使い分けよう。

あとはserialise :: Serialise a => a -> ByteStringdeserialise :: Serialise a => ByteString -> Either WineryException aで自由にシリアライズ・デシリアライズができる。

> serialise (User "Fumiaki" "Kinoshita" "fumiexcel@gmail.com")
"\EOT\EOT\ETX\nfirst_name\NAK\tlast_name\NAK\ENQemail\NAK\aFumiaki\tKinoshita\DC3fumiexcel@gmail.com"

> deserialise @User "\EOT\EOT\ETX\nfirst_name\NAK\tlast_name\NAK\ENQemail\NAK\aFumiaki\tKinoshita\DC3fumiexcel@gmail.com"
Right (User {first_name = "Fumiaki", last_name = "Kinoshita", email = "fumiexcel@gmail.com"})

互換性

レコードにフィールドを追加したときや、バリアントからコンストラクタを削除したときなどに古いデータとの互換性が失われる。そんな場合のための処理をコンポーザブルに記述できる仕組みがwineryには備わっている。

UserにRoleというフィールドを追加したい場合を考えよう。

data Role = Admin | Moderator | Member
  deriving (Show, Generic)
  deriving Serialise via WineryVariant Role

data User = User
  { first_name :: !Text
  , last_name :: !Text
  , email :: !Text
  , role :: !Role
  } deriving (Show, Generic)

データにroleが欠けている場合の振る舞いも、ApplicativeDo記法を用いてカスタマイズができる。なんとメールアドレスがexample.comで終わっていれば自動で昇格するといった芸当も可能だ。

instance Serialise User where
  bundleSerialise = bundleRecord $ const $ buildExtractor $ do
    f <- extractField "first_name"
    l <- extractField "last_name"
    e <- extractField "email"
    r <- const <$> extractField "role"
      <|> pure (\x -> if T.isSuffixOf "example.com" x then Moderator else Member)
    return $ User f l e (r e)

RoleからModeratorを削除した場合も簡単に対応できる。

instance Serialise Role where
  bundleSerialise = bundleVariant $ const $ buildExtractor
    $ ("Admin", \() -> Admin)
    `extractConstructor` ("Moderator", \() -> Member)
    `extractConstructor` ("Member", \() -> Member)
    `extractConstructor` extractVoid

パフォーマンス

どんなに便利でも遅くては仕方がない。広く使われているbinary, cereal, aeson, serialiseと比較するためのテイスティング・セッションを行った。

課題となるのは以下のデータ型だ。それぞれの方法でインスタンスを導出し、1000要素のリストのシリアライズ・デシリアライズをする。

data Gender = Male | Female deriving (Show, Generic)

data TestRec = TestRec
  { id_ :: !Int
  , first_name :: !Text
  , last_name :: !Text
  , email :: !Text
  , gender :: !Gender
  , num :: !Int
  , latitude :: !Double
  , longitude :: !Double
  } deriving (Show, Generic)

{-
1,Shane,Plett,splett0@free.fr,Male,-222,53.3928271,18.3836801
2,Mata,Snead,msnead1@biblegateway.com,Male,-816,51.5141668,-0.1331854
3,Levon,Sammes,lsammes2@woothemes.com,Male,485,51.6561,35.9314
...
-}

結果は以下の通りだ。wineryがダントツで速いだけでなく、生成されるバイト列も最も短い。

encode 1 encode 1000 decode length
winery 0.28 μs 0.26 ms 0.81 ms 58662
cereal 0.82 μs 0.78 ms 0.90 ms 91709
binary 1.7 μs 1.7 ms 2.0 ms 125709
serialise 0.61 μs 0.50 ms 1.4 ms 65437
aeson 9.9 μs 9.7 ms 17 ms 160558

総評

互換性と拡張性、あらゆるデータ型に対応できる柔軟な導出メカニズム、そして卓越したパフォーマンスと簡潔な表現を提供するwinery 1.0は、ここ数年で最高の出来栄えと言えるだろう。Hackageへ急げ!

報告はGitHubもしくはHaskell-jp Slackまで。

旅のチェックリスト

筆者が旅に出る際に確認する項目をまとめた。

事前の準備

  • 渡航ビザ: 必要な場合もあるので事前に確かめよう。
  • ESTA(アメリカの場合): どんな理由であれUSに入国する場合申請する必要がある。大抵すぐ承認されるが、遅くとも出発の72時間前に済ませるべきである。
  • 宿: 好みに応じてホテルでもAirBnBなどで民泊を予約しても。後者はキッチンが用意されているところもある。
  • 交通手段: 電車は大抵の場合当日で大丈夫だが、もちろん船舶や航空機の場合は予約が必須である。
  • 冷蔵庫の整理: 日持ちしないものは消費してしまおう。

携帯するもの

  • 財布: 財布は現金やカードを収納する。リスク回避の観点から財布は省きセキュリティポーチで代用することもできる。
  • : 自宅を施錠、および帰りに解錠するのに必要である。こちらもリスク回避のため、自宅の鍵のみを持っていくという選択もある。
  • 交通系ICカード: 空港や港に向かったり、コンビニで買い物したりする際に便利である。
  • 保険証(国内の場合): 怪我や病気などになった場合、ないと損する。
  • クレジットカード: 紛失した場合無効化できる。
  • 腕時計 時間を気にするならあったほうがよいだろう。
  • 装飾品 首掛けバードコールやブレスレットなど。省略可

一般

汎用性が高いため、これらはまとめて一つの袋などに入れておくと有用である。

  • ビニール袋: ゴミや細々とした物をまとめるために、2枚程度は用意したい。
  • マイクロファイバークロス: レンズやメガネなどの光学機器を使う場合必須である。
  • 非常食 質量・体積あたりのカロリー密度が高いものを100kcal*日数くらい用意しておくと、いざという時の体力の回復に役立つ。
  • インスタント食品 カップ麺やスープなどは熱湯を要求するが、食味とカロリー密度において優れている。特に海外に行く際、一つは用意しておくと心も暖まる。宿泊場所にキッチンがあるがスーパーは遠いといった場合、袋麺なども選択肢になり、荷物の圧縮につながる。

国内で入手しやすいものの質量とカロリーを比較すると以下のようになる。

名前 質量(g) カロリー(kcal) 質量比
inゼリー スーパーエネルギー 120 200 1.67
大粒ラムネ 41 153 3.73
カップヌードル カレー 87 422 4.85
カロリーメイト 80 400 5.0

ゼリーは液体として扱われ、国際線には手荷物として持ち込めないので注意が必要である。

  • 酔い止め: 乗り物酔いする体質の場合
  • サプリメント: 旅先でバランスのいい食事ができるとは限らないのでマルチビタミンは確保したい。また、疲労対策としてアミノ酸サプリメントもあるとよい。小分けにする場合は怪しまれないよう気を付けたい。
  • ボディソープ、シャンプー、コンディショナー、洗顔料など 機内に持ち込めるよう、小さい容器に入れ密封可能な袋にまとめておく。もし宿泊先にあるという確証がある場合は省いても良い。
  • 固体石鹸: もし上記のいずれかを切らした場合のバックアップになる。液体枠を圧迫しないため持っておいて損はない。
  • 剃刀: 除去すべき体毛がある場合用意すべきである。
  • ネックライト: 街灯がなく真っ暗闇になるところもあり、安全を確保する上で重要だ。
  • 爪切り: 爪が伸びすぎると危険かつ不衛生である。1週間を超える滞在の場合は爪切りは必須である。
  • 日焼け止め: 低緯度地域に向かう場合、紫外線から体を守るために用意したい。
  • ポケットティッシュ
  • : 袋でもいいしハンカチでもいい。
  • 絆創膏: 大きめのものが3枚程度あると安心だ。
  • 櫛・ヘアブラシ
  • 新聞紙などの薄い紙: 靴が濡れた際に乾かすのに使える。

衣類

行き先の気候に合わせたものを用意する。

  • 下着
  • 靴下
  • シャツ
  • 手袋
  • 洗濯可能な衣類ケース

電子・電気製品

電気製品は一つの袋にまとめておくと、手荷物検査を迅速に進められる。

  • イヤホン・ヘッドホン: 移動中に音楽を楽しみたい場合。音漏れしにくく、遮音性が高いものを選びたい。国際線では機内エンターテイメントのためにイヤホンが配布される場合もあるが、音質は極めて劣悪だ。
  • 撮影機材: 旅の思い出を残す一つの手段だ。
    • カメラボディ: 割となんでもよい。レンズを交換する隙を晒したくない場合は複数持って行こう。
    • 広角レンズ: 風景、建築、料理や集合写真など、トリミングする前提で幅広く応用できる。大は小を兼ねるとはこのことだ。
    • 超望遠ズーム: 150-600mmなど。2kg程度で取り回しがよく、野鳥や動物の撮影に適する。
    • 高倍率ズームレンズ: 画質・明るさにこだわらないなら、18-300mmなどの高倍率ズームレンズの一本だけでもよい。多くはAPS-C向けで、風景から、野鳥などの撮影まで使える画角を持つ。
    • 三脚: 夜景、自撮り、動画のいずれかを撮る予定なら三脚は欲しい。いざという時は武器にもなる
    • カメラのバッテリーの充電器: 写真のみなら大抵数日は持つが、それ以上の場合は充電器を用意しておくと安心だ。
    • カメラの予備バッテリー
  • カメラとPCを接続するためのケーブルやハブ
  • ラップトップPC: 現地で撮った写真を取り込んで編集、投稿するという一連の流れを実現する上であると望ましい。
  • USB充電器: タップに5V出力が付いたようなものは変換プラグとのシナジーがある。
  • スマートフォンを充電するためのケーブル
  • モバイルバッテリー: 携帯端末のバッテリー切れは避けたい。航空機を使う場合、こちらは預けることができないので要注意。

国外の場合

  • ボールペン: 税関申告書や出入国カードの記入に必要となる。機内で取り出せるようにしておこう。
  • SIMカードを二枚挿しできるスマートフォン: SIMカードの入れ替えは紛失のリスクが伴う。二枚挿入できるスマートフォンを持って行こう。 
  • 旅券(パスポート): 言わずもがな。
  • 海外キャッシングのできるカード: 大量の現金を事前に用意するのはコストやリスクの観点からあまりよろしくなく、通貨によってはそもそも事前に用意できないケースもある。現地で現金を得る手段として確保しておきたい。
  • 変換プラグ: 行き先によっては必要となる。
  • 現金: 最低限、現地の通貨をあらかじめ用意しておきたい。それが難しい場合、現地で両替できるようなものを代わりに持って行こう(メキシコペソなら米ドルなど)。

娯楽

荷物に余裕があるなら、いずれかを持っていくのも一興だ。

  • 携帯用ゲーム機: 移動中の暇潰しになる。
  • トランプ、花札、サイコロなど: 筆者とは無縁だが、複数人での旅なら一つの楽しみとなりうる。
  • DJコントローラ: もし知人同士で自動車に乗り、運転しないということであれば車内が盛り上がること間違いなしだ。
  • MIDIキーボード: 旅先の雰囲気を音楽として残したいなら是非とも用意したい。25鍵など小さいものでもあるとないとでは大違いだ。

出発の直前に(国外の場合)

  • 日本食は食べたか? 長旅の前に日本の食べ物を体に蓄えておきたい。和食やラーメンなどはもちろんだが、見落としがちなのは洋食(オムライスなどの日本料理)だ。
  • 風呂に入ったか? 日本から北米までの距離を渡る際、ほぼ一日風呂に入らずに過ごすことになる。しかも浴室は日本よりも簡素な場合がほとんどなので、出発する直前に入念に体を洗おう。

余録

いかがだろうか?今回ダラスへと向かう機内で執筆していたが、ネックライトと新聞紙を忘れていたことに気づいた。次回はこのリストを見返して気をつけると同時に、読者にもチェックリストの作成をおすすめしたい。

ある期間内に更新されたデータを素早く検索できるモデル

特定の技術とは関係ない、誰でも思いつきそうな、でも便利なお話。

こんなケースを考えてみよう。

人気のトレーディングカードゲームAugur Unlimitedを扱うショップ「しらさぎ商店」では、1000種類にも及ぶカードの買い取り・販売をしている。記録のため、カードごとに日時、価格、在庫数などをまとめたレコードを毎日データベースに書き込んでいる。

新着・売り切れや、価格の変化などを、指定された期間について一覧で表示するようなWebページを作りたいとオーナーは考えた。しかし、ユーザーからの要求ごとに全データの差分を取るのは、あまり効率的な手段とはいえない。レアなカードでもない限り価格は一定であることが多いからだ。 どうすれば更新されたものだけを効率よく取り出せるだろうか?

答えはシンプルで、「日時」を「作成日時」と「終了日時」に分け、価格などが変わった時だけ新しくレコードを作成すると同時に、前のレコードの終了日時を更新すればよいのだ。新しいレコードの終了日時は未来永劫先とする。こうすると、任意の期間t0 ~ t1について、「更新される前のデータの集合」と「更新後のデータの集合」を取得することができる(データベースがこのようなクエリを許す限り)。

  • 更新前: t0 < 終了日時 < t1 かつ 作成日時 < t0
  • 更新後: t0 < 作成日時 < t1 かつ 終了日時 > t1

図にするとこんな感じだ。

f:id:fumiexcel:20190212190421p:plain

赤で示したレコードと緑で示したレコードを比較すると、サンカノゴイが削除され、イスカとカワセミが更新、コブハクチョウが新しく追加されたことがわかる。二番目の条件は、期間内に作成・終了されたレコード(カワセミ)を弾くためのものだ。

至極単純なアプローチだが、このような問題について記述している文章が見つからなかったので、今後のために残しておく。

追記 この形式はValid timeと呼ばれているらしい。

戊戌の追憶

この記事は、筆者が過ごした2018年を簡潔に振り返り、その経験を糧とすることを狙う。

1月

第二鰓弓由来側頸嚢胞という先天異常が原因で首が化膿し、激痛に苦しんでいた。対人関係のトラブルなどもあり軽い錯乱状態にあったのか、自分が知らない間に高い買い物をすることがあった。

drinkery: Boozy streaming library というストリーム処理ライブラリを作った。当初はすべて酒関係の用語を用いていたが、批判を受けてそこはやめた。今思えばそれで正解だった気がする。 パフォーマンスはモナディックなAPIを持つライブラリの中ではトップクラスで、双方向性や多入力多出力のような発展的な機能もあるが、ListTが正しく効率的に実装されているのがなによりの魅力である。ListTのために時々使っている。

危うい精神状態だったが被写体には恵まれた。この写真はけっこう気に入っている。

2月

警察のおかげで対人トラブルは解消された。アリピプラゾール(エビリファイ)の服薬を始めて、自分の脳の働きが変質しているような感じがした。薬のせいか忘れ物が増えた。

Discordのボイスチャンネルに入った際に通知メッセージを投稿する GitHub - fumieval/discord-vc-notification を作った。実用とHaskellチュートリアルを兼ねている。けっこうな数のサーバーに導入されたようで喜ばしい。

fumieval.hatenablog.com

生き甲斐の一つである野鳥撮影は続けた。

3月

花粉症とその薬のせいで生産性がかなり削られていた気がする。

PPL 2018: 第20回プログラミングおよびプログラミング言語ワークショップ

のために鳥取に行った。ヘラサギというレアな鳥に会えた。

4月

溜め込んでいた力を解放できた月だ。

Bigmoonが私の看板ライブラリであるextensibleを使っており、偵察のためにアルバイトを始めた。2週ごとに名古屋に出勤という形で楽しく仕事を続けている。

Haskell-jpの新しいロゴ案を作り、投票によって正式に採用された。薬でブーストされたセンスのおかげだと思う。

5月

アリピプラゾールの副作用の悪夢や物忘れが気になってくる。

Wikiシステムを作った。アルゴリズムからWebプログラミングまで様々な技術を応用するいい課題だった。現在もextensible攻略Wikiに使われている。

この時期はシギ・チドリ類が飛来し、干潟などでよく観察できる。毎年お疲れ様と言いたい。

6月

スキーマを導出してWell typedかつ短いエンコードができるだけでなく、後方互換でコンポーザブルなデシリアライザを構築できる直列化ライブラリ、wineryを創り出した。機能面もパフォーマンスもなかなか優秀なライブラリだと思う。

fumieval.hatenablog.com

サギの雛たちが育ってきてコロニーでは賑やかな光景が見られた。

7月

CAT S60という、サーモグラフィー搭載のごついスマートフォンを買った。他に使っている人を見たことはなく、自慢できる一本だ。

Overwatchでメインで使っていたキャラクターであるシンメトラがリワークを受け、使える技が一新された。研究がされてないこともあいまって環境にぶっ刺さり、シルバーからプラチナ帯までのし上がった。

とあるオフ会に参加して知り合いが増えた。

togetter.com

8月

Lisztというデータベースの実装を一新し、全データを一つのファイルにまとめる試みをしていた。非常に興味深い例題でけっこうな時間を費やした。

Minecraft (Bedrock Edition)でよく遊んだ。しばらくMinecraftから離れていたが、新しい生物やブロックなどが追加されていて通話などもしつつ楽しめた。新たな居場所を見出したような気がした。

9月

Compact regionsというGHC 8.2の新機能の効果的な使い方を発見した。更新頻度が低いデータを納め、それをIORefで保持するのがよい。私が執筆したものではないがこの記事でよく説明されている。

qiita.com

ガス欠気味であまり新しいものを生み出せなかった。なおOverwatchではシンメトラで暴れまくった。

10月

三宅島へと飛んだ。船で行く予定だったが台風で欠航になり、仕方なく新中央航空の19人乗りの双発機で行った。

f:id:fumiexcel:20181001093145j:plain

ほぼ徒歩で島を一周するという目論見で、穏やかながら新鮮な離島の雰囲気を味わうことができた。

予約していた民宿の女将は欠航が理由で私は来ないと思い込んでいたようで、無人の宿の前で待ちぼうけを食うというアクシデントがあった。幸い、数時間したら女将が戻ってきたため蚊に血を吸い尽くされるのは免れた。女将の作ってくれた料理はとても美味しかった。結局、宿泊費はただにしてもらったので結果オーライである。

f:id:fumiexcel:20181002124857j:plain

個人経営の古めかしいスーパーマーケットに東方や艦これのグッズが飾ってあり、離島は離島でも同じ世界にいることを感じた。

f:id:fumiexcel:20181003091512j:plain

三宅島で過ごした三日間は、間違いなく幸せなものだった。鳥の多い時期にまた行きたい。

行きつけのMinecraft BEのサーバーが過疎気味だったので、自分で新しいサーバーを立てた。Java版ゆえにサーバーMODなどが豊富で、以前とはまた違った楽しみ方ができた。

11月

Haskell Day 2018が開催された。Haskell関連の勉強会が開催されるのは久しぶりだ。来場者は150人と大盛況で、有意義なものだった。なお、私はLisztについての発表をしたが、しばらくこのような場に立つことがなかったため発表スキルの低下を痛感した。

仕事ではGHC 8.6への移行に従事していた。セグメンテーション違反で落ちる致命的なバグが見つかったのもいい思い出だ。#15892 (Segmentation fault with ByteString) – GHC

自分でも理由はよくわからないが、この月は写真をあまり撮らなかった。よくよく考えると精神的に不安定だった気がする。

12月

心の調子が急激によくなった。

簡潔データ構造に興味が湧き、厳密には簡潔データ構造ではないがElias-fano encodingという手法について調べていた。

fumieval.hatenablog.com

普段扱っている純粋関数型データ構造とはまた違ったトリッキーさがあり、刺激的な体験だった。

ローグライクなカードゲームのSlay the Spireに少しはまったりした。一押しはディフェクトで、「山札から任意の2枚を選ぶ」「山札の先頭数枚から好きなだけ選んで捨てる」「捨て札を手札に戻す」といった制御系のカードを揃えていき、運ゲー運ゲーでなくする過程が楽しい。

そして鳥の季節がやってきた。昨年は見られなかったアトリが来ていて喜ばしい。

総評

一年を通して、私の心と体、そして人間関係などの環境は徐々に改善された。ストレスの減少によって体づくりの効率も上がったのも間違いない。

そして、私は新しい能力、新しい道具、新しい仲間を得ることができた。来年からとは言わず今日から、それらを無駄にすることのないよう心がけていきたい。

Elias-Fano encoding: 単調増加する数列をほぼ簡潔に表現する

Haskell Advent Calendar 2018 20日

単調増加する自然数の列を、最低限のビット数で表現するための興味深いテクニックと、Haskellによる実装を紹介する。

Elias-Fano encoding

この手法は、簡潔データ構造に分類されるもの一つであるが、厳密には条件を満たさないため疑似簡潔データ構造と呼ばれる。1970年代、Peter EliasとRobert Mario Fanoによって独立して発見された。

例題として1, 1, 4, 10, 17, 22, 23, 30という列をエンコードしてみよう。まず、それぞれの数を上位3ビットと下位2ビットに分割する。列の長さをNとしたとき、上位のビット数は{ \displaystyle
\lceil \lg N \rceil
}とする。

上位ビットの列は000 000 001 010 100 101 101 111となる。これをヒストグラムのようにして23個のビンに分ける。

  • 000: 2個
  • 001: 1個
  • 010: 1個
  • 011: 0個
  • 100: 1個
  • 101: 2個
  • 110: 0個
  • 111: 1個

これにアルファ符号(個数分だけ1を並べ、0で区切る)を適用すれば上位の表現は完成だ。要素数分の1と、バケット{ \displaystyle
2^{\lceil \lg N \rceil}
}分の0を合わせるのでおよそ{ \displaystyle
2N
}ビット使う。

1101010010110010

下位ビットの列は、そのまま結合する。こちらは、元のビット数をWとしたとき、{ \displaystyle
N(W-lg(N))
} ビット消費する。

0101001001101110

32ビットの整数を105個格納する場合、消費ビット数は17*105ビットとなかなか優秀な圧縮率を誇る。

n番目の値を読み出すときは、上位は{ \displaystyle select_1(n) - n}を求め、下位はそのまま取り出してくっつければよい。{ \displaystyle select_1(n)}は簡潔データ構造の文脈でよく使われる演算の一つで、ビット列のn番目に出現する1の位置を求める。nを引くのは、ちょうどn個だけ0が混ざっているからだ。

実装

早速実装してみよう。上位ビットのエンコーダは非自明そうに見えるが、要素の位置、上位ビット、カウンタの三つ組(i, u, n)を持つステートマシンで簡単に表現できる。

  • (i, u, n) = (0, 0, 0)から開始する
  • uが最大値を超えたとき、nを出力し停止
  • i番目の上位ビットとuを比較する
    • 等しい場合、(i + 1, u, n + 1)に更新する
    • 異なる場合、nを出力し、(i, u + 1, 0)に更新する

あまり知られていないが、vectorパッケージにはData.Vector.Fusion.Stream.Monadicという簡単なオートマトンを表現するためのモジュールがある。状態と、それを更新する関数の対という単純な作りで、最適化が効く限りこの構造は消滅してただのループとなる。表現力は限られているが、他の追従を許さないパフォーマンスを誇る。

data Stream m a = forall s. Stream (s -> m (Step s a)) s

data Step s a where
  Yield :: a -> s -> Step s a
  Skip  :: s -> Step s a
  Done  :: Step s a

ビット列をVector Boolのように愚直に扱っていては空間効率が悪いので、まずはビット列をWord64の配列に変換する仕組みを作りたい。ここでは受けとったWord64から任意のビット数だけ切り取り、それらを連結して出力する変換器を定義する。Bの最初のフィールドが切り取るビット数となる。溢れたビットの処理はやや煩雑だが、やるだけなので読み飛ばしても構わない。ただしINLINEは必須で、これがないと最適化が止まってしまいポテンシャルを発揮できない。

import Data.Bits
import Data.Word (Word64)
import qualified Data.Vector.Fusion.Stream.Monadic as S

data B = B !Int !Word64

data Chunker s = Chunker s !Word64 !Int
  | ChunkerDone

chunk64 :: Applicative m => S.Stream m B -> S.Stream m Word64
chunk64 (S.Stream upd s0) = S.Stream go $ Chunker s0 zeroBits 0 where
  go ChunkerDone = pure S.Done
  go (Chunker s acc len) = flip fmap (upd s) $ \case
    S.Done -> S.Yield acc ChunkerDone
    S.Skip s' -> S.Skip $ Chunker s' acc len
    S.Yield (B width w) s' -> case mask width .&. w of
      w' | width + len >= 64 -> S.Yield (acc .|. unsafeShiftL w' len)
            $ Chunker s' (unsafeShiftR w' (64 - len)) (len + width - 64)
         | otherwise -> S.Skip $ Chunker s' (acc .|. unsafeShiftL w' len) (len + width)
{-# INLINE chunk64 #-}

次に、アルファ符号のエンコーダを定義する。chunk64は64より長いビット列を受け取れないので、複数に分けるという処理をする。

data Unary s = Unary s | UnaryCont !Int s

unary :: Applicative m => S.Stream m Int -> S.Stream m B
unary (S.Stream upd s0) = S.Stream go $ Unary s0 where
  go (Unary s) = flip fmap (upd s) $ \case
    S.Done -> S.Done
    S.Skip s' -> S.Skip (Unary s')
    S.Yield n s' -> step n s'
  go (UnaryCont n s') = pure $ step n s'
  step n s'
    | n < 64 = S.Yield ((n + 1) `B` mask n) (Unary s')
    | otherwise = S.Yield (B 64 (complement zeroBits)) (UnaryCont (n - 64) s')
{-# INLINE unary #-}

これらを組み合わせてエンコーダを定義する。エンコードの結果として出力するのは以下の5つ組だ。

data EliasFano = EliasFano
    { efLength :: !Int
    , efWidth :: !Int
    , efUpper :: !(UV.Vector Word64)
    , efRanks :: !(UV.Vector Int)
    , efLower :: !(UV.Vector Word64)
    }
    deriving Show
  • efLength: 要素数
  • efWidth: 下位ビットの幅
  • efUpper: 上位ビットの列
  • efRanks: 上位ビットの列をpopcountして累積加算させた列(あとで有利に働く)
  • efLower: 下位ビットの列

以下がエンコーダの実装だ。Streamを効率よくVectorに変換する関数が提供されており、fromStream'でそれらを利用している。upd関数は先に述べたアルゴリズムを実装している。unsafeが散らばっていて可読性はよくないが、ロジックは比較的わかりやすいだろう。

import Control.Monad.ST
import Data.Bits
import qualified Data.Vector.Generic as V
import qualified Data.Vector.Generic.Mutable as GM
import qualified Data.Vector.Unboxed as UV
import qualified Data.Vector.Fusion.Bundle.Monadic as B
import qualified Data.Vector.Fusion.Bundle.Size as B
import qualified Data.Vector.Fusion.Stream.Monadic as S
import Data.Word

data EncoderState s = ESCont !Int !Word64 !Int | ESDone

unsafeFromVector :: V.Vector v Word64 => v Word64 -> EliasFano
unsafeFromVector vec = runST $ do
  efLower <- fromStream' ((efWidth * efLength + 63) `div` 64)
    $ chunk64 $ S.map (B efWidth . fromIntegral) $ B.elements $ B.fromVector vec
  efUpper <- fromStream' ((efLength + 3) `div` 4)
    $ chunk64 $ unary $ S.Stream upd $ ESCont 0 0 0
  return EliasFano
    { efRanks = UV.prescanl (+) 0 $ UV.map popCount efUpper
    , ..
    }
  where
    upd ESDone = pure S.Done
    upd (ESCont i current n)
      | current > maxValue `unsafeShiftR` efWidth = pure $ S.Yield n ESDone
      | otherwise = pure $ case fromIntegral $ V.unsafeIndex vec i `unsafeShiftR` efWidth of
        u | u == current -> S.Skip $ ESCont (i + 1) current (n + 1)
          | otherwise -> S.Yield n (ESCont i (current + 1) 0)

    efLength = V.length vec

    fromStream' len s = GM.munstream (B.fromStream s (B.Exact len))
      >>= UV.unsafeFreeze
    {-# INLINE fromStream' #-}

    maxValue
      | V.null vec = 1
      | otherwise = V.last vec + 1
    efWidth = max 1 $ ceiling $ logBase 2 (fromIntegral maxValue / fromIntegral efLength :: Double)
{-# SPECIALISE unsafeFromVector :: UV.Vector Word64 -> EliasFano #-}

鬼門となるのは要素のアクセスだ。まずはWord64に対するselect関数を実装しなければならない。これに関しては優れたアルゴリズムが研究されており*1、ekmett先生によってすでに実装されていた*2のでそれを拝借した。この手法を直感的に理解するのは、私の頭では不可能だった。

ここさえクリアすれば、Word64の配列に対してselectを実装するのはさほど難しくない。どの要素に対してselectWord64を呼べばいいかは、先に用意しておいたpopcountの配列に対する二分探索によって判断できる。

select :: (V.Vector v Int, V.Vector v Word64) => v Int -> v Word64 -> Int -> Int
select ranks vec q = go 0 (V.length ranks - 1) where
  go l r
    | l >= r = selectWord64 v (q - V.unsafeIndex ranks l) + 64 * l
    | q < V.unsafeIndex ranks (i + 1) = go l i
    | otherwise = go (i + 1) r
    where
      i = div (l + r) 2
      v = V.unsafeIndex vec i
{-# SPECIALISE select :: UV.Vector Int -> UV.Vector Word64 -> Int -> Int #-}

下位ビットを読み出す処理は、ビットを跨ぐ場合さえ気をつければ大丈夫だ。

readBits :: V.Vector v Word64 => v Word64 -> Int -> Int -> Word64
readBits vec width pos
  | b + width > 64 = unsafeShiftL extra (64 - b) .|. base
  | otherwise = base
  where
    i = unsafeShiftR pos 6
    b = pos .&. 63
    base = (V.unsafeIndex vec i `unsafeShiftR` b) .&. mask width
    extra = V.unsafeIndex vec (i + 1) .&. mask (width + b - 64)
{-# SPECIALISE readBits :: UV.Vector Word64 -> Int -> Int -> Word64 #-}

これらを合わせればインデックスの処理が出来上がる。上位ビットの配列は、元の列の長さNに対して{ \displaystyle O(\log N)}個、selectの計算量は配列の長さNについて{ \displaystyle O(\log N)}なので、この演算の計算量は{ \displaystyle O(\log \log N)}となる。

(!) :: EliasFano -> Int -> Word64
(!) (EliasFano _ width upper ranks lower) i
  = fromIntegral (unsafeShiftL (select ranks upper i - i) width)
  .|. readBits lower width (i * width)

ここで紹介したコードはGitHubに保存している。

github.com

テスト

ビット演算という性質上、同じ型の中でたくさんの値を扱うためバグが湧きやすい。QuickCheckは大いに役立った。最終チェックとして以下のテストを残した。

import qualified Test.QuickCheck as QC

prop_access :: [QC.NonNegative Int] -> QC.NonNegative Int -> QC.Property
prop_access xs i_ = QC.counterexample (show (base, ef, i))
  $ ef ! i == base !! i
  where
    i = QC.getNonNegative i_ `mod` length base
    base = scanl (+) 0 $ map (fromIntegral . QC.getNonNegative) xs
    ef = unsafeFromVector $ UV.fromList base

ベンチマーク

やはり気になるのはパフォーマンスだ。適当に単調増加する数列をこしらえ、反転やインデックスなどの基本的な演算と比較した。

td :: V.Vector Word64
td = V.scanl (+) 0 $ V.fromList $ map (toEnum . fromEnum) $ "Lorem ipsum dolor sit amet, consectetur adipiscing elit, sed do eiusmod tempor incididunt ut labore et dolore magna aliqua. Ut enim ad minim veniam, quis nostrud exercitation ullamco laboris nisi ut aliquip ex ea commodo consequat. Duis aute irure dolor in reprehenderit in voluptate velit esse cillum dolore eu fugiat nulla pariatur. Excepteur sint occaecat cupidatat non proident, sunt in culpa qui officia deserunt mollit anim id est laborum."

main = do
  let ef = unsafeFromVector td
  defaultMain
    [ bench "encode/elias-fano" $ whnf unsafeFromVector td
    , bench "encode/vector" $ whnf V.reverse td
    , bench "access/elias-fano" $ nf (map (ef!)) [0..V.length td - 1]
    , bench "access/vector" $ nf (map (td V.!)) [0..V.length td - 1]
    ]

結果はこの通りだ。インデックスはUnboxed Vectorの2倍強遅いが、内部で3つの配列を使っていることを考えると期待以上であると言える。

encode/elias-fano                        mean 3.891 μs  ( +- 78.82 ns  )
reverse/vector                            mean 705.7 ns  ( +- 12.20 ns  )
access/elias-fano                        mean 16.69 μs  ( +- 423.2 ns  )
access/vector                            mean 7.499 μs  ( +- 2.076 μs  )

応用

Elias-Fano encodingはマイナーな手法ではあるが、よく知られている応用として検索のためのインデックス化が挙げられる。単語ごとに、マッチする文書の番号の一覧をメモリ上に保持するといった風に利用できる。ここでは紹介しなかったが、ある値より等しいかそれ以上の要素を探すという演算も効率よく実装でき、積集合を求める操作において並外れたパフォーマンスを発揮する。

また、個人的な研究として、LOUDSなどの木構造の簡潔な表現と組み合わせ、シリアライズに応用できないか模索している。直列化に簡潔データ構造を用いる例は少ないので開拓しがいがあると感じている。

まとめ

  • Elias-Fano encodingは、単調増加する自然数の列を圧縮しつつ、効率の良いアクセスも提供する
  • Data.Vector.Fusion.Stream.Monadicを使って、パフォーマンスを犠牲にすることなく抽象度を高められる
  • QuickCheckにより、複雑でバグを仕込みやすい処理も簡単にテストできる
  • 利用例がまだ少なく、研究しがいがある

参考文献