LoginSignup
19
12

More than 3 years have passed since last update.

@YoshikuniJujo

Freer Effectsが、だいたいわかった: 1. Freeモナドの概要

Last updated at Posted at 2017-09-13

Freer Effectsが、だいたいわかった: 1. Freeモナドの概要

目次

(0). 導入

  1. Freeモナドの概要
    • Freeモナドとは
    • FreeモナドでReaderモナド、Writerモナドを構成する
  2. 存在型(ExistentialQuantification拡張)の解説
  3. 型シノニム族(TypeFamilies拡張)の解説
  4. データ族(TypeFamilies拡張)の解説
  5. 一般化代数データ型(GADTs拡張)の解説
  6. ランクN多相(RankNTypes拡張)の解説
  7. FreeモナドとCoyoneda
    • Coyonedaを使ってみる
    • FreeモナドとCoyonedaを組み合わせる
      • いろいろなモナドを構成する
  8. Freerモナド(Operationalモナド)でいろいろなモナドを構成する
    • FreeモナドとCoyonedaをまとめて、Freerモナドとする
    • Readerモナド
    • Writerモナド
    • 状態モナド
    • エラーモナド
  9. モナドを混ぜ合わせる(閉じた型で)
    • Freerモナドで、状態モナドとエラーモナドを混ぜ合わせる
  10. 存在型による拡張可能なデータ構造(Open Union)
  11. 追加の言語拡張
    1. ScopedTypeVariables拡張
    2. TypeOperators拡張
    3. KindSignatures拡張
    4. DataKinds拡張
    5. ...
  12. モナドを混ぜ合わせる(開いた型で)
    • FreerモナドとOpen Unionを組み合わせる
    • 状態モナドにエラーモナドを追加する
  13. Open Unionを型によって安全にする
  14. Freer Effectsで、IOモナドなどの、既存のモナドを使用する
  15. 関数を保管しておくデータ構造による効率化
  16. いろいろなEffect
    • 関数handleRelayなどを作成する
    • NonDetについて、など

モナドのおさらい

つぎのような関数が定義できるような型mをモナドと呼ぶ。

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

おなじことを、つぎの、みっつの関数でも表現できる。

fmap :: (a -> b) -> m a -> m b
pure :: a -> m a
join :: m (m a) -> m a

このことは、つぎのように示すことができる。

fmap = flip (>>=) . (pure .)
join = (>>= id)

(>>=) = flip $ (join .) . fmap

Freeモナドを理解するうえで、モナドがfmap, pure, joinのみっつで表現されるという側面をおさえておくことも、助けとなるだろう。モナドとは、つぎのような操作ができる文脈mと言える。

  • 値に、文脈をつけることができる (pure :: a -> m a)
  • 文脈のなかの値に、関数を適用できる (fmap :: (a -> b) -> m a -> m b)
  • 二重になった文脈を、一段の文脈にほどくことができる (join :: m (m a) -> m a)

ファンクタからモナドへ

ファンクタとは、つぎのような関数をもつ型fのことである。

fmap :: (a -> b) -> f a -> f b

つまり、モナドとはファンクタであるような型fに、さらにつぎの、ふたつの関数を追加したものである。

pure :: a -> m a
join :: m (m a) -> m a

モナドにできて、ファンクタにできないこと: リストの例

ここで、つぎのような演算子を定義する。

listExample.hs
(>>-) :: Functor f => f a -> (a -> f b) -> f (f b)
(>>-) = flip fmap

ファイルlistExample.hsに定義しておく。モナドのbind関数と比較してみよう。

(>>-) :: Functof f => f a -> (a -> f b) -> f (f b)
(>>=) :: Monad m => m a -> (a -> m b) -> m b

ファンクタのほうの演算子では、文脈が二重になっているのがわかる。ファイルlistExample.hsを読み込んで、つぎのように試してみよう。

> [1, 2] >>= \x -> "abc" >>= \y -> [False, True] >>= \z -> [(x, y, z)]
[(1,'a',False),(1,'a',True),(1,'b',False),(1,'b',True),(1,'c',False),
(1,'c',True),(2,'a',False),(2,'a',True),(2,'b',False),(2,'b',True),
(2,'c',False),(2,'c',True)]
> [1, 2] >>- \x -> "abc" >>- \y -> [False, True] >>- \z -> [(x, y, z)]
[[[[(1,'a',False)],[(1,'a',True)]],[[(1,'b',False)],[(1,'b',True)]],
[[(1,'c',False)],[(1,'c',True)]]],[[[(2,'a',False)],[(2,'a',True)]],
[[(2,'b',False)],[(2,'b',True)]],[[(2,'c',False)],[(2,'c',True)]]]]

