Edited at

モナドに至る道 at Nakameguro.hs #2

このスライドはモナド勉強会 at Nakameguro.hs #2の発表資料です


Nakameguro.hs これまでの軌跡

今回ほぼ3年ぶりに開催!



平日にサクッと集まってHaskellのニッチな話題について語れる勉強会としてやっていきたい気持ちです



モナドに至る道



なぜモナドが重要なのか?


私たちは関数のみを使ってプログラミングしたい。(つまるところ「関数型プログラミング(FP)」)

なぜモナドが必要なのか? - Qiita


しかし非決定的な計算・副作用を伴う計算などなど、関数でどう扱えばいい?


モナドは値およびその値を使う計算の並びという観点からいえば、計算を構造化する方法です

モナドのすべて - イントロダクション


非決定性・副作用・例外処理など全部モナドで構造化された計算として表してしまえばいい!

(そしてそれが可能である!)


それが良いかどうかは別として、純粋さをとことん追求した必然の孤高の帰結がモナドというわけです

モナドはなぜHaskellでしか積極的に使われていないのか? - uehaj's blog


最近はasync/await等よく似た機能が他の言語にも徐々に取り入れられている



増え続けるモナドチュートリアル


プログラミングにおけるモナドの起源

E. Moggi "Computational Lambda-Calculus and Monads" (1988)

プログラミングにおけるモナドの初期の歴史について - 再帰の反復blog


世の中にはたくさんのモナドチュートリアルが溢れている

それだけ注目されているが理解するのが簡単ではないということ



Monad tutorials timeline - HaskellWiki

今日はせっかくの勉強会なので対話を通して一人ひとりの理解に向き合えたらと思います

なので気軽にいつでも質問してください!



Haskellのおさらい



Haskell Recap / Hello World

あとに出てくるコードを読むために必要な知識を高速におさらい

main :: IO ()

main = putStrLn "Hello World"

mainに書かれた処理が実行されます

> :t putStrLn

putStrLn :: String -> IO ()



Haskell Recap / 型

型を定義する3つの方法

-- 型シノニム

-- 既存の型に別名をつける
type Point = (Int, Int)

-- newtype は既存の型と同値な型を定義する
newtype Reader r a = Reader { runReader :: r -> a }

-- data は全く新しい型を定義する
data Signal = Green | Yellow | Red



Haskell Recap / 関数

パターンマッチ

canGo :: Signal -> Bool

canGo Green = True
canGo _ = False

case式

canGo :: Signal -> Bool

canGo x = case x of
Green -> True
_ -> False

再帰

take :: Int -> [a] -> [a]

take 0 _ = []
take n (x:xs) = x : take (n-1) xs

中置記法

> :t elem

elem :: a -> [a] -> Bool

> 5 `elem` [1..10]
True



Haskell Recap / 高階型

型を受け取って型になる型

data Maybe a = Nothing | Just a

data [] a = [] | a : [a]

2つ以上の型変数も扱える

data (,) a b = (,) a b

data (->) a b = ...

受け取った方の値を使わない幽霊型

data Const a b = Const a



Haskell Recap / 高階関数

関数を引数に取ったり、関数を返り値にしたりする型

map :: (a -> b) -> ([a] -> [b])

合成関数の演算子

(.) :: (b -> c) -> (a -> b) -> (a -> c)



Haskell Recap / リスト操作

> [1,2,3,4,5]

[1,2,3,4,5]

> -- レンジ
> [1..5]
[1,2,3,4,5]

