Free Monads Getting Started

406 Views

May 26, 17

haskell scala 関数型プログラミング free monad

スライド概要

Freeモナド入門
Haskell/ScalaでFreeモナドを使ってみよう(*> ᴗ •*)ゞ

profile-image
スライド一覧

「楽しく楽にcoolにsmartに」を理想とするprogrammer/philosopher/liberalist/realist。 好きな言語はClojure, Haskell, Python, English, français, русский。 読書、プログラミング、語学、法学、数学が大好き! イルカと海も大好き🐬

シェア

またはPlayer版

埋め込む »CMSなどでJSが使えない場合

ダウンロード

ダウンロード(pdf - 451.03kB)

関連スライド

slide-thumbnail

JavaからScala、そしてClojureへ: 実務で活きる関数型プログラミング
関数型言語 関数型プログラミング java scala clojure
user-img Kent OHASHI 29.2K
slide-thumbnail

Clojureコレクションで探るimmutableでpersistentな世界
関数型プログラミング clojure java scala コレクション
user-img Kent OHASHI 6.1K
slide-thumbnail

RDBでのツリー表現入門
rdb sql モデリング テーブル設計 ツリー
user-img Kent OHASHI 2K
slide-thumbnail

インターフェース定義言語から学ぶモダンなWeb API方式: REST, GraphQL, gRPC
web api rest graphql grpc
user-img Kent OHASHI 2K
slide-thumbnail

ClojurianからみたElixir
elixir clojure 関数型プログラミング
user-img Kent OHASHI 1.7K
slide-thumbnail

Scala vs Clojure?: The Rise and Fall of Functional Languages in Opt Technologies
clojure scala web api 技術選定
user-img Kent OHASHI 1.6K
各ページのテキスト
1.

Free Monads Getting Started

2.

Self-introduction lagénorhynque /laʒenɔʁɛ k ̃ / カマイルカ (defprofile lagénorhynque :name "Kent OHASHI" :account @lagenorhynque :company "Opt, Inc." :languages [Clojure Haskell Python Scala English français Deutsch русский] :interests [programming language-learning mathematics] :contributing [github.com/japan-clojurians/clojure-site-ja])

3.

Contents 1. What are monads? 2. What are Free monads? 3. Example: RPN expressions

4.

What are monads?

5.

de nition of Monad GHC.Base#Monad class Applicative m => Monad m where (>>=) :: forall a b. m a -> (a -> m b) -> m b (>>) :: forall a b. m a -> m b -> m b m >> k = m >>= \_ -> k {-# INLINE (>>) #-} return return :: a -> m a = pure fail fail s :: String -> m a = errorWithoutStackTrace s cf. scalaz/Monad.scala

6.

return 値 a をモナド m に⼊れる Haskell: return a -> m a Scalaz: point A => M[A]

7.

bind 値 m a に 関数 a -> m b を適⽤して m b にする Haskell: >>= m a -> (a -> m b) -> m b Scalaz: bind (cf. flatMap) M[A] => (A => M[B]) => M[B]

8.

do notation (Haskell) a = Just 2 b = Just 3 c = do x <- a y <- b return $ x * y ↓ desugar a = Just 2 b = Just 3 c = a >>= (\x -> b >>= (\y -> return $ x * y))

9.

