Haskell
===

###### tags: `Programming Language`

## Functional Programming
- [The Foundations of Functional Concurrency](https://freecontent.manning.com/the-foundations-of-functional-concurrency/)

## Reference
- [Hoogle](https://www.haskell.org/hoogle/)
- [Directory listing for base-4.3.1.0 documentation](http://hackage.haskell.org/package/base-4.3.1.0/docs/src/)
- [Zvon - Haskell Reference](http://zvon.org/other/haskell/Outputprelude/)

## [Write You a Haskell](http://dev.stephendiehl.com/fun/index.html)
- [Parsing](http://dev.stephendiehl.com/fun/002_parsers.html)

## [HackerRank](https://www.hackerrank.com/domains/fp/intro)

> :info Integral
instance Integral Int
> :t fromIntegral
fromIntegral :: (Integral a, Num b) => a -> b
> :info Num
instance Num Double
instance Num Int
instance Num Float

## [Functional Thursday](https://www.youtube.com/channel/UC-rw-O1QGamq6pUsDRkwgpw)
- [The Road To Monad Transformers](https://www.slideshare.net/plisek/the-road-to-monad-transformers)

## [Introduction to Functional Programming](https://courses.edx.org/courses/course-v1:DelftX+FP101x+3T2015/course/)
- [Programming in Haskell](http://www.cs.nott.ac.uk/~pszgmh/pih.html)
- [The Hugs 98 User's Guide](https://www.haskell.org/hugs/pages/users_guide/index.html)

hugs -Evi test.hs

### First Steps

> (+) 2 2
4
> 5 `div` 3
1
> :t drop 
drop :: Int -> [a] -> [a]
> tail [1, 2, 3]
[2, 3]
> :t (:)
(:) :: a -> [a] -> [a]

Note: ```::``` is type annotation.

### Types and Type Classes
Syntactically well-formed expression has a type and that type is calculated by the compiler at **compile-time** using a process called **type inference**.

**Type errors** are also in Haskell found at **compile-time**.

Functions that take their arguments one by one are called **curried functions**. The person that invented this way of dealing with functions was Haskell B. Curry and Haskell is named after him. Functions with **more than two arguments** can be curried by returning nested functions.

For application the parentheses associate to the left, for the function arrow they associate to the right, and that matches up perfectly (So in practice we don't have to write any parentheses).

Polymorphic Function
* [Theorems for free!](https://people.mpi-sws.org/~dreyer/tor/papers/wadler.pdf) 
* **Type variables** start with a **lower case** and **types** start with an **upper case**.

* Overloaded when type of polymorphic function has one or more class constraints.

### Defining Functions
* Sections
An infix binary operator can be converted into a curried function written before its two arguments by using parentheses.

> 1 + 2
3
> (+) 1 2
3
> (+2) 1
3
> (1+) 2
3

### Higher-Order Function
**Higher-order** if a function takes a function as an argument or returns a function as a result.

**Common programming idioms** can be encoded as functions within the language itself.

**Domain specific languages** can be defined as collections of higher-order functions.

**Algebraic properties** of higher-order functions can be used to reason about programs.

* The ```foldr``` function

foldr :: (a -> b -> b) -> b -> [a] -> b
foldr f v [] = v
foldr f v (x : xs) = f x (foldr f v xs)

* Instances of ```foldr```

sum [] = 0
sum (x : xs) = x + sum xs

sum = foldr (+) 0

or [] = False
or (x : xs) = x || or xs

or = foldr (||) False

plusplus ys [] = ys
plusplus ys (x : xs) = (:) x (plusplus ys xs)

plusplus ys = foldr (:) ys

## [Learn You a Haskell for Great Good!](http://learnyouahaskell.com/chapters)
- [HASKELL 趣學指南](https://learnyoua.haskell.sg/content/zh-tw/)
- [Welcome to the GHC User’s Guide](https://downloads.haskell.org/~ghc/latest/docs/html/users_guide/index.html#)

### Syntax in Functions

> :info +
> 1 + 2
> (+) 1 2
> elem 'a' ['a', 'b']
> 'a' `elem` ['a', 'b']

Note: 
* We can define functions to be automatically infix by naming them using only special characters.
* Not only can we call funcitons as infix with backticks, we can also define them using backticks.
#### Pattern Matching
* When defining functions in Haskell, you can create separate function bodies for different patterns.
* When making patterns, we should always include a catchall pattern (name that starts with lowercase letter instead of actual value) at the end.
* Patterns that include the ```:``` character will match only against lists of length one or more.

> let f [x, y, _] = True
> f [1, 2, 3]
True

> let f (x:y:_) = True
> f [1, 2]
True
> f [1, 2, 3]
True
> f [1, 2, 3, 4]
True

#### As-patterns

firstLetter :: String -> String
firstLetter "" = "Empty string!"
firstLetter all@(x:xs) = "The first letter of " ++ all ++ " is " ++ [x]

#### Guards, Guards!
* A **guards** is indicated by a pipe character ```|```, followed by a Boolean expression, followed by the function body that will be used if that expression evaluates to ```True```.
* ***Guards*** must be indented by at least one space (I like to indent them by four spaces so that the code is more readable.)
* The last guard in a function is ```otherwise```, which catches everything. If all the guards in a function eveluate to ```False```, and we haven't provided an ```otherwise``` catchall guard, evaluation falls through to thr next pattern.
#### Where?!
* ```where``` binding makes our programs faster, since our values are calculated just once.
* All the variable names are aligned in a single column.
* The variables we define in the ```where``` section of a function are visible only to that function.

bmiTell :: (RealFloat a) => a -> a -> String
bmiTell weight height
| bmi <= skinny = "You're underweight, you emo, you!"
| bmi <= normal = "You're supposedly normal. Pffft, I bet you're ugly!"
| bmi <= fat = "You're fat! Lose some weight, fatty!"
| otherwise = "You're a whale, congratulations!"
where bmi = weight / height ^ 2
skinny = 18.5
normal = 25.0
fat = 30.0

#### Pattern Matching with where

initials :: String -> String -> String
initials firstname lastname = [f] ++ ". " ++ [l] ++ "."
where (f:_) = firstname
(l:_) = lastname

#### Let It Be
* ```let``` expressions allow you to bind to variables anywhere and are expressions themselves. 
* ```let``` are visible within the entire ```let``` expression.

let <bindings> in <expression>

ghci> (let a = 100; b = 200; c = 300 in a*b*c, let foo="Hey "; bar = "there!" in foo ++ bar)
(6000000,"Hey there!")

#### Pattern Matching with let

ghci> (let (a,b,c) = (1,2,3) in a+b+c) * 100
600

#### let in List Comprehensions
* The names defined in this ```let``` are visible to the output (the part before the ```|```) and everything in the list comprehension that comes after the ```let```.
* If we use ```in``` in list comprehension, then only ```let``` expression knows the binding. 

calcBmis :: (RealFloat a) => [(a, a)] -> [a]
calcBmis xs = [bmi | (w, h) <- xs, let bmi = w / h ^ 2, bmi >= 25.0]

Note: ```(w, h) <- xs``` is called the **generator**.
#### let in GHCi
We omitted the ```in``` part in our first line, GHCi knows that we're not using ```zoot``` in that line, so it remembers for the rest of session.

ghci> let zoot x y z = x * y + z
ghci> zoot 3 9 2
29

A ```let``` expression that doesn't leave out the ```in``` part is an experssion in itself and represent a value.

ghci> let boot x y z = x * y + z in boot 3 4 2
14
ghci> boot
< interactive>:1:0: Not in scope: `boot'

#### case Expressions
* ```case``` expressions are expressions, much like ```if else``` expressions and ```let``` expressions.
* ```case``` expressions can be used anywhere.

case expression of
pattern -> result
pattern -> result
pattern -> result

describeList :: [a] -> String
describeList xs = "The list is " ++ case xs of [] -> "empty."
[x] -> "a singleton list."
xs -> "a longer list."

### Higher-Order Functions
Haskell functions can take functions as parameters and return functions as return values. A function that does either of these things is called a **higher-order function**.
* **Currying** is when you break down a function that takes multiple arguments into a series of functions that take part of the arguments.
* If we call a function with too few parameters, we get back a **partially applied function**, which is a function that takes as many parameters as we left out.

multThree :: (Num a) => a -> a -> a -> a

equals

multThree :: (Num a) => a -> (a -> (a -> a))

#### Sections
Infix function can also be partially applied by using **sections**.
Note: ```-4``` means negative four. Use ```(subtract 4)``` to subtract 4.
#### Lambda
* Lambdas are anonymous functions that we use when need a function only once.
* Lambda are expressions.
* We usually surround lambdas with parantheses.
* You can pattern match in lambdas, the only difference is that you can't define several patterns for one parameter.
#### I Fold You So
* Folds allow you to reduce a data structure (like a list) to a single value.
* A fold takes a binary function, a starting value (often called the accumulator), and a list to fold up.
* The fold function calls the given binary function, using the accumulator and the first (or last) element of the list as parameters. The resulting value is the new accumulator. This repeats until the function has traversed the entire list and reduce it down to a single accumulator.
* ```foldl1``` and ```foldr1``` can not work on empty list, but ```foldl``` and ```foldr``` can.
#### Left Folds with foldl

map' :: (a -> b) -> [a] -> [b]
map' f xs = foldl (\acc x -> acc ++ [f x]) [] xs

#### Right Folds with foldr

map' :: (a -> b) -> [a] -> [b]
map' f xs = foldr (\x acc -> f x : acc) [] xs

Note: ```++``` is much slower than ```:```.
#### The foldl1 and foldr1 Functions
They assume the first (or last) element of the list to be the starting accumulator, and then start the fold with the element next to it.

> let maximum' = foldr1 (\x acc -> if x > acc then x else acc)
> maximum' [2]
2
> maximum' [2, 1]
2

> let last' = foldl1 (\_ x -> x)
> last' [2]
2
> last' [2, 1]
1

#### Another Way to Look at Folds
Given ```[3, 4, 5, 6]``` and accumulator ```z```.
* Right fold

f 3 (f 4 (f 5 (f 6 z)))

* Left fold

g (g (g (g z 3) 4) 5) 6

#### Folding Infinite Lists
* Right folds work on infinite list, whereas left folds do not.
* ```foldr``` will work on infinite lists when the binary function that we are passing to it does not always need to evaluate its second parameter to give us some sort of answer.
#### Scans
The ```scanl``` and ```scanr``` functions are like ```foldl``` and ```foldr```, except they report all the intermediate accumulator states in the form of a list.

ghci> scanl (+) 0 [3,5,2,1]
[0,3,8,10,11]
ghci> scanr (+) 0 [3,5,2,1]
[11,8,3,1,0]

#### Functions Application with $
* ```$``` function is called **function application operator**.
* You can imagine```$``` as almost being the equivalent of writing an opening parenthesis and then writing a closing parenthesis on the far right side of the expression.
* ```$``` has lowest precedence, whereas normal function application (putting a space between two things) has a really high precedence.

($) :: (a -> b) -> a -> b
f $ x = f x

f a b c = ((f a) b) c

f $ g $ x = f $ (g $ x)

#### Function Composition 

(.) :: (b -> c) -> (a -> b) -> a -> c
f . g = \x -> f (g x)

* Function composition is right-associative

(f . g . z) x = f (g (z x))

### Build Our Own Type and Type Class

> :t fromIntegral
fromIntegral :: (Num b, Integral a) => a -> b

#### Algebraic data types intro
* Value constructors are actually functions that ultimately return a value of a data type.

data Shape = Circle Float Float Float | Rectangle Float Float Float Float deriving (Show)
ghci> :t Circle
Circle :: Float -> Float -> Float -> Shape
ghci> :t Rectangle
Rectangle :: Float -> Float -> Float -> Float -> Shape

* Pattern match against value constructors (```[]```, ```False```, and ```5```, but those values did not have any fields).
#### Type parameters
* It's a very strong convention in Haskell to never add typeclass constraints in data declarations. 
#### Derived Instances
* **Type class** is a sort of an interface that defines some behavior.
* A **type** can be made an instance of a type class if it supports that behavior.
#### Type Synonyms
* Type synonyms are just about giving some types different names.

type String = [Char]

* Type synonyms can be used only in the type portion of Haskell.
  * Type declarations
  * Data declarations
  * Type annotations
#### Recursive Data Structures
* Infix value constructors must begin with a colon

infixr 5 :-:
data List a = Empty | a :-: (List a) deriving (Show, Eq, Ord, Read)

#### Type Classes 102

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

* ```a``` is type variable that will be made an instance of ```Eq``` .
* Type variable must be lowercase. 
* Only require type declaration of those **behaviors (functions)** in type class definition (function bodies is optional).

instance (Eq m) => Eq (Maybe m) where
Just x == Just y = x == y
Nothing == Nothing = True
_ == _ = False

* By specifying a type parameter as a type variable (```m```, which is in lowercase), we said that we want all types that are in the form of ```Maybe m```, where ```m``` is any type, to be an instance of ```Eq```.
#### The Functor Type Class

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

* ```f``` must be a type constructor that takes only a parameter.
* The type variable of ```Functor``` is kind of ```* -> *```.
#### Kinds and some Type-Foo

> :k Int
Int :: *

* A kind is the label of a type; while a type is the label of a value.
* ```*``` indicates that the type is a concrete type.

### Input and Output

ghc --make test.hs
./test

* An I/O action is something that, when performed, will carry out an  action with a side effect.
* I/O actions are performed only when they fall into ```main```or we try to evaluate them at GHCi prompt.
* When we punch in a number or call a function in GHCi and press ```ENTER```, GHCi will apply ```show``` to the resulting value, and then it will print it to the terminal by using ```putStrLn```. (GHCi actually uses ```print``` on that value to display it on the terminal.)

print :: (Show a) => a -> IO ()
print x = putStrLn (show x)

* When we evaluate an I/O action in GHCi, that action is performed, and then its result is printed out, unless that result is ```()```.

> :t getLine
getLine :: IO String
> getLine
abc
"abc"
> :t print
print :: (Show a) => a -> IO ()
> print "abc"
"abc"
> :t return ()
return () :: Monad m => m ()
> return ()
> :t return 5
return 5 :: (Monad m, Num a) => m a
> return 5
5

* Run ```main``` without printing out I/O action result.

runhaskell test.hs

#### Hello, World!

main = do
putStrLn "Hello"
name <- getLine
putStrLn ("Hello " ++ name)

* To get the value out of an I/O action, you must perform it inside another I/O action by binding it to a name with ```<-```.
* ```getLine``` is an I/O action that yields a String, so ```name``` has a type of String.
* In a ```do``` block, except for the last line, every line in a ```do``` block that doesn't bind can be written with a bind ```->```.
* The action that we got has a type of ```IO ()```, as that's the type of the last I/O action.

> :t putStrLn
putStrLn :: String -> IO ()
> :t getLine
getLine :: IO String
> :t main
main :: IO ()

* The ```do``` block automatically extracts the value from the last action and yields that as its own result.

main = do
return 1
putStrLn "b"
putStrLn "c"
return 2

> :t main
main :: IO Integer

> main
b
c
2

### Applicative Functors
We don't need to think about types belonging to a big hierarchy , we can also introduce a new type class and then make already existing types instances of it.

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

instance Functor [] where
fmap = map

#### Functors Redux

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

instance Functor Tree where
fmap f EmptyTree = EmptyTree
fmap f (Node x leftsub rightsub) =
Node (f x) (fmap f leftsub) (fmap f rightsub)

instance Functor (Either a) where
fmap f (Right x) = Right (f x)
fmap f (Left x) = Left x

#### I/O Actions As Functors

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

#### Functions As Functors

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

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

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

#### Functor Law
* All instances of ```Functor``` should abide by these two laws.
* They are not enforced by Haskell automatically, so you need to test them youself when you make a functor.
* Even though it's part of the ```Functor``` type class, it dosen't obey this functor law and is therefore not a functor. 
* Law 1

fmap id = id

* Law 2

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

#### Using Applicative Functors

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

Note: ```<*>``` is left associative.
#### The Applicative Style

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

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

#### Maybe the Applicative Functor

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

#### Lists

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

#### IO is Applicative Functor, too

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

#### Functions as Applicatives

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

#### Zip Lists

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

Note: ```ZipList a``` type does not have a ```Show``` instance, so we need to use the ```getZipList``` function to extract a raw list from a zip list.
#### Applicative Laws
* Identity

* Composition

* Homomorphism

* Interchange

* As a consequence of these laws, the ```Functor``` instance for ```f``` will satisfy.

### Monoids
#### types vs. newtype vs. data
* If you just want your type signatures to look cleaner and be more descriptive, you probably want ```type``` synonyms.
* If you want to take an existing type and wrap it in a new type in order to make it an instance of a type class, chances are you're looking for a ```newtype```.

newtype Pair b a = Pair {getPair :: (a, b)}

instance Functor (Pair c) where
    fmap f (Pair (x, y)) = Pair (f x, y)

* If you want to make something completely new, odds are good that you're looking for the ```data``` keyword.
#### Wrapping an Existing Type into a New Type
In practice, you can think of ```newtype``` declarations as ```data``` declarations that can have only one value constructor and one field.

newtype ZipList a = ZipList { getZipList :: [a] }

> :t ZipList
ZipList :: [a] -> ZipList a
> :t getZipList
getZipList :: ZipList a -> [a]

Note:
1. ``data`` is slower than ```newtype``` due to overhead to all that wrapping and unwrapping type inside it.
2. Pattern matching on ```newtype``` values isn't like taking something out of a box (as it is with ```data```), but more about making a direct conversion from one type to another.
3. If we derive the instance for a type class, the type that we're wrapping must already be in that type class.
#### The Monoid Type Class
A monoid is made up of an associative binary function and a value that acts as an identity with respect to that function.
Note: Associative means the order that we apply the binary function to the values does not matter.

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

#### The Monoid Laws
* ```mempty `mappend` x = x```
* ```x `mappend` mempty = x```
* ```(x `mappend` y) `mappend` z = x `mappend` (y `mappend` z)```

### Meet Some Monoids
#### Lists are Monoids

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

#### Product and Sum

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)

#### Any and All

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)

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)

#### The Ordering Monoid

instance Monoid Ordering where  
    mempty = EQ  
    LT `mappend` _ = LT  
    EQ `mappend` y = y  
    GT `mappend` _ = 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)

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

#### Folding with Monoids
* **Foldable** is for things that can be folded up.

ghci> import qualified Data.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> :t F.foldl
F.foldl :: (F.Foldable t) => (b -> a -> b) -> b -> t a -> b

* Implementing ```foldMap``` is all it takes for our type to be an instance of ```Foldable``` (we get ```foldr``` and ```foldl``` for free).

 class Foldable t where
     foldMap :: Monoid m => (a -> m) -> t a -> m

 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

 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

 ghci> F.foldMap (\x -> [x]) testTree  
[1,3,6,5,8,9,10]

### A Fistful of Monads
#### Upgrading Our Applicative Functors
Monads are just applicative functors that support ```>>=```. (The ```>>=``` function is called **bind**)
#### The Monad Type Class

class Applicative m => 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

#### do Notation
* Gruing together monadic values in sequence.
* ```do``` expressions are just different syntax for chaining monadic values.

 instance Monad Maybe where  
    return x = Just x  
    Nothing >>= f = Nothing  
    Just x >>= f  = f x  
    fail _ = Nothing

 Just 3 >>= (\x -> Just "!" >>= (\y -> Just (show x ++ y)))

 foo :: Maybe String
 foo = do
     x <- Just 3
     y <- Just "!"
     Just (show x ++ y)

Note: If any of the values that we try to extract from are ```Nothing```, the whole ```do``` expression will result in a ```Nothing```.

 routine :: Maybe Pole  
routine = do  
    start <- return (0,0)  
    first <- landLeft 2 start  
    Nothing  
    second <- landRight 2 first  
    landLeft 1 second

Note: Above ```Nothing``` is equivalent form of ```_ <- Nothing```.
#### Pattern Matching and Failure
When pattern matching fails in a ```do``` expression, the ```fail``` function (part of the ```monad``` type class) enables it to result in a failure in the context of the current monad, instead of making the program crash.
#### The List Monad

 instance Monad [] where  
    return x = [x]  
    xs >>= f = concat (map f xs)  
    fail _ = []

 ghci> [] >>= \x -> ["bad","mad","rad"]  
[]  
ghci> [1,2,3] >>= \x -> []  
[]

 ghci> [1,2] >>= \n -> ['a','b'] >>= \ch -> return (n,ch)  
[(1,'a'),(1,'b'),(2,'a'),(2,'b')]

listOfTuples :: [(Int,Char)]  
listOfTuples = do  
    n <- [1,2]  
    ch <- ['a','b']  
    return (n,ch)

In fact, list comprehensions are just syntatic sugar for using lists as monads.

ghci> [ (n,ch) | n <- [1,2], ch <- ['a','b'] ]  
[(1,'a'),(1,'b'),(2,'a'),(2,'b')]

#### MonadPlus and the guard Function

class Monad m => MonadPlus m where  
    mzero :: m a  
    mplus :: m a -> m a -> m a

instance MonadPlus [] where  
    mzero = []  
    mplus = (++)

guard :: (MonadPlus m) => Bool -> m ()  
guard True = return ()  
guard False = mzero

ghci> [1..50] >>= (\x -> guard ('7' `elem` show x) >> return x)  
[7,17,27,37,47]

ghci> guard (5 > 2) >> return "cool" :: [String]  
["cool"]  
ghci> guard (1 > 2) >> return "cool" :: [String]  
[]

#### A Knight's Quest

type KnightPos = (Int,Int)

moveKnight :: KnightPos -> [KnightPos]  
moveKnight (c,r) = do  
    (c',r') <- [(c+2,r-1),(c+2,r+1),(c-2,r-1),(c-2,r+1)  
                ,(c+1,r-2),(c+1,r+2),(c-1,r-2),(c-1,r+2)  
                ]  
    guard (c' `elem` [1..8] && r' `elem` [1..8])
    return (c',r')

ghci> moveKnight (6,2)  
[(8,1),(8,3),(4,1),(4,3),(7,4),(5,4)]  
ghci> moveKnight (8,1)  
[(6,2),(7,3)]

in3 :: KnightPos -> [KnightPos]  
in3 start = do   
    first <- moveKnight start  
    second <- moveKnight first  
    moveKnight second

in3 start = return start >>= moveKnight >>= moveKnight >>= moveKnight

canReachIn3 :: KnightPos -> KnightPos -> Bool  
canReachIn3 start end = end `elem` in3 start

ghci> (6,2) `canReachIn3` (6,1)  
True
ghci> (6,2) `canReachIn3` (7,3)  
False

import Data.List  

inMany :: Int -> KnightPos -> [KnightPos]  
inMany x start = return start >>= foldr (<=<) return (replicate x moveKnight)

canReachIn :: Int -> KnightPos -> KnightPos -> Bool  
canReachIn x start end = end `elem` inMany x start

#### Monand Laws
#### Left Identity

#### Right Identity

#### Associativity

(.) :: (b -> c) -> (a -> b) -> (a -> c)
f . g = (\x -> f (g x))

(<=<) :: (Monad m) => (b -> m c) -> (a -> m b) -> (a -> m c)
f <=< g = (\x -> g x >>= f)

f <=< (g <=< h) = (f <=< g) <=< h

### For a Few Monads More
* The ```mtl``` package comes with Haskell-Platform (a **package** is a collection of modules), check by **ghc-pkg list**.
#### The Writer Type
* The ```Writer``` monad is for values that have another value attached that acts as a sort of log value. 
* ```Writer``` allows us to do computations while making sure that all the log values are combined into one log value, which then is attached to the result.

newtype Writer w a = Writer { runWriter :: (a, w)}

instance (Monoid w) => Monad (Writer w) where
return x = Writer (x, mempty)
(Writer (x, v)) >>= f = let (Writer (y, v')) = f x in Writer (y, v `mappend` v')

import Control.Monad.Writer

Note: The ```Writer``` instance doesn't feature an implementation for ```fail```, so if a pattern match fails in ```do``` notation, ``error`` is called.
* In this case, all the monoid values that come attached are ``mappended``, and so are reflected in the final result.

multWithLog :: Writer [String] Int
multWithLog = do
a <- logNumber 3
b <- logNumber 5
tell ["Gonna multiply these two"]
return (a*b)

ghci> runWriter multWithLog
(15,["Got number: 3","Got number: 5","Gonna multiply these two"])

> :t tell ["hello"]
tell ["hello"] :: MonadWriter [[Char] m => m ()

Note: ```MonadWriter``` is a type class.
#### Inefficient List Construction
A list is a data structure that's constructed from left to right.
* Fast ver.

a ++ (b ++ (c ++ (d ++ (e ++ f))))

* Slow ver. 
(Everytime it wants to add the right part to the left part, it must construct the left part all  the way from the begnning!)

((((a ++ b) ++ c) ++ d) ++ e) ++ f

#### Using Difference Lists
A difference list is actually a function that takes a list and prepends another list to it.

newtype DiffList a = DiffList { getDiffList :: [a] -> [a] }

instance Monoid (DiffList a) where
mempty = DiffList (\xs -> [] ++ xs)
(DiffList f) `mappend` (DiffList g) = DiffList (\xs -> f (g xs))

toDiffList :: [a] -> DiffList a
toDiffList xs = DiffList (xs++)

fromDiffList :: DiffList a -> [a]
fromDiffList (DiffList f) = f []

#### Comparing Performance

finalCountDown :: Int -> Writer (DiffList String) ()
finalCountDown 0 = do
tell (toDiffList ["0"])
finalCountDown x = do
finalCountDown (x-1)
tell (toDiffList [show x])

ghci> mapM_ putStrLn . snd . runWriter $ finalCountDown 500000

#### Functions as Monads

import Control.Monad.Instances

instance Monad ((->) r) where
return x = \_ -> x
h >>= f = \w -> f (h w) w

#### The Reader Monad
The function monad is also called the reader monad.

import Control.Monad.Instances

addStuff :: Int -> Int
addStuff = do
a <- (*2)
b <- (+10)
return (a+b)

ghci> addStuff 3
19

#### Stateful Computations
Assignment in most other languages could be thought of as a stateful computation.
#### The State Monad

import Control.Monad.State

newtype State s a = State { runState :: s -> (a,s) }

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

import Control.Monad.State

pop :: State Stack Int
pop = State $ \(x:xs) -> (x,xs)

push :: Int -> State Stack ()
push a = State $ \xs -> ((),a:xs)

stackStuff :: State Stack ()
stackStuff = do
a <- pop
if a == 5
then push 5
else do
push 3
push 8

ghci> runState stackStuff [9,0,2,1,0]
((),[8,3,0,2,1,0])

#### Getting and Setting State

class Monad m => MonadState s m | m -> s where

Minimal definition is either both of `get` and `put` or just `state`

> :t get
get :: MonadState s m => m s
> :t put
put :: MonadState s m => s -> m ()
> :t  state
state :: MonadState s m => (s -> (a, s)) -> m a

get = state $ \s -> (s,s)

put newState = state $ \s -> ((),newState)

stackyStack :: State Stack ()  
stackyStack = do  
    stackNow <- get  
    if stackNow == [1,2,3]  
        then put [8,3,1]  
        else put [9,2,1]

#### Error Error On the Wall

import Data.Either

instance Monad (Either e) where
    return x = Right x
    Left l >>= _ = Left l
    Right r >>= k = k r

#### Some Useful Monadic Functions
#### liftM and Friends

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

liftM :: (Monad m) => (a -> b) -> m a -> m b  
liftM f m = m >>= (\x -> return (f x))

liftM :: (Monad m) => (a -> b) -> m a -> m b  
liftM f m = do  
    x <- m  
    return (f x)

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

ap :: (Monad m) => m (a -> b) -> m a -> m b  
ap mf m = do  
    f <- mf  
    x <- m  
    return (f x)

liftM2 :: (Monad m) => (a -> b -> c) -> m a -> m b -> m c
liftM2 f x y = f <$> x <*> y 

#### The join Function

join :: (Monad m) => m (m a) -> m a  
join mm = do  
    m <- mm  
    m

ghci> join (Right (Right 9)) :: Either String Int  
Right 9  
ghci> join (Right (Left "error")) :: Either String Int  
Left "error"  
ghci> join (Left "error") :: Either String Int  
Left "error"

* To flatten a ```Writer``` value whose result is a ```Writer``` value itself, we need to ```mappend``` the monoid value.

ghci> runWriter $ join (Writer (Writer (1,"aaa"),"bbb"))  
(1,"bbbaaa")

ghci> runState (join (State $ \s -> (push 10,1:2:s))) [0,0,0]  
((),[10,1,2,0,0,0])

* If we're making our own ```Monad``` instance for some type. This is because it's often easier to figure out how we would flatten a nested monadic value than to figure out how to implement ```>>=```.

m >>= f = join (fmap f m)

Just 9 >>= (\x -> Just (x+1)) 
= Just 10
join (fmap (\x -> Just (x+1)) Just 9)
= Just 10

#### filterM

filter :: (a -> Bool) -> [a] -> [a]

filterM :: (Monad m) => (a -> m Bool) -> [a] -> m [a]

keepSmall :: Int -> Writer [String] Bool  
keepSmall x  
    | x < 4 = do  
        tell ["Keeping " ++ show x]  
        return True  
    | otherwise = do  
        tell [show x ++ " is too large, throwing it away"]  
        return False

ghci> mapM_ putStrLn $ snd $ runWriter $ filterM keepSmall [9,1,5,2,10,3]  
9 is too large, throwing it away  
Keeping 1  
5 is too large, throwing it away  
Keeping 2  
10 is too large, throwing it away  
Keeping 3

powerset :: [a] -> [[a]]  
powerset xs = filterM (\x -> [True, False]) xs

ghci> powerset [1,2,3]  
[[1,2,3],[1,2],[1,3],[1],[2,3],[2],[3],[]]

#### foldM

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

foldM :: (Monad m) => (a -> b -> m a) -> a -> [b] -> m a

binSmalls :: Int -> Int -> Maybe Int  
binSmalls acc x  
    | x > 9     = Nothing  
    | otherwise = Just (acc + x)

ghci> foldM binSmalls 0 [2,8,3,1]  
Just 14  
ghci> foldM binSmalls 0 [2,11,3,1]  
Nothing

#### Composing Monadic Functions

ghci> let g = (\x -> return (x+1)) <=< (\x -> return (x*100))  
ghci> Just 4 >>= g  
Just 401

ghci> let f = foldr (.) id [(+1),(*100),(+3)]  
ghci> f 1  
401