うやむやで終わる記事なので事前にご了承ください。

前回のあらすじ

（前回などないので探さなくていいです。）

高カインドデータ型（Higher-kinded Datatypes; HKD）というものがあります。

fumieval.hatenablog.com

簡単に説明すると下記のようなデータ型 D があるとき

data D =
  D { a :: A
    , b :: B
    }

D の代わりに H のようなデータ型を作ると便利という発想です。

data H f =
  H { a :: f A
    , b :: f B
    }

H Identity だと D と同じ意味になりますし、H Maybe だと部分的に（もしくは全部）値が欠けたものを意味します。

HKD をサポートするライブラリーとして barbies がポピュラーです。

hackage.haskell.org

H を D のように使うには Identity をたくさん書くことになりますが barbies の提供する機能を使うと Identity を書く手間が減らせます。

こういうものが用意されているので、

data Bare
data Covered

type family Wear t f a where
  Wear Bare    f a = a
  Wear Covered f a = f a

H を B のように書き換えます。

data B b f =
  B { a :: Wear b f A
    , b :: Wear b f B
    }

このとき B Bare f は D と同じ構造に B Covered f は H と同じ構造になります。

こういうデータ型に対する操作も barbies は提供しています。

class FunctorB (b Covered) => BareB b where
  bstrip :: b Covered Identity -> b Bare Identity
  bcover :: b Bare Identity -> b Covered Identity

ここまでが「前回のあらすじ」です。

重ね着

ここからは「なんかこういうのがほしいな」という発展です。

data L f =
  L { a :: f A
    , d :: f (D f) -- D も HKD
    }

HKD が入れ子になっててもいいじゃない。

経緯としては、抽象構文木（Abstract Syntax Tree; AST）のデータ型を書いていて、位置情報を持つファンクター（例えば WithLocation とする）を f に与えるようにするとすっきりならんかと思いました。

data Expression f
  = Abstract
      { variable :: f Variable
      , expression :: f (Expression f)
      }
  | Application
      { expression1 :: f (Expression f)
      , expression2 :: f (Expression f)
      }

ファイルをパースして構築するときは Expression WithLocation として、テスト時は Expression Identity として使用します。

こうするとノードに付与する追加データと AST 自体の構造とが分離できて嬉しいです。

ここで barbies にあった Wear を使うとこうなります。

data Expression b f
  = Abstract
      { variable :: Wear b f Variable
      , expression :: Wear b f (Expression b f)
      }
  | …

ここで Expression が BareB のインスタンスになるか考えます。

そのためには FunctorB のインスタンスでないといけません。

FunctorB は次のような型クラスです。

class FunctorB b where
  bmap :: (forall a . f a -> g a) -> b f -> b g

Expression に対する bmap を実装してみます。

instance FunctorB (Expression Covered) where
  bmap f (Abstract v e) = Abstract (f v) (_ $ f e)
  bmap f (Application e1 e2) = …

穴 _ の部分の型は g (Expression Covered f) -> g (Expression Covered g) となるはずですが、うーん実装できなさそうです。

入れ子 HKD では bmap の型は Functor g => (forall a. f a -> g a) -> b f -> b g もしくは Functor f => (forall a. f a -> g a) -> b f -> b g となる必要がありそうです。

そんなわけで入れ子 HKD は barbies の提供する FunctorB や BareB とは別の型クラスが必要となります。

さて、ここでリストを考えます。

newtype List x b f = List { unlist :: [Wear b f (x b f)] }

こういうデータ型があると、これに関して bmap を定義できて便利そうです。

同様にタプルについてもこんな Tuple2 を考えると……

newtype Tuple2 x y b f = Tuple2 { untuple2 :: (Wear b f (x b f), Wear b f (y b f)) }

というふうに考えて進めてたんですが、元の型と Wear 版の型との相互変換がいっぱいになったり、List x Bare Identity が [] になってほしくなって型族を使いだしたりして収拾がつかなくなって一旦やめます、というお話です。

なんやそら。

趣味はデバッグ……

重ね着したバービー人形 in Haskell

前回のあらすじ

重ね着