for expression (Scala) val a = Some(2) val b = Some(3) val c = for { x <- a y <- b } yield x * y ↓ desugar val a = val b = val c = b.map x * } } Some(2) Some(3) a.flatMap { x => { y => y

10.

What are Free monads?

11.

de nition of Free Control/Monad/Free.hs data Free f a = Pure a | Free (f (Free f a)) instance Functor f => Monad (Free f) where return = pure {-# INLINE return #-} Pure a >>= f = f a Free m >>= f = Free ((>>= f) <$> m) cf. scalaz/Free.scala

12.

リストのような再帰的データ構造 data [] a = [] | a : [a] f が Functor ⇒ Free f は Monad → Functor のインスタンスを Free で包めば Monad として扱える ※ GHC拡張で Functor を⾃動導出することも: DeriveFunctor

13.

Example: RPN expressions

14.
15.

RPN: Reverse Polish Notation 逆ポーランド記法 - Wikipedia 861-*2+ ↓ with parentheses ((8 (6 1 -) *) 2 +) ↓ evaluate 42

16.

DSL interpreter RPN DSL = AST -- Free monad → eval :: AST -> Num → stringify :: AST -> String ← parse :: String -> AST

17.

RPNのASTを表現するデータ型 RPNExpr を定義する data RPNExpr n expr = Number n expr | Add expr | Sub expr | Mul expr | End deriving (Show)

18.

RPNExpr を Functor にする instance fmap fmap fmap fmap fmap Functor (RPNExpr n) f (Number n expr) = f (Add expr) = f (Sub expr) = f (Mul expr) = _ End = where Number n $ f expr Add $ f expr Sub $ f expr Mul $ f expr End

19.

RPNExpr を Free で包んで RPN Monad として扱う type RPN a b = Free (RPNExpr a) b liftF :: (Functor f) => f r -> Free f r liftF = Free . fmap Pure num num add add sub sub mul mul end end :: a -> RPN a () n = liftF $ Number n () :: RPN a () = liftF $ Add () :: RPN a () = liftF $ Sub () :: RPN a () = liftF $ Mul () :: RPN a b = liftF End

20.

RPN モナド(RPNのDSL = AST)を試してみる > | | | | | | | | :{ expr1 :: RPN Double () expr1 = do num 8 num 6 num 1 sub mul :} > expr1 Free (Number 8.0 (Free (Number 6.0 (Free (Number 1.0 (Free (Sub (Free (Mul (Pure ()))))))))))

21.

> | | | | | | :{ expr2 :: RPN Double () expr2 = do num 2 add end :} > expr2 Free (Number 2.0 (Free (Add (Free End)))) 複数の式を連結してみる > expr1 >> expr2 Free (Number 8.0 (Free (Number 6.0 (Free (Number 1.0 (Free (Sub (Free (Mul (Free (Number 2.0 (Free (Add (Free End)))))))))))))) > :t expr1 >> expr2 expr1 >> expr2 :: Free (RPNExpr Double) () -- RPN Double ()

22.

RPNのASTを⽂字列化する関数 stringify stringify stringify stringify stringify stringify stringify stringify :: (Show a) => RPN a b -> String (Free (Number n e)) = show n ++ " " ++ stringify e (Free (Add e)) = "+ " ++ stringify e (Free (Sub e)) = "- " ++ stringify e (Free (Mul e)) = "* " ++ stringify e (Free End) = "." (Pure _) = ""

23.

> expr1 Free (Number 8.0 (Free (Number 6.0 (Free (Number 1.0 (Free (Sub (Free (Mul (Pure ())))))))))) > stringify expr1 "8.0 6.0 1.0 - * " > expr2 Free (Number 2.0 (Free (Add (Free End)))) > stringify expr2 "2.0 + ." > stringify $ expr1 >> expr2 "8.0 6.0 1.0 - * 2.0 + ."

24.

⽂字列をRPNのASTに変換する関数 parse parse :: (Read a) => String -> Either String (RPN a ()) parse = foldM rpn (Pure ()) . reverse . words where rpn e "+" = Right . Free $ Add e rpn e "-" = Right . Free $ Sub e rpn e "*" = Right . Free $ Mul e rpn _ "." = Right $ Free End rpn e n = case reads n of [(v,_)] -> Right . Free $ Number v e _ -> Left "invalid input"

25.

> parse "8.0 6.0 1.0 - * " :: Either String (RPN Double ()) Right (Free (Number 8.0 (Free (Number 6.0 (Free (Number 1.0 (Free (Sub (Free (Mul (Pure ()))))))))))) > parse "2.0 + ." :: Either String (RPN Double ()) Right (Free (Number 2.0 (Free (Add (Free End))))) > parse "8.0 6.0 1.0 - * 2.0 + ." :: Either String (RPN Double ()) Right (Free (Number 8.0 (Free (Number 6.0 (Free (Number 1.0 (Free (Sub (Free (Mul (Free (Number 2.0 (Free (Add (Free End))))))))))))))) > parse "2.0 3.0 /" :: Either String (RPN Double ()) Left "invalid input"

26.

RPNのASTを評価する関数 eval eval :: (Num a) => RPN a b -> Either String a eval = calc [] where calc stack (Free (Number n e)) = calc (n : stack) e calc (n1:n2:ns) (Free (Add e)) = calc (n2 + n1 : ns) e calc (n1:n2:ns) (Free (Sub e)) = calc (n2 - n1 : ns) e calc (n1:n2:ns) (Free (Mul e)) = calc (n2 * n1 : ns) e calc (n:_) (Free End) = Right n calc (n:_) (Pure _) = Right n calc _ _ = Left "invalid expression"

27.

> expr1 Free (Number 8.0 (Free (Number 6.0 (Free (Number 1.0 (Free (Sub (Free (Mul (Pure ())))))))))) > eval expr1 Right 40.0 > expr2 Free (Number 2.0 (Free (Add (Free End)))) > eval expr2 Left "invalid expression" > eval $ expr1 >> expr2 Right 42.0

28.

データ型を定義して Functor にすることで、 Free を介して Monad が得られた 例えば データ型として定義したASTをモナドに ⇒ 合成可能なDSL(= モナド)が提供できる ⇒ AST(= モナド)を解釈する関数群を⽤意する ことでインタプリタが書ける

29.

Further Reading Haskell for all: Why free monads matter 独習 Scalaz Free Monad 猫番 ⾃由モナド (Free) 『Scala関数型デザイン＆プログラミング』/ Functional Programming in Scala 第13章 外部作⽤とI/O

30.
31.

Interpreter パターン - Wikipedia 『すごいHaskellたのしく学ぼう！』/ Learn You a Haskell for Great Good! 10.1 逆ポーランド記法電卓 14.6 安全な逆ポーランド記法電卓を作ろう MP in Scala cf. MP in Haskell Functor, Applicative, Monadのシンプルな定式化