Haskellの代数的データ型

多相性の実現

Haskellでは型クラスによってアドホック多相が実現でき、型変数によってパラメータ多相が実現できる。また、部分型付けは型変数に対して型クラス制約を課すことで近しいことが実現できる。個人的な印象では、Haskellの型システムは強い型付けという意味で安全で、静的な強い型付けにも関わらず簡単に多相性を実現できるという意味で高機能だと思う。多相再帰も簡単に書けて便利なことがあった。

アドホック多相は同じ名前の関数を引数の型ごとに使い分ける抽象化。例えばDoubleでもIntegerでも(+)が使える。また、パラメータ多相は型によらない共通の処理を行う抽象化。例えばmapはどの型のリストに対しても使える。部分型付けは (オブジェクト指向言語で) 型の派生関係を利用して、共通して持つ処理を実際の型ごとに使い分ける。Haskellでは完全に同等な機能はないが、型クラス制約を付けた型変数を利用することに近い。また、GHCの存在量化拡張または一般化代数的データ型拡張を利用すれば、部分型付けを実現できる。
ポリモーフィズム - Wikipedia

多相性の実現
型変数を持つ代数的データ型
FunctorとApplicative Functor
MonadとMonad変換子

型変数を持つ代数的データ型

Haskellの代数的データ型では、要素を列挙したり、それぞれの要素に幾つかのフィールドを持たせたりできる。フィールドは再帰的にも定義できる。また、フィールドには名前を付けることもできる。

data (型名) = (値コンストラクタ名(型名と同じでも良い)) (フィールドの型名 ..) | ..
data Type0 = A | B | C
data Type1 = Recursive Integer String Type1 | Terminal
data Type2 = Type2 { filed1 :: Type0, field2 :: Integer -> Integer }

代数的データ型にも型変数を持たせることができて、例えばリストや木のような構造を定義して、中に入っている型に依らない抽象的な処理を記述することができる。

data (型コンストラクタ名) (型変数名 ..) = (値コンストラクタ名) (フィールドの型名(型変数名を含む) ..) | ..
data Tensor a = Tensor [Tensor a] | Elem a deriving (Eq)

instance Show a => Show (Tensor a) where
  show (Elem x) = show x
  show (Tensor []) = "[]"
  show (Tensor xs) = "[" ++ init (concatMap ((++ ",") . show) xs) ++ "]"

instance Functor Tensor where
  fmap f (Elem x) = Elem (f x)
  fmap f (Tensor xs) = Tensor $ map (fmap f) xs

型変数には自分で定義した代数的データ型でも関数でも何の型でも入れられるので、それをコンテナと解釈するか、何かの文脈と解釈するか、可能性は自由に広がっている。型変数を持つデータ型は、その型変数に入るHaskellの任意の型に対して、ラベルを付けているとも言える。そこで、こうしたラベル付きの型に対して、関数を適用してラベル付きのまま計算していく方法を考えてみたい。まず取り上げたいのが、そのデータ型の中身に関数を適用できるFunctorと、そのデータ型の中に入っている関数に、そのデータ型の中に入っている引数を適用していけるApplicativeという型クラス。(型クラスは、そのインスタンスとしたデータ型が指定の関数を持つことを要請してくれる。)

FunctorとApplicative Functor

データ型の中身に関数を適用して、別のものに写せることを要請する型クラスがFunctor。Functorのインスタンスはfmap関数を実装し、その関手としての意味からFunctor則を満たすことが要請されている。(fmap id == id (恒等変換で不変)、fmap f . fmap g == fmap (f . g) (関数合成の保存) Data.Functor)

class Functor f where
  fmap :: (a -> b) -> f a -> f b

cite #source

例としてTypeというデータ型を定義し、TypeをFunctorのインスタンスにし、fmapを実装してみる。

data Type a = Content a | Empty deriving (Show)

instance Functor Type where
  fmap f (Content x) = Content (f x)
  fmap _ Empty = Empty

> fmap (^2) (Content 7)
=> Content 49
> fmap (*2) Empty
=> Empty

Typeに入っていても、Haskellの普通の型 (ここではTypeの外の世界の型という意味。Typeも普通の型。) の値であるかのように、Typeの中身にfmapで普通の関数を適用できるようになった。いったい何が嬉しいのかわからないかもしれないが、例えばリストはFunctorでリストのfmapはmapである。そのデータ型の意味に応じて適切に定義されたfmapによって、データ型の中身を普通のHaskellの関数で写せることは役に立ちそうだ。

