Monads to the Rescue

Functional Programming Paradigm

• "[I]ts fundamental operation is the application of functions to arguments." - John Hughes
• Pure functions don't have side-effects; they are referentially transparent
• Functions are first-class; higher-order functions take other functions as arguments or return a function as a result

FP Features

• Immutable data
• Lazy evaluation
• Lambda expressions
• Closures
• Pattern matching
• Alternatives to loops
• Partial application/currying

Haskell Example

myList = ["a"] --"a":[]

myFunc :: (Num a, Enum a) => [b] -> Int -> [(a,b)]
myFunc (x:xs) n = foldr (\i acc -> (i,x):acc) [] (take n [1..])

-- foldr :: (a -> b -> b) -> b -> [a] -> b

myFunc myList 3 = 1:2:3:[]
1 (\i acc -> (i,x):acc) 2 (\i acc -> (i,x):acc) 3 (\i acc -> (i,x):acc) []
(1 (\i acc -> (i,x):acc) (2 (\i acc -> (i,x):acc) (3 (\i acc -> (i,x):acc) [])))
(1 (\i acc -> (i,x):acc) (2 (\i acc -> (i,x):acc) [(3,"a")]))
(1 (\i acc -> (i,x):acc) [(2,"a"),(3,"a")])
[(1,"a"),(2,"a"),(3,"a")]

Java 8 Lambdas

public interface Function<T, R> {
    public R apply(T t);
}

public interface BiFunction<T, U, R> {
    R apply(T t, U u);
}

public static List<Integer> map(List<Integer> list, Function<Integer, Integer> func) {
    List<Integer> result = new ArrayList<>();
    for (Integer num : list) {
        result.add(func.apply(num));
    }
    return result;
}

System.out.println(map(Arrays.asList(1, 2, 3), i -> i + 1));
// [2, 3, 4]

FP Benefits

• Ability to reason about program behaviour; can use equational reasoning
• Higher-order functions and lazy evaluation facilitate more modular programs; code reuse
• Removing side-effects aids concurrent programming
• Programs often more succinct
• Automated test generation with tools such as QuickCheck

The Monad Costume

A monad is a structure that puts values in a computational context and implements two functions:

• Return: a → Monad a
  (also known as Unit/Pure)
• Bind: (Monad a, (a → Monad b)) → Monad b
  (also known as FlatMap/SelectMany)

A Few Monads

• Identity Monad
• Maybe/Option Monad
• List Monad
• IO Monad
• State Monad
• Writer Monad
• Reader Monad
• Continuation Monad

Monad Laws

• Left Identity: return x >>= f ≡ f x
• Right Identity: m >>= return ≡ m
• Associativity: (m >>= f) >>= g ≡ m >>= (\x -> f x >>= g)

Maybe/Option Monad

-- data Maybe a = Just a | Nothing 

returnMaybe :: a -> Maybe a
returnMaybe a = Just a

returnMaybe 7
-- Just 7

bindMaybe :: Maybe a -> (a -> Maybe b) -> Maybe b
Nothing `bindMaybe` f = Nothing
Just a `bindMaybe` f = f a

Just 7 `bindMaybe` (\x -> returnMaybe (x+1))
-- Just 8

Nothing `bindMaybe` (\x -> returnMaybe (x+1))
-- Nothing

Just 7 `bindMaybe` (\x -> returnMaybe (x+1)) `bindMaybe` (\y -> returnMaybe (y*5))
-- Just 40

Maybe in Java 8

public abstract class Maybe<A> {

    public abstract <B> Maybe<B> bind(Function<A, Maybe<B>> func);

    public static <A> Nothing<A> nothing() {
        return new Nothing<>();
    }

    public static <A> Just<A> just(A value) {
        return new Just<>(value);
    }

    public static <A> Maybe<A> fromNullable(A value) {
        if (value == null) return nothing();
        else return just(value);
    }
}

private static final class Nothing<A> extends Maybe<A> {

    @Override
    public <B> Maybe<B> bind(Function<A, Maybe<B>> func) {
        return nothing();
    }
}

private static final class Just<A> extends Maybe<A> {

    private final A value;

    private Just(A value) {
        this.value = value;
    }

    @Override
    public <B> Maybe<B> bind(Function<A, Maybe<B>> func) {
        return func.apply(value);
    }
}

Maybe vs Null

public static Maybe<Integer> processIntegerWithMaybe(Maybe<Integer> maybeNum) {
    return maybeNum.bind(x -> just(x + 1)).bind(y -> just(y * 5));
}

