Functors, Applicative Functors and Monoids

{{% section %}}

Functors, Applicative Functors and Monoids

@wusyong, 吳昱緯

{{% /section %}}

---

{{% section %}}

Functors redux

fmap :: (a -> b) -> f a -> f b

give me a function that takes an a and returns a b and a box with an a (or several of them) inside it and I'll give you a box with a b (or several of them) inside it.

---

computational context

The context might be that the computation can have a value or it might have failed (Maybe and Either a) or that there might be more values (lists), stuff like that.

---

Functor on IO

instance Functor IO where  
    fmap f action = do  
        result <- action  
        return (f result)  

---

Functor on IO

main = do line <- getLine   
            let line' = reverse line  
            putStrLn $ "You said " ++ line' ++ " backwards!"  
            putStrLn $ "Yes, you really said" ++ line' ++ " backwards!"  

main = do line <- fmap reverse getLine  
          putStrLn $ "You said " ++ line ++ " backwards!"  
          putStrLn $ "Yes, you really said" ++ line ++ " backwards!"  

---

Functor on IO

fmap :: (a -> b) -> IO a -> IO b

---

Functor on IO

If you ever find yourself binding the result of an I/O action to a name, only to apply a function to that and call that something else, consider using fmap,

import Data.Char  
import Data.List  
  
main = do line <- fmap (intersperse '-' . reverse . map toUpper) getLine  
          putStrLn line

$ runhaskell fmapping_io.hs  
hello there  
E-R-E-H-T- -O-L-L-E-H

---

(->) r

The function type r -> a can be rewritten as (->) r a

---

functions functors

Control.Monad.Instances

instance Functor ((->) r) where  
    fmap f g = (\x -> f (g x))

fmap :: (a -> b) -> ((->) r a) -> ((->) r b)

fmap :: (a -> b) -> (r -> a) -> (r -> b)

---

Function composition

We pipe the output of r -> a into the input of a -> b to get a function r -> b

instance Functor ((->) r) where  
    fmap = (.)

---

using fmap over functions

ghci> :t fmap (*3) (+100)  
fmap (*3) (+100) :: (Num a) => a -> a  
ghci> fmap (*3) (+100) 1  
303  
ghci> (*3) `fmap` (+100) $ 1  
303  
ghci> (*3) . (+100) $ 1  
303  
ghci> fmap (show . (*3)) (*100) 1  
"300"

---

lifting a function

takes an a -> b function and returns a function f a -> f b

ghci> :t fmap (*2)  
fmap (*2) :: (Num a, Functor f) => f a -> f a  
ghci> :t fmap (replicate 3)  
fmap (replicate 3) :: (Functor f) => f a -> f [a]

When we say a functor over numbers, you can think of that as a functor that has numbers in it. That functor can be a list, a Maybe , an Either String.

---

lifting a function

The type fmap (replicate 3) :: (Functor f) => f a -> f [a] means that the function will work on any functor.

ghci> fmap (replicate 3) [1,2,3,4]  
[[1,1,1],[2,2,2],[3,3,3],[4,4,4]]  
ghci> fmap (replicate 3) (Just 4)  
Just [4,4,4]  
ghci> fmap (replicate 3) (Right "blah")  
Right ["blah","blah","blah"]  
ghci> fmap (replicate 3) Nothing  
Nothing  
ghci> fmap (replicate 3) (Left "foo")  
Left "foo"

---

functor laws

Calling fmap on a functor should just map a function over the functor.

---

First law

The first functor law states that if we map the id function over a functor, the functor that we get back should be the same as the original functor.

fmap id = id (\x -> x)

ghci> fmap id (Just 3)  
Just 3  
ghci> id (Just 3)  
Just 3  
ghci> fmap id [1..5]  
[1,2,3,4,5]  
ghci> id [1..5]  
[1,2,3,4,5]  
ghci> fmap id []  
[]  
ghci> fmap id Nothing  
Nothing

---

Second law

The second law says that composing two functions and then mapping the resulting function over a functor should be the same as first mapping one function over the functor and then mapping the other one.

