Lazy Evaluation

Why does `a ++ (b ++ c)` faster than `a ++ (b ++ c)`?

++ traverses the left parameter and append each item of it to the right parameter which leads to a worse performance when using the wrong association.

In short, the bad association gives a quadratic amount of traversal as it redoes all the traversals it has already done, plus one more, at each invocation of (++), while the good association traverses each list at most once.

Functor

What's the definition of Functor?

Functor is a type class, the definition of Functor is:

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

Each Functor f is a type (type constructor) with exactly one type slot.

The operator that Functor f support is fmap.

`Instance Functor Maybe` or `Instance Functor (Maybe m)`?

Functor is a special type class, for we define Functor type class as:

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

In classical type classes, which is defined such as following:

class Eq a where 
	(==) :: a -> a -> Bool 
	(/=) :: a -> a -> Bool 
	x == y = not (x /= y) 
	x /= y = not (x == y)

there a denotes a type variable which can be think as Int, Double, Char and so on. When we implement this type class, we use instance clause such as following:

instance Eq TrafficLight where 
	Red == Red = True 
	Green == Green = True 
	Yellow == Yellow = True 
	_ == _ = False

where TrafficLight is a concrete type,

Think of that a functor is also a type class, when we implement functor type class, we use following statements:

instance Functor Maybe where 
	fmap f (Just x) = Just (f x) 
	fmap f Nothing = Nothing

Question 1: When we implement the Eq type class, we use a concrete type TrafficLight; but when we implement the Functor type class, why we can use Maybe which is just a type constructor and not a type?

Answer: Just as an answer in Stack Overflow question What is a functor in functional programming, we can just think Maybe as a more general type with some collective properties, it can take a type such as Int as its parameters and generate a new type Maybe Int, which is a concrete type not so general as type Maybe is.

So the right answer is Instance Functor Maybe.

How to understand `Function as Functor` and `Function as Applicative`?

First, how to understand function as functor?

We can regard functor as an empty box such as:

instance Functor Maybe where 
	fmap :: (a -> b) -> f a -> f b
	fmap f (Just x) = Just (f x) 
	fmap f Nothing = Nothing

there, Maybe type can be seen as an empty box with one slot which take a type to generate a concrete type Maybe a. In the fmap function:

The first parameter is a function, which maps from a to b;
The second parameter is a value of the type with the slot filled(concrete type), this concrete type is generated by type constructor and has the type f a (f is Maybe, so f a is Maybe a ).

When we implement function functors, for function functors must have two parameters to make a type a -> b, if we want our function functor has exactly one slot, we should first fill a slot, so the type constructor of function functor is ((->) r):

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

As the same as the fmap function in Maybe Functor, we should regard the second parameter g as a value of a concrete type which is generate by f (f equals (->) r), so f a is (->) r a which can be seen as r -> a. Finally, it is not difficult to understand that the g x in the fmap function cannot be seen as r -> x, it is just a function application which can be seen as (r -> a) x, also (x -> a).

Finally, it is not hard to understand that the <*> function in Applicative function (->) r can be implemented as following:

<*> :: f (a -> b) -> f a -> f b
<*> :: (r -> a -> b) -> (r -> a) -> (r -> b)
<&> :: (a -> b) -> (r -> a) -> (r -> b)
f <*> g = \r -> f r (g r)

for g r will map r to a, f r a will map r, a to b, so the whole lambda function can be seen as r -> b, also f b. For an instance:

((+) <*> (+3)) 5

the result is 5 + (5 + 3) = 13.

Applicative Functor

What's the definition of Applicative Functor?

Applicative Functor is a type class, it is also a Functor, the definition of Applicative Functor is:

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

Each Applicative Functor f is a type (type constructor) with exactly one type slot.

The operator that Applicative Functor f support is pure, <*> and <$> (Just another name for fmap).

How to understand in functions as applicatives using applicative style: `(+) <$> (+3) <> (100) $ 5` = 508?

We know (+) has type: Num a, a -> a -> a;

We also know (+3) and (*100) has type: Num r, a, r -> a;

(+) <$> (+3) equals pure (+) <*> (+3), where :t pure (+) equals Num _, a, _ -> a -> a -> a

In another words, the pure (+) simply takes a _ parameter whatever and return the + operator, the parameter _ has no effect on the final return value. pure (+) also maps the return value of function (+3) to a function. Now for

f <*> g = \r -> f r (g r)

we can apply the operators and get:

pure (+) <*> (+3) = 
	\r -> f r (gr) =
	\r -> + (gr) =
	\r -> + (r + 3) =
	\r x -> x + (r + 3)

it has the type r -> x -> a. We then calculate pure (+) <*> (+3) <*> (*100) using the definition of <*>, and get:

pure (+) <*> (+3) <*> (*100) = 
	\r -> f r (gr) =
	\r -> (r + 3) + (gr)
	\r -> (r + 3) + (r * 100)

then we apply this function with parameter 5, we get:

(5 + 3) + (5 * 100) = 508 

we can simply think this applicative style as first to calculate the value after <$> and sum them up with the operator before <$>. In last example, this operator is a binary operator equals (+), we can replace it with a triple operator (\x y z -> [x,y,z]), so the following equation holds:

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

Monoid

What's the definition of Monoid?

Monoid is a type class, this type class is for types whose values can be combined together with a binary operation. The definition of Monoid is:

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

First, we see that only concrete types can be made instances of Monoid, because the m in the type class definition doesn’t take any type parameters. This is different from Functor and Applicative, which require their instances to be type constructors that take one parameter.

The operator that Monoid m support is mempty, mappend and mconcat.

Monad

What's the definition of Monad?

Monad is a type class, it is also an Applicative Functor, the definition of Monad is:

class Monad m where 
	return :: a -> m a
	(>>=) :: m a -> (a -> m b) -> m b
	(>>) :: m a -> m b -> m b 
	x >> y = x >>= \_ -> y
	fail :: String -> m a 
	fail msg = error msg

Each Monad m is a type (type constructor) with exactly one type slot.

The operator that Monad m support is return (Just another pure), >>= (beefed-up <*>), >> and fail.

How to understand the implementation of `State s` Monad

The implementation of Monad State s is:

instance Monad (State s) where 
	return x = State $ \s -> (x, s) 
	(State h) >>= f = State $ \s -> let (a, newState) = h s 
										(State g) = f a
									in g newState

Well, the result of feeding a stateful computation to a function with >>= must be a stateful computation, right? So, we start of with the State newtype wrapper, and then we type out a lambda. This lambda will be our new stateful computation. function h has type s -> (a, s), and the result function has type s -> (b, s). The whole implementation of >>= do is passing a state to the function h, computing its new state and pass the new state to function g implied in f, getting the newer state. So that's not strange that when we define following function:

import Control.Monad.State
stackManip :: State Stack Int 
stackManip = do 
	push 3 
	a <- pop 
	pop

and we execute it with runState stackManip [5,8,2,1]. The first state is [5,8,2,1], we pass the state to the push 3 and a newer state [3,5,8,2,1] is generated when it turns to a <- pop, and so on.