public static Integer processInteger(Integer num) {
    if (num == null) return null;
    // Or perhaps throw new IllegalArgumentException("Num cannot be null!");
    Integer incrementedNum = increment(num);
    if (incrementedNum == null) return null;
    return multiplyByFive(incrementedNum);
}

public static Integer increment(Integer num) {
    return (num == null) ? null : num + 1;
}

public static Integer multiplyByFive(Integer num) {
    return (num == null) ? null : num * 5;
}

List Monad

-- picture a type declaration something like: data [a] = [] | a:[a]

returnList :: a -> [a]
returnList a = [a]

returnList "Bar"
-- ["Bar"]

bindList :: [a] -> (a -> [b]) -> [b]
bindList l f = foldr (\x acc -> f x ++ acc) [] l

["Super","Spider","Bar"] `bindList` (\x -> returnList (x ++ "man"))
-- ["Superman","Spiderman","Barman"]

public abstract class List<A> {
    public abstract <B> List<B> bind(Function<A, List<B>> func);

    public abstract List<A> append(List<A> list);

    public abstract <B> B foldRight(BiFunction<A, B, B> func, B acc);

    public static <A> List<A> cons(A value, List<A> list) {
        return new ItemList<A>(value, list);
    }

    public static <A> EmptyList<A> emptyList() {
        return new EmptyList<>(); 
    }

    public static <A> List<A> itemList(A... values) {
        if (values.length == 0) return emptyList();
        List<A> list = emptyList();
        for (int i = values.length - 1; i >= 0; i--) {
            list = cons(values[i], list);
        }
        return list;
    }
}

private static class EmptyList<A> extends List<A> {

    @Override
    public <B> List<B> bind(Function<A, List<B>> func) {
        return emptyList();
    }
}

private static class ItemList<A> extends List<A> {

    private final A value;
    private final List<A> next;

    private ItemList(A value, List<A> next) {
        this.value = value;
        this.next = next;
    }

    @Override
    public <B> List<B> bind(Function<A, List<B>> func) {
        return foldRight((value, acc) -> (func.apply(value)).append(acc), emptyList());
    }
}

Why Monads Are Useful

They help to combat the perils of:

• Code duplication
• Unnecessary complexity
• Poor maintainability

Monadic Heroes

• Identity Monad Can blend in
  anywhere
• Maybe Monad If this hero succeeds,
  you'll know it
• List Monad Can do many things
  at once
• IO Monad Puts world manipulators
  where they belong
• State Monad Always keeps track of
  the state of affairs
• Writer Monad Never forgets
  a detail
• Reader Monad Can tell what
  you're thinking
• Continuation Monad Can travel
  through time
• Parser Monad Speaks every language
  known to computer

Maybe Monad Example Use

currencySupply = [(20, 5), (50, 10), (100, 1)]

-- lookup :: Eq a => a -> [(a, b)] -> Maybe b

unitsLeft :: [(Int, Int)] -> Int -> Int -> Maybe Int
unitsLeft supply val num = (lookup val supply) `bindMaybe` (\u -> if u - num < 0 
  then Nothing else returnMaybe (u - num))

unitsLeft currencySupply 20 3
-- Just 2

unitsLeft currencySupply 20 10
-- Nothing

unitsLeft currencySupply 70 1
-- Nothing

// public static <K, V> Maybe<V> lookup(List<Tuple<K, V>> tupleList, K key) { }

public static Maybe<Integer> unitsLeft(List<Tuple<Integer, Integer>> currencySupply,
  Integer value, Integer unitsWanted) {
    return lookup(currencySupply, value).bind(numUnits -> (numUnits - unitsWanted < 0) 
      ? nothing() : just(numUnits - unitsWanted));
}	

List Monad Example Use

listNotes :: [Int] -> [String] -> [String]
listNotes amts curs = amts `bindList` (\amt -> curs `bindList` (\cur -> 
  returnList (cur ++ (show amt))))

listNotes [20, 50, 100] ["$AU", "$NZ"]
-- ["$AU20","$NZ20","$AU50","$NZ50","$AU100","$NZ100"]	

public static <String> List<String> listNotes(List<Integer> amts, List<String> currs) {
    return amts.bind(amt -> currs.bind(curr -> itemList(curr + amt.toString())));
}

Sequence Maybe Demo

currencySupply = [(20, 5), (50, 10), (100, 1)]

checkComboServiceable :: [(Int, Int)] -> [(Int, Int)] -> Maybe [Int]
checkComboServiceable cur combo = sequenceMaybe (foldr (\(val,num) acc -> 
  (unitsLeft cur val num):acc) [] combo)