fmap (f . g) = fmap f . fmap g

fmap (f . g) F = fmap f (fmap g F)

---

pathological example

data CMaybe a = CNothing | CJust Int a deriving (Show)

ghci> CNothing  
CNothing  
ghci> CJust 0 "haha"  
CJust 0 "haha"  
ghci> :t CNothing  
CNothing :: CMaybe a  
ghci> :t CJust 0 "haha"  
CJust 0 "haha" :: CMaybe [Char]  
ghci> CJust 100 [1,2,3]  
CJust 100 [1,2,3]

---

Make it instance of functor

instance Functor CMaybe where  
    fmap f CNothing = CNothing  
    fmap f (CJust counter x) = CJust (counter+1) (f x)

ghci> fmap (++"ha") (CJust 0 "ho")  
CJust 1 "hoha"  
ghci> fmap (++"he") (fmap (++"ha") (CJust 0 "ho"))  
CJust 2 "hohahe"  
ghci> fmap (++"blah") CNothing  
CNothing

---

It violtes the law

ghci> fmap id (CJust 0 "haha")  
CJust 1 "haha"  
ghci> id (CJust 0 "haha")  
CJust 0 "haha"

{{% /section %}}

---

{{% section %}}

Applicative functors

Applicative typeclass, in the Control.Applicative module

---

function wrapped in functor

ghci> :t fmap (++) (Just "hey")  
fmap (++) (Just "hey") :: Maybe ([Char] -> [Char])  
ghci> :t fmap compare (Just 'a')  
fmap compare (Just 'a') :: Maybe (Char -> Ordering)  
ghci> :t fmap compare "A LIST OF CHARS"  
fmap compare "A LIST OF CHARS" :: [Char -> Ordering]  
ghci> :t fmap (\x y z -> x + y / z) [3,4,5,6]  
fmap (\x y z -> x + y / z) [3,4,5,6] :: (Fractional a) => [a -> a -> a]

---

Make use of it

ghci> let a = fmap (*) [1,2,3,4]  
ghci> :t a  
a :: [Integer -> Integer]  
ghci> fmap (\f -> f 9) a  
[9,18,27,36]

...but the fuction will not be compatible between like Just (3 *) and Just 5

---

Applicative typeclass

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

pure should take a value of any type and return an applicative functor with that value inside it.

Whereas fmap takes a function and a functor and applies the function inside the functor, <*> takes a functor that has a function in it and another functor and sort of extracts that function from the first functor and then maps it over the second one.

---

Applicative instance implementation for Maybe

instance Applicative Maybe where  
    pure = Just  
    Nothing <*> _ = Nothing  
    (Just f) <*> something = fmap f something

ghci> Just (+3) <*> Just 9  
Just 12  
ghci> pure (+3) <*> Just 10  
Just 13  
ghci> pure (+3) <*> Just 9  
Just 12  
ghci> Just (++"hahah") <*> Nothing  
Nothing  
ghci> Nothing <*> Just "woot"  
Nothing

---

Applicative instance implementation for Maybe

With normal functors, you can just map a function over a functor and then you can't get the result out in any general way, even if the result is a partially applied function. Applicative functors, on the other hand, allow you to operate on several functors with a single function.

ghci> pure (+) <*> Just 3 <*> Just 5  
Just 8  
ghci> pure (+) <*> Just 3 <*> Nothing  
Nothing  
ghci> pure (+) <*> Nothing <*> Just 5  
Nothing

---

applicative laws

pure f <*> x equals fmap f x

Instead of writing pure f <> x <> y <> ..., we can write fmap f x <> y <*> ...

---

<$>

just fmap as an infix operator

(<$>) :: (Functor f) => (a -> b) -> f a -> f b  
f <$> x = fmap f x

we can write f <$> x <> y <> z (like f x y z in normal value)

---

<$>

ghci> (++) <$> Just "johntra" <*> Just "volta"  
Just "johntravolta"

ghci> (++) "johntra" "volta"  
"johntravolta"

---

Applicative instance implementation for List