ファンクタのほうの演算では、リストがネストしていってしまう。

Freeモナドとは

もとの型がファンクタであれば、それを変換してモナドにすることができるデータ型。つぎのような定義となる。

data Free t a
        = Pure a
        | Join (t (Free t a))

再帰的な定義となっていて、たとえばリストでは、つぎのような値を定義することができる。

Join [Join [Join [Join [Pure True]]]] :: Free [] Bool

Join [...]を何重に入れ子にしても、おなじ型Free [] Boolとして、あつかうことができる。つまり、もとの型によるデータ構造が、何重にネストしてしまったとしても、この型の値に変換することで、ネストのない型として、あつかうことができるということになる。

[[[[True]]]] :: [[[[Bool]]]]
Join [Join [Join [Join [Pure True]]]] :: Free [] Bool

値はネストしても、型はネストしない。このように、値はネストしたままで、関数joinと同様の効果を、得ることができる。

リストの例

リストはファンクタなので、Freeモナドによる変換が可能だ。ここでは、対話環境で表示できるように、リスト専用のデータ型を用意して、それを使ってみよう。つぎのデータ型を定義する。ファイルfreeList.hsを作成し、つぎのように定義しよう。

freeList.hs
data FreeList a
        = PureL a
        | JoinL [FreeList a]
        deriving Show

整数をたし算、または、かけ算で、つぎつぎにつないでいったときの、すべての組み合わせをもとめることを考える。つぎのような関数を演算子(>>=)でつないでいけばいい。ファイルfreeList.hsに、つぎの関数を追加しよう。

freeList.hs
mulAdd :: Integer -> Integer -> [Integer]
mulAdd y x = [x + y, x * y]

まずは、ふつうに、リストモナドとして試してみる。

> :load freeList.hs
> return 5 >>= mulAdd 3 >>= mulAdd 8 >>= mulAdd 11
[27,176,75,704,34,253,131,1320]

これは、つぎのような計算をしたということだ。

[
5 + 3 + 8 + 11, (5 + 3 + 8) * 11, (5 + 3) * 8 + 11, (5 + 3) * 8 * 11,
5 * 3 + 8 + 11, (5 * 3 + 8) * 11, 5 * 3 * 8 + 11, 5 * 3 * 8 * 11
]

おなじことを、Freeモナドで試してみる。まずは、データ型FreeListをFunctorクラスのインスタンスにする。

freeList.hs
instance Functor FreeList where
        f `fmap` PureL x = PureL $ f x
        f `fmap` JoinL xs = JoinL $ fmap f `map` xs

PureLに対しては、なかの値xに関数fを適用すればいい。JoinLに対しては、関数fmapをリストの要素すべてに、再帰的に、適用している。おなじように、Applicativeクラスのインスタンスにする。

freeList.hs
instance Applicative FreeList where
        pure = PureL
        PureL f <*> mx = f <$> mx
        JoinL fs <*> mx = JoinL $ (<*> mx) `map` fs

クラス関数の定義の、うえの2行については、だいたいわかるだろう。3行目はリストfsの要素に対して(<*> mx)を、再帰的に、適用している。Monadクラスのインスタンスにする。

freeList.hs
instance Monad FreeList where
    PureL x >>= f = f x
    JoinL xs >>= f = JoinL $ (f =<<) `map` xs

(>>=)を再帰的に適用している。ここで、リストという構造に対しては、関数mapというファンクタ的な演算を、使用していることに注意しよう。それによって、リストはネストしてしまう。そのリストのネストはJoinLによって、型としては解消されている。

リストモナドについて定義したのと、おなじ関数を型FreeListについても、定義してみよう。

freeList.hs
mulAddF :: Integer -> Integer -> FreeList Integer
mulAddF y x = JoinL [PureL $ x + y, PureL $ x * y]

対話環境で試してみる。

> :reload
> return 5 >>= mulAddF 3 >>= mulAddF 8 >>= mulAddF 11
JoinL [JoinL [JoinL [PureL 27,PureL 176],JoinL [PureL 75,PureL 704]],
JoinL[JoinL [PureL 34, PureL 253],JoinL[ PureL 131,PureL 1320]]]
> :type it
it :: FreeList Integer

値としては、おこなった操作の手順を反映した、ネストしたリストとなっているが、型としてはネストのない型となっている。

FreeList型からリスト型の値にするには、リストに対する演算子(=<<)である関数concatMapを使えばいい。

freeList.hs
runList :: FreeList a -> [a]
runList (PureL x) = [x]
runList (JoinL xs) = runList `concatMap` xs

試してみよう。

