class: center, middle # Freer Monads, More Extensible Effects Tim McGilchrist (@lambda_foo) .bottom[] ??? * Check your MTL at the door. --- # Outline "Freer Monads, More Extensible Effects" paper by Oleg Kiselyov and Hiromi Ishii. May contain traces of Free Monads, no understanding required. ??? ICFP 2015 --- class: center, middle, section-white background-image: url(/talks/fp-syd-freer-2016/background-image01.jpg) --- # Motivation Acknowledge the issue being addressed, composability of Effects ie Monads. There are 3 approaches proposed for addressing this: 1. Monad Transformers (transformers/MTL) 2. Combine monads via a co-product 3. Effects as an interaction and having effect handlers ??? 2 is Data types ala carte 3. Eff language Extensible effects emerge as a combination of free monads and open union 2 & 3. --- # Effects as Data ``` haskell data Reader i a = Pure a | Get (i -> Reader i a) ``` -- ``` haskell data Writer o a = Pure a | Put o (() -> Writer o a) ``` ??? Having a look at effects as data types -- ```haskell data ReadWrite i o a = Pure a | Get (i -> ReadWrite i o a) | Put o (() -> ReadWrite i o a) ``` ??? Not extensible. Data types are closed union --- # Effects as Data cont ```haskell instance Monad (ReadWrite i o a) where return = Pure Pure x >>= k = k x Get k' >>= k = Get (k' >>> k) Put u k' >>= k = Put x (k' >>> k) ``` * Not extensible * Data types are closed union ??? Monad instance for Reader Writer. (>>>) Kleisli composition, is the composition of effectful functions Common pattern here. --- # Free Monad ``` haskell data Free f a = Pure a | Impure (f (Free f a)) ``` Pure represents no requests, while Impure are the requests. Containing the continuation that receives the reply. Instances of `f` define the effect signature of a particular effectful computation. ??? --- # Free Monad cont ```haskell instance Functor f => Monad (Free r) where return = Pure Pure a >>= k = k a Impure f >>= k = Impure (fmap (>>= k) f) ``` ??? * free monad's compose because they're based off functors which do compose. * free monad recover a free monad from the data type definition. * tricky bit is writing the interpreter --- # Freer Monad ```haskell data FFree f a where Pure :: a -> FFree f a Impure :: f x -> (x -> FFree f a) -> FFree f a ``` Insight, make the `fmap` external ??? In this way we can remove the Functor constraint. --- # Freer Monad cont ```haskell data FReaderWriter i o x where Get :: FReaderWriter i o i Put :: o -> FReaderWriter i o () instance Monad (FFree f) where ... Impure fx k’ >>= k= Impure fx (k’ >>> k) ``` ??? * more common pattern of accumulating continuations * more general, it imposes less constaints than before * Monad instance but also the Functor and Applicative instances for free. * Direct access to the continuation means no rebuilding the mapped data like with fmap * Can change the representation of the continuation to be more efficient. More on this later --- # Extensible Effects `A Monad type is extensible if we can add a new effect without having to touch or even recompile the old code.` ??? * transformers doesn't provide this? * Bloody stupidly designed Monad Transformer stack * Modeling the Effects as a data type is not extensible. --- # Open Union `Union (r :: * -> *) x` The first argument r is a type level list of effect labels. The second argument is the response type. A concrete union has a single effect label and response type. ??? * A way of describing effects, that's extensible --- # Effect Isolation Next we'd like to talk about effects in isolation, the `freer` library provides this typeclass. ``` haskell class Member t r where inj :: t v -> Union r v prj :: Union r v -> Maybe (t v) ``` ??? This allows us to assert a label `t` occurs in the list `r`. Impure takes a concrete union of a single effect and response type, a function from `x` to `FEFree r a` and gives you that. --- # FEFree ```haskell data FEFree r a where Pure :: a -> FEFree r a Impure :: Union r x -> (x -> FEFree r a) -> FEFree r a data Reader i x where Get :: Reader i i data Writer o x where Put :: o -> Writer o () ask :: Member (Reader i) r => Eff r i ask = Impure (inj Get) return ``` ??? Pure is fairly straight forward. Impure takes a concrete union of a single effect and response type, a function from `x` to `FEFree r a` and gives you that. --- # Performance Issues The original `Free` monad while elegant had poor performance. ``` haskell addGet :: Int -> Reader Int Int addGet x = ask >>= \i -> return (i + x) (((return >>> addGet) >>> addGet) >> addGet) 0 ... ((Impure (inj Get) return . (+0)) >>= addGet) >>= addGet ... ``` ??? * bind traverses the left argument but passes around the right argument * performs poorly on left-associated list appends * [31] "Reflections without remorse: Revealing a hidden sequence to speed up monadic reflection" by Oleg --- # Final Result ``` haskell data FEFree r a where Pure :: a -> FEFree r a Impure :: Union r x -> (x -> FEFree r a) -> FEFree r a ``` * with request continuation exposed, represent it in other ways ??? -- ``` haskell instance Monad (FEFree f) where ... Impure fx k' >>= k = Impure fx (k' >>> k) ``` * represent the continuations as a concrete sequence [31] "Reflections without remorse..." --- # Final Result II ``` haskell type Arr r a b = a -> Eff r b ``` * type appreviation for the request continuation. ``` haskell type FTCQueue (m : * -> *) a b ... tsingleton :: (a -> m b) -> FTCQueue m a b (|>) :: FTCQueue m a x -> (x -> m b) -> FTCQueue m a b ``` * type aligned sequence minimal interface `Data.FTCQueue` * enforce the variant, the result type of one function matches the input of the next one. ?? --- # Code Examples Switch to Emacs ??? --- # Performance Evaluation * For deep monad stacks, EE runs in constant time, while MTL takes linear time in the number of layers. Also 40% faster than previous EE based off Free -- * Cost of deep MTL stacks is severe. Implications for design. -- * Memory usage for EE is linear with the number of layers. MTL is quadratic in the number of layers. EE is more memory efficient than MTL -- * State benchmark shows MTL is 30 times faster than EE. Special optimisation passes for MTL State :-) -- * Non optimised version the performance between EE and MTL is comparible ??? State is a special snowflake with dedicated optimisations. Trying to replicate results with 7.10 and 8 --- # Conclusion * Removing fmap constraint * Represent continuations as type aligned list * Externalise fmap * Promising performance vs Free and MTL --- # Examples * Catching IO Exceptions * LogicT, non-determinism with comitted choice * Monadic Regions --- # Resources * [free on hackage](https://hackage.haskell.org/package/free) * [freer on Hackage](https://hackage.haskell.org/package/freer) * [freer source](https://gitlab.com/queertypes/freer/) * [Oleg on Extensible Effects](http://okmij.org/ftp/Haskell/extensible/) --- class: center, middle # Thanks! Tim McGilchrist @lambda_foo Master Commander of Big Data @ Ambiata Thanks!