[PFDS写経]GADTs拡張で型コンストラクタに制約をつける

HaskellではGADTs拡張によって型コンストラタを一般化して定義できます。これを使って二分木のブランチを表すデータ構造に要素が全順序付けできるという制約を定義してみました。

佐々木一洋

2021.07.07

この記事は公開されてから1年以上経過しています。情報が古い可能性がありますので、ご注意ください。

はじめに

７月から期が変わったこともあり、PFDS をHaskellで写経しながら読み進めています。HaskellはすごいH本を斜め読みした程度しか触っていないので写経と言ってもHaskellについて調べながら進めています。

今回はPFDS から「2.2 二分探索木」を読みました。

二分探索木

文中で取り上げられている二分探索木は以下のようなものです。

datatype Tree = E | T of Tree * Elem * Tree

Haskellで素直に書くと以下のようになると思います。

data Tree = E | T Tree a Tree

型パラメータに制約をつけたい

ところで二分探索木の性質を考えた時、上記の型パラメータaは全順序づけされている必要があります。この制約をTreeの定義に含めるにはGADTs(Generalized algebraic datatypes)拡張を使います。これによって通常の関数定義と同様に型コンストラクタTのパラメータaにOrdクラスのインスタンスであるという制約をつけることができます。

{-# LANGUAGE GADTs #-}

data Tree where 
  E :: Tree
  T :: (Ord a) => Tree -> a -> Tree -> Tree

まとめ

GADTs拡張によって二分木の要素を全順序付けられている制約をつけることができました。PFDSの方の進捗は思ったように進みませんが、Haskellの勉強にはなっているので引き続きやっていきます。

参考

*