instance Applicative [] where  
    pure x = [x]  
    fs <*> xs = [f x | f <- fs, x <- xs]

ghci> pure "Hey" :: [String]  
["Hey"]  
ghci> pure "Hey" :: Maybe String  
Just "Hey"

---

Applicative instance implementation for List

ghci> [(*0),(+100),(^2)] <*> [1,2,3]  
[0,0,0,101,102,103,1,4,9]

ghci> [(+),(*)] <*> [1,2] <*> [3,4]  
[4,5,5,6,3,4,6,8]

ghci> (++) <$> ["ha","heh","hmm"] <*> ["?","!","."]  
["ha?","ha!","ha.","heh?","heh!","heh.","hmm?","hmm!","hmm."]

---

good replacement for list comprehensions

ghci> [ x*y | x <- [2,5,10], y <- [8,10,11]]     
[16,20,22,40,50,55,80,100,110]

ghci> (*) <$> [2,5,10] <*> [8,10,11]  
[16,20,22,40,50,55,80,100,110]

ghci> filter (>50) $ (*) <$> [2,5,10] <*> [8,10,11]  
[55,80,100,110]

---

Applicative instance implementation for IO

instance Applicative IO where  
    pure = return  
    a <*> b = do  
        f <- a  
        x <- b  
        return (f x)

(<*>) :: IO (a -> b) -> IO a -> IO b

---

Applicative instance implementation for IO

myAction :: IO String  
myAction = do  
    a <- getLine  
    b <- getLine  
    return $ a ++ b
-- which can be
myAction :: IO String  
myAction = (++) <$> getLine <*> getLine
-- which can also do this
main = do  
    a <- (++) <$> getLine <*> getLine  
    putStrLn $ "The two lines concatenated turn out to be: " ++ a 

---

Applicative instance implementation for (->) r

instance Applicative ((->) r) where  
    pure x = (\_ -> x)  
    f <*> g = \x -> f x (g x)

ghci> (pure 3) "blah"  
3

---

Applicative instance implementation for (->) r

ghci> :t (+) <$> (+3) <*> (*100)  
(+) <$> (+3) <*> (*100) :: (Num a) => a -> a  
ghci> (+) <$> (+3) <*> (*100) $ 5  
508

ghci> (\x y z -> [x,y,z]) <$> (+3) <*> (*2) <*> (/2) $ 5  
[8.0,10.0,2.5]

---

Applicative instance implementation for ziplist

ZipList is a list type can make [(+3),(*2)] <*> [1,2] become [1 + 3, 2 * 2]

instance Applicative ZipList where  
        pure x = ZipList (repeat x)  
        ZipList fs <*> ZipList xs = ZipList (zipWith (\f x -> f x) fs xs)

---

getZipList to extract a raw list out of a ziplist

The (,,) function is the same as \x y z -> (x,y,z). Also, the (,) function is the same as \x y -> (x,y).

ghci> getZipList $ (+) <$> ZipList [1,2,3] <*> ZipList [100,100,100]  
[101,102,103]  
ghci> getZipList $ (+) <$> ZipList [1,2,3] <*> ZipList [100,100..]  
[101,102,103]  
ghci> getZipList $ max <$> ZipList [1,2,3,4,5,3] <*> ZipList [5,3,1,2]  
[5,3,3,4]  
ghci> getZipList $ (,,) <$> ZipList "dog" <*> ZipList "cat" <*> ZipList "rat"  
[('d','c','r'),('o','a','a'),('g','t','t')]

---

liftA2: applies a function between two applicatives

liftA2 :: (Applicative f) => (a -> b -> c) -> f a -> f b -> f c  
liftA2 f a b = f <$> a <*> b

ghci> fmap (\x -> [x]) (Just 4)  
Just [4]

ghci> liftA2 (:) (Just 3) (Just [4])  
Just [3,4]  
ghci> (:) <$> Just 3 <*> Just [4]  
Just [3,4]

---

Practice: sequenceA

Let's try implementing a function that takes a list of applicatives and returns an applicative that has a list as its result value.

