matchable解説

最近、matchableというライブラリーを Hackageに上げました。この記事では、matchableが何をするライブラリーなのか・なぜ作ったのかに ついて解説します。

matchableって何？

matchableは、その名の通りMatchableという型クラスを提供するライブラリーです。 そのMatchableとは何かと言うと、ドキュメントをご覧ください。

では解説記事にならないので、解説します。といってもMatchableは大して複雑な型クラスではありません。 その定義であるソースコードを見たほうが早いでしょう。

class (Eq1 t, Functor t) => Matchable t where
  zipMatch :: t a -> t b -> Maybe (t (a,b))
  zipMatch = zipMatchWith (curry Just)

  zipMatchWith :: (a -> b -> Maybe c) -> t a -> t b -> Maybe (t c)

Matchable tにおけるtはMaybeやリスト[]のようなコンテナです。 また、Matchableは、zipMatchとzipMatchWithという2つのメソッドを持つクラスです。それぞれ、次のような関数です。

• zipMatchは、2つのコンテナta :: t a と tb :: t bを取り、もしこれらが全く同じ「かたち」をしていれば、 対応する各要素をペアにした新しいコンテナtab :: t (a,b)を返します。 ただし、taとtbが全く同じ「かたち」でなければ、zipMatchは失敗します。

  成功/失敗はMaybeで表されます。成功すればJust tabが、失敗すればNothingが返り値になるということです。

  具体例をあげると、リスト型[]の場合、zipMatchは 次のような動作をします。

  • 2つの引数ta, tbの長さが同じなら、Just (zip ta tb)を返す
  • そうでなければ、Nothingを返す

  >>> zipMatch [1, 2, 3] ['a', 'b', 'c']
  Just [(1,'a'),(2,'b'),(3,'c')]
  >>> zipMatch [1, 2, 3] ['a', 'b']
  Nothing

  さて、『コンテナが全く同じ「かたち」をしていれば』という表現をさっき使いましたが、これでは少しあいまいです。 なので、“Functor則”や”Monoid則”のように、Matchableのインスタンスが満たすべき”Matchable則”があります。

  Matchable則

  zipMatch ta tb = Just tab が成立する ⇔
  　　あるtabが存在して、ta = fmap fst tab かつ tb = fmap snd tabが成り立つ

  さもなくば、zipMatch ta tb = Nothing である

• zipMatchに対するzipMatchWithは、zipに対するzipWithのようなものです。ただし、 zipMatchWithが引数に取る関数はa -> b -> Maybe cです。この関数は、残り2つの引数として 渡されたコンテナta, tbの対応する各要素に対して適用されますが、この関数がNothingを 返すと、zipMatchWith全体がNothingを返します。

  実際、ドキュメントでは次の等式が成り立つことを要求しました。

  zipMatchWith f ta tb = zipMatch ta tb >>= traverse (uncurry f)

  これまた例をリスト型[]で示すなら、次のようになります。

  >>> let f x y = if x >= y then Just (x - y) else Nothing
  >>> zipMatchWith f [1,2,3] [0,1,2]
  Just [1,1,1]
  >>> zipMatchWith f [1,2,3] [2,2,3]
  Nothing

  zipMatchWith f [1,2,3] [2,2,3]では、2つのリストは同じ長さですが、最初の要素で f 1 2 = Nothing なので全体としてもNothingになっています。

  省略しますが、zipMatchWithにもzipMatchと同じように満たすべき法則があります。

なぜMatchableが必要なのか？

私がMatchableが必要だと感じたのは、自分で簡単なプログラミング言語を実装しているときでした。 パターンマッチングの実装を考え始め、次のようなコードを書き始めました。

data Value = IntVal Int
           | NullVal
           | ObjectVal ClassName [Value]

data Pattern = IntPat Int
             | NullPat
             | ObjectPat ClassName [Pattern]
             | VarPat VarName

そしてふと思ったのです。明らかに同じことを繰り返し書いている。どうにか簡潔に書けないかと。

data ValueF a = IntF Int
              | NullF
              | ObjectF ClassName [a]

type Value = Fix ValueF
type Pattern = Free ValueF VarName

patternMatch :: Pattern -> Value -> Maybe [(VarName, Value)]
patternMatch = {- 省略 -}

「これでイケルじゃん！」と思いました。次の関数を実装しようと考えるまでは。

-- | 一般化したパターンマッチ
patternMatch :: (???) => Free f a -> Fix f -> Maybe [(a, Fix f)]
patternMatch (Pure a) value         = Just [(a, value)]
patternMatch (Free fPat) (Fix fVal) =
  if 一番外側がマッチする fPat fVal
    then fmap fold . sequenceA $ zipWithみたいな関数 patternMatch fPat fVal
    else Nothing

一番外側がマッチする :: (Eq1 f) => f a -> f b -> Bool
一番外側がマッチする = liftEq (\_ _ -> True)

ここでつまづきました。いろいろなライブラリーを漁ってみても、既存の型クラスに

zipWithみたいな関数 :: (a -> b -> c) -> f a -> f b -> f c

を適切に実装できそうなものは思い当たりませんでした。 また、このzipWithみたいな関数は、前提条件として一番外側がマッチするがTrueである引数に対してしか定義できないという問題もありました。

そこで、「zipMatch :: f a -> f b -> Maybe (f (a,b))があったらいいなー」となったわけです。 その後、zipMatchの満たすべき性質についていろいろ考えた結果、このMatchableができました。

さらなる応用：ユニフィケーション

また、Matchableが既存のライブラリーに存在しないか調査する過程で、unification-fdというライブラリーを発見しました。そこにあったのは、

data UTerm t v = UVar !v
               | UTerm !(t (UTerm t v))

class Traversable t => Unifiable t where
    zipMatch :: t a -> t a -> Maybe (t (Either a (a, a))) 

unify :: (...ちょっと複雑な制約, 一部 Unifiable t を含む...)	 
      => UTerm t v	 
      -> UTerm t v	 
      -> em m (UTerm t v)

という非常によく似た型クラスUnifiableでした。これに触発されて、 Matchableを使ったユニフィケーションの例も書いてみました。

実はいらない！？

実は、zipMatchは既存の型クラスの組み合わせで実装できたのです。

import Data.Functor.Classes (Eq1(..))
import Data.Foldable
import Control.Monad.State

zipMatch :: (Traversable f, Eq1 f) => f a -> f b -> Maybe (f (a,b))
zipMatch fa fb | liftEq (\_ _ -> True) fa fb = Just (unsafeZip fa fb)
               | otherwise                   = Nothing

unsafeZip :: (Traversable f) => f a -> f b -> f (a,b)
unsafeZip fa fb = evalState (traverse step fa) (toList fb)
  where
    step :: a -> State [b] (a,b)
    step a = state $ \bs ->
      [] -> error "differently shaped arguments"
      (b:bs) -> ((a,b),bs)

しかし、この実装は（難癖に近いかもしれませんが）少しだけ問題があります。

1. Eq1には法則が無いため、本当に安全にunsafeZipが呼び出せる保証がないこと。 Matchableは新しい型クラスなので、必要なMatchable則を定義できる。
2. liftEqとtraverseとtoListで、faとfbをそれぞれ2回走査しなければいけないこと。 ほとんどの場合zipMatchは1回の走査で実装できる。

このうち2.はあまり関係ない(Matchableのインスタンスは大抵非再帰的な小さい型)のですが、 1.はMatchableをライブラリーとして公開する理由になると考えています。

結論

Matchableという型クラスを提供するmatchableライブラリーを作ったので、紹介しました。 Matchableはパターンマッチやユニフィケーションを実装するのに便利です。