Software Engineering Lecture s02
Menu Menu
Haskell のデータ構造の復習
data を使ってHaskell のデータ構造を定義するがいくつかの意味が重なっている直積 複数のデータを格納する
直和
場合分け
MyList を作ってみる
data MyList a =
Nil
| Cons a (MyList a)
deriving (Show, Eq)
Nil と Cons の二つの場合ががる。Nil と Cons は Constructor つまり、MyList を作る構文
l0 = Nil
l1 = Cons 1 l0
l2 = Cons 2 l1
l3 = Cons 3 l1
などと使う。Cons には二つのデータが格納されて、一つは型a、もう一つはMyList a、つまり再帰的なデータ構造になっている
Cons a (MyList a)Nil 側には何もない。
Cons と Nil はパターンマッチで場合分けする。case文も使える。
myLength Nil = 0
myLength (Cons _ tail) = 1 + ( myLength tail )
append x y =
if x == Nil
then y
else
Cons (myHead x) (append (myTail x) y )
append3 x y = case x of
Nil -> y
(Cons h t) -> Cons h ( append3 t y)
List.hs
Functor
以下では Haskell の内蔵のListを使う。 Nil が []、Cons が::、そして、表示をきれいにしてくれる。List の要素を変換することを考える
[1,2,3] を ["1","2","3"]
にしたい。
to-string :: List a -> List String
to-string [] = []
to-string (h : t) = show h : to-string t
とすれば良い。変換する関数を与えられるようにすると、
f-map :: (a -> b) -> List a -> List b
f-map _ [] = []
f-map f (h : t) = f h : f-map f t
すれば良い。
あるデータ構造f が型aを要素として含むとする。すると、関数 a -> b を使って
fmap :: (a -> b) -> f a -> f b
というのがあると考えられる。これは data構造を作った人が自分で実装する。
fmap を持つデータ型を Functor という。
Functor の型
Functor の型は、型 class を使って以下のように定義される。
class Functor f where
fmap :: (a -> b) -> f a -> f b
この型は、
:t fmapで確認できる。
f a は、型 a に依存した型になる。
Funcotr はデータ構造X a の中身の一つに対して関数 f を適用する。
instance Functor MyList where
fmap _ Nil = Nil
fmap f (Cons h t) = Cons (f h) ( fmap f t )
instance Functor (MyList a) ではないのは何故か?
数字のリストを文字のリストに変更したかったら、
let numList = Cons 1 ( Cons 2 Nil )
fmap show numList
とする。
Functor Law
identity functionid : a -> a id x = xに対しては、
fmap id x = xであるべきだろう。fmap は、そのように実装されて欲しい。
関数の合成 f . g に関しては、
fmap ( f . g ) x = fmap f ( fmap g x ) = ( fmap f . fmap g ) xであるべきだろう。つまり、 何かの型a を含むデータ構造xの型a の部分に関数f を作用させる操作なら、
データ構造xに対してfmap f x は関数f を作用させるように振る舞って欲しい
この二つを Functor Law と呼ぶ。
Haskell の functor では、これを強制することはしない。
問題5.1
MyList と Haskell 内蔵の List が Functor Law を満たすことを確認する。また、それがFunctor Law を満たすことを文章で示せ。
自然変換 (natrural transforamation)
Tree を考えてみよう。
data Tree a = Node (Tree a) (Tree a)
| Leaf a
deriving (Show)
これも List と同じように一つの型変数aを持っている。
これにたいして fmap を定義して Tree を Functor にすることができる。
Tree と List の二つの Functor を定義できた。Tree を depth first にたどって List を作ってみよう。
これは Functor から Functor への変換 flattern になる。この時に、
fmap f (flatten t) と flatten (fmap f t )は同じになって欲しい。これは可換性と呼ばれる。
fmap f
Tree a ---------> Tree b
| |
|flatten a | flatten b
v v
List a ---------> List b
この時に、二つのflatten は別な型 aと b 上で作用している。
この可換性の成立するデータ構造の変換を自然変換と言う。
問題5.2
Functor Law を満たす Tree に対する Functorを実装せよ。Tree から List への自然変換を定義せよ。
この時に、Tree を depth first に変換するものと、bredth irst に変換するものの二種類を示せ。
可換性が成立していることを実例で示せ。
Treeの上の検索
Tree に key と value の直積を格納すると、データベースあるいは hash / 連想配列のように使うことができる。検索を実装したいが、見つからなかった時にどうするかを考える必要がある。それは場合分けになる。これをMaybe というデータ構造で表す。
data MyMaybe a = MyNothing
| MyJust a
deriving (Show, Eq)
MayMaybe.hs
見つかった時には、MyJust a を返し、見つからなかったら MyNothing を返す。
問題5.3
Key と Value の組の型をもつ Tree への insert と lookup を MyMaybe を用いて実装せよ。Monad
さて、Treeから二つの値を検索して、その和を検索したい。lookup t k1 + lookup t k2
と書きたいところだが、値は MyMaybe であり、簡単に足し算できない。つまり、
MyNothing が入っていたら MyNothing を返し、両方とも MyJust だったら足し算した MyJust があると良い。
myAdd :: MyMaybe a -> MyMaybe b -> MayMaybe c
myAdd MyNothing _ = MyNothing
myAdd _ MyNothing = MyNothing
myAdd (MyJust x) (MyJust y) = MyJust (x + y )
myAdd ( lookup t k1 ) ( lookup t k2)
これでも良いのだが、もっと、一般的に
f :: a -> MyMaybe b
g :: b -> MyMaybe c
があった時に fg :: a -> MayMaybe c を作りたい。
x :: a なら f x :: MyMaybe b となる。さらに
fmap g (f x) :: MyMaybe (MyMaybe c)となる。これを
y :: MyMaybe cに変換できればよい。これは、
mu :: kMyMaybe (MyMaybe c) -> MyMaybe cという自然変換になると良い。これと、
eta :: a -> MyMaybe aを持つ型クラスを Monad と言う。
muと eta を持つMyMonad を一般的なFunctor f に対して定義する。
class Functor t => MyMonad t where
eta :: a -> t a
mu :: t ( t a ) -> t a
問題5.4
MyMaybe の mu と eta を実装せよ。
mu と eta が自然変換であることを例示せよ。
Monad の構文
Haskell では
class Monad m where
return :: a -> m a
(>>=) :: m a -> (a->m b) -> m b
に対して
mydiv x 0 = MyNothing
mydiv x y = MyJust (x / y)
x21 = do
x <- mydiv 10 2
do
y <- mydiv 12 0
return $ x + y
のような構文が用意されている。
MyMaybe を Monad の実装として定義し、上の構文が動作することを確認してみよう。
しかし、その前に MayMaybe は Applicative である必要がある。Applicative とは何か?
Applicative
myAdd ( lookup t k1 ) ( lookup t k2)
みたいな記述は do 構文でも少し面倒くさい。
(+) <$> lookup t k1 <*> lookup t k2
とかく方法が用意されている。これは。
((+) <$> lookup t k1 ) <*> lookup t k2
という風に解釈するとする。これは
(<*>) :: ? -> MyMaybe b -> MyMaybe c
(<$>) :: (a -> b -> c) <$> Maybe a -> ?
という形であると整合する。? には何が入ると良いのか。b -> c が? にないとよろしくない。
infixl 4 <*>
class Functor f => Applicative f where
pure :: a -> f a
(<*>) :: f (a -> b) -> f a -> f b
とすると良い。ここで、 <$> は pure と <*> から作る。
MyMaybe の Monad と Applicative を実装する
以下の?を埋めていこう
instance Functor MyMaybe where
fmap f MyNothing = MyNothing
fmap f (MyJust x) = MyJust (f x)
instance Applicative MyMaybe where
pure x = ?
(<*>) x = ?
instance Monad1 MyMaybe where
eta x = ?
mu x = ?
instance Monad MyMaybe where
return x = ?
(>>=) x f = ?
Applicative の動作を確認する
mydiv x 0 = MyNothing
mydiv x y = MyJust (x / y)
x22 = pure (+) <*> MyJust 1 <*> MyJust 2
x23 = (+) <$> MyJust 1 <*> MyJust 2
x24 = pure (+) <*> mydiv 3 1 <*> mydiv 3 0
x25 = pure (+) <*> mydiv 3 1 <*> mydiv 3 2
x26 = (\x y z -> sum [ x , y , z]) <$> mydiv 3 1 <*> mydiv 3 2 <*> mydiv 3 0
問題5.5 おまけ Monoidal Functor
Applicative は直積を保存する Monoidal Functor と関係がある
class MonoidalFunctor t where
unit :: t ()
phi :: ( t a , t a ) -> t ( a , a )
MyMaybe に MonoidalFunctor を定義することができる。
さらに、以下のことが可能である。
Applicative を unit と phi を使って実装する MonoidalFunctor を pure と <*> を使って実装するヒント unit = () なので phi だけ作れば良い。