sequenceA :: (Applicative f) => [f a] -> f [a]  
sequenceA [] = pure []  
sequenceA (x:xs) = (:) <$> x <*> sequenceA xs
-- which can be
sequenceA :: (Applicative f) => [f a] -> f [a]  
sequenceA = foldr (liftA2 (:)) (pure [])

---

Practice: sequenceA

ghci> sequenceA [Just 3, Just 2, Just 1]  
Just [3,2,1]  
ghci> sequenceA [Just 3, Nothing, Just 1]  
Nothing  
ghci> sequenceA [(+3),(+2),(+1)] 3  
[6,5,4]  
ghci> sequenceA [[1,2,3],[4,5,6]]  
[[1,4],[1,5],[1,6],[2,4],[2,5],[2,6],[3,4],[3,5],[3,6]]  
ghci> sequenceA [[1,2,3],[4,5,6],[3,4,4],[]]  
[]

---

Practice: sequenceA

ghci> map (\f -> f 7) [(>4),(<10),odd]  
[True,True,True]  
ghci> and $ map (\f -> f 7) [(>4),(<10),odd]  
True

ghci> sequenceA [(>4),(<10),odd] 7  
[True,True,True]  
ghci> and $ sequenceA [(>4),(<10),odd] 7  
True

---

Practice: sequenceA

ghci> sequenceA [[1,2,3],[4,5,6]]  
[[1,4],[1,5],[1,6],[2,4],[2,5],[2,6],[3,4],[3,5],[3,6]]  
ghci> [[x,y] | x <- [1,2,3], y <- [4,5,6]]  
[[1,4],[1,5],[1,6],[2,4],[2,5],[2,6],[3,4],[3,5],[3,6]]  
ghci> sequenceA [[1,2],[3,4]]  
[[1,3],[1,4],[2,3],[2,4]]  
ghci> [[x,y] | x <- [1,2], y <- [3,4]]  
[[1,3],[1,4],[2,3],[2,4]]  
ghci> sequenceA [[1,2],[3,4],[5,6]]  
[[1,3,5],[1,3,6],[1,4,5],[1,4,6],[2,3,5],[2,3,6],[2,4,5],[2,4,6]]  
ghci> [[x,y,z] | x <- [1,2], y <- [3,4], z <- [5,6]]  
[[1,3,5],[1,3,6],[1,4,5],[1,4,6],[2,3,5],[2,3,6],[2,4,5],[2,4,6]]

---

Practice: sequenceA

ghci> sequenceA [getLine, getLine, getLine]  
heyh  
ho  
woo  
["heyh","ho","woo"]

---

Applicative laws

• pure f <*> x = fmap f x
• pure id <*> v = v
• pure (.) <*> u <*> v <*> w = u <*> (v <*> w)
• pure f <*> pure x = pure (f x)
• u <*> pure y = pure ($ y) <*> u

{{% /section %}}

---

{{% section %}}

The newtype keyword

When using newtype, you're restricted to just one constructor with one field.

newtype ZipList a = ZipList { getZipList :: [a] }
newtype CharList = CharList { getCharList :: [Char] } deriving (Eq, Show)

ghci> CharList "this will be shown!"  
CharList {getCharList = "this will be shown!"}  
ghci> CharList "benny" == CharList "benny"  
True  
ghci> CharList "benny" == CharList "oisters"  
False

---

The newtype keyword

CharList :: [Char] -> CharList

getCharList :: CharList -> [Char]

---

Using newtype to make type class instances

newtype Pair b a = Pair { getPair :: (a,b) }
instance Functor (Pair c) where
    fmap :: (a -> b) -> Pair c a -> Pair c b
    fmap f (Pair (x,y)) = Pair (f x, y)

ghci> getPair $ fmap (*100) (Pair (2,3))  
(200,3)  
ghci> getPair $ fmap reverse (Pair ("london calling", 3))  
("gnillac nodnol",3)

---

On newtype laziness

As we know many functions/types are lazy

ghci> undefined  
*** Exception: Prelude.undefined

ghci> head [3,4,5,undefined,2,undefined]  
3

---

On newtype laziness

But not data type