Functorでは、fmapに渡す関数はTypeの中から1つの引数しか取れないが、複数のTypeの中身を引数としてあたえたい時はどうしたら良いだろうか。Typeの中に関数を入れて、次に渡されたTypeの中身を部分適用した関数を、Typeに入れて返せるような仕組みを作れば良さそうである。こうした仕組みはApplicativeという型クラスが要請している。(ApplicativeのインスタンスはFunctorのインスタンスで、Applicative則を満たす必要がある。Control.Applicative)

class Functor f => Applicative f where
  pure :: a -> f a
  (<*>) :: f (a -> b) -> f a -> f b

cite #source

instance Applicative Type where
  pure = Content
  Content f <*> Content x = Content (f x)
  _ <*> _ = Empty

> pure (^) <*> Content 2 <*> Content 4
=> Content 16
> mod <$> Content 14 <*> Content 3
=> Content 2

pureは引数をTypeの中に入れ、<*>はTypeの中に入っている関数に次のTypeの中に入っている値を適用する。<$>はfmapの別名。Typeの中に部分適用された関数が入れば続けて適用を繰り返せる。Typeの中に入っていても、Haskellの普通の型の値のように、複数の引数を取る普通の関数に適用できるようになった。

FunctorやApplicative Functorはデータ型の中身を、そのデータ型が意味する文脈に応じて、普通の関数で操作するという意味合いが強いと思うが、Haskellの代数的データ型の表現力はそれに留まらず、文脈を付与されたデータ型に対して、その文脈において意味のある計算を自由に定義し、これを連ねていくことを記述できる。

MonadとMonad変換子

MonadのインスタンスはApplicativeのインスタンスであって、Monad則をみたす必要がある。(Control.Monad)

class Applicative m => Monad m where
  (>>=) :: forall a b. m a -> (a -> m b) -> m b
  
  (>>) :: forall a b. m a -> m b -> m b
  m >> k = m >>= \_ -> k
  
  return :: a -> m a
  return = pure

cite #source

forall a bはaとbが型変数であることを明示的に宣言しているがここでは省略できる。Monadが要請するのはbindと呼ばれる演算子>>=の実装で、Monadの中身を取り出し、あたえられた関数 (a -> m b) に適用し、Monadとして返す。>>=にあたえる関数はMonadアクションと呼ばれている。>>は左の値を利用しないbindで (文脈の処理は行われる)、returnはpureと同じもの (つまり値を中に入れるだけで、文脈は操作しない)。

これだけでは何のことかわからないかもしれないが、Monadは元々はプログラムを純粋な関数によって構成しながらも、文脈 (状態) を伴った計算をすっきり記述するために導入されている。これを実現しようとした時、まずは文脈を引数で渡して行くことが考えられるが、常に引数で持ち回すのは煩雑だし、文脈を明示的に意識せず表の計算や計算の構成に集中したいこともある。そこで文脈を型に入れて、背景で自動的に処理される2つ目の計算ラインに移してしまったのがMonadだ。

FunctorやApplicativeとの違いは、Monadでは>>=によって背景で自動的に文脈の処理が行われることや、その時、アクションが表の計算を利用しながら文脈に働きかけることができる点にある。適切なアクションによる値の操作と文脈の供給を用意しておけば、文脈の処理はMonadにまかせることができ、値の計算や、アクションの組み合わせという計算の構成に集中することができる。つまり、>>=を定義しMonadアクションを用意することは、Monadの文脈を処理する計算を構成するためのDSLを用意することに近しい。

Typeを拡張して、Emptyが出てこない限り、計算の点数を数えるような計算という意味をTypeに追加してみる。

data Type a = Content a Int | Empty deriving (Show)

instance Functor Type where
  fmap f (Content x n) = Content (f x) n
  fmap _ Empty = Empty

instance Applicative Type where
  pure x = Content x 0
  (Content f n) <*> (Content x m) = Content (f x) (n + m)
  _ <*> _ = Empty

instance Monad Type where
  Empty >>= f = Empty
  (Content x n) >>= f = case f x of
                          Empty -> Empty
                          (Content y m) -> Content y (n + m)