> :reload
> return 5 >>= mulAddF 3 >>= mulAddF 8 >>= mulAddF 11
JoinL [JoinL [JoinL [PureL 27,PureL 176],JoinL [PureL 75,PureL 704]],
JoinL[JoinL [PureL 34, PureL 253],JoinL[ PureL 131,PureL 1320]]]
> runList it
[27,176,75,704,34,253,131,1320]

IOの例

入出力の例をみてみよう。freeIO.hsを作成し、つぎのように定義する。

freeIO.hs
data FreeIO a
        = PureIO a
        | JoinIO (IO (FreeIO a))

ファンクタ、アプリカティブ、モナドの定義を追加する。

freeIO.hs
instance Functor FreeIO where
        f `fmap` PureIO x = PureIO $ f x
        f `fmap` JoinIO m = JoinIO $ fmap f <$> m

instance Applicative FreeIO where
        pure = PureIO
        PureIO f <*> mx = f <$> mx
        JoinIO mf <*> mx = JoinIO $ (<*> mx) <$> mf

instance Monad FreeIO where
        PureIO x >>= f = f x
        JoinIO mx >>= f = JoinIO $ (f =<<) <$> mx

入出力の例として、引数の整数を表示して、それをカウントアップしてかえす機械を考える。まずは、通常のIOについて試す。ファイルfreeIO.hsに、つぎの関数を追加する。

freeIO.hs
count :: Integer -> IO Integer
count n = putStrLn ("n = " ++ show n) >> return (n + 1)

対話環境で試してみよう。

> :load freeIO.hs
> count 8 >>= count >>= count >>= count
n = 8
n = 9
n = 10
n = 11
12

おなじ機械のFreeIO型バージョンを書く。

freeIO.hs
countF :: Integer -> FreeIO Integer
countF n = JoinIO $ putStrLn ("n = " ++ show n) >> return (PureIO $ n + 1)