data CoolBool = CoolBool { getCoolBool :: Bool }
helloMe :: CoolBool -> String  
helloMe (CoolBool _) = "hello"

ghci> helloMe undefined  
"*** Exception: Prelude.undefined

---

On newtype laziness

Use newtype for laziness

newtype CoolBool = CoolBool { getCoolBool :: Bool }

ghci> helloMe undefined  
"hello"

---

type vs. newtype vs. data

• type for type alias
• newtype for wrapping existing type. Mainly for making instance of typeclass
• data for creating whole new type

{{% /section %}}

---

{{% section %}}

Monoids

Monoids in math:

ghci> 4 * 1  
4  
ghci> 1 * 9  
9  
ghci> [1,2,3] ++ []  
[1,2,3]  
ghci> [] ++ [0.5, 2.5]  
[0.5,2.5]
ghci> (3 * 2) * (8 * 5)  
240  
ghci> 3 * (2 * (8 * 5))  
240  
ghci> "la" ++ ("di" ++ "da")  
"ladida"  
ghci> ("la" ++ "di") ++ "da"  
"ladida"

---

Monoids properties

It seems that both * together with 1 and ++ along with [] share some common properties

• The function takes two parameters.
• The parameters and the returned value have the same type.
• There exists such a value that doesn't change other values when used with the binary function.

---

Monoid typeclass

class Monoid m where  
    mempty :: m  
    mappend :: m -> m -> m  
    mconcat :: [m] -> m  
    mconcat = foldr mappend mempty

---

Monoid laws

• mempty mappend x = x
• x mappend mempty = x
• (x mappend y) mappend z = x mappend (y mappend z)

---

Lists are monoids

instance Monoid [a] where  
    mempty = []  
    mappend = (++)

ghci> [1,2,3] `mappend` [4,5,6]  
[1,2,3,4,5,6]  
ghci> ("one" `mappend` "two") `mappend` "tree"  
"onetwotree"  
ghci> "one" `mappend` ("two" `mappend` "tree")  
"onetwotree"  
ghci> "one" `mappend` "two" `mappend` "tree"  
"onetwotree"  
ghci> "pang" `mappend` mempty  
"pang"  
ghci> mconcat [[1,2],[3,6],[9]]  
[1,2,3,6,9]  
ghci> mempty :: [a]  
[]

---

Product type

newtype Product a =  Product { getProduct :: a }  
    deriving (Eq, Ord, Read, Show, Bounded)

instance Num a => Monoid (Product a) where  
    mempty = Product 1  
    Product x `mappend` Product y = Product (x * y)

ghci> getProduct $ Product 3 `mappend` Product 9  
27  
ghci> getProduct $ Product 3 `mappend` mempty  
3  
ghci> getProduct $ Product 3 `mappend` Product 4 `mappend` Product 2  
24  
ghci> getProduct . mconcat . map Product $ [3,4,2]  
24

---

Sum type

ghci> getSum $ Sum 2 `mappend` Sum 9  
11  
ghci> getSum $ mempty `mappend` Sum 3  
3  
ghci> getSum . mconcat . map Sum $ [1,2,3]  
6

---

Any and All

Basically means OR/AND. Here's Any type:

newtype Any = Any { getAny :: Bool }  
    deriving (Eq, Ord, Read, Show, Bounded)

instance Monoid Any where  
        mempty = Any False  
        Any x `mappend` Any y = Any (x || y)

ghci> getAny $ Any True `mappend` Any False  
True  
ghci> getAny $ mempty `mappend` Any True  
True  
ghci> getAny . mconcat . map Any $ [False, False, False, True]  
True  
ghci> getAny $ mempty `mappend` mempty  
False

---

Any and All

And here's All tytpe

newtype All = All { getAll :: Bool }  
        deriving (Eq, Ord, Read, Show, Bounded)

instance Monoid All where  
        mempty = All True  
        All x `mappend` All y = All (x && y)

ghci> getAll $ mempty `mappend` All True  
True  
ghci> getAll $ mempty `mappend` All False  
False  
ghci> getAll . mconcat . map All $ [True, True, True]  
True  
ghci> getAll . mconcat . map All $ [True, True, False]  
False