このMonadでの文脈の処理として、>>=で中身を取り出しアクションにあたえて、その後ろで点数を足し合わせていく。>>では点数の加算のみが行われる。また、1度でもEmptyが出て来たら、常にEmptyになる。

アクションを定義して、計算しながら掛け算の数を数えてみる。

square :: Num a => a -> Type a
square n = Content (n * n) 1

fact :: Integral a => a -> Type a
fact n = Content (f n) (fromIntegral n - 1)
  where f m | m < 2 = 1
            | otherwise = m * f (m - 1)

> square 2 >>= fact >>= square
=> Content 576 5

addCount :: Int -> Type ()
addCount n = Content () n

calc :: Type Integer
calc = do
  x <- square 2
  y <- fact x
  addCount 3
  square y

> calc
=> Content 576 8

do記法はMonad計算を直感的に書くための構文糖衣。各式はそのMonadの型で、>>で結ばれていると見なせる。また、Monadの中身は<-で取り出して変数に束縛できる。 (その場合は、>>=で値を取り出し、無名のアクションの引数として変数に束縛しているような状態。) もっとたくさんのアクションが用意され、calcのdo記法の中身のような計算が大規模になって複雑になっても、点数の計算と失敗の記録はTypeが後ろで自動的に行ってくれるので、このMonadを使う人は、ただ値の計算に集中することができる。

こんな風に、自分のデータ型にあたえたい計算の意味に応じて、適切に>>=とアクションを定義すれば、文脈に沿った処理が簡単に書けるようになる。関数合成演算子 (.) のように、Monad計算におけるアクションの合成を行う演算子 (f >=> g = \x -> f x >>= g) を考えると、Monad則は、>=>による計算の合成において、returnが左単位元かつ右単位元となることと、>=>が結合法則をみたすことを意味している。(つまり、returnは文脈を変更せず、連続する>=>はどの2項から計算を合成しても結果が変わらない必要がある。) このように考えると、Monadをつくることは、単位元を持ち結合法則を満たす新しい計算の体系をつくっているとも捉えられる。自然数の掛け算で類推するなら、自然数がMonadアクションで、*が>=> 、1がreturnになる。

Haskellのライブラリには、状態のStateやReaderやWriter、入出力のIO、失敗可能性のMaybeやEither、DSLの構文木処理のFreeなど便利なMonadが色々用意されていて、必要に応じてMonad変換子で複数を組み合わせて使うこともできる。

import Control.Monad.Trans.Maybe
import Control.Monad.Trans.Class (lift)
import Control.Monad (guard)
import Text.Read (readMaybe)

readPositiveInteger :: MaybeT IO Integer
readPositiveInteger = do
  l <- lift getLine
  x <- (MaybeT . return) (readMaybe l)
  guard (x > 0)
  lift $ putStrLn "thank you for the correct value!"
  return x

> runMaybeT readPositiveInteger
hello
=> Nothing
> runMaybeT readPositiveInteger
1.0
=> Nothing
> runMaybeT readPositiveInteger
1
thank you for the correct value!
=> Just 1

MaybeTの中にIOが入っているが、MaybeTのdoの中でも、liftを使えば内側のIOの関数を使うことができる。guardは零元を持つ2項演算を抽象化したMonadPlus (零元はmzero、演算はmplus) の関数で、引数がFalseの時、零元になる。MaybeTでの実装では、MaybeT (return Nothing) が入る。ちなみにMonadPlusのApplicative版にAlternativeがあり、また単位元を持つ2項演算を抽象化したMonoid (単位元はmempty、演算はmappend) などもある。特定のMonadに依らない、抽象化されたMonad計算を用意したい時にはこうした型クラスも使える。Monadが便利に使われている身近な例としては、リストの内包表記もリストMonadのdo記法だったりする。Monadを使うと純粋な関数のみでも表現力の高い言語内DSLを作ることができるので、そのうちそうした記事も書いてみたい。

実用的なMonad変換子の使い方についてはこちらの記事がわかりやすかった。
http://dev.stephendiehl.com/hask/#monad-transformers

MonadはHaskellの文法によって特殊な地位をあたえられている訳ではなく (構文糖衣doはあるが) 、こうした記述能力は型変数を持つHaskellの代数的データ型と型クラスの能力によって自然に実現されている。