かとじゅんの技術日誌

技術の話をするところ

Scalazを使ってMaybeモナドを自作してみる(前編)

Play or Scala Advent Calendar 2012の 12/21日の記事です。

モナドを理解するために、Haskellでモナドを作ってみたのですが、Scalaz*1でもMaybeモナドを作ってみようと思い試した結果を報告します。

MyOptionを定義する

例のごとくMaybe型を定義します。 Haskellより冗長だけどまぁこんな感じで書けます。

sealed trait MyOption[+T]
case object MyNone extends MyOption[Nothing]
case class MySome[T](value: T) extends MyOption[T]

Functor型クラスの実装

Scalazでは次のように実装します。implicit objectですね。

object MyOption {
  implicit object Functor extends Functor[MyOption] {
    def map[A, B](fa: MyOption[A])(f: A => B): MyOption[B] = {
      fa match {
        case MySome(v) => MySome(f(v))
        case MyNone => MyNone
      }
    }
  }
}

利用する時はこんな感じ。*2 op1にmapメソッドがないけど呼べるのは、FunctorOpsのおかげですね*3

object Main extends App {
  val op1: MyOption[Int] = MySome(1)
  println(op1.map(_ + 1))
}

Applicative型クラスの実装

Functor型クラスの強化版である、Applicative*4型クラスの実装です。

強化版なのでFunctorの機能はそのまま使えます。pointメソッドはaを保持するMySomeを返します。 apメソッドはちょっと難しいですが、MyOptionに通常の値と、MyOptionに関数が格納されていて、その関数に値を適用した結果をMySomeに格納します。

object MyOption {
  implicit object Applicative extends Applicative[MyOption] {

    def point[A](a: => A): MyOption[A] = MySome(a)

    def ap[A, B](fa: => MyOption[A])(f: => MyOption[A => B]): MyOption[B] = {
      (f, fa) match {
        case (MySome(l), MySome(r)) => MySome(l(r))
        case _ => MyNone
      }
    }
  }
}

利用例を見た方が早いですね。op1は値が格納されていて、op2は引数に1を加算して戻り値で返す関数が格納されています。 op3は二つの引数を加算する関数ですね。 r1の例では、<*>を使って関数と値を適用しています。MySomeから値を取り出すことなく。これは便利!

r2の例では値を格納するMySome同士をop3に適用して加算しています。

他にもメソッドあるので試してみるといいですね!

object Main extends App {
  val op1: MyOption[Int] = MySome(1)
  val op2: MyOption[Int => Int] = MySome((_:Int) + 1)
  val op3 = (_:Int) + (_:Int)

  println(op1.map(_ + 1))

  val r1 = op1 <*> op2
  println(r1) // MySome(2)

  val r2 = (op1 <**> op1)(op3)
  println(r2) // MySome(2)

}

Applicativeにはmapメソッドの実装はないのですが、次のようにpointとapで実装できてしまうようです。

override def map[A, B](fa: F[A])(f: A => B): F[B] =
    ap(fa)(point(f))

ということで、Scalazを使えばHaskellの型クラスの種類を一通り実現できそうです。 後編でMonoidとMonadを実装します*5

*1:Scalaz7です

*2:型アノテーションを記述しないとコンパイルエラーになるのね…

*3:気になる人はpackage objectであるsyntaxあたり参照。ここも参考にするとよい → http://d.hatena.ne.jp/xuwei/20121217/1355687398

*4:Applicativeと略していますが、Applicative Functorが正式名のようです

*5:後編はScalaz Advent Calendarで、22日でお願い!

Maybeを自作してみる(Monad編 その2)

do式でのモナドの記述方法について簡単にまとめる。

Some 1 >>= \x -> Some(x+2)

をdo式に書き直すと

apply = do 
    a <- Some 1
    Some $ a + 2

Monadにはreturnがあるのでそれに書き換える。

apply = do 
    a <- return 1 :: Option Int
    return $ a + 2

関数の引数にOptionを受け取る場合はこんな感じ。