> -- 無限リスト
> repeat 1
[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,^C

> -- リストの長さ
> length [1..5]
5

> -- map :: (a -> b) -> [a] -> [b]
> map (*2) [1..5]
[2,4,6,8,10]

> -- zip :: [a] -> [b] -> [(a, b)]
> zip [1..5] ['a'..'z']
[(1,'a'),(2,'b'),(3,'c'),(4,'d'),(5,'e')]

> -- zipWith :: (a -> b -> c) -> [a] -> [b] -> [c]
> zipWith (+) [1..5] [100..]
[101,103,105,107,109]

> -- concat :: [[a]] -> [a]
> concat [[1, 2], [3, 4], [5, 6]]
[1,2,3,4,5,6]

> -- concatMap :: (a -> [b]) -> [a] -> [b]
> concatMap (\x -> [x, 10 * x]) [1..5]
[1,10,2,20,3,30,4,40,5,50]

モナドのエッセンスがここに詰まっています



まずは型クラス



型クラス

"アドホック多相"を実現するための言語機能

class Show a where

show :: a -> String

showは型クラスShowのインスタンスになっている型なら何でも引数に取れる

> show 123

"123"

> show True
"True"

> -- これはダメな例
> show length
No instance for (Show ([a0] -> Int)) arising from a use of show
...

インスタンスの定義

data Signal = Green | Yellow | Red

instance Show Signal where
show Green = "Green"
show Yellow = "Yellow"
show Red = "Red"

> show Green

"Green"

関数の型には型クラス制約として現れる

> :t print

print :: Show a => a -> IO ()

> print 123

123

> print True
True

> print "Haskell"
"Haskell"

> print Red
Red



代表的な型クラス / Eq

値が同じかどうか比較するための型クラス

class Eq a where

(==) :: a -> a -> Bool
(/=) :: a -> a -> Bool

x == y = not (x /= y)
x /= y = not (x == y)

インスタンスの例

instance Eq Bool where

True == True = True
False == False = True
_ == _ = False

instance (Eq a, Eq b) => Eq (a, b) where
(x1, y1) == (x2, y2) = x1 == x2 && y1 == y2



代表的な型クラス / Ord

値の大小を比較するための型クラス

data Ordering = LT | EQ | GT

class Eq a => Ord a where
compare :: a -> a -> Ordering
(<), (<=), (>), (>=) :: a -> a -> Bool
max, min :: a -> a -> a

compare x y = if x == y then EQ
else if x <= y then LT
else GT

x < y = case compare x y of { LT -> True; _ -> False }
x <= y = case compare x y of { GT -> False; _ -> True }
x > y = case compare x y of { GT -> True; _ -> False }
x >= y = case compare x y of { LT -> False; _ -> True }

max x y = if x <= y then y else x
min x y = if x <= y then x else y

インスタンスの例

instance Ord Bool where

True <= True = True
False <= True = True
True <= False = False
False <= False = True



代表的な型クラス / 数値型


Num

整数のような計算(足し算掛け算等)を備えた型クラス

class Num a where

(+) :: a -> a -> a
(-) :: a -> a -> a
(*) :: a -> a -> a
negate :: a -> a
abs :: a -> a
signum :: a -> a
fromInteger :: Integer -> a

x - y = x + negate y
negate x = 0 - x

インスタンスの例

instance Num Int where

...

instance Num Double where
...


Fractional

割り算が出来るような演算を備えた型クラス

class Num a => Fractional a  where

(/) :: a -> a -> a
recip :: a -> a
fromRational :: Rational -> a

recip x = 1 / x
x / y = x * recip y

インスタンスの例

instance Fractional Double where

...


Haskellの数値系型クラスの関係



Numeric Tower - WHAT I WISH I KNEW WHEN LEARNING HASKELL



代表的な型クラス / Monoid

結合演算とそれに対する単位元を備えた型クラス

class Monoid a where

mempty :: a
mappend :: a -> a -> a

mconcat :: [a] -> a
mconcat = foldr mappend mempty

インスタンスの例

instance Mononid [a] where

mempty = []
mappend xs ys = xs ++ ys

-- 足し算に関するモノイド
newtype Sum a = Sum { getSum :: a }

instance Num a => Monoid (Sum a) where
mempty = Sum (fromIntegral 0)
mappend (Sum x) (Sum y) = Sum (x + y)

-- 掛け算に関するモノイド
newtype Product a = Product { getProduct :: a }

instance Num a => Monoid (Product a) where
mempty = Product (fromIntegral 1)
mappend (Product x) (Product y) = Product (x * y)



Functor Applicative Monad



型クラスの依存関係



The Typeclassopediaを訳しました, The Typeclassopedia - #3(2009-10-20)



Functor



Functor

class Functor f where

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

普通の関数をFunctorに包まれた型に適用できるようにするのがfmap

日本語で関手とも呼ばれる



Functor / Maybe

data Maybe a = Nothing | Just a

instance Functor Maybe where
fmap f Nothing = Nothing
fmap f (Just a) = Just (f a)

Maybefmapは中身があれば作用する

> fmap (+1) Nothing

Nothing

> fmap (+1) (Just 1)
Just 2

> fmap (++" World") (Just "Hello")
Just "Hello World"



Functor / List

data [] a = [] | a : [a]

instance Functor [] where
fmap f [] = []
fmap f (x:xs) = f x : fmap f xs

リストのfmapは全ての中身に作用する

> [1..5]

[1,2,3,4,5]

> fmap (+1) [1..5]
[2,3,4,5,6]

> fmap (+1) []
[]



Functor / ZipList

ZipListは型としてリストと同型

> :i ZipList

newtype ZipList a = ZipList {getZipList :: [a]}

Functorの実装はリストと同じ

instance Functor ZipList where

fmap f (ZipList xs) = ZipList (fmap f xs)

後に出てくるApplicativeの実装に違いが出てくる



Functor / 関数

instance Functor ((->) r) where

-- fmap :: (a -> b) -> (r -> a) -> (r -> b)
fmap f g = f . g

関数のfmapは関数合成

> fmap (+1) (+2) 3

6

> fmap (++ "sec") show 5
"5sec"



Functor / Const

data Const a b = Const a

instance Functor (Const a) where
fmap f (Const a) = Const a

Constfmapは"何もしない"

> fmap (++ "Hello") (Const 1)

Const 1



Applicative



Applicative

class Functor f => Applicative f where

pure :: a -> f a
(<*>) :: f (a -> b) -> f a -> f b

pureを使って値を包むことが出来る(Pointed)

(<*>)を使って包まれた世界の中で関数適用をすることが出来る



Applicative / Maybe

instance Applicative Maybe where

pure = Just

Nothing <*> _ = Nothing
_ <*> Nothing = Nothing
(Just f) <*> (Just a) = Just (f a)

Maybepureは値をJustで包む

Maybe<*>は中身があれば作用させる

> Just (+1) <*> Just 2

Just 3



Applicative / List

instance Applicative [] where

pure a = [a]

fs <*> xs = concat (map (\f -> map (\x -> f x) xs) fs)
-- [f x | f <- fs, x <- xs]

リストのpureは一つの要素を持つリストを作る

リストの<*>は全ての組み合わせで作用させる

> [(+1), (*2)] <*> [1, 2]

[2,3,2,4]



Applicative / ZipList

instance Applicative ZipList where

pure a = ZipList (repeat a)

(ZipList fs) <*> (ZipList xs) = ZipList (zipWith (\f x -> f x) fs xs)
-- ZipList (zipWith ($) fs xs)

ZipListpureは値を無限にコピーする

ZipList<*>はリストの中身を対応する順番に作用させる

> ZipList [(+1), (*2)] <*> ZipList [1, 2]

ZipList {getZipList = [2,4]}

> ZipList [(+1), (*2)] <*> ZipList [1]
ZipList {getZipList = [2]}



Applicative / 関数

instance Applicative ((->) r) where

pure a = const a

f <*> g = \r -> f r (g r)

関数のpureは定数関数を作る

関数の<*>は全ての関数に引数を作用させる

> pure 1 "Hello"

1

> ((+) <*> (+1)) 1
3



Applicative / Const

Const aはApplicativeのインスタンスには出来ない

ただしaがMonoidであれば可能

instance Monoid a => Applicative (Const a) where

pure _ = mempty

(Const a) <*> (Const b) = Const (a `mappend` b)



Monad



Monad

class Applicative m => Monad m where

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

(>>=) は包まれた値を、値を変換して包まれた値にする関数に適用して包まれた値を作成する

実はこれはdo構文に適した定義になっている

同値でより分かりやすそうなモナドの定義を後で紹介します



Monad / Maybe

Maybeは失敗するかもしれない計算を構造化するモナド

instance Monad Maybe where

Nothing >>= _ = Nothing
(Just a) >>= k = k a

> :t find

find :: (a -> Bool) -> [a] -> Maybe a

> :t lookup
lookup :: Eq a => a -> [(a, b)] -> Maybe b

> Just 3 >>= (\x -> find (\n -> n `mod` x == 0) [10..15] >>= (\y -> lookup y [(12, "A"), (15, "B")]))
Just "A"

>>= を使った書き方はすぐに煩雑になってしまう



do記法

do構文を使えばあたかも逐次的な処理を記述しているかのように書ける

Just 3 >>= (\x -> find (\n -> n `mod` x == 0) [10..15] >>= (\y -> lookup y [(12, "A"), (15, "B")]))

== -- ここはただ整形してるだけ

Just 3 >>= (\x ->
find (\n -> n `mod` x == 0) [10..15] >>= (\y ->
lookup y [(12, "A"), (15, "B")]))

== -- do構文!

do
x <- Just 3
y <- find (\n -> n `mod` x == 0) [10..15]
lookup y [(12, "A"), (15, "B")]

Maybeはどこかの計算で失敗すれば全体が失敗する



Monad / List

リストは非決定的な計算を構造化するモナド

instance Monad [] where

xs >>= k = concat (fmap k xs)
-- concatMap k xs

これはいわゆるflatMap

> do

| x <- [1..30]
| y <- [x..30]
| z <- [y..30]
| if x^2 + y^2 == z^2 then [(x,y,z)] else []
[(3,4,5),(5,12,13),(6,8,10),(7,24,25),(8,15,17),(9,12,15),(10,24,26),(12,16,20),(15,20,25),(18,24,30),(20,21,29)]

上記のようにモナドを使えば"前の値"に応じて計算を分岐することが出来る


構造化定理 (...) 逐次、反復、分岐があれば、計算しうる計算はすべて記述できるという定理です。Monad の説明にありがちな圏論を持ち出されるより、よっぽどいいでしょう?

Haskell の Monad とは言語内DSLのフレームワークである - あどけない話




Monad / ZipList

ZipListはモナド則を満たせないのでモナドにはなりません(後述)



Monad / 関数

関数はある引数を受け取る計算を構造化するモナド

instance Monad ((->) r) where

f >>= k = \r -> k (f r) r

> average = do

| x <- sum
| y <- length
| pure (x / fromIntegral y)

> average [1..10]
5.5

このモナドはReaderとも呼ばれ便利に使われます(詳しくは後半のセッションで)


考えているモナドによってdo構文が直感的に表している手続き的な操作の意味がそれぞれ変わってくる

この感覚を以ってモナドは文脈とも言われている



もっとモナドの例 / IO


IOはOSとやり取りするためのEDSL

"Building Haskell Programs with Fused Effects" by Patrick Thomson - YouTube


> :t getLine

getLine :: IO String

> :t putStrLn
putStrLn :: String -> IO ()

IOはモナドなのでdo構文を使って組み合わせることが出来る

> :{

| do
| putStrLn "お名前は?"
| name <- getLine
| putStrLn ("こんにちは" ++ name)
| :}
お名前は?
lotz
こんにちはlotz



もっとモナドの例 / Hedis

http://hackage.haskell.org/package/hedis

HaskellのRedisクライアント

> :t set

set :: String -- key
-> String -- value
-> Redis Status

> :t get
get :: String -- key
-> Redis (Maybe String)

> :t runRedis
runRedis :: Connection -> Redis a -> IO a

Redisはモナドなのでdo構文を使って組み合わせることが出来る

> runRedis conn $ do

| set "hello" "hello"
| set "world" "world"
| hello <- get "hello"
| world <- get "world"
| pure (hello, world)
(Just "hello", Just "world")

※分かりやすさを優先して少し型は変えてます



モナドに至る別の道



joinで実装するMonad

class Applicative m => Monad m where

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

(>>=) :: m a -> (a -> m b) -> m b
f >>= k = join (fmap k f)

join x = x >>= id

二重に包まれた構造を潰して一重にするのがjoin

リストで言えばconcatやflattenにあたる操作



joinで実装するMonad / 具体例

instance Monad Maybe where

join Nothing = Nothing
join (Just x) = x

instance Monad [] where
join = concat

モナドは二重になった構造を潰せる高階型と考えることが出来る



<=< で実装するMonad

class Applicative m => Monad m where

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

(>>=) :: m a -> (a -> m b) -> m b
x >>= k = (k <=< id) x
g <=< f = \a -> fmap g (f a) >>= id

合成関数の演算子.を思い出すと、

> :t (.)

(.) :: (b -> c) -> (a -> b) -> a -> c

(<=<)は型コンストラクタ付き関数結合だと思える

[Haskell] 爆速でモナドを理解する - Qiita



<=< で実装するMonad / 具体例

instance Monad Maybe where

g <=< f = \a -> case f a where
Nothing -> Nothing
Just b -> g b

instance Monad [] where
g <=< f = concatMap g . f

モナドは型コンストラクタ付き関数合成を備えた高階型と考えることが出来る



同値性

(>>=)join(<=<) の同値性を図で確認してみる

@ryota-ka 原案 @lotz 作)



圏論の影



モナド則

任意のモナドのインスタンスは以下の関係を満たすことが要請されます

1.  pure x >>= f     <=>  f x

2. m >>= pure <=> m
3. (m >>= f) >>= g <=> m >>= (\x -> f x >>= g)

しかしこの関係を満たしていることはコンパイラが保証してくれるものではありません

この性質はプログラムの書き換えが正しく行えることを保証してくれるので実際のプログラミングでも役に立ちます

詳しくは: モナド則とプログラミング - Qiita

このモナド則を満たす必要があるためZipListはモナドにはなれません

詳しくは: リストデータ型にのるモナド構造の単位射は a -> [a] だけ (1) - Qiita



圏論


ワドラーは批判を和らげるために、こう語っている。「モナドは単なる自己関手の圏におけるモノイド対象だよ。何か問題でも?」

不完全にしておよそ正しくないプログラミング言語小史




まとめ



まとめ


  • モナドは単なる型クラス

  • do構文で便利に使える

モナドを理解するためにはまず手を動かして使ってみるのが一番の近道です

モナドが手に馴染んできた暁には自分の理解の形を記事に書いて

是非モナドへの新しい登頂ルートを開拓してください!



ご清聴ありがとうございました