型チェックされた空ではない文字列
Type-checked non-empty strings (exploring-better-ways.bellroy.com)
要約
この記事は、Haskellにおける「型チェックされた空ではない文字列」の作成に焦点を当てたHaskellコアンです。GHCのRequiredTypeArgumentsを活用し、型レベルで空文字列を検出し、コンパイル時にカスタムエラーメッセージを生成する技術を紹介しています。このアプローチにより、既存のTemplateHaskellによる実装を数千箇所置き換え、大規模なパッケージのビルド時間を約10%改善した具体的な効果が示されています。また、このテクニックを正のNatural数など他の型レベルの検証にも応用できる可能性を探っています。
全文翻訳
Haskell koan: 型チェックされた空でない文字列
この記事はHaskellのkoan(公案)です。背景と動機については後述しますが、ここでは私たちが採用し、気に入っている、あまり一般的ではない小さなテクニックを共有することを目的としています。これはブログのネタにぴったりです。
要するに、型チェックされた空でない文字列コンストラクタを作成し、数千もの同等の TemplateHaskell の呼び出しを置き換えたところ、多くの呼び出しを行っていた大規模でデータ量の多いパッケージでビルド時間が約10%改善されました。
before, after, invalidBefore, invalidAfter :: NonEmptyText
before = $$(NonEmptyText.make "hello")
after = NonEmptyText.make "hello"
invalidBefore = $$(NonEmptyText.make "") -- ⇝ スプライス評価中にエラー...
invalidAfter = NonEmptyText.make "" -- ⇝ 型エラー: 空でない文字列が必要です
無効な状態を表現不可能にすることは、Bellroyのソフトウェアにおける中心的な設計目標です。この点を念頭に、私たちが頻繁に利用する(そして大量にある)テキストデータのための型として NonEmptyText があります。これは文字通り、この型の値は少なくとも1文字を持つ文字列であることを意味します。
このテクニックは、過去15年ほどのGHC機能の収束の結果です。特に、GHC 9.10で導入されたRequiredTypeArgumentsにより、型レベルの文字列リテラルを値のように関数に渡すことができます。型レベルで空文字列を見た場合に、"Expected a non-empty string" のようなカスタム型エラーメッセージを投げることができます。以下に例を示します。
type family IsNonEmptySymbol symbol :: Constraint where
IsNonEmptySymbol "" = Unsatisfiable (Text "Expected a non-empty string")
IsNonEmptySymbol _ = (()::Constraint) -- 空の制約は常に満たされる
-- 注: RequiredTypeArguments を使用しない以前の構文:
-- make :: forall symbol. IsNonEmptySymbol symbol => NonEmptyText
-- 使用例: `make @"hello!"`
make :: forall symbol -> (IsNonEmptySymbol symbol) => NonEmptyText
make symbol = NonEmptyText (fromString (symbolVal (Proxy :: Proxy symbol)))
test :: NonEmptyText
test = make "hello!"
適切な LANGUAGE 拡張機能を使用すると、これは実際に機能します。これには UndecidableInstances が必要ですが、それ自体は有害ではありません。ただし、何が起こりうるかの可能性を開いてしまいます1。
さらに、IsNonEmptySymbol は型ファミリーであるため、通常の型クラス制約のように直接使用することはできません。例えば、Dict にパッケージ化したり、Data.SOP.hcfoldMap のような関数で使用したりすることはできません。通常の型クラスのように「インスタンスを要求する」ことはできませんが、制約を返す点は似ています。
このトリックの最終ステップは、IsNonEmptySymbol を型クラスとして記述することです。
class IsNonEmptySymbol symbol
instance {-# OVERLAPPING #-} Unsatisfiable (Text "Expected a non-empty string") => IsNonEmptySymbol ""
instance IsNonEmptySymbol a
-- make: 上記と同じ
make :: forall symbol -> (IsNonEmptySymbol symbol) => NonEmptyText
make symbol = NonEmptyText (fromString (symbolVal (Proxy :: Proxy symbol)))
GHCが空文字列を与えられた IsNonEmptySymbol 制約を解決する際に、_ => instance IsNonEmptySymbol "" と instance IsNonEmptySymbol a の両方を見つけます。もし OVERLAPPING プラグマを省略した場合、GHCはどちらのインスタンスを選択すべきか分からず、重複する可能性について不平を言うでしょう。これは、重複するインスタンスが存在するのが、私たちが禁止したい、入力が "" の場合だけなので、問題ありません。
したがって、ここでの OVERLAPPING プラグマの効果は、GHCが私たちが「望む」インスタンス、つまりカスタム型エラーを持つインスタンスを選択することです。そのインスタンスは、空でない文字列が必要であったことをユーザーに通知するカスタムエラーメッセージを発生させます。
影響
私たちの内部の bellroy-data パッケージ(既知の貨物・配送業者、会計システム、製品データ、税コードなどの情報を含む)には、$$(NonEmptyText.makeTH _) のような数千ものTHスプライスがありました。RequiredTypeArgument アプローチに移行したことで、そのパッケージのコンパイル時間が約10%短縮されました。
このトリックを適用できる類似ケース
(ほぼ)全く同じコードを再利用して、与えられた Natural が正であることを検証し、型チェックされた Positive コンストラクタを作成できます。一般的に、このテクニックは、型レベルの述語を定義できるあらゆる型に使用できます。
ここから、例えば型レベルの文字列解析を使用して、URIを構築するための型安全なターム構文を定義できると想像できるかもしれません。それは機能しますが、GHCのデフォルトの還元制限である20にすぐにぶつかるでしょう。n文字長の文字列に対するO(n)の型レベルバリデーターは、20回の「還元」(つまり解析)ステップのハードキャップがあり、解析は20文字を超えることはできません。これは、解析ステップ自体が制限にカウントされていないと仮定した場合です。
一般的に、非自明なアルゴリズムも型ファミリーで表現するのは困難です。例えば、let バインディングを書き込んだり、case のような構文でパターンマッチングを行ったりする方法はありません。どちらかが必要な場合は、追加の型引数とヘルパー型ファミリーの組み合わせで表現する必要があります。また、上記の IsNonEmptySymbol クラスのように、型クラスとして機能させるためには、ある程度の配線が必要です。
それにもかかわらず、ここまで読んだあなたは、それがどのようなものになるかに興味があるかもしれません。どうぞ🪄、DynamoDBテーブル名の型レベル解析をご覧ください。
{-# LANGUAGE DataKinds #-}
{-# LANGUAGE QuantifiedConstraints #-}
{-# LANGUAGE RequiredTypeArguments #-}
{-# LANGUAGE TypeFamilies #-}
{-# LANGUAGE UndecidableInstances #-}
import Data.Proxy
import Data.String (fromString)
import Data.Text (Text)
import Data.Type.Bool qualified as Bool
import GHC.TypeError
import GHC.TypeLits
-- | 有効なDynamoDBテーブル名は正規表現 /^[a-zA-Z_.-]{3,255}$/ に一致する必要があります
newtype TableName = TableName Text
deriving (Show)
make :: forall name -> (IsValidTableName name) => TableName
make name = TableName (fromString (symbolVal (Proxy :: Proxy name)))
ここまでは順調です。しかし、無効な文字列をすべて列挙するには時間がかかります。上記の IsNonEmptySymbol のような方法ではなく、アルゴリズム的なアプローチが必要です。上記と同様に、これを Type -> Constraint の型クラスにカプセル化したいと考えています。ここで使用するアプローチは、型ファミリーを使用して内部型クラスの解決を指示することです。したがって、このアプローチは単項型クラス(望ましい)として機能し、プログラマーにカスタム型エラーメッセージを表示します(素晴らしい)。
class (KnownSymbol a) => IsValidTableName a
instance (KnownSymbol a, IsValidTableName__ validity a) => IsValidTableName a
-- | わかりやすいエラーメッセージを生成するラッパークラス
--
-- `wasValid` パラメータは `IsValidTableName__` 型ファミリーによって計算されます。
-- その後、GHCをノーオペレーションインスタンス(成功)または
-- ある程度情報量の多いエラーを発生させるインスタンスに誘導できます。
class (IsValidTableName__ a ~ wasValid) => IsValidTableName_ (wasValid :: Bool) a
instance (IsValidTableName__ a ~ 'True) => IsValidTableName_ 'True a
instance (Unsatisfiable ('Text "Encountered invalid TableName")) => IsValidTableName_ 'False a
ここで、IsValidTableName__ 型ファミリーを実際に実装する必要があります。これは IsValidTableName__ (input :: Symbol) :: Bool のような形になります。
type IsValidTableName__ text = IsValidTableName_go 0 'Nothing (UnconsSymbol text)
-- IsValidTableName__ の内部ループ
type family IsValidTableName_go (len :: Nat) (invalidLastChar :: Maybe Char) (unconsResult :: Maybe (Char, Symbol)) :: Bool where
IsValidTableName_go len 'Nothing ('Just '(x, xs)) = IsValidTableName_go (len + 1) (InvalidTableChar x) (UnconsSymbol xs)
IsValidTableName_go len 'Nothing _ = (3 <=? len) Bool.&& (len <=? 255)
IsValidTableName_go len ('Just invalidChar) _ = 'False
-- 個々の文字の有効性をチェックします
type family InvalidTableChar (ch :: Char) :: Maybe Char where
InvalidTableChar ch = Bool.If (IsValidTableChar ch) 'Nothing ('Just ch)
type family IsValidTableChar (ch :: Char) :: Bool where
IsValidTableChar '-' = 'True
IsValidTableChar '_' = 'True
IsValidTableChar '.' = 'True
IsValidTableChar ch =
('a' <=? ch Bool.&& ch <=? 'z')
Bool.|| ('A' <=? ch Bool.&& ch <=? 'Z')
Bool.|| ('0' <=? ch Bool.&& ch <=? '9')
最後に、これを実際に使用できます。
valid, invalid, invalid2 :: TableName
valid = make "hello-bellroy123"
invalid = make "no" -- エラー! "Encountered invalid TableName"
invalid2 = make "tablename!!" -- エラー! "Encountered invalid TableName"
結論
singletons-th パッケージを使用して、実際のタームレベルの関数(IsValidTableName 関数など)を昇格させることができますが、ここでのポイントは、それが実際にどのように機能するかを示すことです。
Dependent Haskellへの避けられない進歩があり、それはすべてのメジャーなGHCリリースで着実に現実化に近づいています。IdrisやLeanのような言語は今日それを持っていますが、良くも悪くも、Haskellはこの分野で最も普及しており、慣性のある言語です。GHC開発者の皆さん、続けてください!🙂
フッター
- Dennis Gosnell は
UndecidableInstancesを詳細に説明し、それが非常に危険なユースケースを詳述した素晴らしいブログ記事を書いています。 ↩