apply :: Option Int -> Option Int
apply op = do
    a <- op
    return $ a + 1

まぁ、これだけの説明だと書き方が違うだけ何がいいかよくわからないので、引数が入れ子のOption型でその内部の値を取り出し二乗しOption型で返す場合を考えてみる。

case ofでの実装は次のとおり。>>=の時に説明したようにNoneケースを記述するのがだるい。

square :: (Option (Option Int)) -> Option Int
square x = case x of
    None -> None
    Some n -> case n of
        None -> None
        Some m -> Some $ m * m

次は>>=を使って書いてみる。Noneのケースは記述しなくてよくなったが、入れ子が見通しを悪くしている。

square :: (Option (Option Int)) -> Option Int
square x = x >>= (\a -> a >>= (\b -> Some $ b * b))

ちなみに括弧なしでも記述できます。

square :: (Option (Option Int)) -> Option Int
square x = x >>= \a -> a >>= \b -> Some $ b * b

読みづらいw

square x = x >>= (\a ->
           a >>= (\b ->
           Some $ b * b))

すごいH本にも書いある例のように改行してみたけど、やっぱり見づらい。

さて、do式で書いてみる。おお、これはシンプルになった。というかラムダ式が消えた。

square :: (Option (Option Int)) -> Option Int
square x = do
           a <- x
           b <- a
           return $ b * b

という訳で、Monadに対応したデータ型ならdo式が使えるみたい。これは便利。

ここから蛇足ですが、Scalaでも>>=相当のメソッドがあります。flatMapです。

def square(op : Option[Option[Int]]) : Option[Int] = {
  op.flatMap{ a =>
    a.flatMap{ b =>
      Some(b * b)
    }
  }
}

そして、do式相当に使えるのがfor式です。

def square(op : Option[Option[Int]]) : Option[Int] = {
  for {
    a <- op
    b <- a
  } yield { b * b }
}

Maybeを自作してみる(Monad編 その1)

Monadを調べていると、モナモナ言いたくなりますね!

さて、OptionをMonad対応する例を書いてみます。

Monad型クラスは次のような定義になっています。returnと>>=を実装せいということらしい。

class Monad m where

    return :: a -> m a

    (>>=) :: m a -> (a -> m b) -> m b

    (>>) :: m a -> m b -> m b
    x >> y = x >>= \_ -> y

    fail :: String -> m a
    fail msg = error msg

return関数はApplicative Functorのpureと同等の処理でよいらしいので、値コンストラクタを指定します。 >>=*1はOptionと、Someの値を引数にとりOptionを返す関数を受け取り、Optionを返します。 >>は問答無用で>>の右側に指定された値を返す関数を適用します。 コードは次のとおり。

import Control.Monad

data Option a = None | Some a deriving (Show)

instance Functor Option where
  fmap f (Some x) = Some (f x)
  fmap f None = None

instance Monad Option where
  return = Some
  None >>= f = None
  Some x >>= f = f x
  fail _ = None

apply = let
            m1 = None >>= \x -> Some(x+1)
            m2 = Some 1 >>= \x -> Some(x+2)
            m3 = Some 1 >> None
            m4 = Some 1 >> Some(2)
            m5 = Some 1 >>= \x -> Some(x+2) >>= \y -> Some(y+3)
            m6 = Some 1 >> None >>= \y -> Some(y+1)
            m7 = (Some (Some 1)) >>= fmap (+2)
         in
            [m1, m2, m3, m4, m5, m6, m7]

main = mapM print apply

結果はこれ

None
Some 3
None
Some 2
Some 6
None
Some 3

この>>=関数は、Noneの時はNoneを返し、Someの時はf xを返します。

apply関数内のm1はNoneなので関数は適用されずにNone。m2は別の値を持つSomeに変換される。m3は問答無用でNoneに変換される。m4も問答無用で Some(2)に変換される。m6は関数呼び出しが連なっています。m7は途中でNoneに変換されるので2つ目の関数は適用されずにNoneに変換される。