checkComboServiceable currencySupply [(20, 1), (50, 1)]
-- Just [4,9]

checkComboServiceable currencySupply [(20, 6), (50, 1)] 
-- Nothing

Sequence List Demo

createValueUnitPairs :: Int -> Int -> [(Int, Int)]
createValueUnitPairs amt val = zip (repeat val) [0..(amt `div` val)]

createValueUnitPairs 70 20
-- [(20, 0), (20, 1), (20, 2), (20, 3)]

combinations :: Int -> [(Int, Int)]
combinations amt = sequenceList (foldr (\val acc -> 
  (createValueUnitPairs amt val):acc) [] [20, 50, 100])

combinations 70
-- [[(20, 0), (50, 0), (100, 0)], 
--  [(20, 0), (50, 1), (100, 0)],
--  [(20, 1), (50, 0), (100, 0)],
--  [(20, 1), (50, 1), (100, 0)],
--  [(20, 2), (50, 0), (100, 0)],
--  [(20, 2), (50, 1), (100, 0)],
--  [(20, 3), (50, 0), (100, 0)],
--  [(20, 3), (50, 1), (100, 0)]]

Implementing Sequence

mapMaybe :: (a -> b) -> Maybe a -> Maybe b
mapMaybe f Nothing = Nothing
mapMaybe f (Just a) = Just (f a)

lift2Maybe :: (a -> b -> c) -> Maybe a -> Maybe b -> Maybe c
lift2Maybe f ma mb = (mapMaybe f ma) `bindMaybe` (`mapMaybe` mb)

sequenceMaybe :: [Maybe a] -> Maybe [a]
sequenceMaybe ls = foldr (\l acc -> lift2Maybe (:) l acc) (returnMaybe []) ls

sequenceMaybe [Just 4, Just 3, Just 7] = 
[Just 4, Just 3, Just 7]                 Just (7:[])
[Just 4, Just 3]                         Just (3:[7])
[Just 4]                                 Just (4:[3,7])
[]                                       Just [4,3,7]

mapList :: (a -> b) -> [a] -> [b]
mapList f l = foldr (\x acc -> (f x):acc) [] l

lift2List :: (a -> b -> c) -> [a] -> [b] -> [c]
lift2List f la lb = (mapList f la) `bindList` (`mapList` lb)lift2Maybe f ma mb = (mapMaybe f ma) `bindMaybe` (`mapMaybe` mb)

sequenceList :: [[a]] -> [[a]]
sequenceList ls = foldr (\l acc -> lift2List (:) l acc) (returnList []) lssequenceMaybe ls = foldr (\l acc -> lift2Maybe (:) l acc) (returnMaybe []) ls

sequenceList [[(20,0),(20,1),(20,2)],[(50,0),(50,1)]] = 
[[(20,0),(20,1),(20,2)],[(50,0),(50,1)]]                [(50,0):[],(50,1):[]]
[[(20,0),(20,1),(20,2)]]                                [(20,0):[(50,0)],(20,0):[(50,1)],
                                                         (20,1):[(50,0)],(20,1):[(50,1)],
                                                         (20,2):[(50,0)],(20,2):[(50,1)]]
[]                                                      [[(20,0),(50,0)],[(20,0),(50,1)],
                                                         [(20,1),(50,0)],[(20,1),(50,1)],
                                                         [(20,2),(50,0)],[(20,2),(50,1)]]

Monad Type Class

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

instance Monad Maybe where
  Nothing >>= f = Nothing
  Just a >>= f = f a  
  return a = Just a

instance Monad [] where
  l >>= f = foldr (\x acc -> f x ++ acc) [] l  
  return x = [x]

fmap :: Monad m => (a -> b) -> m a -> m b
fmap f ma = ma >>= (\a -> return (f a))

liftM2 :: Monad m => (a -> b -> c) -> m a -> m b -> m c
liftM2 f ma mb = (fmap f ma) >>= (`fmap` mb)

sequence :: Monad m => [m a] -> m [a]
sequence l = foldr (m acc -> liftM2 (:) m acc) (return []) l

Links, References and Credits

Code Credits

• Mario Fusco: Javaz
• Tony Morris: Course

Image Credits

• Open Clip Art Library
• HeroMachine
• Book cat
• Hero dog

References

• The Monad Squad
• Monads Are Not Metaphors
• Monads in 15 Minutes

Recommended Reading

• Learn You A Haskell
• Functional Programming in Java
• Typeclassopedia
• Monad Tutorials

Questions?

Slides:
monads.codemiller.com

Code:
github.com/codemiller
/superhero-monads