Free Monad talk @ Bento Miso

free-monads.tpp

--title Rapid Prototyping in Haskell with Free Monads
--author Aaron Levin
--date today
--footer aaron levin (c) 2015 @ Bento Miso
--newpage

--center who?

* Aaron Levin
---
* MSc. Mathematics (pure) / BSc. Engineering Physics
---
* @aaronmblevin
---
* github.com/aaronlevin
---
* (unemployed)
---
* talk to me about: rare records, feels, marxism, existentialism

--newpage

--center we are here to talk about Free Monads

1. the setup
---
2. free stuff
---
3. free monads
---
4. tradeoffs
---
5. ???
---
6. profit

--newpage
--center how do you start?

--beginoutput
module Bento where

  data User = User Int String

  getUser :: Int -> IO User
---
  getUser i = do
---
  -- oh snap where am I storing users?
  -- I need a db lib! which one?! WHAT DB?!?!
--endoutput

--newpage
--center how do you start?

--beginoutput
module Bento where

  data User = User Int String

  program :: (Int -> IO User) -- ^ method to get user from db
          -> Int              -- ^ user id
          -> IO User
---
  program db i = do
    user <- db i
---
    -- oh crap but maybe I should do some logging!

--endoutput

--newpage
--center how do you start?

--beginoutput
module Bento where

  data User = User Int String

---
  program :: (String -> IO ()) -- ^ logger
---
          -> (Int -> IO User)  -- ^ method to get user from db
---
          -> Int               -- ^ user id
---
          -> IO User
---
  program log db i = do
    log "get that user, yo!"
    user <- db i
    log "got the user, yo!"
    return user
---
    -- oh but what about the cache?!

--endoutput

--newpage
--center how do you start?

--beginoutput
module Bento where

  data User = User Int String

---
  program :: (Int -> IO (Maybe User)) -- ^ get from cache
---
          -> (User -> IO ())          -- ^ write to cache
---
          -> (String -> IO ())        -- ^ logger
---
          -> (Int -> IO User)         -- ^ method to get user from db
---
          -> Int                      -- ^ user id
---
          -> IO User
---
  program getCache writeCache log db i = do
    log "get that user, yo!"
    cachedUser <- getCache i
    case cachedUser of
      Nothing -> log "no user for you!" >> do
                   user <- db i
                   log "got user" >> writeCache user >> return user

      (Just u) -> log "got user from cache" >> return u
---
    -- oh but what about async processing for our users?!
--endoutput

--newpage
--center "this is madness." - S. N. Goenka
---

--center "what kind of programmer is this aaron levin?" - you
---

* `(User -> IO ())` is opaque
---
* `program` will grow and grow and grow, making it hard to reason and read.
---
* `ReaderT ( (Int -> IO (Maybe user)), (User -> IO ()), ...)) IO User` is NOT a solution
---
* nor is `ReaderT MyHugeDatatypeOfDependencies IO User`
---
* laws?
---
* where do we assert what each function should do?
---




--center There must be a better way!

--newpage
--center solutions

---
* typeclasses
---
* mtl
---
* other ways (???)
---
* free monads!

--newpage
--center Free Monads sales pitch

Free monads allow you to:

---
- capture your operations as constructors of a Functor
---
- turn that Functor into a Monad and write monadic programs
---
- write more than one "interpreter" that compiles programs in your free monad to some value.
---
  - interpreters can: be pure
---
  - interpreters can: be random
---
  - interpreters can: run IO
---
  - interpreters give you freedom!

--newpage













--center free stuff

--newpage
--center let's play a game!
---

I give you a Set, and you give me a group!

---
(reminder: group = a Set S, an operation (*) :: SxS -> S, identity element, inverses, laws)
---

S = {a,b,c,d}

what is my group?

---
G = S U {a`, b`, c`, d`} U {e}

---
where, we define:

- a * a` = e = a` * a
- e * g = g * e = g forall g in G
- g * h = gh forall g,h in G