---

The Ordering monoid

instance Monoid Ordering where  
    mempty = EQ  
    LT `mappend` _ = LT  
    EQ `mappend` y = y  
    GT `mappend` _ = GT

ghci> LT `mappend` GT  
LT  
ghci> GT `mappend` LT  
GT  
ghci> mempty `mappend` LT  
LT  
ghci> mempty `mappend` GT  
GT

---

The Ordering monoid

lengthCompare :: String -> String -> Ordering  
lengthCompare x y = let a = length x `compare` length y   
                        b = x `compare` y  
                    in  if a == EQ then b else a
-- which can be
import Data.Monoid  
  
lengthCompare :: String -> String -> Ordering  
lengthCompare x y = (length x `compare` length y) `mappend`  
                    (x `compare` y)

ghci> lengthCompare "zen" "ants"  
LT  
ghci> lengthCompare "zen" "ant"  
GT

---

Maybe the monoid

instance Monoid a => Monoid (Maybe a) where  
    mempty = Nothing  
    Nothing `mappend` m = m  
    m `mappend` Nothing = m  
    Just m1 `mappend` Just m2 = Just (m1 `mappend` m2)

ghci> Nothing `mappend` Just "andy"  
Just "andy"  
ghci> Just LT `mappend` Nothing  
Just LT  
ghci> Just (Sum 3) `mappend` Just (Sum 4)  
Just (Sum {getSum = 7})

---

Maybe the monoid: First as example

fromChunks takes a list of strict bytestrings and converts it to a lazy bytestring. toChunks takes a lazy bytestring and converts it to a list of strict ones.

newtype First a = First { getFirst :: Maybe a }  
    deriving (Eq, Ord, Read, Show)

instance Monoid (First a) where  
    mempty = First Nothing  
    First (Just x) `mappend` _ = First (Just x)  
    First Nothing `mappend` x = x

ghci> getFirst $ First (Just 'a') `mappend` First (Just 'b')  
Just 'a'  
ghci> getFirst $ First Nothing `mappend` First (Just 'b')  
Just 'b'  
ghci> getFirst $ First (Just 'a') `mappend` First Nothing  
Just 'a'

ghci> getFirst . mconcat . map First $ [Nothing, Just 9, Just 10]  
Just 9

---

Using monoids to fold data structures

Whereas foldr takes a list and folds it up, the foldr from Data.Foldable typeclass accepts any type that can be folded up, not just lists!

import qualified Foldable as F

ghci> :t foldr  
foldr :: (a -> b -> b) -> b -> [a] -> b  
ghci> :t F.foldr  
F.foldr :: (F.Foldable t) => (a -> b -> b) -> b -> t a -> b

ghci> foldr (*) 1 [1,2,3]  
6  
ghci> F.foldr (*) 1 [1,2,3]  
6

---

Making instance of Foldable

Implement foldMap function: foldMap :: (Monoid m, Foldable t) => (a -> m) -> t a -> m

data Tree a = Empty | Node a (Tree a) (Tree a) deriving (Show, Read, Eq)

instance F.Foldable Tree where  
    foldMap f Empty = mempty  
    foldMap f (Node x l r) = F.foldMap f l `mappend`  
                             f x           `mappend`  
                             F.foldMap f r

---

Making instance of Foldable

testTree = Node 5  
            (Node 3  
                (Node 1 Empty Empty)  
                (Node 6 Empty Empty)  
            )  
            (Node 9  
                (Node 8 Empty Empty)  
                (Node 10 Empty Empty)  
            )
        
ghci> F.foldl (+) 0 testTree  
42  
ghci> F.foldl (*) 1 testTree  
64800

---

Making instance of Foldable

ghci> getAny $ F.foldMap (\x -> Any $ x == 3) testTree  
True
ghci> getAny $ F.foldMap (\x -> Any $ x > 15) testTree  
False
ghci> F.foldMap (\x -> [x]) testTree  
[1,3,6,5,8,9,10]

{{% /section %}}