Software Engineering Lecture s02-1
Menu Menu
Applicative
Functor つまり fmap f では、f の引数は一つだった。複数の引数の場合はどうだろう?
x : List a
y : List b
に、
g : a -> b -> c
を作用させたい。つまり、
g <*> x <*> y : List c
みたいなものが欲しい。
g : a -> ( b -> c )
だったことを思い出すと、
(g <*> x ) <*>' y
と前と後ろの演算子<*>を区別すると、
<*>' : List ( a -> ( b -> c ) ) -> List a -> List ( b -> c )
<*> : List ( b -> c ) -> List b -> List c
であればよい。つまり、
つまり、
<*> : f (a -> b) -> f a -> f b
があって欲しい。ちなみに fmap は、
fmap : (a -> b) -> f a -> f b
で定義されていた。
そういうものを Applicative と言う。つまり、Applicative は以下の型classを持つ。
infixl 4 <*>
class Functor f => Applicative f where
pure :: a -> f a
(<*>) :: f (a -> b) -> f a -> f b
=> で Applicative を定義するには それは Functor である必要があることを示している。
ここで infixl 4 <*> は x <*> y のように infix (中置演算子) として使うことを指定している。
pure は、型 a のものから functor a を作り出す constructor である。その作り方を実装として示す必要があるので、pure を要求している。
infix を単独名で使う場合には (<*>) の様にする。
MyList の Applicative の実装の一つとして、
instance Applicative MyList where
pure _ = Nil
(<*>) Nil x = Nil
(<*>) (Cons f tf) list = myAppend (fmap f list) ( tf <*> list )
pure の _ は無名変数で、その変数を無視することを意味している。
例えば、
(Cons ( * 2 ) ( Cons ( + 5 ) Nil )) <*> ( Cons 5 ( Cons 7 ( Cons 9 Nil )))
を試してみよう。
Applicative と直積
Applicative は直積を保存するMonoidal Functor と関係がある。
g : a -> b -> c
は、
g : ( a x b ) -> cと同じように思える。
newtype と ZipList
appliative は functor と違って unique にならない。MyList に対して、違う実装の Applicative を定義したい。もちろん、Applicative の instance にしたい。 例えば、
instance Applicative MyList where
pure _ = Nil
(<*>) Nil x = Nil
(<*>) (Cons f tf) (Cons x tx) = Cons (f x) ( tf <*> tx )
しかし、MyList のApplicative は既に定義されてしまっている。
この時には、関数名を返るのではなくて、MyList と同じ型で違う名前を持つものを作る。data を使って、もう一度定義してやっても良いが、同じ型というのを強調する、つまり、data の field は一つという制限を持つ newtype を使う。
newtype MyZipList a = MyZipList { getMyList :: MyList a }
Applicative は Functor を要求するので、まず、それを定義する。
instance Functor MyZipList where
fmap f (MyZipList x ) = MyZipList ( fmap f x )
そして、MyZipList のApplicativeを定義しよう。
myZipWith f Nil _ = Nil
myZipWith f (Cons fs ft) (Cons xs xt) = Cons ( f fs xs) ( myZipWith f ft xt )
instance Applicative MyZipList where
pure x = MyZipList Nil
(MyZipList fs) <*> (MyZipList xs) = MyZipList (myZipWith ($) fs xs)
これを MyZipList (Cons ( * 2 ) ( Cons ( + 5 ) Nil )) <*> MyZipList ( Cons 5 ( Cons 7 ( Cons 9 Nil ))) というように使うが、印字できない。getMyList を使って結果を確認しよう。(印字できないのは newtype には derived を付けられないため)
MyList をメタデータと考えてみる
Haskellの関数は通常は一つの値しか返さない。複数の可能な値をMyListとして返す多値関数を考えよう。
let b0 = Cons True ( Cons False Nil )
TrueとFalseは、Haskellに内蔵されている Bool 型 である。Bool型には not 、||、&& が使える。
not は fmap で
let b1 = fmap not b0
などと書ける。
b0 に True と||を取りたいとする。
let b2 = fmap (|| True) b0
などと書ける。
b0 に b1 と||を取りたいとする。
let b3 = fmap (\x -> fmap (\y -> x || y) b1) b0
悪くはないのだが、結果は二重になったMyList になってしまっている。これを一重に展開した方が良い。
flatMyList Nil = Nil
flatMyList (Cons Nil t) = flatMyList t
flatMyList (Cons (Cons h t1) t) = Cons h ( flatMyList (Cons t1 t ) )
これは、
flatMyList :: MyList (MyList a) -> MyList a
という型を持っている。
重複を取り除いた方が良いが、ここでは気にしない。この組合せを多値関数の||だと定義する。
let myListOr b0 b1 = flatMyList ( fmap (\x -> fmap (\y -> x || y) b1) b0 )
これの型は、
myListOr :: MyList Bool -> MyList Bool -> MyList Bool
となっている。
つまり、b0が元々多値関数で、b1とOrを取るいうの多値関数と合成を作ると、MyListが二重になってしまうので、それを一重にするという手順になる。
MyList Bool と
BoolからMyList boolを返す関数を受け取り
MyList Bool
を返すというものが望ましい。
MyList Bool -> (Bool -> MyList Bool ) -> MyList Bool
という型のものが欲しい。一般的には、
MyList a -> (a -> MyList b ) -> MyList b
という形になる。この二つの引数を x と f としよう。
まず、x は MyList a なので、fmap f x すると、MyList ( MyList b ) が得られる。これを flatMyList を使って MyList b にすればよい。
これをまとめると
(>>=) : MyList a -> (a -> MyList b ) -> MyList b
(>>=) x f = flatMyList ( fmap f x )
となる。
b0 >>= ( \x -> fmap (\y -> x || y ) b1 )
の用に使うことができる。
一つしか値を返さない普通の関数は、Cons を一つ付けてやればMyListになる。
return :: a -> m a
return x = Cons x Nil
これらを一般的な型classにしたものが Monad である。
f1 b0 b1 = b0 >>= ( \x -> fmap (\y -> x || y ) b1 )
は、
f2 b0 b1 = do
x <- b0
fmap (\y -> x || y ) b1
と書く構文が Haskell に用意されている。
Monad
class Applicative m => Monad m where
(>>=) :: m a -> (a -> m b) -> m b
return :: a -> m a
というように定義されている。Monad は Applicative であることが要求されているので、Applicative は Functor でもあるから、fmap も実装する必要がある。
ここでは、エラーを返すのに用いる Maybe を自分で定義してみよう。
data MyMaybe a = MyNothing
| MyJust a
deriving (Show, Eq)
例えば、
mydiv x 0 = MyNothing
mydiv x y = MyJust (x / y)
というように使う。
x1 = mydiv 10 2
x2 = mydiv 10 0
まず、Functorにするために fmap を定義しよう。
import Control.Monad
import Control.Applicative
instance Functor MyMaybe where
fmap f MyNothing = MyNothing
fmap f (MyJust x) = MyJust (f x)
次は Applicative
instance Applicative MyMaybe where
pure x = MyJust x
(<*>) MyNothing x = MyNothing
(<*>) (MyJust f) MyNothing = MyNothing
(<*>) (MyJust f) (MyJust x) = MyJust (f x)
pure x = MyJust x は、pure = MyJust と書いても良い。
(<*>) (MyJust f) m = fmap f m
としても良い。
Monad の return は、Applicative の pure と同じものにする。
instance Monad MyMaybe where
return x = MyJust x
(>>=) MyNothing f = MyNothing
(>>=) (MyJust x) k = k x
とする。k の型は a -> MyMaybe b なので、MyMaybeを返す関数である。
x8' x = (fmap (* 10) x ) >>= (\x' -> return x')
のように使うことができる。これを、
x8 x = do
x' <- fmap (* 10) x
return x'
という構文で書くことになっている。これは、MyMaybeな値に10をかけて、それをMyMaybeとして返すというつもり。
MyNothing を x8 に食わせると、MyNothingが返ってくる。コードには return とあるので、MyJust が返りそうであるが、そうはならない。
x8 も x9 も MyMaybe が出てこない。つまり、このコードは、MyMaybe 以外の Monad でもつかるコードになっている。
return は Monad を返すわけだが、自分でMonadを作って返しても良い。
x9' x = x >>= (\x' -> mydiv 10 x')
これを、
x9' x = do
x' <- x
mydiv 10 x'
と書く。Monad な x から普通の値を取り出して、それを使って Monad を生成して返すというつもりになっている。
関数の組み合わせ
List の tail を
let t2 = tail tailとして、tail を二回働かせることはできるだろうか。これは、エラーになる。
<interactive>:123:12:
Couldn't match expected type `[a0]' with actual type `[a1] -> [a1]'
In the first argument of `t', namely `t'
t をちゃんと関数として呼び出すには、
t (t x)
という形にする必要がある。
let t2 = \x -> t (t x)とすれば良い。これで、
t2 "abcde"を実行すると、"cde" が返るはずである。
さらに、t を引数にすると、
let x2 = \t x -> t (t x)1引数関数を受け取って二回関数適用(apply)する関数ができる。
x2 tail "abcde"を試してみよう。これは、
tail (tail "abcde")と同じ。
let x2 f = f f ではダメである。何故か?
関数を二つ取って、それを順番に適用する関数を作ろう。
let comp x y = \z -> x (y z)あるいは、
let comp x y z = x (y z)これは、(.) として、infixとして定義されている。(.) と comp が同じ型を持つことを確認せよ。
let apply f x = f xとすると関数の適用を関数にすることができる。これは、($)として infix で定義されている。
(Cons ( * 2 ) ( Cons ( + 5 ) Nil )) <*> ( Cons 5 ( Cons 7 ( Cons 9 Nil )))
を
( Cons ( * 2 ) $ Cons ( + 5 ) $ Nil ) <*> ( Cons 5 $ Cons 7 $ Cons 9 $ Nil )
のように書くことができる。括弧の数が減る利点がある。
遅延評価
Prelude> let c = getChar
c :: IO Char
Prelude> c
g'g'
it :: Char
Prelude> let b = c
b :: IO Char
Prelude> b
k'k'
it :: Char
getChar を代入した時点では、文字入力は要求されない。
c を表示しようとした時点で要求される。
再帰的な処理
変数の値を関数中で変えることができないので、 while 文などは、再帰で置き換える。例えば、Ruby の fibonacci
fib n # write Fibonacci series up to n
result = []
a, b = 0, 1
while b < n do
result.push(b)
a, b = b, a+b
end
return result
end
は、以下のようになる。 ループで使う変数をすべて引数にしてしまうのが簡単。
fib n = fib1 0 1 n
fib1 a b n =
if b < n then
(b : fib1 b (a + b) n)
else []
:l fib.hs
*Main> fib 10
[1,1,2,3,5,8]
fact.hs
逆順のリストを作る
こういう方法でリストを作ると、一番先に入れたものが先頭に来る。逆順のリストを再帰で作るには、最初に [] を引数で渡してしまうと良い。
rev x = rev1 x []
rev1 [] x = x
rev1 (x:xs) y = rev1 xs (x:y)
異なる決まった値の入力を複数の関数で選択するのは、パターン、あるいはルールと呼ばれる。ここではリストの終了と cons pair を選択している。
rev2 n =
if n==[] then
[]
else
(rev2 (tail n)) ++ [head n]
この方法だと ++ を n 回繰り返すことになる。
rev1 は、
rev3 n t =
if n==[] then
t
else
rev3 (tail n) ((head n) : t)
と書いても同じ。(この方が普通っぽい?)
無限リスト
inc 0 = []
inc n = n : inc (n + 1)
inc 1 は、普通止まらない。これは無限リストを表している。でも、Haskell では必要とされる分しか計算されない。
take1 0 x = []
take1 n (x:xs) = x : take1 (n-1) xs
というのを作り、
*Main> take 10 (inc 1)
[1,2,3,4,5,6,7,8,9,10]
というように使うことができる。
Tree
data を使ってを作ろう。List は同じ型の要素しか持てない。入れ子になった List を作ることはできない。そこで、入れ子を作れる Node を定義する。Node は 値を持つLeaf か 二つの Node を持つかどちらかと考える。
data Nodes a = Node (Nodes a) (Nodes a)
| Leaf a
deriving (Show)
| がどちらかというのを表している。
deriving (Show)を使うと、表示できるようになる。a はList でも使われていた型変数である。
*Main> let a = Leaf 1
*Main> a
Leaf 1
*Main> let b = Node a a
*Main> b
Node (Leaf 1) (Leaf 1)
*Main> let x = Node (Node (Leaf 1) (Leaf 2)) (Leaf 3)
このように入れ子構造を作ることができる。
flatten n = case n of
Node s t -> (flatten s)++(flatten t)
Leaf v -> [v]
この関数を使うことにより、
*Main> x
Node (Node (Leaf 1) (Leaf 2)) (Leaf 3)
*Main> flatten x
[1,2,3]
と平坦にすることができる。