波打たせるものの正体(エクステンシブル・タングル)

Haskell Advent Calendar 11日目


リアルワールドなHaskellerは、幾十ものフィールドを持つ大きなレコードをしばしば扱う羽目になる。モナディックにレコードを構築したい場合、RecordWildCards拡張を用いて以下のようにするのが定番だ。

import System.Random

data Rec = Rec { foo :: String, bar :: Int, baz :: Double, qux :: Bool }

makeRec = do
  foo <- getLine
  bar <- length <$> getLine
  baz <- readLn
  qux <- randomIO
  return Rec{..}

しかし、<-の右辺が大きい、フィールドの数が多い、といったリアルワールドにありがちな事象が掛け算されれば、定義は巨大になってしまう。

そこで登場するのがextensibleの拡張可能レコードである。たとえアプリカティブに包まれていようと、一発でレコードを鋳出すことができる。

extensibleについておさらいしよう。根幹となるのは拡張可能な積だ。

(:*)
  :: (k -> *) -- 顕現せし型
  -> [k] -- 要素のリスト
  -> *

拡張可能な積(:*)顕現せし型要素のリストの二つの型パラメータを持つ。顕現せし型は、要素を現実、つまり種*の型に対応させる型である。例えば、T :* '[A, B, C]はタプル(T A, T B, T C)と等価となる。

普通のレコードとして使う場合、顕現せし型としてField Identityを帯びる。

