Free Monads Getting Started

Free Monads Getting Started

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])

• https://github.com/lagenorhynque

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

What are monads?

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

• http://hackage.haskell.org/package/base-4.9.1.0/docs/src/GHC.Base.html#Monad
• https://github.com/scalaz/scalaz/blob/v7.2.12/core/src/main/scala/scalaz/Monad.scala

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

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]

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))

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

What are Free monads?

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

• https://github.com/scalaz/scalaz/blob/v7.2.12/core/src/main/scala/scalaz/Free.scala
• http://hackage.haskell.org/package/free-4.12.4/docs/src/Control-Monad-Free.html

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

• https://ghc.haskell.org/trac/ghc/wiki/Commentary/Compiler/DeriveFunctor

Example: RPN expressions

repositories lagenorhynque/freemonad-hs FreeMonad/RPNExpr.hs cf. lagenorhynque/freemonad-scala freemonad/RPNExpr.scala

• https://github.com/lagenorhynque/freemonad-scala
• https://github.com/lagenorhynque/freemonad-hs
• https://github.com/lagenorhynque/freemonad-hs/blob/master/src/FreeMonad/RPNExpr.hs
• https://github.com/lagenorhynque/freemonad-scala/blob/master/src/main/scala/freemonad/RPNExpr.scala

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

• https://ja.wikipedia.org/wiki/逆ポーランド記法

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

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

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

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

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 ()))))))))))

> | | | | | | :{ 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 ()

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 _) = ""

> 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 + ."

⽂字列を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"

> 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"

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"

> 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

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

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

• http://book.impress.co.jp/books/1114101091
• http://www.haskellforall.com/2012/06/you-could-have-invented-free-monads.html
• http://eed3si9n.com/learning-scalaz/ja/
• http://eed3si9n.com/learning-scalaz/ja/Free Monad.html
• http://eed3si9n.com/herding-cats/ja/
• http://eed3si9n.com/herding-cats/ja/Free-monads.html
• http://localhost:1948/free-monads.md?print-pdf

free: Monads for free Control/Monad/Free.hs scalaz/scalaz scalaz/Free.scala typelevel/cats cats/free/Free.scala

• http://hackage.haskell.org/package/free
• http://hackage.haskell.org/package/free-4.12.4/docs/src/Control-Monad-Free.html
• https://github.com/scalaz/scalaz
• https://github.com/scalaz/scalaz/blob/v7.2.12/core/src/main/scala/scalaz/Free.scala
• https://github.com/typelevel/cats
• https://github.com/typelevel/cats/blob/v0.9.0/free/src/main/scala/cats/free/Free.scala

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

• http://shop.ohmsha.co.jp/shop/shopdetail.html?brandcode=000000001926
• https://www.slideshare.net/KentOhashi/mp-in-haskell
• https://ja.wikipedia.org/wiki/Interpreter_パターン
• http://learnyouahaskell.com/
• https://www.slideshare.net/KentOhashi/mp-in-scala
• http://qiita.com/lagenorhynque/items/e68ada9ee2d63539eb45