677 Views
May 26, 17
スライド概要
Freeモナド入門
Haskell/ScalaでFreeモナドを使ってみよう(*> ᴗ •*)ゞ
「楽しく楽にcoolにsmartに」を理想とするprogrammer/philosopher/liberalist/realist。 好きな言語はClojure, Haskell, Python, English, français, русский。 読書、プログラミング、語学、法学、数学が大好き! イルカと海も大好き🐬
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])
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
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
リストのような再帰的データ構造 data [] a = [] | a : [a] f が Functor ⇒ Free f は Monad → Functor のインスタンスを Free で包めば Monad として扱える ※ GHC拡張で Functor を⾃動導出することも: DeriveFunctor
Example: RPN expressions
repositories lagenorhynque/freemonad-hs FreeMonad/RPNExpr.hs cf. lagenorhynque/freemonad-scala freemonad/RPNExpr.scala
RPN: Reverse Polish Notation 逆ポーランド記法 - Wikipedia 861-*2+ ↓ with parentheses ((8 (6 1 -) *) 2 +) ↓ evaluate 42
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
free: Monads for free Control/Monad/Free.hs scalaz/scalaz scalaz/Free.scala typelevel/cats 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のシンプルな定式化