[初心者向け] Haskellで型クラスのインスタンス定義に型制約を含める

はじめに

PFDSの演習でHaskellでの実装方法がわからずに悩んでいたことをhaskell-jpで質問したら一瞬で解決したので基本的な内容ですが記事にしてみました。

やりたかったこと

以下のような型クラス Heapがあるとします。

class Heap h where
  insert :: (Ord a) => h a -> a > h a
  empty :: (Ord a) => h a
  isEmpty :: h a -> Bool
  merge :: (Ord a) => h a -> h a -> h a

そのインスタンスをラップするADTを考えます。

-- 任意のヒープをラップして別のヒープを構成したい
-- HWはHeapWrapperの略
data HW h a = Node a (h a) | Empty

またHWもまたHeapとします。

instance Heap HW where

問題

ここで２つの問題があります。

1. HWのカインドは(* → *) → * → *であり期待されているカインド* → *と異なる
2. HWでラップするのはHeapである必要がある

インスタンスに型制約をつける

上記の問題には以下のようにインスタンス定義に型クラス制約を含めることで対応できます。

instance Heap h => Heap (HW h) where

これによってインスタンスにはHeapを実装するカインド*→*である型が必要であることが示せます。

謝辞

型クラス制約を含めることができることはhaskell-jpのslackワークスペースで教えていただきました。mod_poppo さん、ありがとうございました！！