Some 1 >>= \x -> Some(x+2) >>= \y -> Some(y+3)

このように>>=をつなげて使って、Someの場合だけのコードを記述できるというのがシンプルになっていいですね。これをcase ofで記述するNoneの場合のコードも記述しないといけないわけですから。

*1:バインドと呼ぶ

Maybeを自作してみる(Monoid編その2)

前回の続きから、Maybeの中身がMonoidだった場合の型クラスの実装は次のとおり。

import Data.Monoid

data Option a = None | Some a
                deriving (Eq, Ord, Read, Show)

instance (Monoid a) => Monoid (Option a) where
  mempty = None
  None `mappend` any = any
  any `mappend` None = any
  (Some x) `mappend` (Some y) = Some (x `mappend` y)

main = print $ Some (Sum 1) `mappend` Some (Sum 2)

SumはMonoidです。実行するとこんな感じになる。

Some (Sum {getSum = 3})

次はMaybeの中身がMonoidじゃなかった場合の実装を考えてみたけど、GHCのソースみた方がはやいのでFirst, Lastを調べてみました。

newtype First a = First { getFirst :: Maybe a }
        deriving (Eq, Ord, Read, Show)

instance Monoid (First a) where
        mempty = First Nothing
        r@(First (Just _)) `mappend` _ = r
        First Nothing `mappend` r = r

newtype Last a = Last { getLast :: Maybe a }
        deriving (Eq, Ord, Read, Show)

instance Monoid (Last a) where
        mempty = Last Nothing
        _ `mappend` r@(Last (Just _)) = r
        r `mappend` Last Nothing = r

ほほー、MaybeをFirstやLastでラップして新しい型を定義していますね。そしてそれぞれに対応したMonoid型クラスのインスタンスを定義しています。Firstのmappendの実装では、Justである最初の値を返しています。Lastは逆にJustである最後の値を返します。

実装をまねるので面白くないですが、、、とりあえずこんな感じ。

newtype FirstOp a = FirstOp { getFirst :: Option a }
        deriving (Eq, Ord, Read, Show)

instance Monoid (FirstOp a) where
        mempty = FirstOp None
        r@(FirstOp (Some _)) `mappend` _ = r
        FirstOp None `mappend` r = r

newtype LastOp a = LastOp { getLast :: Option a }
        deriving (Eq, Ord, Read, Show)

instance Monoid (LastOp a) where
        mempty = LastOp None
        _ `mappend` r@(LastOp (Some _)) = r
        r `mappend` LastOp None = r

使い方の例はこんな感じ。

*Main> print $ FirstOp (Some 1) `mappend` FirstOp (Some 2)
FirstOp {getFirst = Some 1}
*Main> print $ LastOp (Some 1) `mappend` LastOp (Some 2)
LastOp {getFirst = Some 2}

Maybeの中身がMonoidじゃない場合はなんとかしてmappendを振るまいを定義しないといけないけど、それをFirstやLastというコンテナによってどうmappendするか決めているってだけですな。ストラテジパターンに似てるなぁ。この仕組の有益性をぜんぜん理解できていないですが、ぜんぜん難しくないよね!!

というわけで、次はMonadですよ。

Maybeを自作してみる(Monoid編)

今回は自作したMaybe用のMonoid型クラスの実装を作ってみます。

Monoidって何ってさっぱりわからないので、型クラスの定義を見てみます。

class Monoid m where
  mempty :: m
  mappend :: m -> m -> m
  mconcat :: [m] -> m
  mconcat = foldr mappend mempty

mconcatはデフォルト実装があるようなので、memptyとmappendを実装する感じかな。memptyはそのMonoidの単位元を表す。mappendは二項演算子で同じ型の引数を二つ取り、同じ型の値を返す関数です。*1

MaybeのMonoidはちょっと難しいので先にリストのMonoid実装を見てみる。

instance Monoid [a] where
  mempty = []
  mappend = (++)

早速試す。

