基礎から学ばないFree Monad

FreeMonad.md

基礎から学ばないFree Monad

自己紹介

• なかやん・ゆーき / ぺんぎん / もみあげ
• @pocketberserker / id:pocketberserker
• 来週から東京に移住
• Microsoft MVP for .NET (～ 2015/03/31)
• 圏論とかHaskellとかわからない
• そのうち東京でLens勉強会やりたい

発表経緯

某社あるある: 発表者に突っ込まれる

発表タイトルを変えた理由

• 後半の発表で必要っぽい
• https://twitter.com/yoshihiro503/status/557046792940818432
• HaskellやScala（の一部界隈）では非常によく知られている。

Free Monad is 何

大雑把にいうと

• Functorを持つデータ型をMonadにできる
• シングルトン生成とネストの結合を一般化

Haskell

class Functor f where
  fmap :: (a -> b) -> f a -> f b

class Monad m where
  return :: a -> m a
  (>>=) :: forall a b. m a -> (a -> m b) -> m b

data Free f a = Pure a | Free (f (Free f a))

instance Functor f => Monad (Free f) where
  -- return :: a -> Free a
  return a = Pure a
  -- (>>=) :: Free f a -> (a -> Free f b) -> Free f b
  Pure a >>= k = k a
  Free m >>= k = Free (fmap (>>= k) m)

m :: f (Free f a)
k :: a -> Free f b

Continuation Passing Style

• bindの列は左結合時のパフォーマンスが良くない
• CPSはそれを解決する一つの手段

newtype F f a = F { runF :: forall r. (a -> r) -> (f r -> r) -> r }

instance Monad (F f) where
  -- return :: a -> F f a
  return a = F (\kp _ -> kp a)
  -- (>>=) :: F f a -> (a -> F f b) -> F f b
  F m >>= f = F (\kp kf -> m (\a -> runF (f a) kp kf) kf)

Reflection without remorse

• 中間状態にアクセスする場合はCPSの利点が損なわれる
• 結合の形に寄らず効率的に動作し、効率的に中間状態にアクセスできるシーケンスを効率の良いデータ構造で表現することで解決
• type aligned sequenceというものに一般化して、CPSと同等の一般性を持たせる
• これはFree Monad、Iteratee、LogicTなどに適用できる

利点

• 定義するのが面倒くさい(MonadReaderとか…)もの
• パフォーマンス問題
• 言語によってはスタックオーバーフロー問題

をFreeが提供 or 解決してくれるかもしれない

参考資料

• https://github.com/atzeus/reflectionwithoutremorse