Freeモナド

code:hs

data Free f a = Pure a

| Join (f (Free f a))

instance Functor f => Functor (Free f) where

fmap = (<$>)

-- fmap f (Pure x) = Pure $ f x

-- fmap f (Join fx) = Join $ fmap (fmap f) fx

instance (Functor f) => Applicative (Free f) where

pure = Pure

Pure f <*> a = fmap f a

Join f <*> a = Join $ fmap (<*> a) f

instance Functor f => Monad (Free f) where

return = Pure

Pure x >>= f = f x

Join x >>= f = Join $ fmap (>>= f) x

code:hs

data Free f a where

Pure :: a -> Free f a

Bind :: f x -> (x -> Free f a) -> Free f a

instance Functor (Free f) where

fmap = (<$>)

instance Applicative (Free f) where

pure = Pure

f <*> x = f >>= \f' -> x >>= \x' -> pure $ f' x'

instance Monad (Free f) where

return = Pure

(>>=) (Pure a) a2fb = a2fb a

(>>=) (Bind fx x2fa) a2fb = Bind fx (a2fb <=< x2fa)

参考

説明がそれなりに簡潔で良い

出てくるコードは上のHaskell for allの類似

かなり親切で詳細

Freeモナドの4種の定義

"String Diagrams for Free Monads"

Freeモナドの持つ外延的な性質（emb, interp）をストリング図に落とし込むことでFreeモナドやFreeモナドトランスフォーマーの満たす性質をストリング図で証明する話

GPT-4o.icon

🧠 3. 直感的な理解

🧪 4. 例：簡単なDSLをFreeモナドで作る

たとえば、「コンソール入出力」を表すDSLを考えましょう。

code:haskell

data ConsoleF next

= ReadLine (String -> next)

| WriteLine String next

deriving Functor

code:haskell

type Console = Free ConsoleF

命令を組み立てる：

code:haskell

readLine :: Console String

readLine = liftF (ReadLine id)

writeLine :: String -> Console ()

writeLine s = liftF (WriteLine s ())

使ってみる：

code:haskell

program :: Console ()

program = do

name <- readLine

writeLine ("Hello, " ++ name)

ここでは「何も実行していない」。

ただ、命令の木構造（抽象構文木）を作っているだけです。

🏃 5. 実行（interpretation）

このDSLを「どう実行するか」は別途定義します。

code:haskell

runConsoleIO :: Console a -> IO a

runConsoleIO (Pure a) = pure a

runConsoleIO (Free (ReadLine next)) = getLine >>= runConsoleIO . next

runConsoleIO (Free (WriteLine s next)) = putStrLn s >> runConsoleIO next

code:haskell

liftF :: Functor f => f a -> Free f a

liftF fa = Free (fmap Pure fa)

これは「単一の命令をFreeモナドに持ち上げる」関数。

圏論

pursの場合

むかし

code:purs(hs)

-- Type

data Free f a = Free (FreeView f Val Val) (CatList (ExpF f))

data FreeView f a b = Return a

| Bind (f b) (b -> Free f a)

newtype ExpF f = ExpF (Val -> Free f Val)

data Val

-- Functor

instance Functor (Free f) where

map f k = f <$> k

-- Apply

instance Apply (Free f) where

apply = ap

-- Bind

instance Bind (Free f) where

bind (Free v s) k = Free v (snoc s (ExpF (unsafeCoerceBind k)))

where

unsafeCoerceBind :: forall a b. (a -> Free f b) -> Val -> Free f Val

unsafeCoerceBind = unsafeCoerce

-- Applicative

instance Applicative (Free f) where

pure = fromView <<< Return

-- Monad

instance Monad (Free f)

ここにかいてた

どのへんが「Free」なのか

code:hs

data MyProgram n = Old Int n | Hey n | Hello n | GoodBye

instance Functor MyProgram where

fmap f (Old o n) = Old o (f n)

fmap f (Hey n) = Hey (f n)

fmap f (Hello n) = Hello (f n)

fmap f GoodBye = GoodBye

runProgram :: Show r => Free MyProgram r -> IO ()

runProgram (Free (Old o n)) = putStrLn ("I'm " ++ show o ++ " years old") >> runProgram n

runProgram (Free (Hey n)) = putStrLn "Hey!!!" >> runProgram n

runProgram (Free (Hello n)) = putStrLn "Hello!!!" >> runProgram n

runProgram (Free GoodBye) = putStrLn "GoodBye!!!"

runProgram (Pure r) = putStrLn $ "return " ++ show r

pg :: Free MyProgram ()

pg = do

Free $ Hey (Pure ())

Free $ Hello (Pure ())

Free $ Old 2 (Pure ())

Free GoodBye

main :: IO ()

main = runProgram pg

data Fix f = Fix (f (Fix f))

todos

pursのFreeの構成の意味

TrampolineモナドとFreeTどっちを使うのか

コンパイル後JSでどんなふうに変わっているのか観察

関連

処理効率を考えて実装されたFreeモナド

ASTのデータ型からFreeのアクションを導出する

論文

ユースケース

2Dゲーム

普通に型で区切られた世界とどう違うのか

あ、普通にMonadを作ることをDSL作成と言ってるだけか

「Monadを作ること」が「DSLを作ること」にほぼ同じなのであれば、「Freeモナドを作ることの嬉しさ」として「DSLを作れること」って挙げるのおかしくない？

あくまでも「Freeモナドの嬉しさ」は「簡単にモナドを作れること」であって、

「DSLを作ること」は「Monadの嬉しさ」の一つに過ぎないだろう

Monad構造を動的に操作する例

それを使ってデータの操作をした有用な例みたいなのを見てみたい

ps

実用例