Prelude> import Data.Monoid
Prelude Data.Monoid> [1..3] `mappend` [4..6]
[1,2,3,4,5,6]
Prelude Data.Monoid> "hoge" `mappend` mempty
"hoge"
Prelude Data.Monoid> mconcat [[1..3], [4..6]]
[1,2,3,4,5,6]

最後のmconcat [[1..3], [4..6]]は、mconcatのデフォルト実装を見ればわかるけど、foldr (++) [] [[1..3],[4..6]]と同じ意味になります。

前置き長くなったけど、自作したMaybeにもMonoid対応。コードは次のとおり。

import Data.Monoid
import Control.Applicative

data Option a = None | Some a
                deriving (Eq, Ord, Read, Show)

instance Functor Option where
  fmap f (Some x) = Some (f x)
  fmap f None = None

instance Applicative Option where
  pure = Some
  None <*> _ = None
  Some f <*> other = fmap f other

instance Num a => Monoid (Option a) where
  mempty = None
  None `mappend` o = o
  o `mappend` None = o
  (Some x) `mappend` (Some y) = Some (x + y)

getOrElse :: Option a -> a -> a
getOrElse None v = v
getOrElse (Some x) _ = x

main = do
          let op1 = Some (1) `mappend` Some (2)
          let op2 = None `mappend` Some (2)
          let op3 = Some (1) `mappend` None
          let op4 = Some (1) `mappend` None `mappend` Some (2)
          print (op1, op2, op3, op4)

とりあえず型引数aをNumにしました。

instance Num a => Monoid (Option a) where

memptyはNoneを返します。

None `mappend` o = o
o `mappend` None = o

oはSomeしかないのでそれを返します。

(Some x) `mappend` (Some y) = Some (x + y)

aがNumの場合はx + yができる。

ということで一応できたけど、Num以外は対応できていないので、そろそろGHCのソース見ないと無理感。

xuwei_kさんに教えてもらったのでソース読んでみる。

まず "そのまま" ってやつどうなっているのか。

instance Monoid a => Monoid (Maybe a) where
  mempty = Nothing
  Nothing `mappend` m = m
  m `mappend` Nothing = m
  Just m1 `mappend` Just m2 = Just (m1 `mappend` m2)

おおお、型引数であるaがNumとかじゃなく、それ自体がMonoidであるとしていますね。であれば、Just (m1 `mappend` m2)と記述できますな。なるほど。

というわけで、同じように書き換えると次のとおり。

instance Monoid a => Monoid (Option a) where
  mempty = None
  None `mappend` o = o
  o `mappend` None = o
  (Some x) `mappend` (Some y) = Some (x `mappend` y)

とりあえず、長くなったので今回はこのへんで。

車輪の再発明は学習用途にはうってつけですね!

*1:memptyのように引数をとらない関数は多相定数というらしい。

ページング用データに対応したFunctorを実装してみる

連続投稿ですが、すごいH本を読みながら、ふとアイデアが湧いてきたのでHaskellコードを書きなぐってみた。

すごいHaskellたのしく学ぼう!

すごいHaskellたのしく学ぼう!

Functorは写像を作るための型クラス。写像とは単なるコピーではなく、何からの変換処理を意味するのですが、そのFunctorの題材としてなんかよいものないかなーと考えていたのですが、ページング処理でよく使う"ページ"をFunctorにすると便利じゃないか!と思ったので考えてみた。コードは次のとおり。

data Page a = EmptyPage |
              DefinedPage {
                    items :: [a],
                    pageNo :: Int,
                    offset :: Int,
                    total :: Int
              } deriving Show


prev :: Page a -> Maybe Int
prev EmptyPage = Nothing
prev (DefinedPage _ p _ _) = if (p -1 > -1)
                             then Just $ p - 1
                             else Nothing
next :: Page a -> Maybe Int
next EmptyPage = Nothing
next (DefinedPage i p o t) = if (o + length i < t)
                             then Just $ p + 1
                             else Nothing