---

- G is the "free group generated by S"
- G is the set of all "expressions" / "words" / "terms" of S and

---
we can do this for any Set S!

--newpage
--center let's play a game!
---

I give you a type in Hask, you give me a Monoid!

---
(reminder: monoid = a type with an operation `(*) :: a -> a -> a`, identity element, laws)
---

- answer: list!
---
- For any type a, [a] is a monoid!
- (*) = (:)
- identity = []

--newpage
--center free structures

- Free groups
- Free monoids

Why Free?

- "Free X for S" => 'free from assumptions about the underlying object (S)'.
- (this is my interpretation, ymmv)

--newpage
--center let's play a game!
---

I give you a Functor f, you give me a Monad!

---
reminder:

--beginoutput

  -- for f of kind * -> *

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

---
  class Functor f => Applicative f where
      pure  :: a -> f a
      (<*>) :: f (a -> b) -> f a -> f b

---
  class Applicative f => Monad f where
      (>>=) :: f a -> f (a ->  f b) -> f b
--endoutput

--newpage
--center useful neumonic (sp?)

--beginoutput

Functor:       (a -> b) -----> f a -> f b
Applicative: f (a -> b) -----> f a -> f b
Monad:       (a -> f b) -----> f a -> f b

--endoutput

i digress...

--newpage
--center let's play a game!
---

I give you a Functor f, you give me a monad!
---

--beginoutput

data Free f a = Pure a                -- ^ a pure value
              | Free ( f (Free f a) ) -- ^ a `Free f a` value held in f
--endoutput

---

* Functor f "holds" the next "next' computation
---
  * if `f` has interesting structure, computations will get interesting!
---
* This is just one encoding.
---
* There are several, each with different tradeoffs (later).

--newpage
--center claim: `Free f a` is a functor

--beginoutput

instance Functor f => Functor (Free f) where
    fmap :: (a -> b) -> Free f a -> Free f b
    fmap f (Pure a) = Pure (f a)
    fmap f (Free fa) = Free (fmap (fmap f) fa)        -- ^ remember, `f` is a functor!

---

instance Functor f => Applicative (Free f) where
    pure :: a -> Free f a
    pure a = Pure a

    (<*>) :: Free f (a -> b) -> Free f a -> Free f b
    (Pure g)   <*> fa = fmap g fa
    (Free fab) <*> fa = Free $ fmap (<*> fa) fab

---

instance Functor f => Monad (Free f) where
    (>>=) :: (a -> Free f b) -> Free f a -> Free f b
    (Pure a)  >>= afb = afb a
    (Free fa) >>= afb = Free $ fmap (>>= afb) fa

--endoutput

--newpage
--center now that you're convinced, some examples!

What is: Free [] a?

--beginoutput

  myProgram :: Free [] a
  myProgram = ...

  -- elsewhere
  case myProgram of
    Pure a -> ...
    (Free [as :: Free [] a]) -> ...

--endoutput

---

- This looks a lot like a tree!

---

What is: Free Empty a?

- `data Empty a = Empty`
- Pure a or Free Empty
- ismorphic to `Identity a`

---

What is: Free Identify a?

- `newtype Identity a = Identity { it :: a }`
- Free (Identity (x :: (Free Identity a)))

---

What is: Free (Const c) a?

- `newtype Const c a = Const { getConst :: c }`
- Pure a
- Free ( c :: Const c (Free (Const c) a) )
---
- this ignores evertyhing instruction the first `Pure`!

---

What is: Free Maybe a?

- `data Maybe a = Nothing | Just a`
- either: `Free Nothing` or `Free (Just (x :: Free Maybe a))`
- inserting `Free Nothing` is kind of like putting in a breakpoint!

--newpage
--center But how do I use it in real life?

Let's use a Free Monad to model a Key-Value store!

--beginoutput

  -- operations in our key-value store!
  data KV k v next = Get k (Maybe v -> next)
                   | Set k v next

