読者です 読者をやめる 読者になる 読者になる

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

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らしい表現力を活かしていきたい。

割とすぐに始められるextensibleチュートリアル(レコード編)

ごきげんよう諸君。今回はextensibleについて説明しよう。

extensibleはその名の通り、拡張可能なデータ構造を提供するライブラリである。具体的には、型レベルのリストによって特徴づけられるを提供する。非常に残念なことに、GHC 8.0.1ではコンパイラのバグのせいでそもそもライブラリがビルドできない*1。来たる8.0.2では修正されているので、それを待つほかない。

とにかく、ここではの応用技である拡張可能レコードについて紹介する。使い方は簡単だ。まず使いたいフィールド名をスペースで区切ってmkFieldに渡す。

{-# LANGUAGE TemplateHaskell, DataKinds, TypeOperators, FlexibleContexts #-}
{-# OPTIONS_GHC -fno-warn-unticked-promoted-constructors #-}

import Data.Extensible
import Control.Lens hiding ((:>))

mkField "name collective cry"

すると、フィールド名を表す値がTemplate Haskellによって自動生成される。仰々しい型をしているが気にせず先に進もう。

$ stack ghci --package lens --package extensible
> :load tutorial.hs
...
> :t name
name
  :: forall (kind :: BOX)
            (f :: * -> *)
            (p :: * -> * -> *)
            (t :: (Assoc GHC.TypeLits.Symbol kind -> *)
                  -> [Assoc GHC.TypeLits.Symbol kind] -> *)
            (xs :: [Assoc GHC.TypeLits.Symbol kind])
            (h :: kind -> *)
            (v :: kind)
            (n :: Data.Extensible.Internal.Nat).
     (Labelling "name" p, Wrapper h,
      Data.Extensible.Internal.KnownPosition n, Extensible f p t,
      Elaborate "name" (FindAssoc "name" xs) ~ 'Expecting (n ':> v)) =>
     Data.Extensible.Internal.Rig.Optic' p f (t (Field h) xs) (Repr h v)

ここで、動物の名前と、群れの呼び方、ある場合は鳴き声の擬声語を含むデータ型を定義する。

type Animal = Record
  [ "name" :> String
  , "collective" :> String
  , "cry" :> Maybe String
  ]

Recordは、フィールドの名前と型のリストをパラメータとして持つレコードの型だ。名前と型のペアは:>で作る。

Record :: [Assoc k *] -> *
(:>) :: k -> v -> Assoc k v

例としてハトとハクチョウを作ってみよう。 構築の方法はリストと同じと思ってよい。Nilは空のレコードで、(<:)で値を追加する。@=でフィールド名と実際の値を指定する。

-- (@=) :: FieldName k -> v -> Field Identity (k :> v)

-- infix 1 @=

dove :: Animal
dove = name @= "dove"
  <: collective @= "dule"
  <: cry @= Just "coo"
  <: Nil

swan :: Animal
swan = name @= "swan"
  <: collective @= "lamentation"
  <: cry @= Nothing
  <: Nil

作っても使えなければ意味がない、しかし心配はいらない。実は、最初に定義したフィールド名はLensとしても使えるレンズ沼仕様になっているのだ。

> swan ^. name
"swan"

Lensなので当然更新もできる。地上のハクチョウはbankと呼ぶのでそれを反映させてみよう。

> swan & collective .~ "bank"
name @= "swan" <: collective @= "bank" <: cry @= Nothing <: Nil

動物を取り、その集団を表す句を返す関数を定義できる。

collectiveOf :: Animal -> String
collectiveOf a = unwords ["a", a ^. collective, "of", a ^. name ++ "s"]
> collectiveOf dove
"a dule of doves"
> collectiveOf swan
"a lamentation of swans"

collectiveOfAnimal型を引数として取るが、実は以下のように一般化できる。

collectiveOf :: (Associate "name" String s, Associate "collective" String s)
  => Record s -> String

もはや引数はAnimalである必要はない。namecollectiveStringとして持つなら、どんなレコードに対しても使える。これが拡張可能たる所以だ。

一見難解な仕組みに見えるが、実用するうえで必要なのはRecordおよび:>型とmkField@=<:Nilだけであり、決して覚えるのが大変なものではない。同じ名前をどこでも使い回せる、lensとの相性がよいなどの性質があるので、従来のレコードの代わりに使うのも便利だ。

extensibleの拡張可能レコードは、ジェネリックな関数が書きやすいというメリットもある。以下のコードは、JSONのオブジェクトをレコードにするFromJSONインスタンスだ。 これは、GHCのジェネリクスを用いた実装(332行)と比べるとはるかに短い。

{-# LANGUAGE TemplateHaskell, DataKinds, TypeOperators, FlexibleContexts, UndecidableInstances #-}
{-# OPTIONS_GHC -fno-warn-unticked-promoted-constructors #-}

import Data.Extensible
import Control.Lens hiding ((:>))
import Data.Aeson (FromJSON(..), withObject)
import Data.Proxy
import Data.String
import GHC.TypeLits

instance Forall (KeyValue KnownSymbol FromJSON) xs => FromJSON (Record xs) where
  parseJSON = withObject "Object" $ \v -> hgenerateFor (Proxy :: Proxy (KeyValue KnownSymbol FromJSON))
    $ \m -> let k = symbolVal (proxyAssocKey m) in case v ^? ix (fromString k) of
      Just a -> Field . pure <$> parseJSON a
      Nothing -> fail $ "Missing key: " ++ k

ForallhgenerateForがこのインスタンスの要になっている。Forall c xsは、「xsのすべての要素が制約cを満たす」という制約で、この場合、すべてのフィールドについて、名前は型レベル文字列、値の型はFromJSONインスタンスであることを示している。hgenerateForはその制約を用いてレコードを一気に構築する関数だ。

Forall :: (k -> Constraint) -> [k] -> Constraint
hgenerateFor
  :: (Applicative f, Forall c xs) =>
     proxy c
     -> (forall (x :: k). c x => Membership xs x -> f (h x))
     -> f (h :* xs)

Membership xs xxxsの要素であることを表す型である。ここでは、フィールド名をsymbolValproxyAssocKeyStringに変換するために使われている。Field . pureは具体的なフィールド名を指定せずにフィールドを構築する関数である。

> decode <$> fromString <$> getLine :: IO (Maybe Animal)
{"name": "zebra", "collective": "dazzle", "cry": "whoop"}
Just (name @= "zebra" <: collective @= "dazzle" <: cry @= Just "whoop" <: Nil)

リポジトリにはToJSONのインスタンスの例もある。

レコードに関しては、GHCGenericsとは比べ物にならないほど簡潔に汎用的なインスタンスを記述できる。もし自前のクラスについてジェネリックインスタンスを定義したいが、複雑で実装が難しいという場合は、ぜひextensibleを使ってみてほしい。

ここで紹介したのはextensibleの一部に過ぎない。次回は、レコードと対をなす構造、拡張可能ヴァリアントについて紹介したい。

写真の撮り方

物体の発する光や反射した光を結像し、何らかの媒体に記録したものを写真と呼ぶ。カメラと呼ばれる道具には「撮影」という動作が必ず定義されており、撮影によって内部状態に画像を記録できる。内部状態を取り出して処理する(現像)ことで写真が得られる。大抵のカメラには以下のようなパラメータがあり、それらを最適化するのが撮影者の仕事になる。

焦点(Focus)

はっきりとした像を得るには、光学系の焦点をそれに合わせる必要がある。最近のカメラは対象物の距離を測定し、自動で焦点を合わせる(オートフォーカス)機能を持っているものもある。

焦点距離(Focal length)

焦点距離が長いほど像は拡大されて見えるようになる。デバイスの規格に依存して、ヒトの視野に近いと考えられている40度前後の画角を持つような焦点距離が決まり、その焦点距離を持つレンズを標準レンズと呼ぶ。APS-Cの規格のセンサーを持つデジタル一眼レフカメラにおける主流は35mmである。レンズによっては動的に焦点距離を変えられるものもある。

f値(f-ratio)

絞りとも呼ばれる。焦点距離f、レンズの有効口径(無限遠点にある点光源が通過できる光束の直径)を\Phiとおくと、対応するf値Nは以下のように表される。

\displaystyle N = \frac{f}{\Phi}

多くのカメラは有効口径を動的に変える機構を備えている。f値が高いほど、像がはっきりと写る範囲(被写界深度)も大きくなる。

露出時間(Exposure time)

現在を0とする時刻tにおける世界の状態をW(t)とおく。世界の状態にカメラcを適用し、それを定積分することによって画像が得られる。このときの積分する範囲Tが露出時間である。

\displaystyle I = \int_0^{T} c(W(t)) dt

露出時間が長ければ長いほど、世界の状態の変化が画像に表れる。そのため、ものを一定の位置に保つのが難しい生体がカメラを保持する場合、露出時間は10ミリ秒のスケールまで短くする。

ISO感度(Film speed)

ISO感度は理想的にはカメラc内の定数係数であり、ISO感度が2倍ならば、半分の露出時間、もしくは\sqrt{2}倍のf値で同じ明るさの画像が得られる。技術的制約により、ISO感度と画質はトレードオフの関係にある。

露出値(Exposure value)

露出はf値と露出時間によって決まる相対的な光量の尺度である。APEXと呼ばれる体系では露出値E_vを以下のように定義しており、広く使われている。

\displaystyle E_v = log_2 \frac{T}{N^2}

撮影の流れ

ISO感度を簡単に変更できるカメラの場合、以下のようにするとやりやすい。

  • 目的の焦点距離を決め、レンズを取り付ける。
  • 目的の被写界深度を持つよう、f値を決定する。
  • 対象物に焦点を合わせる。
  • 露出時間を決定する。
  • 適切な明るさとなるようにISO感度を決定する。もしISO感度が限界に達した場合、露出時間とf値を見直し、それでも明るすぎる場合は減光フィルターをカメラに取り付けて光量を減らす。暗すぎる場合はあきらめる。
  • レリーズボタンを押して撮影する。

近年ではソフトウェアで現像できることも多い。筆者はAdobe Lightroomを使用している。

  • 色温度コントラスト、明るさなどを調整する。この処理によって情報が失われない、RAWフォーマットと総称される形式をサポートしているカメラが多い。
  • 目的の形式でファイルへ書き出すか、印刷する。

所見

近年のカメラは各パラメータを自動で計算する機能が備わっていることが多いが、目的とする表現が得られないことが多いため、咄嗟の場面でパラメータを気にせずに撮影したいという状況以外は推奨しない。

レリーズボタンにオートフォーカスを統合し、撮影する直前にオートフォーカスするようになっているカメラが多いが、予期せぬほうへ焦点を変えてしまう恐れがあるため、筆者は別のボタンにオートフォーカスをアサインし、レリーズボタンはレリーズボタンとしてのみ機能するように設定している。

まとめ

写真撮影は最適化すべきパラメータが少なく、比較的とっつきやすい。携帯電話などに内蔵された簡易なカメラしか使ったことがない人でも、本記事で触れたようなパラメータについて考えてみれば、本格的な写真撮影をする動機がきっと生まれるはずだ。

今のところ比較的簡単なモナドの作り方

準備

モナドを作るには、どんなモナドを作りたいか考える。モナドは一般に、どのようなアクションが使えるかによって特徴付けられる。その点ではオブジェクト指向におけるインターフェイスとよく似ている。

では、foo :: String -> M Boolbar :: M Intという二種類のアクションを持つモナドを作るとしよう。まず、どんなアクションが使えるかを表すデータ型を定義する。

{-# LANGUAGE GADTs #-}

data MBase x where
    Foo :: String -> MBase Bool
    Bar :: MBase Int

GADT(一般化代数的データ型)の各データコンストラクタがアクションに対応する。GADTsを使ったことがなくても心配してはいけない。引数の型と結果の型に着目しよう。

モナドにする

monad-skeletonをインストールする。

$ stack install monad-skeleton

モジュールをインポートし、先ほどのMBaseを使い、Mを定義する。bone :: t a -> Skeleton t aMBaseの値をMの値にする。

{-# LANGUAGE GADTs #-}

import Control.Monad.Skeleton

data MBase x where
    Foo :: String -> MBase Bool
    Bar :: MBase Int

type M = Skeleton MBase

foo = bone . Foo
bar = bone Bar

Mはもう、モナドになっている。拍子抜けするほど簡単だ。

:t bar >>= foo . show bar >>= foo . show :: Skeleton MBase Bool

モナドを使う

作っても使わなければ意味がない -- 誰か

アクションにdebone :: Skeleton t a -> MonadView t (Skeleton t) aを適用すると、MonadViewというデータ型の値が得られる。

data MonadView t m x where
  Return :: a -> MonadView t m a
  (:>>=) :: t a -> (a -> m b) -> MonadView t m b

Return aはそのアクションが実質的にreturn aであること、t :>>= kは最初に実行すべきアクションがtであることを意味する。ktの結果を渡すと、その次に実行すべきアクションが得られる。これらを使うと、Mを実際に解釈する関数を定義できる。ここでは、fooを「与えられた文字列の長さがある値より短いか判定する」、barを「判定基準を返す」ものとして定義しているが、型さえ合えば実際はなんでもよく、一つのMに対して複数の解釈を与えることさえ可能だ。

runM :: Int -> M a -> a
runM n m = case debone m of
    Foo str :>>= k -> runM n $ k $ length str <= n
    Bar :>>= k -> runM n $ k n
    Return a -> a

monad-skeletonはDSL(ドメイン特化言語)を作るのに適している。何より、簡単に使えるのが売りなので、初心者にもおすすめだ。

runMのような「モナドを解釈する関数」に内部状態を持たせられたら便利なのに、と思う人もいるかもしれない。実はこれにも既に解決法があるので、次の機会に紹介しよう。

GHC 8.0.1/base-4.9.0.0の新機能まとめ

GHC 8.0.1は、最上位の桁が変わるだけあって、かなり新しい機能が追加されている。

base-4.9.0.0

めっちゃインスタンスが増えた

ghc/changelog.md at ghc-8.0 · ghc/ghc · GitHubを参照。あるべきインスタンスが存在することにより、孤児インスタンスを定義する必要がなくなるため、ぐっとストレスが減る。Monoid a => Monad ((,) a)Traversable ZipListなど、いくつかは私がやった。

Semigroup

ついにData.Semigroupが追加された。将来的にはこれはモノイドのスーパークラスになる。この変更によって、よりリーズナブルな定義ができるということも少なくないはずだ。

ベーシックな型が充実

Compose, Product, Sum, NonEmptyなど、決して利用頻度が高くないとはいえ基礎的かつ重要な型が追加された。種多相になっているので型レベルプログラミングフリークにとっても嬉しい。

MonadFail

ついにfailMonadから切り離された。もはやMonadには一片の羞恥もない。

この変更のため、いくつかの警告や言語拡張が追加された*1

Applicativeへの一般化

forever, filterM, mapAndUnzipM, zipWithM, zipWithM_, replicateM, replicateM_, traceM, traceShowMMonadからApplicativeへと一般化された。痒い所に手が届くようになるだろう。しかし、(*>)(>>)より効率の悪い実装になっていると深刻なダメージになりうるため、Applicativeのインスタンスにはより関心を向けなければならない。

ApplicativeDo

ApplicativeDo拡張を有効にすると、以下のコードをf <$> foo <*> barのようにしてくれる。

do
  x <- foo
  y <- bar
  return (f x y)

MonadよりApplicativeのほうが効率のよいような構造(クラシカルFRPにおけるBehaviorなど)では大いに役立つ。

Strict / StrictData

StrictDataを有効にすると、データ型のフィールドにデフォルトで正格フラグが付与される。アプリケーションを書くうえでフィールドを遅延評価させたい場面は少なく、いちいち!(……)と書く手間がなくなるため非常に有用だ。これをずっと待ち焦がれていた。

Strictを有効にすると、さらにありとあらゆる束縛が正格評価になる。やりすぎな気がしなくもないが、案外実用上は問題ないかもしれない。

TypeError

GHC.TypeLitsにGHC.TypeLits.TypeErrorが追加された。type family TypeError (msg :: ErrorMessage) :: kなる型族で、これを使うと型エラーを作れる。型レベルプログラミングがさらに楽しくなるだろう。

OverloadedLabels

IsLabelというクラスが追加された。

class IsLabel (x :: Symbol) a where
  fromLabel :: Proxy# x -> a

OverloadedLabels拡張を有効にすると、#foo(fromLabel @"x" @alpha proxy#) (fromLabel (Proxy :: Proxy "x")のようなもの)の構文糖衣になる。これにより多相なアクセサを定義できる可能性が生まれたが、非常に残念ながら型クラスの性質上van Laarhoven lens(lensパッケージのLens)にはできない。非常に残念だ。

GenericsのMeta

GHC.GenericsMetaというが追加され、型定義のメタデータを表すM1のパラメータとして与えられる。

data Meta = MetaData Symbol Symbol Symbol Bool
          | MetaCons Symbol FixityI Bool
          | MetaSel  (Maybe Symbol)
                     SourceUnpackedness SourceStrictness DecidedStrictness

Genericsでフィールドやコンストラクタ名を扱うのは骨の折れる仕事だが、これのおかげでいくらか楽になるに違いない。

種の同一性

種の同一性がきちんと扱われるようになった。これによりGADTの型レベルへの昇格や、種族の定義が可能になる。

型族のワイルドカード

type family Tail (xs :: [k]) :: [k] where
  Tail (x ': xs) = xs

と書かなければならなかったところを、

type family Tail (xs :: [k]) :: [k] where
  Tail (_ ': xs) = xs

と書けるようになる。ささいなことだが、型レベルプログラミングジャンキーにとってはナイスな改良だ。

単射なる型族

type family F x y = a | a -> x, a -> yのようにして、型族が単射であることをあらかじめ定義できる。これにより、うまく型推論してくれる場面が増える。型レベルプログラミングフィーンドもこれでさらに活躍できる。

コールスタック

ImplicitParams拡張を有効にしたうえで、?callStack :: CallStackという暗黙のパラメータが使えるようになる。しかしこれはいかがなものか……筆者としてはImplicitParameter自体かなり悪いアイデアだと思う。

コンパイル時間

型周りの大きな拡張により、コンパイル時間も追加されたようだ。エスプレッソを抽出したりラテアートを作る余裕もできるだろう。

比を最適化する

二つの負でない実数pqを考える。比\frac{p}{p + q}をある値rに近づけたいといった条件が複数あり、それらを最適化したいとき、どうするのがよいだろうか。

序: 近道の階段

簡単な方法の一つとして考えられるのは、単純に比の差をとり、それらの平方の和を最適化の対象とするというものだ。

\displaystyle \sum_{i}{(\frac{p_i}{p_i + q_i} - r_i)^2}

しかし、これは最適化の結果、しばしばp_iq_iのどちらかが0にぶつかってしまう。これは目的関数として非常にいびつであり、直感的とも言いがたい。

破: バリアフリー

0や1に近い比率は極端であり、望まれていない。境界に近づくほど目的関数が無限大に発散するようにできないだろうか。

そんなときに使えるのがロジットだ。ロジットは0より大きい1未満の実数を任意の実数に写像する関数である。

\displaystyle logit(x) = log(\frac{x}{1-x})

この関数を比に適用することで、極端な比にはそれなりに大きなペナルティが、なめらかでありながらも力強く課されるようになる。

\displaystyle \sum_{i}{\{logit(\frac{p_i}{p_i + q_i}) - logit(r_i)\}^2}

r_i = \frac{s_i}{s_i + t_i}とおくと以下のようにも表せる。

\displaystyle \sum_{i}{\{log(\frac{p_i}{q_i}) - log(\frac{s_i}{t_i})\}^2}

こうすれば、境界を気にすることなく最適化することができる。最適化される変数にとってもこれは心地の良いことだろう。

急: ノーマライゼーション

めでたしめでたし…と言いたいところだが、まだ気になる点はある。目的の比 rがもともと0や1に近ければ、 logit(r)は大きな絶対値を取る。そのため、その比にやたらと敏感になってしまう。差をロジットの導関数 logit'(x) = \frac{1}{x - x^2}で割ってやることで、各比の感度を目的の値にかかわらず一定にできる。

\displaystyle \sum_{i}{\{(r_i - r_i^2)(logit(\frac{p_i}{p_i + q_i}) - logit(r_i))\}^2}

まとめ

本記事では比を最適化するための方法について議論した。この考え方は多かれ少なかれ直感に基づいており、直感にうまく当てはまる表現を見つけることは有用だと感じた。

デシリアライザとスキーマ

盛大に遅れました…

qiita.com

最近思いついたネタで実用性の高そうなものを紹介。

binarycerealのようなライブラリはデータを密にシリアライズするが、その際にフィールド名や型などの情報は失われてしまう。かといってそれらを一つ一つすべて含めるとひどく効率の悪いフォーマットになってしまう。そこで、スキーマを分離できるような仕組みを作れないかと考えて作ったのがこのクラスだ。

{-# LANGUAGE TypeFamilies, ScopedTypeVariables, FlexibleContexts, UndecidableInstances #-}
import Data.Binary

class HasSchema a where
    type Schema a :: *
    toSerializer :: a -> Put
    toDeserializer :: Schema a -> Get a

HasSchemaクラスは、普通にシリアライズするメソッドtoSerializerと、スキーマを使ってデシリアライズするtoDeserializerを持っている。Schemaは型族なのでどんなものでも使える(一般にどうあるべきかよく考えていない)。

instance HasSchema a => HasSchema [a] where
    type Schema [a] = [Schema a]
    toSerializer = mapM toSerializer
    toDeserializer = mapM toDeserializer

同じスキーマの値が連続している場合、以下のTableという型を使うと無駄がない。

newtype Table a = Table (V.Vector a)

instance HasSchema a => HasSchema (Table a) where
    type Schema (Table a) = Schema a
    toSerializer (Table v) = put (V.length v) >> mapM toSerializer v
    toDeserializer sch = get
        >>= \n -> Table <$> V.fromListN n <$> replicateM n (toDeserializer sch)

このSchematicというデータ型はスキーマとデータの対にすぎないが、これで包んでおくことで簡単にHasSchemaの力を引き出せる。

data Schematic a = Schematic !(Schema a) !a

instance (HasSchema a, Binary (Schema a)) => Binary (Schematic a) where
    get = get >>= \sch -> Schematic sch <$> toDeserializer sch
    put (Schematic sch a) = put sch >> toSerializer a

今のところ、社内で使っているレコード型を簡単にシリアライズするために実験的に使っているが、より一般的で面白い使い方があるかもしれない。この記事では、実体のあるHasSchemaインスタンス(instance HasSchema Intなど)は一切定義されていない。どう作っていくかは、これからの課題だ。