instance Functor Page where
  fmap f EmptyPage = EmptyPage
  fmap f (DefinedPage i p o t) = DefinedPage {
                                    items = map f i,
                                    pageNo = p,
                                    offset = o,
                                    total = t
                                 }

main = do
        let defined = DefinedPage{ items = [1, 2, 3], pageNo = 1, offset = 0, total = 10 }
        let empty = EmptyPage
        let fmapPage1 = fmap (+1) defined
        let fmapPage2 = fmap (+1) empty
        putStrLn $ show(fmapPage1) ++ ", prev = " ++ show(prev fmapPage1) ++ ", next = " ++ show(next fmapPage1)
        putStrLn $ show(fmapPage2) ++ ", prev = " ++ show(prev fmapPage2) ++ ", next = " ++ show(next fmapPage2)

ざっと解説。 Pageは型引数を一つ取るページを表す独自データ型です。EmptyPageは空のページを表す。DefinedPageにはページ内のデータを表すitems, ページ番号のpageNo, オフセットのoffset, 全件数のtotalの属性を持っています。prev関数とnext関数はそのページの前後のページ番号を返します。

Page用のFunctor型クラスのインスタンス(実装)を定義。EmptyPageが来た時はEmptyPageを返し、DefinedPageの時は関数であるfをitemsにmapしその結果を保持する新たなDefinedPageを返します。

このFunctorインスタンスのおかげで、

*Main> fmap (+1) EmptyPage
EmptyPage

*Main> fmap (+1) DefinedPage { items = [1,2,3], pageNo = 1, offset = 1, total = 10 }
DefinedPage {items = [2,3,4], pageNo = 1, offset = 1, total = 10}

が可能になります。これは便利すぎる! というわけで、main部分の処理では、DefinedPageやEmptyPageを気にせずにfmapやってます。(mainの処理を関数に切り出したいな…)

Maybeを自作してみる(Applicative編)

Maybeの自作ですが、前回に引き続きApplicative型クラスの実装を追加してみました。 コードは次のとおり。

import Control.Applicative

data Option a = None | Some a
                deriving (Eq, Show)

instance Functor Option where
  fmap f (Some x) = Some (f x)
  fmap f None = None

instance Applicative Option where
  pure = Some
  None <*> _ = None
  Some f <*> other = fmap f other

getOrElse :: Option a -> a -> a
getOrElse None v = v
getOrElse (Some x) _ = x

main = do
          let op1 = Some (*2) <*> Some (2) -- 4
          let op2 = pure (*2) <*> Some (2) -- 4
          let op3 = (*2) <$> Some (2) -- 4
          let op4 = Some (*2) <*> None -- None
          let op5 = None <*> Some (2) :: Option Int -- None
          let op6 = (+) <$> Some (1) <*> Some (2) -- 3
          print (op1, op2, op3, op4, op5, op6)

Applicativeの定義は次のとおり。(Functor f) =>はfはFunctorだよと制約を宣言しているらしい。んで、pureと<*>関数を実装するだけらしい。

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

op1はSome f <*> other = fmap f otherの実装が読めればさほど難しくない。op2もだいたい想像つく。

op3とop2は意味は同じだけ記述形式が違う。

pure f <*> x = fmap f x 

という法則があるらしく、pure (*2) <*> Some (2)fmap (*2) Some (2)に書き換えれるらしい。

pure (+) <*> Just 1 <*> Just 1

なら

fmap (+) (Just 1) <*> Just 1

に書き換えれる。fmap f xはよく使うのでApplicativeでは

f <$> x = fmap f x

と定義されているので、

(+) <$> Just 1 <*> Just 1

このように書くんだそうだ。

リストやIOもApplicativeなんですが、とりあえずこんなもんで。

追記:

let op5 = None <*> Some (2) :: Option Int

の部分の、:: Option Int の記述。これは型アノテーションかな? None <*> anyの場合は型推論がきかないそうで、こういう記述しないといけないらしい。ゆろよろせんせー ご指摘ありがとうございました。