---
  -- trust me, KV k v a is a functor!
  instance Functor (KV k v) where
      fmap f (Get k g) = Get k (f <$> g)
      fmap f (Set k v n) = Set k v (f n)

---
  -- smart constructur for 'get'
  getKV :: k -> Free (KV k v) (Maybe v)
  getKV k = Free $ Get k Pure

---
  -- smart constructor for 'set'
  setKV :: k -> v -> Free (KV k v) ()
  setKV k v = Free $ Set k v (Pure ())

---
  -- a wrapper to check a value from the cache.
  getCached :: (a -> v) -> k -> a -> Free (KV k v) v
  getCached createV k a = do
      maybeV <- getKV k
      case maybeV of
          Nothing -> let v = createV a in setKV k v >> return v
          Just v  -> return v

--endoutput


--newpage
--center a Pure interpreter!


--beginoutput
pureKV :: Ord k => Free (KV k v) a -> State (Map k v) a
pureKV (Pure a)           = return a
pureKV (Free (Get k g))   = fmap (g . lookup k) get >>= pureKV
pureKV (Free (Set k v n)) = modify (insert k v) >> pureKV n
--endoutput

--newpage
--center an interpreter that uses Redis!


--beginoutput
pureKV :: Ord k => Free (KV k v) a -> IO a
pureKV (pure a)           = return a
pureKV (Free (Get k g))   = redisGet k >>= pureKV . g
pureKV (Free (Set k v n)) = redisSet k v >> pureKV n
--endoutput

--newpage
--center Yeah, but how do I use this for prototyping?

recall:

--beginoutput
  program :: (Int -> IO (Maybe User)) -- ^ get from cache
          -> (User -> IO ())          -- ^ write to cache
          -> (String -> IO ())        -- ^ logger
          -> (Int -> IO User)         -- ^ method to get user from db
          -> Int                      -- ^ user id
          -> IO User
--endoutput

becomes:

--beginoutput
  program :: Int -> Free MyFreeMonad User
  program = do ...

  log :: String -> Free MyFreeMonad ()
  getCache :: Int -> Free MyFreeMonad (Maybe User)
  ...

  run :: (forall a. Free MyFreeMonad a -> IO a) -> IO ()
  run interpreter = interpreter program >> print "done!"
--endoutput

--newpage
--center what is this MyFreeMonad business?

* We can roll everything up into one giant functor, but then we're not anywhere better.
---
* We can take co-products of Functors!

---
--beginoutput

newtype Coproduct f g a = Coproduct { getCoproduct :: Either (f a) (g a) }

--endoutput

* this is a functor, so we can make a free monad from it!
---

* you can apply type-level magic to make a "finally initial" encoding (See A. Cowley)

--exec google-chrome-stable "http://www.seas.upenn.edu/~acowley/papers/hocl.pdf"

---

* Free Monads can be fused! See "Fusion for Free" by N. Wu & T. Schrijvers

--exec google-chrome-stable "http://people.cs.kuleuven.be/~tom.schrijvers/Research/papers/mpc2015.pdf"

--newpage
--center pros / cons

* pro: many interpters, one language!
---
* con: you rarely need 'pure' interpreters

---
* pro: wrap a service! one free language, client interpreter + server interpreter!
---
* con: not all things can be modeled in this way.

---
* pro: love monads!
---
* con: monadic bind has a quadradic cost!
---
* solution: Church-encoded free monad! (continuation passing instead of induction)

--newpage
--center Free Monads in the real world.

hello
---

--exec google-chrome-stable "https://bitbucket.org/aterica/galene-common/src/fba985c66521bafe5fd23098a03ee619c6f25403/src/Galene/Common/Free/Algebra.hs?at=master" "https://bitbucket.org/aterica/galene-data/src/269db08dfb58992d35662bbf3c6d4e365c08b705/src/Galene/Data/Free.hs?at=master"

--newpage










--center fin

If you want to "view" the presentation, download tpp and use it.