FreeIO型の値は、そのままでは表示も実行もできないので、関数runIOを定義する。ここでは、LambdaCase拡張を使っている。ファイルの先頭に{-# LANGUAGE LambdaCase #-}を追加しよう。

freeIO.hs
runIO :: FreeIO a -> IO a
runIO = \case
        PureIO x -> return x
        JoinIO m -> m >>= runIO

対話環境で試してみよう。

> :reload
> action = countF 8 >>= countF >>= countF >>= countF
> runIO action
n = 8
n = 9
n = 10
n = 11
12

FreeIO型の値はIO型の値が入れ子になっている状態であり、それぞれの入出力はまだ合成されていない。それを示すために、関数runWithを定義する。

freeIO.hs
runWith :: FreeIO a -> IO b -> IO a
runWith fio act = case fio of
        PureIO x -> return x
        JoinIO m -> act >> m >>= (`runWith` act)

対話環境で試す。

> :reload
> action = countF 8 >>= countF >>= countF >>= countF
> action `runWith` putStrLn "hello"
hello
n = 8
hello
n = 9
hello
n = 10
hello
n = 11
12

FreeIO型では、それぞれの入出力がばらばらで保管されているため、このように、あいだにほかの入出力をはさむことができる。

Freeモナドを使って、いろいろなモナドの機能を定義する

Freeモナドを定義

データ型Freeを定義しておこう。ファイルFree.hsを作成し、つぎのように定義する。

Free.hs
module Free (Free(..)) where

data Free t a
        = Pure a
        | Join (t (Free t a))

instance Functor t => Functor (Free t) where
        f `fmap` Pure x = Pure $ f x
        f `fmap` Join tx = Join $ fmap f <$> tx

instance Functor t => Applicative (Free t) where
        pure = Pure
        Pure f <*> m = f <$> m
        Join tf <*> m = Join $ (<*> m) <$> tf

instance Functor t => Monad (Free t) where
        Pure x >>= f = f x
        Join tx >>= f = Join $ (f =<<) <$> tx

型FreeLやFreeIOと、ほぼ、おなじ定義だ。だいたいの感じとしては、Pureならそのまま適用、Joinなら再帰的に適用していく、といった定義になっている。

Readerモナド

まずは、Freeモナドを使ってReaderモナドの機能を定義してみよう。ファイルfreeMonads.hsを作成して、つぎのような定義を追加する。

freeMonads.hs
import Free

data Reader e a = Reader (e -> a)

instance Functor (Reader e) where
        f `fmap` Reader k = Reader $ f . k

ask :: Free (Reader e) e
ask = Join $ Reader Pure

runReader :: Free (Reader e) a -> e -> a
runReader m e = case m of
        Pure x -> x
        Join (Reader k) -> runReader (k e) e

関数askでは、Pureによって、Reader e aのaのところを、Free (Reader e) e型の値としている。さらに、値構築子JoinによってFree (Reader e) e型の値を構成する。関数runReaderでは値構築子Readerのもつ(e -> Free (Reader e) a)型の値を、値eに適用することでFree (Reader e) a型の値を取り出し、それに対して関数runReaderを再帰的に適用している。試してみる。

> :load freeMonads.hs
> :module + Data.Char
> (`runReader` 100) $ do x <- ask; return $ chr x
'd'

Writerモナド

つぎにWriterモナドの機能を定義する。

freeMonads.hs
data Writer w a = Writer w a

instance Functor (Writer w a) where
        f `fmap` Writer w a = Writer w $ f a

tell :: w -> Free (Writer w) ()
tell w = Join . Writer w $ Pure ()

runWriter :: Monoid w => Free (Writer w) a -> (a, w)
runWriter = \case
        Pure x -> (x, mempty)
        Join (Writer w m) -> second (w <>) $ runWriter m

関数tellでは、Pure ()によってWriter w aの、aのところをFree (Writer w) ()型としている。関数runWriterでは、値構築子Writerのもつ、ふたつめの値であるmに対して、関数runWriterを再帰的に適用し、その結果であるタプルの、ふたつめの値に対して、値構築子Writerの、ひとつめの値であるwを追加している。試してみる。

> :load freeMonads.hs
> runWriter $ do tell "x = 8\n"; x <- return 8; tell "y = 5\n"; y <- return 5; tell $ "x * y = " ++ show (x * y); return $ x * y
(40,"x = 8\ny = 5\nx * y = 40")

ReaderとWriterの両方

ReaderとWriterの両方の機能をもつモナドを作ってみよう。ファイルreaderWriter.hsを作成し、つぎのように定義する。

readerWriter.hs
import Control.Arrow
import Data.Monoid

import Free

data RW e w a
        = Reader (e -> a)
        | Writer w a

instance Functor (RW e w) where
        f `fmap` Reader k = Reader $ f . k
        f `fmap` Writer w x = Writer w $ f x

ask :: Free (RW e w) e
ask = Join $ Reader Pure

tell :: w -> Free (RW e w) ()
tell w = Join . Writer w $ Pure ()

例として、つぎの式を定義する。

readerWriter.hs
sample :: Free (RW String String) (String, String)
sample = do
        x <- ask
        tell $ "I say " ++ x ++ ".\n"
        y <- ask
        tell $ "You say Good-bye!\n"
        return (x, y)

ReaderとWriterの意味論をそのままに

さて、まずはReaderとWriterの、もともとの意味論を、そのままにして計算してみよう。askは環境から値を読み出し、tellはログに値を記録する。

readerWriter.hs
runRW :: Monoid w => Free (RW e w) a -> e -> (a, w)
runRW m e = case m of
        Pure x -> (x, mempty)
        Join (Reader k) -> runRW (k e) e
        Join (Writer w m') -> second (w <>) $ runRW m' e

サンプルの式の評価を、試してみよう。

> :load readerWriter.hs
> sample `runRW` "hello"
(("hello","hello"),"I say hello.\nYou say Good-bye!\n")

式askのかえす値は、環境に定義された値"hello"であり、変化しない。また、関数tellでは、引数に指定した値がログに記録される。

ReaderとWriterで状態モナドとする

さて、ここで「『読み出し』と『書き込み』ができるのなら状態モナドが作れるのでは」と、思うだろう。それは正しい。ReaderとWriterから状態モナドを作ってみる。

hoge.hs
runStateRW :: Free (RW s s) a -> s -> (a, s)
runStateRW m s = case m of
        Pure x -> (x, s)
        Join (Reader k) -> runStateRW (k s) s
        Join (Writer s' m') -> runStateRW m' s'

サンプルの式の評価を、試してみよう。

> :reload
> sample `runStateRW` "hello"
(("hello","I say hello.\n"),"You say Good-bye!\n")

式askのかえす値は、状態の値である。関数tellは状態の値を変化させていく。

おなじモナドの例が、2通りに

ひとつの例sampleが、runRWで評価されるのと、runStateRWで評価されるのとで、異なる結果となった。これは、Freeモナドでは、バインド(>>=)の意味の決定を、モナドを合成しているときではなく、後回しにすることができるということだ。実際の計算をする代わりに、データ構造に保管していると考えることができる。

まとめ

Freeモナドについて見てきた。Freeモナドは、ファンクタであるようなデータ構造をモナドに変換する仕組みだ。バインド(>>=)によって作られる構造は、データの構造として保管される。そのため、モナドの合成のあとから、バインドの動作を決定することができる。

参考

Freeモナドって何なのさっ!?
そろそろFreeモナドに関して一言いっとくか

19
12
3

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
19
12