type family AssocValue (kv :: Assoc k v) :: v where
  AssocValue (k ':> v) = v

newtype Field (h :: v -> *) (kv :: Assoc k v) = Field
  { getField :: h (AssocValue kv) }

これにより、以下の型は前に定義したRecと等価になる。

type Rec = Field Identity
  :* ["foo" :> String, "bar" :> Int, "baz" :> Double, "qux" :> Bool]

レコードを作るには、各フィールドごとに関数を定義し、hgenerateForにほぼ直接渡すだけでよい。 インスタンス宣言でフィールドの型を二度書かないといけないのは少々面倒だが、これで拡張性を得られた。

{-# LANGUAGE TemplateHaskell, DataKinds #-}
import Control.Monad.Trans.Class
import Data.Extensible
import Data.Functor.Identity
import Data.Proxy

mkField "foo bar baz qux"

type Fields = ["foo" :> String, "bar" :> Int, "baz" :> Double, "qux" :> Bool]

type Rec = Record Fields

class MakeRec kv where
  make :: proxy kv -- kvを明示しないといけない
    -> IO (AssocValue kv)

instance MakeRec ("foo" :> String) where
  make _ = getLine

instance MakeRec ("bar" :> Int) where
  make _ = length <$> getLine

instance MakeRec ("baz" :> Double) where
  make _ = readLn

instance MakeRec ("qux" :> Bool) where
  make _ = randomIO

makeRec :: IO Rec
makeRec = hgenerateFor (Proxy :: Proxy MakeRec) (\m -> Field . pure <$> make m)

しかし、アクションに依存関係があるとこの方法は使えない。do記法とRecordWildCardsの定番スタイルでも、ステートメントの順番をうまく並べ替えなければならず、別の定義に切り分けるというのもそう簡単ではない。

そこでエクステンシブル・タングルという新しいアプローチを始めた。拡張可能な積h :* xsを構築するためのモナド変換子、TangleT h xsを導入する。

TangleT :: (k -> *) -- 顕現せし型
  -> [k] -- 要素のリスト
  -> (* -> *) -- 礎のモナド
  -> * -- 結果の型

先ほどの例をTangleTを使うように変えると以下のようになる。liftを入れてTangleT (Field Identity) Fieldsを返している以外は特に違いはない。

class MakeRec kv where
  make :: proxy kv -> TangleT (Field Identity) Fields IO (AssocValue kv)

nstance MakeRec ("foo" :> String) where
  make _ = lift getLine

instance MakeRec ("bar" :> Int) where
  make _ = lift $ length <$> getLine

instance MakeRec ("baz" :> Double) where
  make _ = lift readLn

instance MakeRec ("qux" :> Bool) where
  make _ = lift randomIO

まずmakeを一か所に集める。型合わせのためにCompが使われている点に注意。

-- newtype Comp (f :: j -> *) (g :: i -> j) (a :: i) = Comp { getComp :: f (g a) }

tangles :: Comp (TangleT (Field Identity) Rec m) (Field Identity) :* Rec
tangles = htabulateFor (Proxy :: Proxy MakeRec)
    $ \m -> Comp $ Field . pure <$> make m)

これをレコードに変換するのがrunTanglesだ。最初の引数には先ほどのtangles、次は既知の値(ある場合)を渡す。既知の値はないのでwrench Nilを渡す。

-- runTangles :: Monad m
--    => Comp (TangleT h xs m) h :* xs
--    -> Nullable h :* xs
--    -> m (h :* xs)

makeRec :: IO (Record Rec)
makeRec = runTangles tangles (wrench Nil)

このモナドの価値を決める必殺技とも言うべき固有アクション、それはlassoである。

lassoにフィールド名を渡すとその値が返ってくる。二度以上呼んでも実際の計算は一回しか行われないのがポイントである。

lasso :: forall k v m h xs
    . (Monad m, Associate k v xs, Wrapper h)
    => FieldName k
    -> TangleT h xs m (Repr h (k ':> v))

これにより、依存関係をいくら孕んでいようとも、簡単にレコードを構築できる。foobazが文字列として一致しているか確かめるコードはこんな感じになる。

instance MakeRec ("qux" :> Bool) where
  make _ = do
    str <- lasso foo
    x <- lasso baz
    return $ str == show x

しかし、なぜこんなものが必要になったのか――その動機は「波打たせるもの」にある。

メッセージフォーマット勉強会にて、このプログラムの存在について軽く触れた*1。監視対象はログを出力し、ネットワークを通じてオフィスのサーバーに配送される。ビューア(監視プログラム)はリアルタイムでログを読み取り、GUIとして表示するが、一つの問題が生じる。

「あるイベントが発生した回数」を表示したいとしよう。監視プログラムはそのイベントが出てくるたびに内部のカウンタを増やす。しかし、少し前の値を見ようとシークした途端、その値は無意味なものになってしまう。そういった値は監視対象がログに含めるという手もあるが、遠隔地にあり帯域も制限されているだけでなく、パフォーマンス上の要求から処理を増やしたくないため、なるべくこちら側で解決したい。そこで手を打つべく開発されたのが「波打たせるもの<コラゲーター>」である。

「波打たせるもの」は、監視対象と監視プログラムの中間に設置するプロセスであり、ログを読み取って監視プログラムのためのデータを生成する。出力はビューアに必要な情報(コラゲーションと呼ぶ)をすべて含んでおり、ストリームのどこにシークしても、イベントの回数などの累積的な値を正しく表示できる。結果として、ビューアはインターフェイスを除けば状態が不要になり、コードの簡略化にも繋がる。

波打たせるものが導入される前のログも読めなければいけないので、ビューアにもビルトイン・コラゲーターが内蔵されている。ビルトイン・コラゲーターは「ログとコラゲーションを読む」「部分的に非互換なコラゲーションを読む」「ログのみを読む」の3つのケースに対応する必要があり、ここがこのエクステンシブル・タングルの力の見せ所になる。

ログとコラゲーションが存在する場合、ビューアは何もする必要がない。そこでコラゲーションの有無で条件分岐するのではなく、runTanglesの二番目の引数にコラゲーションを渡す。こうすると、コラゲーションの一部が読み取れない場合も、必要な部分のみを計算できる。ログのみの場合は空っぽのレコードを渡せばすべて自力で賄う。

前回の記事*2でも触れたように、extensibleのレコードはデシリアライザを非常に簡潔に実装できる。また、顕現せし型を例えばField Maybeとすれば、部分的なデシリアライズも表現できる。エクステンシブル・タングルと組み合わせることで、パフォーマンスを損なわずに拡張性と互換性を持つロジックを記述できるのだ。

エクステンシブル・タングルが必要な場面は非常に限られていると思うが、ここぞというとき有効であることは約束する。他の言語ではなかなか真似できない、Haskellらしい表現力を活かしていきたい。