the Patch-Tag blog

A wise haskell hacker said you don’t need to understand monads to use em, and this I find to be mostly true.

You don’t need to understand category theory either.

Lately though, I’ve been trying to deepen my intuition a bit anyway.

This is something I wrote lately that I keep revisiting when thinking about monadic machinery: specificaly the bind, left bind, join and return operators, as well as the pure and fmap operators used with Applicative and Functor.

How do these funny named operators fit together and what are they good for?

Concrete examples help, and for now my concrete example is the list monad. Pure and return do the same thing, since the list monad is also an applicative functor: just :[], put in a list. Fmap is, of course, map. I find myself using left bind more often than bind in my code, and in the list monad left bind is concatMap. Oh, and join is concat. You don’t hear about join much, but it turns out to be important when understanding monads categorically. Join takes m (m a) -> m (a), ie two monad nestings deep to one. Mysterious, eh?

If any of this rang a bell and you have been scratching your head for a simple bit of code you can stare at and play around with in your head, you may enjoy this.

To start with, try out f1 xs, f2 xs, f3 xs, u1 xs, u2 xs in ghci, just to see what’s giong on. Then… well, just read the code for suggestions about how to learn from it.

{-# LANGUAGE NoMonomorphismRestriction #-}
import Control.Applicative
import Control.Monad
import Test.QuickCheck

-- inspired by mixing monads, arrows, and applicative functors
-- http://yumagene.livejournal.com/2245.html
--  http://www.sfu.ca/~ylitus/courses/cmpt481731/slides/FPjul9.pdf

-- An interesting thing for learning you can do in your head:
-- replace (=<<), (<$>), and join with the list equivalents, after staring at this for a while.
-- The equivalents:
--   (=<<): concatMap
--   (<$>): map
--   join: concat
-- doing that helped me understand monad/functor machinery better.

-- a list of lists, to illustrate "burrowing in" two levels with (<$>) . (<$>) and other machinery
xs :: [[Integer]]
xs = [[2,4,6],[7..13],[10,20..50]] 

t = sequence_ [tflattened, tunflattened]

infs = repeat [1,2,3] -- the f functions produce output fine with infinite lists as well.

-- you lose the "list of lists" structure, because (=<<)/join are flattening
f1 els = (=<<) ((<$>) (* 3)) $ els
f2 els = join . ((<$>) $ (<$>) (* 3)) $ els
f3 els = join . (((<$>) . (<$>)) (*3)) $ els -- same thing, note the burrowing in two levels thing.
tflattened = quickCheck p
  where p :: [[Integer]] -> Bool
        p xs = (f1 xs) == (f2 xs) && (f1 xs) == (f3 xs)

-- if you want to preserve the list of lists structure, compose your monadic function with (pure .) behind it.
u1 els = (=<<) (pure . (<$>) (* 3)) els
u2 els = join . ((pure . (<$>) (* 3)) <$>) $ els

tunflattened = quickCheck p
  where p :: [[Integer]] -> Bool
        p xs = u1 xs == u2 xs


--flatten=join


-- Questions/Lessons Learned: 

-- Q0: are f1 and f2, and u1 and u2 the same function?
-- by same I mean
-- a) produce the same output for the same input everywhere (appears to be true for list monad)
-- b) computed the same way, one is not more efficient than the other
-- Answer to Q0: yes, pretty much.

-- Q1. what is the relationship between bind and join?
-- A. -- (=<<) f mx = join . (f <$>)  $ mx -- bind could have been defined this way, though in practice it's not.
  --  translation : -- functor map your monad function over the monad value (<$> f)
                    -- and pop one level of structure (join)
                    -- in a list, (=<<) f is concat . (map f)
-- Q. can this be proved using monad/functor/applicative laws or similar?
-- A. not proved exactly, but more like trivially true assuming the monad laws hold for your structure, which they should. 
--   (Monad laws should be proven separately for each structure you define a monad laws. They *are* proven for list, maybe, maybe others.
-- Q. does ((<$>) . (<$>)) have some interesting roles in reasoning about monads or applicatives?
-- A. Burrow in two levels before applying the function.


-- (=<<) is concatMap in list context. join is concat in list context.