Instantly share code, notes, and snippets.

Created April 27, 2022 06:45
Show Gist options
• Save ehzawad/7936568cb338f5bf6480267c3e94931e to your computer and use it in GitHub Desktop.

# HASKELL PROGRAMMING FROM FIRST PRINCIPLES

## CHAPTER1. ALL YOU NEED IS LAMBDA

### 1.1 All You Need is Lambda

#### lambda calculus:

computation model, 1930s, Alonzo Church, formalizing a method, Turing machines

### 1.2 What is functional programming?

#### functional programming:

expression combination, first class function, purity, referential transparency, abstraction and composability

### 1.3 What is a function?

relation -> input & output,

input set = domain, output = codomain, output <- input = range,

### 1.4 The structure of lambda terms

lambda calculus -> three lambda terms: expressions, variables, abstractions

expression: variable name, abstraction, combination of those things.

abstraction: anonymous function 𝜆𝑥.𝑥 = function = head (𝜆 lambda + parameter name) + body (expression) <- argument (input value)

#### Alpha equivalence

𝜆𝑥.𝑥 = 𝜆𝑑.𝑑 = 𝜆𝑧.𝑧

### 1.5 Beta reduction

(𝜆𝑥.𝑥)(𝜆𝑦.𝑦) => [𝑥 ∶= (𝜆𝑦.𝑦)] => 𝜆𝑦.𝑦

𝜆𝑥.𝑥𝑦 <= y

### 1.6 Multiple arguments

currying: 1920s Moses Schönfinke -> Haskell Curry

𝜆𝑥𝑦.𝑥𝑦 -> 𝜆𝑥.(𝜆𝑦.𝑥𝑦)

### 1.7 Evaluation is simplification

beta normal form: cannot reduce further

### 1.8 Combinators

combinator: a lambda term with no free variables:

1. 𝜆𝑥.𝑥 2. 𝜆𝑥𝑦.𝑥 3. 𝜆𝑥𝑦𝑧.𝑥𝑧(𝑦𝑧)

not combinator, free variable: 1. 𝜆𝑦.𝑥 2. 𝜆𝑥.𝑥𝑧

### 1.9 Divergence

Divergence: reduction process never terminates:

#### omega:

(𝜆𝑥.𝑥𝑥)(𝜆𝑥.𝑥𝑥) => ([𝑥 ∶= (𝜆𝑥.𝑥𝑥)]𝑥𝑥) => (𝜆𝑥.𝑥𝑥)(𝜆𝑥.𝑥𝑥)

### 1.10 Summary

• FP: expression composition
• function: head, body <= apply, reduce, evaluate
• function declaration: bound variable
• one argument => function => one result
• function: same input => same output

### 1.11 Exercises

#### Combinators

1. 𝜆𝑥.𝑥𝑥𝑥
2. 𝜆𝑥𝑦𝑧.𝑥𝑦(𝑧𝑥)
3. 𝜆𝑥𝑦𝑧.𝑥𝑦(𝑧𝑥𝑦)

#### Normal form or diverge

1. 𝜆𝑥.𝑥𝑥𝑥 => normal
2. (𝜆𝑧.𝑧𝑧)(𝜆𝑦.𝑦𝑦) => diverge
3. (𝜆𝑥.𝑥𝑥𝑥)𝑧 => nomal

#### Beta reduce

1. (𝜆𝑎𝑏𝑐.𝑐𝑏𝑎)𝑧𝑧(𝜆𝑤𝑣.𝑤) => z
2. (𝜆𝑥.𝜆𝑦.𝑥𝑦𝑦)(𝜆𝑎.𝑎)𝑏 => bb
3. (𝜆𝑦.𝑦)(𝜆𝑥.𝑥𝑥)(𝜆𝑧.𝑧𝑞) => qq
4. (𝜆𝑧.𝑧)(𝜆𝑧.𝑧𝑧)(𝜆𝑧.𝑧𝑦) => yy
5. (𝜆𝑥.𝜆𝑦.𝑥𝑦𝑦)(𝜆𝑦.𝑦)𝑦 => yy
6. (𝜆𝑎.𝑎𝑎)(𝜆𝑏.𝑏𝑎)𝑐 => aac
7. (𝜆𝑥𝑦𝑧.𝑥𝑧(𝑦𝑧))(𝜆𝑥.𝑧)(𝜆𝑥.𝑎) => 𝜆𝑧'.𝑧𝑎

### 1.13 Definitions

• normal order: left associative

### 1.14 Follow-up resources

1. Henk Barendregt; Erik Barendsen. Introduction to Lambda Calculus

2. Jean-Yves Girard; P. Taylor; Yves Lafon. Proofs and Types

install tools

### 2.2 Interacting with Haskell code

#### Using the REPL

command:

• :quit / :q
• :info / : i
• :module / :m #unload module
• :type /:t
• :browse #browse module

### 2.3 Understanding expressions

redexes: reducible expressions

normalizing = executing = evaluating = reducing

### 2.4 Functions

triple x = x * 3

𝑓′ : "eff-prime"

#### Intermission: Exercises

1. half x = x / 2 => add 'let' to run in REPL
2. f r = 3.14 * r * r

### 2.5 Infix operators

default: prefix syntax

#### Associativity and precedence

``````:info (*)
> infixl 7 *
``````

infixl: infix operator, left associative infixr: infix operator, right associative 7: precedence on a scale of 0-9, indicated by higher number

#### Intermission: Exercises

Below are some pairs of functions that are alike except for parenthe- sization. Read them carefully and decide if the parentheses change the results of the function. Check your work in GHCi.

1. a) 8 + 7 * 9 b) (8 + 7) * 9
2. a) perimeter x y = (x * 2) + (y * 2) b) perimeter x y = x * 2 + y * 2
3. a) f x = x / 2 + 9 b) f x = x / (2 + 9)

### 2.6 Declaring values

```module Learn where
x = 10 * 5 + y
myResult = x * 5
y = 10```

#### Troubleshooting

spacing:

```let
x = 3
y = 4

-- or

let x = 3
y = 4```
```foo x =
let y = x * 2
z = x ^ 2
in 2 * y * z```

#### Intermission: Exercises

```let area x = 3. 14 * (x * x) -- 3.14
let double x = b * 2 -- b is free
x = 7
y = 10
f = x + y -- spacing```

### 2.7 Arithmetic functions in Haskell

operator: + - * / div mod quot rem

#### Using ‘mod‘

mod & rem:  ```haskell mod (-12) 7 -- 5 rem (-12) 7 -- -2

``````
### 2.8 Negative numbers

syntactic sugar: unary - => negate

2000 + (-1234)
2000 + (negate 1234)
``````

### 2.9 Parenthesizing infix functions

```1 + 1
(+) 1 1
(+ 1) 1 -- sectioning```

### 2.10 Laws for quotients and remainders

(quot x y)*y + (rem x y) == x

(div x y)*y + (mod x y) == x

### 2.12 Let and where

```-- FunctionWithWhere.hs
module FunctionWithWhere where
printInc n = print plusTwo
where plusTwo = n + 2

printInc 1 -- 3```

#### Desugaring let to lambda

```printInc2 n = let plusTwo = n + 2 in print plusTwo

-- turns into

printInc2 n = (\plusTwo -> print plusTwo)(n + 2)```

#### Intermission: Exercises

```let x = 5 in x -- 5

let x = 5 in x * x -- 25

let x = 5; y = 6 in x * y -- 30

let x = 3; y = 1000 in x + 3 -- 6```

#### The lambdas beneath let expressions

λx.x => \x -> x

```let a = b in c
-- equivalent to
(\a -> c) b

let x = 10 in x + 9001
-- equivalent to
(\x -> x + 9001) 10```
```c where a = b
-- equivalent to
(\a -> c) b

x + 9001 where x = 10
-- equivalent to
(\x -> x + 9001) 10```

#### More exercises!

```let x = 3; y = 1000 in x * 3 + y
v = x * 3 + y where x = 3; y = 100

let y = 10; x = 10 * 5 + y in x * 5
v = x * 5 where y = 10; x = 10 * 5 + y

let x = 7; y = negate x; z = y * 10 in z / x + y
v = z / x + y where x = 7; y = negate x; z = y * 10```

### 2.13 Chapter Exercises

#### Parenthesization

```:info (\$)
> (\$) :: (a -> b) -> a -> b
> infixr 0 \$```
```(2^) \$ 2 + 2 -- 16

(2^) (2 + 2) -- 16

(2^) 2 + 2 -- 6

(2^) \$ (+2) \$ 3 * 2 -- 256```

#### Equivalent expressions

```1 + 1 -- 2

10 ^ 2 -- 10 + 9 * 10

400 - 37 -- not (-) 37 400

100 `div` 3 -- 100 / 3

2 * 5 + 18 -- not 2 * (5 + 18)```

### 2.14 Definitions

1. argument & parameter:
```f x = x + 2
f 1```

parameter 𝑥, argument 1

1. expression: combination of constants, variables, and functions.
2. redex: reducible expression.
3. value: expression that cannot be reduced or evaluated.
4. function: a list -> inputs => outputs
5. Infix notation
6. Operators: infix functions
7. Syntactic sugar

### 2.15 Follow-up resources

1. Haskell wiki article on Let vs. Where

## CHAPTER3. STRINGS

### 3.2 A first look at types

[Char] === String

```-- :type "Hello"
"Hello" :: [Char]```

:: type signature

### 3.3 Printing simple strings

```-- print1.hs
module Print1 where main :: IO ()
main = do
putStrLn "Count to four for me:"
putStr   "one, two"
putStr   ", three, and"
putStrLn " four!"
main```

++

### 3.4 Types of concatenation functions

```-- :t concat
concat :: Foldable t => t [a] -> [a]```

### 3.6 More list functions

```'c' : "hris"

tail "Papuchon" -- "apuchon"

take 6 "Papuchon" -- "Papuch"

drop 1 "Papuchon" -- "apuchon"

"Papu" ++ "chon" -- "Papuchon"

"Papuchon" !! 0 -- 'p'```

### 3.8 Definitions

1. String: [Char]
2. type / datatype: value classification
3. concatenation
4. scope: visibility
5. local binding: let where
6. global: top level bindings
7. data structure

## CHAPTER4. BASICDATATYPES

### 4.1 Basic Datatypes

type: classifying, organizing, delimiting data

datatypes, type constructors, data constructors, type signatures, typeclasses

### 4.2 Anatomy of a data declaration

Data declarations: datatype

`data Bool = False | True`

Type constructor: type name, capitalized (Bool)

Data constructor: value (False | True)

### 4.3 Numeric types

#### Integral numbers

1. Int: fixed-precision integer
2. Integer: arbitrarily large numbers

#### Fractional

1. Float: single-precision floating point number.
2. Double: double-precision floating point number.twice bits of Float.
3. Rational: ratio of two Integers
4. Scientific: almost-arbitrary precision scientific number type

typeclass Num: numeric datatype

Typeclass: reuse functionality across type.

#### Integral numbers

Integral number: Int & Integer: no fraction: 1 2 3

#### Integer

infinite data constructor, how represent?

#### Why do we have Int?

```import GHC.Int

127 :: Int8
128 :: Int8 -- warning

--typeclass Bounded
minBound :: Int8 -- -128
maxBound :: Int8 -- 128```

#### Fractional numbers

Float, Double, Rational, Scientific

```-- :t (/)
(/) :: Fractional a => a -> a -> a```

type variable a implement Fractional typeclass

Num is superclass of Fractional. function from Num can be used with Fractional function from Fractional cannot .. Fractional

### 4.4 Comparing values

```['a', 'b'] > ['b', 'a'] -- false
[1, 2] > [2, 1] -- false```
```data Mood = Blah | Woot deriving Show

[Blah, Woot] > [Woot, Blah] -- error```

#### Go on and Bool me

Term-level: code <= running

type-level: type variables, type constructors, and typeclasses <= static analysis & verification

module

#### if-then-else

`if True then "Truthin" else "Falsin"`
```greetIfCool :: String -> IO ()
greetIfCool coolness =
if cool coolness
then putStrLn "eyyyyy. What's shakin'?"
else
putStrLn "pshhhh."
where cool v = v == "downright frosty yo"```

### 4.5 Tuples

multiple values within a single value

tuple's arity: set in type and immutable

pair: two-tuple

triple: three-tuple

```fst :: (x, xs) -> a
snd :: (x, xs) -> xs```

different types in tuple:

```let myTup = (1 :: Integer, "blah")

import Data.Tuple
swap myTup -- ("blah", 1)```

### 4.6 Lists

```let awesome = ["Papuchon", "curry", ":)"]
-- :t awesome
awesome :: [[Char]]```

### 4.7 Chapter Exercises

```awesome = ["Papuchon", "curry", ":)"]
alsoAwesome = ["Quake", "The Simons"]
allAwesome = [awesome, alsoAwesome]```
1. type signature of length:
```-- :t length
length :: Foldable t => t a -> Int```
```length allAwesome -- 3
length (concat allAwesome) -- 5```
```6 / length [1, 2, 3] -- error

-- this works
6 / (fromIntegral (length [1, 2, 3]))
```
1. palindrome
```isPalindrome :: Eq a => [a] -> Bool
isPalindrome x = reverse x == x```
```myAbs :: Integer -> Integer
myAbs n = if n < 0 then (-n) else n```
```f :: (a, b) -> (c, d) -> ((b, d), (a, c))
f (a, b) (c, d) = ((b, d), (a, c)) ```

### 4.8 Definitions

1. tuple: no singleton tuple, but zero tuple/unit ()
2. typeclass:
3. data constructor: constant value(nullary) or take arguments like function, Cat Dog
```type Name = String
data Pet = Cat | Dog Name

-- :t Cat
Cat :: Pet
-- :t Dog
Dog :: Name -> Pet```
1. type constructor: not value, Pet
2. data declaration: create new type constructor + data constructor
3. type alias: alternate name
`type Nam`
1. arity: arguments number
2. polymorphism: parametric or constrained
```-- parametric
id :: a -> a
id x = x

-- constrained
isEqual :: Eq a => a -> a -> Bool
isEqual x y = x == y```

## CHAPTER5. TYPES

### 5.1 Types

type: Bool tuple

type class: Num Eq

### 5.3 Querying and Reading Types

```-- :i (->)
data (->) t1 t2

-- :i (,)
data (,) a b = (,) a b

-- fst is a value of type (a, b) -> a
fst :: (a, b) -> a

:type length
-- before GHC 7.10 length :: [a] -> Int
Foldable t => t a -> Int```

### 5.4 Typeclass constrained type variables

typeclass-constrained polymorphic type variable

```let fifteen = 15

-- :t fifteen
fifteen :: Num a => a```

fifteen is constrained by typeclass Num, but dont know its concrete type. its type can be a Num instance (Float, Int, Integer...).

```-- :info Num
class Num a where
(+) :: a -> a -> a
(-) :: a -> a -> a
(*) :: a -> a -> a
negate :: a -> a
abs :: a -> a
signum :: a -> a
fromInteger :: Integer -> a
{-# MINIMAL (+), (*), abs, signum, fromInteger, (negate | (-)) #-}
-- Defined in ‘GHC.Num’
instance Num Word -- Defined in ‘GHC.Num’
instance Num Integer -- Defined in ‘GHC.Num’
instance Num Int -- Defined in ‘GHC.Num’
instance Num Float -- Defined in ‘GHC.Float’
instance Num Double -- Defined in ‘GHC.Float’```

multiple typeclass constraints:

```(Num a, Num b) => a -> b -> b -- or
(Ord a, Num a) => a -> Ordering```

#### Intermission: Exercises

```not :: Bool -> Bool
length :: Foldable t => t a -> Int
concat :: Foldable t => t [a] -> [a]
(<) :: Ord a => a -> a -> Bool```

### 5.5 Currying

partial application

#### Manual currying and Uncurry

• Uncurried functions: One function, many arguments • Curried functions: Many functions, one argument apiece

#### Currying and uncurrying existing functions

```let curry f a b = f (a, b)

-- :t curry
curry :: ((t1, t2) -> t) -> t1 -> t2 -> t

-- :t fst
fst :: (a, b) -> a

-- :t curry fst
curry fst :: t -> b -> t

fst (1, 2) -- 1
curry fst 1 2 --1

let uncurry f (a, b) = f a b

-- :t uncurry
uncurry :: (t1 -> t2 -> t) -> (t1, t2) -> t

-- :t (+)
(+) :: Num a => a -> a -> a

(+) 1 2 -- 3
uncurry (+) (1, 2) -- 3```

### 5.6 Polymorphism

type signatures types: concrete, constrained polymorphic, or parametrically polymorphic.

polymorphism: parametric polymorphism, constrained polymorphism.

• constrained, ad-hoc polymorphism(overload): puts typeclass constraints on the variable. capitalized name in type signature.

• Parametric polymorphism: type variables, or parameters. fully polymorphic. unconstrained by typeclass, lowercase name in type signature.

more type flexibility, less method; vice versa.

• type: a set of possible values

• type variable: a set of types, constrained by type class

• polymorphic function: type signature has variables which represent more than one type.

#### Intermission: Exercises

1. given function type signature: a -> a. make a function other than id.
`-- impossible`
1. type signature: a -> a -> a, find two and only two functions
```f :: a -> a -> a
f a b = a

f :: a -> a -> a
f a b = b```
1. type signature: a -> b -> b
`f a b = b`

#### Polymorphic constants

```1 + 0.1
-- 1.1

-- :t 1 + 0.1
1 + 0.1 :: Fractional a => a

-- :t 1
1 :: Num t => t

-- :t 0.1
0.1 :: Fractional t => t```

type of 0.1 polymorphic

#### Working around constraints

```6 / (length [1, 2, 3]) -- error

6 / fromIntegral (length [1, 2, 3])```

### 5.7 Type inference

Damas-Hindley-Milner type system

### 5.8 Asserting types for declarations

```-- type signature locally, uncommon
triple x = tripleIt x
where tripleIt :: Integer -> Integer
tripleIt y = y * 3```

### 5.9 Chapter Exercises

#### Determine the type

```(* 9) 6 :: Num a => a

head [(0,"doge"),(1,"kitteh")] :: Num t => (t,[Char])

head [(0 :: Integer ,"doge"),(1,"kitteh")] :: (Integer,[Char])

if False then True else False :: Bool

length [1, 2, 3, 4, 5] :: Int

(length [1, 2, 3, 4]) > (length "TACOCAT") :: Bool```
```x = 5
y = x + 5
w = y * 10 :: Num```
```x = 5
y = x + 5
z y = y * 10
z :: Num a => a -> a```
```x = 5
y = x + 5
f = 4 / y
f :: Fractional a => a```
```x = "Julie"
y = " <3 "
f = x ++ y ++ z
f :: [Char]```

#### Type variable or specific type constructor?

``````f :: Num a => a -> b -> Int -> Int
``````
• constrained polymorphic: a
• fully polymorphic: b
• concrete: Int

#### Write a type signature

```functionH :: [t] -> t
functionH (x : _) = x

functionC :: Ord a => a -> a -> Bool
functionC x y = if (x > y)
then True
else False

functionS :: (t, t1) -> t1
functionS (x, y) = y```

#### Given a type, write the function

```i :: a -> a
i = id

c :: a -> b -> a
c a _ = a

r :: [a] -> [a]
r a = tail a
-- ... others

co :: (b -> c) -> (a -> b) -> (a -> c)
co = (.) -- function composition

a :: (a -> c) -> a -> a
a f x = x -- ???

a' :: (a -> b) -> a -> b
-- a' f x = f x
a' = (\$)```

#### Fix it

```module Arith3Broken where

main :: IO ()
main = do
print \$ 1 + 2
putStrLn \$ show 10
print (negate -1)
print ((+) 0 blah)
where blah = negate 1```

#### Type-Kwon-Do

```f :: Int -> String
f = undefined

g :: String -> Char
g = undefined

h :: Int -> Char
h = g . f```
```data A
data B
data C

q :: A -> B
q = undefined

w :: B -> C
w = undefined

e :: A -> C
e = w . q ```
```data X
data Y
data Z

xz :: X -> Z
xz = undefined

yz :: Y -> Z
yz = undefined

xform :: (X, Y) -> (Z, Z)
xform (a, b) = (xz a, xz b)```
```munge :: (x -> y) -> (y -> (w, z)) -> x -> w
munge f1 f2 x = fst \$ f2 \$ f1 x
munge f1 f2 = fst . f2 . f1```

### 5.10 Definitions

2. principal type: generic type which still typechecks
```a
Num a => a
Int
-- The principal type here is the
-- parametrically polymorphic 'a'```
1. Type inference
2. Type variable: unspecified type or set of types
3. typeclass
4. Parametricity
5. Ad-hoc polymorphism: constrained polymorphism, apply typeclass constraints

### 5.11 Follow-up resources

1. Luis Damas; Robin Milner. Principal type-schemes for func- tional programs
2. Christopher Strachey. Fundamental Concepts in Programming Languages

Popular origin of the parametric/ad-hoc polymorphism distinction.

## CHAPTER6. TYPECLASSES

### 6.1 Typeclasses

• typeclass Eq, Num, Ord, Enum, Show
• type-defaulting typeclass, typeclass inheritance
• implicit function that create side effect

### 6.2 What are typeclasses?

typeclass and type are opposite

• type declaration: how type is created
• typeclass declaration: how type is consumed

typeclass - interface: ad-hoc polymorphism, generalize over a set of types to define and execute a standard set of features. eg, typeclass Eq -> type data comparation

### 6.3 Back to Bool

```-- :info Bool

-- data declaration
data Bool = False | True

-- typeclass that Bool implements.
instance Bounded Bool -- upper and lower bound
instance Enum Bool -- can be enumerated
instance Eq Bool -- equation
instance Ord Bool -- can be put into a sequential order
instance Read Bool -- parse string into thing. DONT USE.
instance Show Bool -- render thing into string```
• Ord <- Eq: be compared for equality before ordering.
• Enum <- Ord: be orderd before put into enumerated list.

### 6.4 Eq

```:info Eq
class Eq a where
(==) :: a -> a -> Bool
(/=) :: a -> a -> Bool

-- List of some Eq instances
instance Eq a => Eq [a]
instance Eq Ordering
instance Eq Int
instance Eq Float
instance Eq Double
instance Eq Char
instance Eq Bool
instance (Eq a, Eq b) => Eq (a, b)
instance Eq ()
instance Eq a => Eq (Maybe a)
instance Eq Integer```
```data (,) a b = (,) a b
instance (Eq a, Eq b) => Eq (a, b)
instance (Ord a, Ord b) => Ord (a, b)
instance (Show a, Show b) => Show (a, b)```

### 6.5 Num

```class Num a where
(+) :: a -> a -> a
(*) :: a -> a -> a
(-) :: a -> a -> a
negate :: a -> a
abs :: a -> a
signum :: a -> a
fromInteger :: Integer -> a
instance Num Integer
instance Num Int
instance Num Float
instance Num Double```

#### Integral

```class (Real a, Enum a) => Integral a where
quot :: a -> a -> a
rem :: a -> a -> a
div :: a -> a -> a
mod :: a -> a -> a
quotRem :: a -> a -> (a, a) divMod :: a -> a -> (a, a)
toInteger :: a -> Integer```

#### Fractional

```class (Num a) => Fractional a where
(/) :: a -> a -> a
recip :: a -> a
fromRational :: Rational -> a```
```divideThenAdd :: Fractional a => a -> a -> a
divideThenAdd x y = (x / y) + 1

divideThenAdd :: Num a => a -> a -> a  -- error
divideThenAdd x y = (x / y) + 1```

## 6.6 Type-defaulting typeclasses

```default Num Integer
default Real Integer
default Enum Integer
default Integral Integer
default Fractional Double
default RealFrac Double
default Floating Double
default RealFloat Double```

### 6.7 Ord

```-- :info Ord
-- Ord is constrained by Eq
class Eq a => Ord a where
compare :: a -> a -> Ordering
(<) :: a -> a -> Bool
(>=) :: a -> a -> Bool
(>) :: a -> a -> Bool
(<=) :: a -> a -> Bool
max :: a -> a -> a
min :: a -> a -> a
instance Ord a => Ord (Maybe a)
instance (Ord a, Ord b) => Ord (Either a b)
instance Ord Integer
instance Ord a => Ord [a]
instance Ord Ordering
instance Ord Int
instance Ord Float
instance Ord Double
instance Ord Char
instance Ord Bool```

### 6.8 Enum

```-- :info Enum
class Enum a where
succ :: a -> a
pred :: a -> a
toEnum :: Int -> a
enumFrom :: a -> [a]
enumFromThen :: a -> a -> [a]
enumFromTo :: a -> a -> [a]
enumFromThenTo :: a -> a -> a -> [a]
instance Enum Ordering
instance Enum Integer
instance Enum Int
instance Enum Char
instance Enum Bool
instance Enum ()
instance Enum Float
instance Enum Double```
```succ 4 -- 5
pred 'd' -- c
succ 4.5 -- 5.5
enumFormTo 3 8 -- [3, 4, 5, 6, 7, 8]
enumFromTo 'a' 'f' -- "abcdef"
enumFromThenTo 1 10 100 ---[1,10,19,28,37,46,55,64,73,82,91,100]```

### 6.9 Show

not for serialization, but for human redability.

```class Show a where
showsPrec :: Int -> a -> ShowS
show :: a -> String
showList :: [a] -> ShowS

instance Show a => Show [a]
instance Show Ordering
instance Show a => Show (Maybe a)
instance Show Integer
instance Show Int instance Show Char
instance Show Bool instance Show ()
instance Show Float instance Show Double```

#### Printing and side effects

```-- :t print
print :: Show a => a -> IO ()```

main function => side effect

() : empty tuple / unit: represents nothing

expression must have return value. () represents the end of IO action.

IO String: a means of producing a String, which perform side effects before get the value.

#### Working with Show

minimal implementation: implement show / showPrec

```data Mood = Blah

instance Show Mood where
show _ = "blah"

-- Blah => blah```
```data Mood = Blah deriving Show
-- Blah -> Blah```
##### Typeclass deriving

Typeclass instances we can magically derive are Eq, Ord, Enum, Bounded, Read, and Show.

```-- :t read

avoid using it:

```read "1234567" :: Integer
-- 1234567

-- *** Exception: Prelude.read: no parse```

### 6.11 Instances are dispatched by type

• a typeclass defines a set of functions and/or values

• types have instances of that typeclass

• the instances specify the ways that type uses the functions of the typeclass

```class Numberish a where
fromNumber :: Integer -> a
toNumber :: a -> Integer

-- pretend newtype is data for now
newtype Age =
Age Integer
deriving (Eq, Show)

instance Numberish Age where
fromNumber n = Age n
toNumber (Age n) = n

newtype Year =
Year Integer
deriving (Eq, Show)

instance Numberish Year where
fromNumber n = Year n
toNumber (Year n) = n```

usage:

```sumNumberish :: Numberish a => a -> a -> a
sumNumberish a a' = fromNumber summed where
integerOfA = toNumber a
integerOfAPrime = toNumber a'
summed = integerOfA + integerOfAPrime

sumNumberish (Age 10) (Age 10)
-- Age 20```
```-- This is even worse than the last one.
-- Don't use typeclasses to define default values.
-- Seriously. Haskell Ninjas will find you
-- and replace your toothpaste with muddy chalk.

class Numberish a where
fromNumber :: Integer -> a
toNumber :: a -> Integer
defaultNumber :: a

instance Numberish Age where
fromNumber n = Age n
toNumber (Age n) = n
defaultNumber = Age 65

instance Numberish Year where
fromNumber n = Year n
toNumber (Year n) = n
defaultNumber = Year 1988

defaultNumber -- error

defaultNumber :: Age -- Age 65

defaultNumber :: Year -- Year 1988```

#### Why not write a typeclass like this?

see Monoid chapter

### 6.12 Writing typeclass instances

#### Eq instances

Minimal complete definition: either == or /=.

```data Trivial = Trivial

Trivial == Trivial -- error, no instance

data Trivial = Trivial'

-- instance TYPECLASS TYPE where
instance Eq Trivial where
-- (DATA CONSTRUCTOR == DATA CONSTRUCTOR) = BOOL
Trivial' == Trivial' = True
-- (==) Trivial' Trivial' = True -- prefix notation

Trivial' == Trivial' -- True```

another example:

```data DayOfWeek =
Mon | Tue | Weds | Thu | Fri | Sat | Sun

-- day of week and numerical day of month
data Date =
Date DayOfWeek Int

instance Eq DayOfWeek where
(==) Mon Mon = True
(==) Tue Tue = True
(==) Weds Weds = True
(==) Thu Thu = True
(==) Fri Fri = True
(==) Sat Sat = True
(==) Sun Sun = True
(==) _ _ = False

instance Eq Date where
(==) (Date weekday dayOfMonth)
(Date weekday' dayOfMonth') =
weekday == weekday' && dayOfMonth == dayOfMonth'

Date Thu 10 == Date Thu 10
-- True
Date Thu 10 == Date Thu 11
-- False
Date Thu 10 == Date Weds 10
-- False```

#### Partial functions — not so strange danger

```f :: Int -> Bool
f 1 = True

f 1 -- True
f 2 -- error

-- using a unconditional case
f :: Int -> Bool
f 1 = True
f _ = False```

#### Sometimes we need to ask for more

```data Identity a = Identity a

-- error
instance Eq (Identity a) where
(==) (Identity v) (Identity v') = v == v'

-- okay, ensure a to have an instance of Eq
instance Eq a => Eq (Identity a) where
(==) (Identity v) (Identity v') = v == v'
```

#### Intermission: Exercises

```-- 1
data TisAnInteger = TisAn Integer

instance Eq TisAnInteger where
(==) (Tis a) (Tis b) = a == b

-- 2
data TwoIntegers = Two Integer Integer

instance Eq TwoIntegers where
(==) (Two a b) (Two a' b') = a' == a' && b == b'

-- 3
data StringOrInt = TisAnInt Int | TisAString String

instance Eq StringOrInt where
(==) (TisAnInt a) (TisAnInt b) = a == b
(==) (TisAString a) (TisAString b) = a == b
(==) _ _ = False

-- 4
data Pair a = Pair a a

instance Eq a => Eq (Pair a) where
(==) (Pair a b) (Pair a' b) = a' == a' && b == b'

-- 5
data Tuple a b = Tuple a b

instance (Eq a, Eq b) => Eq (Tuple a b) where
(==) (Tuple a b) (Tuple a' b) = a' == a' && b == b'

-- 6
data Which a = ThisOne a | ThatOne a

instance Eq a => Eq Which a where
(==) (ThisOne a) (ThisOne b) = a == b
(==) (ThatOne a) (ThatOne b) = a == b
(==) _ _ = False

-- 7
data EitherOr a b = Hello a | Goodbye b

instance (Eq a, Eq b) => Eq (EitherOr a b) where
(==) (Hello a) (Hello b) = a == b
(==) (Goodbye a) (Goodbye b) = a == b
(==) _ _ = False```

#### Ord instances

```data DayOfWeek =
Mon | Tue | Weds | Thu | Fri | Sat | Sun
deriving (Ord, Show)

-- default Eq, left value smaller
Mon > Tue -- False
Sun > Mon -- True
compare Tue Weds -- LT

-- custom instance
instance Ord DayOfWeek where
compare Fri Fri = EQ
compare Fri _ = GT
compare _ Fri = LT
compare _ _ = EQ

compare Fri Sat -- GT
compare Sat Mon -- EQ
compare Fri Mon -- GT
compare Sat Fri -- LT
Mon > Fri -- False
Fri > Sat -- True```

### 6.13 Gimme more operations

```-- error
add :: a -> a -> a
add x y = x + y

-- okay
add :: Num a => a -> a -> a
add x y = x + y

-- error
addWeird :: Num a => a -> a -> a
if x > 1
then x + y
else x

-- okay
addWeird :: (Num a, Ord a) => a -> a -> a
if x > 1
then x + y
else x```

#### Ord implies Eq

```-- error
check' :: a -> a -> Bool
check' a a' = a == a'

-- okay
check' :: Ord a => a -> a -> Bool
check' a a' = a == a'```

#### Concrete types imply all the typeclasses they provide

```add :: Int -> Int -> Int
add x y = x + y
addWeird :: Int -> Int -> Int
if x > 1
then x + y
else x

check' :: Int -> Int -> Bool
check' a a' = a == a'```

### 6.14 Chapter Exercises

#### Does it typecheck?

```-- 1
data Person = Person Bool deriving Show

printPerson :: Person -> IO ()
printPerson person = putStrLn (show person)

-- 2
data Mood = Blah | Woot deriving (Show, Eq)

settleDown x = if x == Woot
then Blah
else x```

#### Given a datatype declaration, what can we do?

```data Rocks = Rocks String deriving (Eq, Show)
data Yeah = Yeah Bool deriving (Eq, Show)
data Papu = Papu Rocks Yeah deriving (Eq, Show)

-- 1 fixed
phew = Papu (Rocks "chases") (Yeah True)

-- 2
truth = Papu (Rocks "chomskydoz")
(Yeah True)

-- 3
equalityForall :: Papu -> Papu -> Bool
equalityForall p p' = p == p'

-- 4  error no instance Ord
comparePapus :: Papu -> Papu -> Bool
comparePapus p p' = p > p'
```

#### Type-Kwon-Do

```-- 1
chk :: Eq b => (a -> b) -> a -> b -> Bool
chk f a b = (f a) == b

-- 2
-- Hint: use some arithmetic operation to
-- combine values of type 'b'. Pick one.
arith :: Num b => (a -> b) -> Integer -> a -> b
arith f i a = (f a) + (fromInteger i)```

### 6.15 Chapter Definitions

1. typeclass inheritance: superclass => typeclass
```class Num a => Fractional a where
(/) :: a -> a -> a
recip :: a -> a
fromRational :: Rational -> a```
1. Side effects:

2. IO:

3. instance: typeclass => type

4. derived instance: deriving ..

### 6.16 Typeclass inheritance, partial

Eq => Ord => Real

Num => Real / Fractional

Real, Enum => Integral

### 6.17 Follow-up resources

2. Cordelia V. Hall, Kevin Hammond, Simon L. Peyton Jones, and Philip L. Wadler. Typeclasses in Haskell.

## CHAPTER7. MOREFUNCTIONALPATTERNS

### 7.1 Make it func-y

function:

• as values in expressions, lists, or tuples;
• as arguments in function;
• as returned result from function;
• make use of syntactic patterns.

### 7.2 Arguments and parameters

#### Binding variables to values

```bindExp :: Integer -> String
bindExp x = let y = 5 in
"the integer was: " ++ show x
++ " and y was: " ++ show y```

```bindExp :: Integer -> String
bindExp x = let x = 10; y = 5 in
"the integer was: " ++ show x
++ " and y was: " ++ show y```

### 7.4 Pattern matching

pattern => value === data constructor

order matters

#### Pattern matching against data constructors

```module RegisteredUser where

newtype AccountNumber = AccountNumber Integer

data User = UnregisteredUser

-- RegisteredUser :: Username -> AccountNumber -> User
-- AccountNumber :: Integer -> AccountNumber

printUser :: User -> IO ()
printUser UnregisteredUser = putStrLn "UnregisteredUser"
(AccountNumber acctNum))
= putStrLn \$ name ++ " " ++ show acctNum

-- usage:
printUser UnregisteredUser -- "UnregisteredUser"

let myAcct = (AccountNumber 10456)
printUser \$ RegisteredUser myUser myAcct```

unpack data constructor:

```data WherePenguinsLive = Galapagos
| Antarctica
| Australia
| SouthAfrica
| SouthAmerica deriving (Eq, Show)

data Penguin = Peng WherePenguinsLive deriving (Eq, Show)

isSouthAfrica' :: WherePenguinsLive -> Bool
isSouthAfrica' SouthAfrica = True
isSouthAfrica' _           = False

gimmeWhereTheyLive :: Penguin -> WherePenguinsLive gimmeWhereTheyLive (Peng whereitlives) = whereitlives

humboldt = Peng SouthAmerica
gentoo = Peng Antarctica
macaroni = Peng Antarctica
little = Peng Australia
galapagos = Peng Galapagos

galapagosPenguin :: Penguin -> Bool
galapagosPenguin (Peng Galapagos) = True
galapagosPenguin _ = False

antarcticPenguin :: Penguin -> Bool
antarcticPenguin (Peng Antarctica) = True
antarcticPenguin _ = False

-- in this final function, the || operator
-- is an `or` function, which will return True
-- if either value is True
antarcticOrGalapagos :: Penguin -> Bool
antarcticOrGalapagos p = (galapagosPenguin p)
|| (antarcticPenguin p)```

#### Intermission: Exercises

```f :: (a, b, c) -> (d, e, f) -> ((a, d), (c, f))
f (a, b, c) (d, e, f) = ((a, d), (c, f))```

### 7.5 Case expressions

```f x = if x + 1 == 1 then "AWESOME" else "wut"

-- using case
funcZ x = case x + 1 == 1 of
True -> "AWESOME"
False -> "wut"

pal' xs = case y of
True -> "yes"
False -> "no"
where y = xs == reverse xs```

#### Intermission: Exercises

```functionC x y = if (x > y) then x else y
-- using case
functionC x y = case x > y of
True -> x
False -> y

ifEvenAdd2 n = if even n then (n+2) else n
-- using case
ifEvenAdd2 n = case even n of
True -> n + 2
False -> n

nums x = case compare x 0 of
LT -> -1
GT -> 1
EQ -> 0```

### 7.6 Higher-order functions

```-- :t flip
flip :: (a -> b -> c) -> b -> a -> c
flip f x y = f y x```

### 7.7 Guards

```myAbs :: Integer -> Integer
myAbs x
| x < 0 = (-x)
| otherwise = x```

### 7.8 Function composition

```(.) :: (b -> c) -> (a -> b) -> a -> c
(f . g) x = f (g x)```
```-- why using \$ ?
negate . sum \$ [1, 2, 3, 4, 5] -- -15

-- :i (.)
(.) :: (b -> c) -> (a -> b) -> a -> c
infixr 9 .

-- composition precedence 9, function application 10

-- wrong
negate . sum [1, 2, 3, 4, 5]
negate . 15 -- error```
```take 5 . reverse \$ [1..10]
-- [10,9,8,7,6]

take 5 . enumFrom \$ 3
-- [3,4,5,6,7]

take 5 . filter odd . enumFrom \$ 3
-- [3,5,7,9,11]```

point: argument

### 7.10 Demonstrating composition

print: the composition of show and putStrLn

```pusStr :: String -> IO()
putStrLn :: String -> IO()

show :: Show a => a -> String

print :: Show a => a -> IO ()

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

### 7.11 Chapter Exercises

#### Let’s write code

```tensDigit :: Integral a => a -> a
tensDigit x = d
where xLast = x `div` 10
d = xLast `mod` 10

-- using divMod
tensDigit :: Integral a => a -> a
tensDigit x = d
where xLast = fst \$ divMod x 10
d = lst \$ divMod xLast 10 ```
```foldBool :: a -> a -> Bool -> a
-- using case
foldBool x y b = case b of
True -> x
False -> y

-- using guard
foldBool x y b =
| b = x
| otherwise = y

-- using pattern matching
foldBool3 :: a -> a -> Bool -> a
foldBool3 x y True = x
foldBool3 x y False = y```
```g :: (a -> b) -> (a, c) -> (b, c)
g f (a, c) = (f a, c)```
```read :: Read a => String -> a
show :: Show a => a -> String

roundTrip :: (Show a, Read a) => a -> a
roundTrip a = read (show a)

main = do
print (roundTrip 4)
print (id 4)

-- using point free
roundTrip :: (Show a, Read a) => a -> a

-- force to Int
main = do
print (roundTrip 4 :: Int)
print (id 4)```

### 7.12 Chapter Definitions

1. Binding or bound
2. anonymousfunction
3. Currying
5. Bottom: non-value, lazy
6. Higher-order functions
7. Composition
8. Pointfree

### 7.13 Follow-up resources

1. Paul Hudak; John Peterson; Joseph Fasel. A Gentle Introduction to Haskell, chapter on case expressions and pattern matching.

2. Simon Peyton Jones. The Implementation of Functional Programming Languages, pages 53-103.

3. Christopher Strachey. Fundamental Concepts in Programming Languages, page 11 for explanation of currying.

4. J.N. Oliveira. An introduction to pointfree programming.

5. Manuel Alcino Pereira da Cunha. Point-free Program Calculation.

## CHAPTER8. RECURSION

### 8.2 Factorial

```fact :: Int -> Int
fact 1 = 1
fact i = i * fact (i-1)```

#### Another way to look at recursion

Any programming language, such as Haskell, that is built purely on lambda calculus has only one verb: apply a function to an argument.

### 8.3 Bottom

⊥ or bottom: computations that do not successfully result in a value.

```f :: Bool -> Int
f False = 0
f _ = error \$ "*** Exception: "
++ "Non-exhaustive"
++ "patterns in function f"```

partial function / total function

```data Maybe a = Nothing | Just a

f :: Bool -> Maybe Int
f False = Just 0
f _ = Nothing```

### 8.4 Fibonacci numbers

1. Consider the types
```fibonacci :: Integer -> Integer
-- or
fibonacci :: Integral a => a -> a```
1. Consider the base case
```fibonacci :: Integral a => a -> a
fibonacci 0 = 0 fibonacci 1 = 1```
1. Consider the arguments
```fibonacci :: Integral a => a -> a
fibonacci 0 = 0
fibonacci 1 = 1
fibonacci x = (x - 1) (x - 2)
-- note: this doesn't work quite yet.```
1. Consider the recursion
```fibonacci :: Integral a => a -> a
fibonacci 0 = 0
fibonacci 1 = 1
fibonacci x = fibonacci (x - 1) + fibonacci (x - 2) ```

### 8.5 Integral division from scratch

```dividedBy :: Integer -> Integer -> Integer
dividedBy = div

-- type synonyms, changes to
type Numerator = Integer
type Denominator = Integer
type Quotient = Integer

dividedBy :: Numerator -> Denominator -> Quotient
dividedBy = div```
```dividedBy :: Integral a => a -> a -> (a, a)

dividedBy num denom = go num denom 0
where go n d count
| n < d = (count, n)
| otherwise = go (n - d) d (count + 1)```

### 8.6 Chapter Exercises

#### Review of types

```-- :t
[[True, False], [True, True], [False, True]] -- [[Bool]]```

#### Recursion

```dividedBy :: Integral a => a -> a -> (a, a)
dividedBy num denom = go num denom 0
where go n d count
| n < d = (count, n)
| otherwise = go (n-d) d (count+1)```
```recSum :: (Eq a, Num a) => a -> a
recSum n = go n 0
where go n acc
| n < 0 = acc
| otherwise = go (n-1) (acc+n)```
```recMul :: (Integral a) => a -> a -> a
recMul a b = go a b 0
where go a b acc
| a == 0 = acc
| otherwise = go (a-1) b (acc+b)```

#### McCarthy 91 function

```mc91 :: Int -> Int
mc91 n
| n > 100 = n - 10
| otherwise = mc91 . mc91 \$ n + 11

map mc91 [95..110]
-- [91,91,91,91,91,91,91,92,93,94,95,96,97,98,99,100]```

#### Numbers into words

```module WordNumber where

import Data.List (intersperse)

digitToWord :: Int -> String
digitToWord n = case n of
0 -> "zero"
1 -> "one"
2 -> "two"
3 -> "three"
4 -> "four"
5 -> "five"
6 -> "six"
7 -> "seven"
8 -> "eight"
9 -> "nine"

digits :: Int -> [Int]
digits n = go n []
where go n acc
| n > 9 = go (div n 10) ((mod n 10) : acc)
| otherwise = n : acc

wordNumber :: Int -> String
wordNumber n = concat . intersperse '-' . map digitToWord . digits ```

1. Recursion

## CHAPTER9. LISTS

### 9.2 The list datatype

```-- data TYPE-CONSTRUCTOR ARGS =
-- DATA CONSTRUCTOR or
-- DATA CONSTRUCTOR and MORE LIST
data [] a = [] | a : [a]```

(:) : cons / construct

### 9.3 Pattern matching on lists

```myHead [] = []
myHead (x : _) = x

-- fall safe
myTail [] = []
myTail (_: xs) = xs```

#### Using Maybe

`data Maybe a = Nothing | Just a`
```safeTail :: [a] -> Maybe [a]
safeTail [] = Nothing
safeTail (_ : []) = Nothing
safeTail (_ : xs) = Just xs```

### 9.4 List’s syntactic sugar

```[1, 2, 3] ++ [4]

-- equals to

1 : 2 : 3 : [] ++ 4 : []```

### 9.5 Using ranges to construct lists

```[1..10]
-- equals to
enumFromTo 1 10

[1, 2..10]```
```class Enum a where
succ :: a -> a
pred :: a -> a
toEnum :: Int -> a
enumFrom :: a -> [a]
enumFromThen :: a -> a -> [a]
enumFromTo :: a -> a -> [a]
enumFromThenTo :: a -> a -> a -> [a]```

#### Exercise

```myEnumFromTo :: Enum a => a -> a -> [a]
myEnumFromTo x y
| xi > yi = []
| otherwise = x : myEnumFromToi (succ xi) yi
myEnumFromToi a b
| a > b = []
| otherwise = (toEnum a) : myEnumFromToi (succ a) b```

### 9.6 Extracting portions of lists

```take :: Int -> [a] -> [a]
drop :: Int -> [a] -> [a]
splitAt :: Int -> [a] -> ([a], [a])

takeWhile :: (a -> Bool) -> [a] -> [a]
dropWhile :: (a -> Bool) -> [a] -> [a]```

#### Intermission: Exercises

1. reverse using `dropWhile` and `takeWhile`
```myWords :: [Char] -> [[Char]]
myWords [] = []
myWords a@(x:xs)
| x == ' ' = myWords xs
| otherwise = takeWhile (/=' ') a : (myWords . dropWhile (/=' ') \$ a)

-- using case
myWords :: [Char] -> [[Char]]
myWords [] = []
myWords a =
case dropWhile (==' ') a of
[] -> []
xs -> takeWhile (/=' ') xs
: myWords (dropWhile (/=' ') xs)

-- using break
myWords :: [Char] -> [[Char]]
myWords [] = []
myWords a =
case dropWhile (==' ') a of
[] -> []
az -> w : rest
where (w, rest) = break (==' ') az

myWords :: String -> [String]
myWords [] = []
myWords (' ':xs) = myWords xs
myWords xs =  takeWhile (/= ' ') xs : myWords (dropWhile (/= ' ') xs)```
```module PoemLines where

firstSen = "Tyger Tyger, burning bright\n"
secondSen = "In the forests of the night\n"
thirdSen = "What immortal hand or eye\n"
fourthSen = "Could frame thy fearful symmetry?"
sentences = firstSen ++ secondSen
++ thirdSen ++ fourthSen

-- putStrLn sentences
-- should print
-- Tyger Tyger, burning bright
-- In the forests of the night
-- What immortal hand or eye
-- Could frame thy fearful symmetry?
-- Implement this

myLines :: String -> [String]
myLines [] = []
myLines xs = case dropWhile (== '\n') xs of
[] -> []
az -> w : myLines rest
where (w, rest) = break (== '\n') az

-- What we want 'myLines sentences' to equal
shouldEqual =
[ "Tyger Tyger, burning bright"
, "In the forests of the night"
, "What immortal hand or eye"
, "Could frame thy fearful symmetry?"
]
-- The main function here is a small test
-- to ensure you've written your function
-- correctly.

main :: IO ()
main =
print \$ "Are they equal? "
++ show (myLines sentences == shouldEqual)```
```separate :: Char -> [Char] -> [[Char]]
separate _ [] = []
separate sep xs = case dropWhile (== sep) xs of
[] -> []
az -> w : separate sep rest
where (w, rest) = break (== sep) az

-- using purely takeWhile and dropWhile
separate' :: Char -> [Char] -> [[Char]]
separate' _ [] = []
separate' sep xs = w : separate' sep ws
where w = takeWhile (/= sep) xs
ws = dropWhile (== sep) (drop (length w) xs)

myWords :: [Char] -> [[Char]]
myWords = separate ' '

myLines :: String -> [String]
myLines = separate '\n'```

### 9.7 List comprehensions

#### List comprehensions with Strings

```-- :t elem
elem :: Eq a => a -> [a] -> Bool```

#### Intermission: Exercises

```[(x, y) | x <- mySqr, y <- myCube]

[(x, y) | x <- mySqr, y <- myCube, x < 50, y < 50]```

### 9.8 Spines and non-strict evaluation

spine (:) => shape of tree, It is also possible to evaluate only part of the spine of a list and not the rest of it.

spine-strict: length

spine-lazt: map

non-strictness

#### Using GHCi’s :sprint command

`:spring`

```l = ['a'..'z'] -- WHNF

-- :sprint
l = _

take 5 l
-- :sprint
l = 'a' : 'b' : 'c' : 'd' : 'e' : _```

#### Spines are evaluated independently of values

weak head normal form: evaluated to reach data constructor

normal form: fully evaluated

```(1, 2) -- WHNF & NF

(1, _ + _)
-- WHNF, but not NF. The (+) and its
-- unknown arguments could be evaluated

(1, 1 + 1)
-- WHNF, but not NF.
-- The 1 + 1 could be evaluated.

\x -> x * 10 -- WHNF & NF

"Papu" ++ "chon" -- Neither WHNF nor NF```

only evaluating spine, so wont crash

```x = [1, undefined, 3]
length x -- 3

-- like this
length :: [a] -> Integer
length [] = 0
length (_:xs) = 1 + length xs```

### 9.9 Transforming lists of values

map lazy

`take 1 . map (+1) \$ [1, 2, undefined] -- [2]`

lazy in the spine, strict in the leaves

### 9.10 Filtering lists of values

```filter :: (a -> Bool) -> [a] -> [a]
filter _ [] = []
filter pred (x:xs)
| pred x = x : filter pred xs
| otherwise = filter pred xs```

#### Intermission: Exercises

`filter (\x -> rem x 3 == 0) [1..30]`
`length . filter (\x -> rem x 3 == 0) \$ [1..30]`
```filter \x -> not \$ elem x ["the", "a", "an"] . words \$ "the brown dog was a goof"

filter (not . flip elem ["the", "a", "an"]) . words \$ "the brown dog was a goof"```

### 9.11 Zipping lists

```-- :t zip
zip :: [a] -> [b] -> [(a, b)]
zipWith :: (a -> b -> c) -> [a] -> [b] -> [c]```

#### Zipping exercises

```zip' :: [a] -> [b] -> [(a, b)]
zip' (a: az) (b: bz) = (a, b) : zip' az bz
zip' _ _ = []```
```zipWith' :: (a -> b -> c) -> [a] -> [b] -> [c]
zipWith' f (a:az) (b:bz) = f a b : zipWith' az bz
zipWith' _ _ _ = []```

### 9.12 Chapter Exercises

#### Data.Char

```import Data.Char

fUp = filter isUpper

capFisrt :: [Char] -> [Char]
capFisrt (x:xs) = toUpper x : xs
capFisrt _ = ""

capAll :: [Char] -> [Char]
capAll (x:xs) = toUpper x : capAll xs
capAll _ = ""

fstCap :: [Char] -> Char
fstCap xs = toUpper \$ head xs```

#### Ciphers

```myOr :: [Bool] -> Bool
myOr (x:xs) = if x then True else myOr xs
myOr [] = False

myOr' [] = False
myOr' (x:xs)
| x = x
| otherwise = myOr xs

myAny :: (a -> Bool) -> [a] -> Bool
myAny f (x:xs) = if f x then True else myAny f xs
myAny _ _ = False

myElem :: Eq a => a -> [a] -> Bool
myElem a (x:xs) = if a == x then True else myElem a xs
myElem _ _ = False

myReverse :: [a] -> [a]
myReverse (x:xs) = myReverse xs ++ [x]
myReverse _ = []

myReverse' a = go a []
where go (x:xs) acc = go xs (x:acc)
go _ acc = acc

squish :: [[a]] -> [a]
squish (x:xs) = x ++ squish xs
squish _ = []

squishMap :: (a -> [b]) -> [a] -> [b]
squishMap f (x:xs) = f x ++ squishMap f xs
squishMap _ _ = []

myMaximumBy :: (a -> a -> Ordering) -> [a] -> a
myMaximumBy f (acc:xs) = go f acc xs
where go f acc (x:xs)
| f acc x == GT = go f acc xs
| otherwise = go f x xs
go _ acc _ = acc
myMaximumBy _ _ = undefined```

### 9.13 Definitions

1. Product type: tuples or data constructors with more than one argument.

2. Sum type: using the pipe, |

3. Cons:

4. Cons cell:

5. spine

## CHAPTER10. FOLDINGLISTS

### 10.1 Folds

Catamorphism: https://en.wikipedia.org/wiki/Catamorphism

### 10.2 Bringing you into the fold

`foldr :: Foldable t => (a -> b -> b) -> b -> t a -> b`

### 10.4 Fold right

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

foldr :: (a -> b -> b) -> b -> [a] -> b
foldr f acc xs = case xs of
[] -> acc
(x:xs) -> f x (foldr f acc xs)```

#### How foldr evaluates

stage: traversal and folding

used with infinite list

```foldr (\_ _ -> 9001) 0 [1..5]
-- 9001

foldr (\_ _ -> 9001) 0 [1, 2, 3, undefined]
-- 9001

foldr (\_ _ -> 9001) 0 ([1, 2, 3] ++ undefined)
-- 9001

foldr (\_ _ -> 9001) 0 [1..]
-- 9001```
```const x _ = x
foldr const 0 [1..]
-- 1```

### 10.5 Fold left

```foldl :: (b -> a -> b) -> b -> [a] -> b
foldl f acc [] = acc
foldl f acc (x:xs) = foldl f (f acc x) xs```
```f = (\x y -> concat ["(",x,"+",y,")"])

foldl f "0" (map show [1..5])
"(((((0+1)+2)+3)+4)+5)"

foldr f "0" (map show [1..5])
"(1+(2+(3+(4+(5+0)))))"

foldr (+) 0 [1..5] -- 15

scanr (+) 0 [1..5] -- [15,14,12,9,5,0]

foldl (+) 0 [1..5] -- 15

scanl (+) 0 [1..5] -- [0,1,3,6,10,15]

last (scanl f z xs) = foldl f z xs
head (scanr f z xs) = foldr f z xs```

#### Associativity and folding

```foldr (:) [] [1..3] -- [1,2,3]

foldl (flip (:)) [] [1..3] -- [3,2,1]```

#### Unconditional spine recursion

foldl: forced spine evaluation => finite list

foldl'

### 10.7 Folding and evaluation

`foldr f acc a = foldl (flip f) acc (reverse a) `

foldl only works for finite list

### 10.8 Summary

foldr:

1. foldr :: `(a -> b -> b) -> b -> [a] -> b`; b in `-> b ->` is the rest of the fold

2. associate to the right

3. infinite list, lazy evaluation

foldl:

1. produce value after reaching the end

2. associate to the right

3. finite list

4. nearly useless; prefer foldl'

### 10.9 Scans

```foldr :: (a -> b -> b) -> b -> [a] -> b
scanr :: (a -> b -> b) -> b -> [a] -> [b]
foldl :: (b -> a -> b) -> b -> [a] -> b
scanl :: (b -> a -> b) -> b -> [a] -> [b]```
```scanl :: (a -> b -> a) -> a -> [b] -> [a]
scanl f q ls =
q : (case ls of
[]   -> []
x:xs -> scanl f (f q x) xs)```

#### Getting the fibonacci number we want

bang bang operator:

`(!!) :: [a] -> Int -> a`
```fibs = 1 : scanl (+) 1 fibs -- infinite list

fibsN x = fibs !! x```

### 10.10 Chapter Exercises

#### Warm-up and review

```stops = "pbtdkg"
vowels = "aeiou"

svs :: [Char] -> [Char] -> [(Char, Char, Char)]
svs stops vowels = [(s, v, s2) | s <- stops, v <- vowels, s2 <- stops]

svs :: [Char] -> [Char] -> [(Char, Char, Char)]
svs stops vowels = [(s, v, s2) | s <- stops, v <- vowels, s2 <- stops, p == 'p']```
```seekritFunc x =
div (sum (map length (words x)))
(length (words x))

-- rewrite
seekritFunc ::  Fractional a => String -> a
seekritFunc x = fromIntegral (sum (map length (words x)))
/ fromIntegral (length (words x))```

#### Rewriting functions using folds

```myOr :: [Bool] -> Bool
myOr = foldr || False

myAny :: (a -> Bool) -> [a] -> Bool
myAny f = foldr (\a acc -> f a || acc) False

myElem :: Eq a => a -> [a] -> Bool
myElem x = foldr (\a acc -> x == a || acc) False

myReverse :: [a] -> [a]
myReverse = foldl (flip :) []

myMap :: (a -> b) -> [a] -> [b]
myMap f = foldr (\a acc -> f a : acc) []
myMap' f = foldr ((:) . f) [] -- nicer

myFilter :: (a -> Bool) -> [a] -> [a]
myFilter f = foldr (\a acc -> if f a then a : acc else acc) []
myFilter' f = foldr g []
where g a acc
| f a = a : acc
| otherwise = acc

squish :: [[a]] -> [a]
squish = foldr (++) []

squishMap :: (a -> [b]) -> [a] -> [b]
squishMap f = foldr (\a acc -> f a ++ acc) []
squishMap' f = foldr ((++) . f) [] -- nicer

myMaximumBy :: (a -> a -> Ordering) -> [a] -> a
myMaximumBy f (x:xs) = foldr (\a acc -> if f a acc == GT
then a
else acc)
x
xs
myMaximumBy _ [x] = x
myMaximumBy _ [] = undefined

myMaximumBy' f (x:xs) = foldr g x xs
where g a b
| g a b == GT = a
|otherwise b
myMaximumBy' _ [x] = x
myMaximumBy' _ [] = undefined```

### 10.11 Definitions

1. Fold:

2. Catamorphism: breaking down structure

3. tail call: final result of a function

4. Tail recursion: a function whose tail calls are recursive invo- cations of itself

### 10.13 Follow-up resources

2. Richard Bird. Sections 4.5 and 4.6 of Introduction to Functional Programming using Haskell (1998).

3. Antoni Diller. Introduction to Haskell

4. Graham Hutton. A tutorial on the universality and expressive- ness of fold.

## CHAPTER11. ALGEBRAICDATATYPES

### 11.1 Algebraic datatypes

pattern matching, type checking, and inference

A type can be thought of as an enumeration of constructors that have zero or more arguments.

sum types, product types: record syntax, type aliases (String = [Char]), newtype

This chapter will:

• `algebra` in algebraic datatypes
• data constructors
• custom datatypes
• type synonyms / newtype;
• kinds

### 11.2 Data declarations review

```-- data TYPE-CONSTRUCTOR (ARGS) = DATA-CONSTRUCTOR (ARGS) or ..

-- enumeration of two possible constructors
data Bool = False | True

data [] a = [] | a:[a]```

### 11.3 Data and type constructors

type constructors: type level, in type signatures and typeclass declarations and instances. Types are static and resolve at compile time.

data constructors: construct the values at term level, values you can interact with at runtime.

constants: Type and data constructors that take no arguments. They can only store a fixed type and amount of data. eg, Bool - type constant;. It enumerates two values that are also constants, True and False, because they take no arguments.

```-- type constants, value constants
data Trivial = Trivial'

-- type constructor, data constructor
data UnaryTypeCon a = UnaryValueCon a```

#### Type constructors and kinds

kind:

```-- :k Bool
Bool :: *

-- :k [Int]
[Int] :: *

-- :k []
[] :: * -> *```

### 11.4 Data constructors and values

data constructors:

constant values:

```-- type constant, constant value
data PugType = PugData

-- phantom a,  constant value
data HuskyType a = HuskyData

--
data DogueDeBordeaux doge = DogueDeBordeaux doge```

query `:t` of the data, not the type

### 11.5 What’s a type and what’s data?

type constructors - compile-time

----> phase separation --->

data constructors - runtime

### 11.6 Data constructor arities

Arity: number of arguments a function or constructor takes.

nullary: takes no arguments

```-- nullary
data Example0 =
Example0 deriving (Eq, Show)

-- unary
data Example1 =
Example1 Int deriving (Eq, Show)

-- product of Int and String
data Example2 =
Example2 Int String deriving (Eq, Show)```

### 11.7 What makes these datatypes algebraic?

cardinality

#### Unary constructors

it has cardinality same as the type they contain

#### newtype

```newType Goats = Goats Int deriving (Eq, Show)

newType Cows = Cows Int deriving (Eq, Show)

tooManyGoats :: Goats -> Bool
tooManyGoats (Goats n) = n > 42```
```class TooMany a where
tooMany :: a -> Bool

instance TooMany Int where
tooMany n = n > 42

newtype Goats = Goats Int deriving Show

instance TooMany Goats where
tooMany (Goats n) = n > 43

newtype Goats = Goats Int deriving (Eq, Show)

instance TooMany Goats where
tooMany (Goats n) = tooMany n```

GeneralizedNewtypeDeriving:

```{-# LANGUAGE GeneralizedNewtypeDeriving #-}
class TooMany a where
tooMany :: a -> Bool

instance TooMany Int where
tooMany n = n > 42

newtype Goats = Goats Int deriving (Eq, Show, TooMany)
-- add pragma, so do not need instance```

#### Intermission: Exercises

```{-# FlexibleInstances #-}
class TooMany a where
tooMany :: a -> Bool

instance TooMany (Int, String) where
tooMany (n, s) = n > 42

-- with newtype
newtype Goats = Goats (Int, String) deriving Show

instance TooMany Goats where
tooMany (Goats (n, s)) = n > 42```
```class TooMany a where
tooMany :: a -> Bool

newtype Goats = Goats (Int, Int) deriving Show

instance TooMany Goats where
tooMany (Goats (a, b)) = (a + b) > 42```
```{-# LANGUAGE FlexibleInstances #-}
class TooMany a where
tooMany :: a -> Bool

instance TooMany Int where
tooMany n = n > 42

instance (Num a, TooMany a) => TooMany (a, a) where
tooMany (n, n') =  tooMany (n + n')```

### 11.9 Product types

#### Record syntax

record: product types with additional syntax to access fields

```data Person = MkPerson String Int deriving (Eq, Show)

-- these are just sample data
jm = MkPerson "julie" 108
ca = MkPerson "chris" 16

namae :: Person -> String
namae (MkPerson s _) = s

-- uaing record
data Person = Person { name :: String
, age :: Int }
deriving (Eq, Show)

-- :t name
name :: Person -> String
-- :t age
age :: Person -> Int

Person "Papu" 5
-- Person {name = "Papu", age = 5}
papu = Person "Papu" 5
age papu -- 5
name papu -- "Papu"```

#### Intermission: Jammin Exercises

```module Jammin where

data Fruit = Peach
| Plum
| Apple
| Blackberry deriving (Eq, Show)

data JamJars = Jam Fruit Int deriving (Eq, Show)

-- using record syntax
data JamJars = Jam {fruit :: Fruit
,jars  :: Int} deriving (Eq, Show, Ord)

rowJars :: [JamJars] -> [Int]
rowJars = map jars

jarsCount :: [JamJars] -> Int
jarsCount = sum . rowJars

mostRow :: [JamJars] -> JamJars
mostRow = maximumBy (\j1 j2 -> compare (jars j1) (jars j2))

compareKind (Jam k _) (Jam k' _) = compare k k'
sortJams :: [JamJars] -> [JamJars]
sortJams = sortBy compareKind

groupJam :: [JamJars] -> [JamJars]
groupJam = groupBy (\j1 j2 -> fruit j1 == fruit j2) . sortJams
```

### 11.10 Normal form

distributive property: `a * (b + c) -> (a * b) + (a * c)`

Product types distribute over sum types

normal form: sum of products

```data Expr = Number Int
| Minus Expr
| Mult Expr Expr
| Divide Expr Expr```
```type Number = Int
type Minus = Expr
type Mult = (Expr, Expr)
type Divide = (Expr, Expr)

type Expr = Either Number
(Either Minus
(Either Mult Divide)))```

### 11.11 Constructing and deconstructing values

#### Exercise

```data OperatingSystem = GnuPlusLinux
| OpenBSDPlusNevermindJustBSDStill
| Mac
| Windows deriving (Eq, Show)

| Agda
| Idris
| PureScript deriving (Eq, Show)

data Programmer =
Programmer {os :: OperatingSystem
,lang :: ProgrammingLanguage} deriving (Eq, Show)

allOperatingSystems :: [OperatingSystem]
allOperatingSystems = [ GnuPlusLinux
, OpenBSDPlusNevermindJustBSDStill
, Mac
, Windows ]

allLanguages :: [ProgrammingLanguage]
allLanguages = [Haskell, Agda, Idris, PureScript]

allProgrammers :: [Programmer]
allProgrammers = [ Programmer { os = o
, lang = l}
| o <- allOperatingSystems
, l <- allLanguages ]```

#### Accidental bottoms from records

```-- partially apply record
partialAf = Programmer {os = GnuPlusLinux}

partialAf -- error```

#### Deconstructing values

```newtype Name    = Name String deriving Show
newtype Acres   = Acres Int deriving Show

data FarmerType = DairyFarmer
| WheatFarmer
| SoybeanFarmer deriving Show

data Farmer = Farmer Name Acres FarmerType deriving Show

-- destructing
isDairyFarmer :: Farmer -> Bool
isDairyFarmer (Farmer _ _ DairyFarmer) = True
isDairyFarmer _ = False

data Farmer = Farmer { name       :: Name
, acres      :: Acres
, farmerType :: FarmerType } deriving Show

-- destruct record
isDairyFarmer :: Farmer -> Bool
isDairyFarmer farmer = farmerType farmer == DairyFarmer```

### 11.12 Function type is exponential

`a -> b` : b ^ a

`a -> b -> c` : (c ^ b) ^ a = c ^ (b * a)

### 11.13 Higher-kinded datatypes

```-- Identical to (a, b, c, d)
-- :kind (,,,)
(,,,) :: * -> * -> * -> * -> *
```

### 11.14 Lists are polymorphic

Any operator that starts with a colon (:) must be an infix type or data constructor.

```data Product a b = a :&: b deriving (Eq, Show)

1 :&: 2 :: (Num a, Num b) => Product a b```
```dataList a = Nil | Cons a (List a)

oneItem = (Cons "woohoo!" Nil)```

### 11.15 Binary Tree

```data BinaryTree a =
Leaf | Node (BinaryTree a) a (BinaryTree a)
deriving (Eq, Ord, Show)```

#### Inserting into trees

```insert' :: Ord a => a -> BinaryTree a -> BinaryTree a
insert' b Leaf = Node Leaf b Leaf
insert' b (Node left a right)
| b == a = Node left a right
| b < a  = Node (insert' b left) a right
| b > a  = Node left a (insert' b right)

-- try it
t1 = insert' 0 Leaf -- Node Leaf 0 Leaf
t2 = insert' 1 t1 -- Node Leaf 0 (Node Leaf 1 Leaf)
t3 = insert' 2 t2 -- Node Leaf 0 (Node Leaf 1 (Node Leaf 3 Leaf))```

#### Write map for BinaryTree

```mapTree :: (a -> b) -> BinaryTree a -> BinaryTree b
mapTree _ Leaf = Leaf
mapTree f (Node left a right) = Node (mapTree left f) (f a) (mapTree right f)```

#### Convert binary trees to lists

```preorder :: BinaryTree a -> [a]
preorder Leaf = []
preorder (Node left a right) = a : (preorder left) ++ (preorder right)

inorder :: BinaryTree a -> [a]
inorder Leaf = []
inorder = (inorder left) ++ [a] ++ (inorder right)

postorder :: BinaryTree a -> [a]
postorder Leaf = []
postorder = (postorder left) ++ (postorder right) ++ [a]```

#### Write foldr for BinaryTree

```-- 3 parameter
foldTree :: (a -> b -> b -> b) -> b -> BinaryTree a -> b
foldTree _ acc Leaf = acc
foldTree f acc (Node left a right) = f a
(foldTree f acc left)
(foldTree f acc right)

-- 2 parameter
foldTree :: (a -> b -> b) -> b -> BinaryTree a -> b
foldTree _ acc Leaf = acc
foldTree f acc bt = foldr f acc (flattenIn bt [])

flattenIn :: BinaryTree a -> [a] -> [a]
flattenIn Leaf l = l
flattenIn (Node left a right) l = flattenIn left (a : (flattenIn right l))```

#### Rewrite map for BinaryTree

```-- 3 parameter, ok
data BinaryTree a = Leaf
| Node (BinaryTree a) a (BinaryTree a)
deriving (Eq, Ord, Show)

foldTree :: (a -> b -> b -> b) -> b -> BinaryTree a -> b
foldTree _ acc Leaf = acc
foldTree f acc (Node left a right) = f a (foldTree f acc left) (foldTree f acc right)

mapTree' :: (a -> b) -> BinaryTree a -> BinaryTree b
mapTree' f bt = foldTree mk Leaf bt
where mk a l r = Node l (f a) r

-- 2 parameter failed, structure ruined
mapTree' :: (a -> b) -> BinaryTree a -> BinaryTree b
mapTree' f bt = foldTree f Leaf bt```

### 11.16 Chapter Exercises

#### Ciphers

Vigenère cipher

```import Data.Char

vigenere :: String -> String -> String
vigenere xs ys = vigenere' xs (cycle ys)

vigenere' [] _ = ""
vigenere' (' ':xs) cyp        = ' ' : vigenere' xs cyp
vigenere' (x:xs)   cyp@(y:ys) = docyp x y : vigenere' xs ys
where base      = ord 'A'
r         = 26
dist c    = ord c - base
docyp x y = chr \$ (dist x + dist y) `mod` r + base

main = print \$ vigenere "MEET AT DAWN" "ALLY" == "MPPR AE OYWY"```

#### As-patterns

```isSubsequenceOf :: (Eq a) => [a] -> [a] -> Bool
isSubsequenceOf [] [] = True
isSubsequenceOf [] ys = True
isSubsequenceOf _ []  = False
isSubsequenceOf sa@(a:az) (b:bz)
| a == b = isSubsequenceOf az bz
| otherwise isSubsequenceOf sa bz

capitalizeWords :: String -> [(String, String)]
capitalizeWords = map f . words
where f wd@(x:xs) = (wd, toUpper x : xs)```

#### Language exercises

```import Data.Char (toUpper)
import Data.List (groupBy)
import Data.Function (on)

capitalizeWord :: String -> String
capitalizeWord [] = ""
capitalizeWord (x:xs)
| x == ' ' = x : capitalizeWord xs
| otherwise = toUpper x : xs

capitalizeParagraph :: String -> String
capitalizeParagraph =
concatMap capitalizeWord . groupBy ((==) `on` (=='.'))```

#### Hutton’s Razor

```data Expr = Lit Integer
eval :: Expr -> Integer
eval (Lit x) = x
eval (Add exp1 exp2) = eval exp1 + eval exp2

printExpr :: Expr -> String
printExpr (Lit x) = show x
printExpr (Add exp1 exp2) = printExpr exp1 ++ " + " ++ printExp3 exp2```

• Nothing, or Just Maybe
• Either left or right, but not both
• higher-kindedness
• anamorphisms, but not animorphs.

### 12.2 How I learned to stop worrying and love Nothing

#### Smart constructors for datatypes

```data Name = String
data Age = Integer
data Person = Person Name Age deriving Show

mkPerson :: String -> Integer -> Maybe Person
mkPerson name age
| name \= "" && age > 0 = Just \$ Person name age
| otherwise = Nothing```

### 12.3 Bleating either

```data Either a b = Left a | Right b

data PersonInvalid = NameEmpty
| AgeTooLow deriving (Eq, Show)

-- Compiles fine without Eq
toString :: PersonInvalid -> String
toString NameEmpty = "NameEmpty"
toString AgeTooLow = "AgeTooLow"

instance Show PersonInvalid where
show = toString

mkPerson :: Name -> Age -> Either PersonInvalid Person
mkPerson name age
| name \= "" && age > 0 = Right \$ Person name age
| name = "" = Left NameEmpty
| age <= 0 = Left AgeTooLow

-- can not catch the AgeTooLow fault
mkPerson "" (-1) -- Left NameEmpty```
```type Name = String
type Age = Integer
type ValidatePerson a = Either [PersonInvalid] a

data Person = Person Name Age deriving Show
data PersonInvalid = NameEmpty
| AgeTooLow deriving (Eq, Show)

ageOkay :: Age -> Either [PersonInvalid] Age
ageOkay age = case age >= 0 of
True -> Right age
False -> Left [AgeTooLow]

nameOkay :: Name -> Either [PersonInvalid] Name
nameOkay name = case name /= "" of
True -> Right name
False -> Left [NameEmpty]

mkPerson :: Name -> Age -> ValidatePerson Person
mkPerson name age = mkPerson' (nameOkay name) (ageOkay age)

mkPerson' :: ValidatePerson Name
-> ValidatePerson Age
-> ValidatePerson Person
mkPerson' (Right nameOk) (Right ageOk) =
Right (Person nameOk ageOk)

### 12.4 Kinds, a thousand stars in your types

Kinds are types one level up.

kind: type of type constructor

type: type constructor(higher-kinded type) / type constant

```-- :kind Int
Int :: *
-- :k Bool
Bool :: *
-- :k Char
Char :: *

data Example a = Blah | RoofGoats | Woot a
-- :k Example
Example :: * -> *

-- :k (,)
(,) :: * -> * -> *

-- :k Maybe
Maybe :: * -> *

-- :k Either
Either :: * -> * -> *```

#### Lifed and unlifed types

lifted type: (->), bottom, polymorphism

unlifed type: no bottom, native machine types and raw pointers, newtype

### Data constructors are functions

```data Unary a = Unary a
instance Show a => Show (Unary a)

Unary id -- ??```

### 12.5 Chapter Exercises

#### String processing

```import Data.List (intercalate)

notThe :: String -> Maybe String
notThe str
| str == "the" = Nothing
| otherwise = Just str

replaceThe :: String -> String
replaceThe = intercalate " " . map athe . fmap notThe . words
where athe Nothing = "a"
athe (Just x) = x```
```isVowel :: String -> Bool
isVowel (x:xs) = elem x "aeiou"

countTheBeforeVowel :: String -> Integer
countTheBeforeVowel = f 0 . words

f :: Integer -> [String] -> Integer
f acc (x:y:xs)
| x == "the" && isVowel y = f (acc+1) xs
| otherwise = f acc (y:xs)
f acc _ = acc```
```isVowel :: Char -> Bool
isVowel = flip elem "aeiou"

countVowels :: String -> Integer
countVowels = f 0

f :: Integer -> String -> Integer
f acc (x:xs)
| isVowel x = f (acc+1) xs
| otherwise = f acc xs
f acc _ = acc```

#### Validate the word

```newtype Word' =
Word' String deriving (Eq, Show)

mkWord :: String -> Maybe Word'
mkWord str
| count str > 2 * countVowels str = Just (Word' str)
| otherwise = Nothing```

#### It’s only Natural

```data Nat = Zero | Succ Nat deriving (Eq, Show)

natToInteger :: Nat -> Integer
natToInteger = f 0
where f acc Zero = acc
f acc (Succ Nat) = f (acc+1) Nat

-- >>> natToInteger Zero
-- 0
-- >>> natToInteger (Succ Zero)
-- 1
-- >>> natToInteger (Succ (Succ Zero))
-- 2

integerToNat :: Integer -> Maybe Nat
integerToNat n
| n < 0 = Nothing
| otherwise = Just (f Zero n)
where f acc n
| n == 0 = acc
| otherwise = f (Succ acc) (n-1)

-- >>> integerToNat 0
-- Just Zero
-- >>> integerToNat 1
-- Just (Succ Zero)
-- >>> integerToNat 2
-- Just (Succ (Succ Zero))
-- >>> integerToNat (-1)
-- Nothing```

#### Small library for Maybe

```-- >>> isJust (Just 1)
-- True
-- >>> isJust Nothing
-- False
isJust :: Maybe a -> Bool
isJust Nothing = False
isJust _ = True

-- >>> isNothing (Just 1)
-- False
-- >>> isNothing Nothing
-- True
isNothing :: Maybe a -> Bool
isNothing Nothing = True
isNothing _ = False```
```-- >>> mayybee 0 (+1) Nothing
-- 0
-- >>> mayybee 0 (+1) (Just 1)
-- 2

mayybee :: b -> (a -> b) -> Maybe a -> b
mayybee _ f (Just a) = f a
mayybee d _ Nothing = d```
```-- >>> fromMaybe 0 Nothing
-- 0
-- >>> fromMaybe 0 (Just 1)
-- 1

fromMaybe :: a -> Maybe a -> a
fromMaybe d v = mayybee d id v```
```-- >>> listToMaybe [1, 2, 3]
-- Just 1
-- >>> listToMaybe []
-- Nothing
listToMaybe :: [a] -> Maybe a
listToMaybe (x:_) = Just x
listToMaybe [] = Nothing

-- >>> maybeToList (Just 1)
-- [1]
-- >>> maybeToList Nothing
-- []
maybeToList :: Maybe a -> [a]
maybeToList (Just a) = [a]
maybeToList Nothing = []```
```-- >>> catMaybes [Just 1, Nothing, Just 2]
-- [1, 2]
-- >>> catMaybes [Nothing, Nothing, Nothing]
-- []
catMaybes :: [Maybe a] -> [a]
catMaybes = map g . filter f
where g (Just v) = v
f = (/= Nothing)

-- foldr
catMaybes' :: [Maybe a] -> [a]
catMaybes' [] = []
catMaybes' xs = foldr f [] xs
where f Nothing xs'  = xs'
f (Just a) xs' = a : xs'```
```-- >>> flipMaybe [Just 1, Just 2, Just 3]
-- Just [1, 2, 3]
-- >>> flipMaybe [Just 1, Nothing, Just 3]
-- Nothing

flipMaybe :: [Maybe a] -> Maybe [a]
flipMaybe = f []
where f acc ((Just a):xs) = f (a:acc) xs
f acc [] = acc
f _ (Nothing:xs) = Nothing

-- using foldr
flipMaybe [] = Just []
flipMaybe xs = foldr f (Just []) xs
where f _ Nothing = Nothing
f Nothing _ = Nothing
f (Just a) (Just b) = Just (a:b)```

#### Small library for Either

```lefts' :: [Either a b] -> [a]
lefts' = foldr f []
where f (Left a) acc = a : acc
f _ acc = acc```
```rights' :: [Either a b] -> [b]
lefts' = foldr f []
where f (Right a) acc = a : acc
f _ acc = acc```
```partitionEithers' :: [Either a b] -> ([a], [b])
partitionEithers' = foldr f ([], [])
where f (Left a) (az, bz) = (a:az, bz)
f (Right b) (az, bz) = (az, b:bz)```
```eitherMaybe' :: (b -> c) -> Either a b -> Maybe c
eitherMaybe' f (Right b) = Just (f b)
eitherMaybe' _ (Left a) = Nothing```
```either' :: (a -> c) -> (b -> c) -> Either a b -> c
either' f _ (Left a) = f a
either' _ f (Right b) = f b```
```eitherMaybe'' :: (b -> c) -> Either a b -> Maybe c
eitherMaybe'' f =  either' f1 f2
f1 _ = Nothing
f2 = Just . f```

#### Unfolds

anamorphisms - catamorphisms

unfoldr

```take 10 \$ iterate (+1) 0
-- [0,1,2,3,4,5,6,7,8,9]

-- :t unfoldr
unfoldr :: (b -> Maybe (a, b)) -> b -> [a]

take 10 \$ unfoldr (\b -> Just (b, b+1)) 0
-- [0,1,2,3,4,5,6,7,8,9]```

#### Why bother?

```import Data.List

mehSum :: Num a => [a] -> a
mehSum xs = go 0 xs
where go :: Num a => a -> [a] -> a
go n [] = n
go n (x:xs) = (go (n+x) xs)

niceSum :: Num a => [a] -> a
niceSum = foldl' (+) 0

mehProduct :: Num a => [a] -> a
mehProduct xs = go 1 xs
where go :: Num a => a -> [a] -> a
go n [] = n
go n (x:xs) = (go (n*x) xs)

niceProduct :: Num a => [a] -> a
niceProduct = foldl' (*) 1

mehConcat :: [[a]] -> [a]
mehConcat xs = go [] xs
where go :: [a] -> [[a]] -> [a]
go xs' [] = xs'
go xs' (x:xs) = (go (xs' ++ x) xs)

niceConcat :: [[a]] -> [a]
niceConcat = foldr (++) []```

#### Write your own iterate and unfoldr

```myIterate :: (a -> a) -> a -> [a]
myIterate f a = a : myIterate f (f a)```
```unfoldr (\b -> Just (b, b+1)) 0

myUnfoldr :: (b -> Maybe (a, b)) -> b -> [a]
myUnfoldr f b = g \$ f b
where g (Just (a, b)) = a : myUnfoldr f b
g _ = []```
``````betterIterate :: (a -> a) -> a -> [a]
betterIterate f = myUnfoldr g
where g b = Just (b, f b)
``````

#### Finally something other than a list!

```data BinaryTree a = Leaf
| Node (BinaryTree a) a (BinaryTree a)
deriving (Eq, Ord, Show)

unfold :: (a -> Maybe (a,b,a)) -> a -> BinaryTree b
unfold f b = case f b of
Nothing -> Leaf
Just (x, y, z) -> Node (unfold f x) y (unfold f z)

treeBuild :: Integer -> BinaryTree Integer
treeBuild n = go n Leaf
where go 0 acc = acc
go n acc = go (n-1) (Node acc (n-1) acc)

-- using unfold
treeBuild :: Integer -> BinaryTree Integer
treeBuild n = unfold f 0
where f m
| m == n = Nothing
| otherwise = Just (m + 1, m, m + 1)
```

### 12.6 Definitions

1. higher kinded type:
```Maybe :: * -> *
[] :: * -> *
Either :: * -> * -> *
(->) :: * -> * -> *

-- The following are not:
Int :: *
Char :: *
String :: *
[Char] :: *```

## CHAPTER15. MONOID,SEMIGROUP

### 15.1 Monoids and semigroups

• Algebras!
• Laws!
• Monoids!
• Semigroups!

Algebra: mathematical symbols and the rules, operation <= implemented with typeclass,

### 15.3 Monoid

monoid: binary associative operation with an identity

monoid: function that takes two arguments and follows two laws: associativity and identity

```-- [] = mempty, or the identity
-- mappend is the binary operation
-- to append, or join, two arguments
mappend [1..5] [] = [1..5]
mappend [] [1..5] = [1..5]
-- or, more generally
mappend x mempty = x
mappend mempty x = x```

### 15.4 How Monoid is defined in Haskell

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

### 15.5 Examples of using Monoid

#### List

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

-- usage:
mappend [1, 2, 3] [4, 5, 6]
-- [1,2,3,4,5,6]

mconcat [[1..3], [4..6]]
-- [1,2,3,4,5,6]

mappend "Trout" " goes well with garlic"
-- "Trout goes well with garlic"

(++) [1, 2, 3] [4, 5, 6]
-- [1,2,3,4,5,6]

(++) "Trout" " goes well with garlic"
-- "Trout goes well with garlic"

foldr (++) [] [[1..3], [4..6]]
-- [1,2,3,4,5,6]

foldr mappend mempty [[1..3], [4..6]]
-- [1,2,3,4,5,6]```

### 15.6 Why Integer doesn’t have a Monoid

Both summation, multiplication are monoidal (binary, associative, having an identity value), but each type should only have one unique instance for a given typeclass, not two (one instance for a sum, one for a product).

solution: wrap the value with Sum, Product newtype

```mappend (Sum 1) (Sum 5)
-- Sum {getSum = 6}

mappend (Product 5) (Product 5)
-- Product {getProduct = 25}

mappend (Sum 4.5) (Sum 3.4)
-- Sum {getSum = 7.9}```

#### Why newtype?

```data Server = Server String
newtype Server' = Server' String```

newtype: unary data constructor, no additional runtime overhead(identical to what it wraps)

#### More on Sum and Product

```import Data.Monoid
-- :info Sum
newtype Sum a = Sum {getSum :: a}
-- .. other instances
instance Num a => Monoid (Sum a)

-- :info Product
newtype Product a = Product {getProduct :: a}
-- .. other instances
instance Num a => Monoid (Product a)```
```-- :t (<>)
(<>) :: Monoid m => m -> m -> m

mappend (Sum 8) (Sum 9)
(Sum 8) <> (Sum 9)
-- Sum {getSum = 17}

mappend mempty Sum 9
mempty <> Sum 9
-- Sum {getSum = 9}

-- error
-- mappend (Sum 1) (Sum 2) (Sum 3)
mappend (Sum 1) (mappend (Sum 2) (Sum 3))
(Sum 1) `mappend` (Sum 2) `mappend` (Sum 3)
(Sum 1) <> (Sum 2) <> (Sum 3)
-- Sum {getSum = 6}

mconcat [(Sum 8), (Sum 9), (Sum 10)]
-- Sum {getSum = 27}```

### 15.7 Why bother?

A common use of monoids is to structure and describe common modes of processing data. Sometimes this is to describe an API for incrementally processing a large dataset, sometimes to describe guar- antees needed to roll up aggregations (think summation) in a parallel, concurrent, or distributed processing framework.

```foldr mappend mempty ([2, 4, 6] :: [Product Int])
-- Product {getProduct = 48}

foldr mappend mempty ([2, 4, 6] :: [Sum Int])
-- Sum {getSum = 12}

foldr mappend mempty ["blah", "woot"]
-- "blahwoot"```

### 15.8 Laws

law - algebra

```-- left identity
mappend mempty x = x

-- right identity
mappend x mempty = x

-- associativity
mappend x (mappend y z) = mappend (mappend x y) z
mconcat = foldr mappend mempty```

### 15.9 Different typeclass instance, same representation

Bool wrapper:

```import Data.Monoid
All True <> All True
-- All {getAll = True}

All True <> All False
-- All {getAll = False}

Any True <> Any False
-- Any {getAny = True}

Any False <> Any False
-- Any {getAny = False}```

Maybe wrapper:

```First (Just 1) `mappend` First (Just 2)
-- First {getFirst = Just 1}

Last (Just 1) `mappend` Last (Just 2)
-- Last {getLast = Just 2}

Last Nothing `mappend` Last (Just 2)
-- Last {getLast = Just 2}

First Nothing `mappend` First (Just 2)
-- First {getFirst = Just 2}```

### 15.10 Reusing algebras by asking for algebras

```instance Monoid b => Monoid (a -> b)
instance (Monoid a, Monoid b) => Monoid (a, b)
instance (Monoid a, Monoid b, Monoid c) => Monoid (a, b, c)```

#### Exercise

```data Optional a = Nada | Only a deriving (Eq, Show)
instance Monoid a => Monoid (Optional a) where
mappend Nada (Only a)     = Only a
mappend (Only a) Nada     = Only a
mappend (Only a) (Only b) = Only (mappend a b)

-- usage:
Only (Sum 1) `mappend` Only (Sum 1)
-- Only (Sum {getSum = 2})

Only (Product 4) `mappend` Only (Product 2)
-- Only (Product {getProduct = 8})

-- Only (Sum {getSum = 1})

-- Only [1]

-- Only (Sum {getSum = 1})```

#### Associativity

monoid is not necessarily commutative

Commutative: reorder the arguments, not just reassociate the parentheses, and still get the same result.

commutative: (+) (*)

not commutative: (-) (++)

identity:

identity value:

#### The problem of orphan instances

problem:

```module Listy where

newtype Listy a =
Listy [a] deriving (Eq, Show)```
```module ListyInstances where

import Data.Monoid
import Listy

instance Monoid (Listy a) where
mempty = Listy []
mappend (Listy l) (Listy l') = Listy \$ mappend l l'```

solution:

1. You defined the type but not the typeclass? Put the instance in the same module as the type so that the type cannot be imported without its instances.

2. You defined the typeclass but not the type? Put the instance in the same module as the typeclass definition so that the typeclass cannot be imported without its instances.

3. Neither the type nor the typeclass are yours? Define your own newtype wrapping the original type and now you’ve got a type that “belongs” to you for which you can rightly define typeclass instances.

```import Data.Monoid
type Verb = String
type Noun = String
type Exclamation = String

-> Noun
-> String
madlibbinBetter' e adv noun adj = mconcat [e, "! he said ", adv, " as he jumped into his car ", noun, " and drove off with this ", adj, " wife."]```

### 15.12 Better living through QuickCheck

#### Validating associativity with QuickCheck

```import Data.Monoid
import Test.QuickCheck

monoidAssoc :: (Eq m, Monoid m) => m -> m -> m -> Bool
monoidAssoc a b c = (a <> (b <> c)) == ((a <> b) <> c)```

#### Quickchecking left and right identity

```monoidLeftIdentity :: (Eq m, Monoid m) => m -> Bool
monoidLeftIdentity a = (mempty <> a) == a

monoidRightIdentity :: (Eq m, Monoid m) => m -> Bool
monoidRightIdentity a = (a <> mempty) == a

quickCheck (monoidLeftIdentity :: String -> Bool)
-- +++ OK, passed 100 tests.

quickCheck (monoidRightIdentity :: String -> Bool)
-- +++ OK, passed 100 tests.```

#### Intermission: Exercise

```newtype First' a =
First' { getFirst' :: Optional a } deriving (Eq, Show)

instance Monoid (First' a) where
mappend (First' (Only x)) _ = First' (Only x)
mappend (First' Nada) (First' (Only x)) = First' (Only x)
mappend _ _ = First' Nada

firstMappend :: First' a -> First' a -> First' a
firstMappend = mappend

type FirstMappend =
First' String
-> First' String
-> First' String
-> Bool

main :: IO () main = do
quickCheck (monoidAssoc :: FirstMappend)
quickCheck (monoidLeftIdentity :: First' String -> Bool)
quickCheck (monoidRightIdentity :: First' String -> Bool)
```

### 15.13 Semigroup

```class Semigroup a where
(<>) :: a -> a -> a

(a <> b) <> c = a <> (b <> c)```

#### NonEmpty, a useful datatype

```-- :| is the data constructor, the product of a and [a]
data NonEmpty a = a :| [a]
deriving (Eq, Ord, Show)

-- or like this
newtype NonEmpty a = NonEmpty (a, [a])
deriving (Eq, Ord, Show)```

ok with binary associative operation, but not with identity.

so, with semigroup:

```-- you need to have `semigroups` installed
import Data.List.NonEmpty as N
import Data.Semigroup as S

1 :| [2, 3]
-- 1 :| [2,3]

:t 1 :| [2, 3]
-- 1 :| [2, 3] :: Num a => NonEmpty a

:t (<>)
-- (<>) :: Semigroup a => a -> a -> a

xs = 1 :| [2, 3]
ys = 4 :| [5, 6]
xs <> ys
-- 1 :| [2,3,4,5,6]

-- 1
N.length (xs <> ys)
-- 6```

#### Strength can be weakness

```class Semigroup a => Monoid a where
...```

the inverse relationship: operations permitted over a type and the number of types that can satisfy.

`id :: a -> a`
• Number of types: Infinite

• Number of operations: one

`inc :: Num a => a -> a`
• Number of types: anything that implements Num. Zero to many.
• Number of operations: 7 methods in Num
`somethingInt :: Int -> Int`
• Number of types: one — just Int.
• Number of operations: considerably more than 7. In addition to Num, Int has instances of Bounded, Enum, Eq, Integral, Ord, Read, Real, and Show. On top of that, you can write arbitrary functions that pattern match on concrete types and return arbitrary values in that same type as the result. Polymorphism isn’t only useful for reusing code; it’s also useful for expressing intent through parametricity so that people reading the code know what we meant to accomplish.

### 15.14 Chapter exercises

#### Monoid exercises

```data Trivial = Trivial deriving (Eq, Show)

instance Semigroup Trivial where
(<>) = Trivial

instance Monoid Trivial where
mempty = Trivial
mappend = (<>)

type TrivialAssoc = Trivial -> Trivial -> Trivial -> Bool

main :: IO () main = do
quickCheck (semigroupAssoc :: TrivialAssoc)
quickCheck (monoidLeftIdentity :: Trivial -> Bool)
quickCheck (monoidRightIdentity :: Trivial -> Bool)```

### 15.15 Definitions

1. monoid

2. semigroup

3. Law

4. algebra: informal notion of operations over a type and its laws, such as with semigroups, monoids, groups, semirings, and rings.

### 15.16 Follow-up resources

1. Algebraic structure; Simple English Wikipedia;

2. Algebraic structure; English Wikipedia

## CHAPTER16. FUNCTOR

### 16.1 Functor

functor: Rudolf Carnap in the 1930s.

• the return of the higher-kinded types;
• fmaps;
• typeclasses and constructor classes;

### 16.2 What’s a functor?

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

### 16.3 There’s a whole lot of fmap going round

```-- Functor f =>
fmap :: (a -> b) -> f a -> f b
:: (a -> b) -> [] a -> [] b
:: (a -> b) -> Maybe a -> Maybe n
:: (a -> b) -> Either e a -> Either e b
:: (a -> b) -> (e,) a -> (e,) b
:: (a -> b) -> Identity a -> Identity b
:: (a -> b) -> Constant e a -> Constant e b```

### 16.4 Let’s talk about 𝑓 , baby

``````(->) :: * -> * -> *
``````

#### Functor is function application

```fmap :: Functorf => (a -> b) -> f a -> f b
(<\$>) :: Functorf => (a -> b) -> f a -> f b
(\$) :: (a->b) -> a -> b```

#### A shining star for you to see what your 𝑓 can truly be

```data FixMePls a = FixMe | Pls a deriving (Eq, Show)

instance Functor FixMePls where
fmap _ FixMe = FixMe
fmap f (Pls a) = Pls (f a)```

### 16.5 Functor Laws

#### Identity

`fmap id == id`

#### Composition

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

### 16.6 The Good, the Bad, and the Ugly

```data WhoCares a = ItDoesnt
| Matter a
| WhatThisIsCalled deriving (Eq, Show)

instance Functor WhoCares where
fmap _ ItDoesnt = ItDoesnt
fmap _ WhatThisIsCalled = WhatThisIsCalled
fmap f (Matter a) = Matter (f a)```

### 16.7 Commonly used functors

#### The functors are stacked and that’s a fact

```lms = [Just "Ave", Nothing, Just "woohoo"]
replaceWithP = const 'p'

(fmap . fmap) replaceWithP lms
-- [Just 'p', Nothing, Just 'p']

(.) :: (b -> c) -> (a -> b) -> a -> c
fmap :: Functor f => (m -> n) -> f m -> f n
fmap :: Functor g => (x -> y) -> g x -> g y

fmap . fmap = ((m -> n) -> (f m -> f n))
-> ((x -> y) -> (g x -> g y))
= (x -> y) -> (f g x -> f g y)
= (x -> y) -> f g x -> f g y```

#### Intermission: Lifting Exercises

`a = fmap (+1) (read "[1]" :: [Int])`
`b = (fmap . fmap) (++ "lol") (Just ["Hi,", "Hello"])`
`c = (*2) . (\x -> x -2)`
`d = ((return '1' ++) . show) . (\x -> [x, 1..3])`

### 16.8 Mapping over the structure to transform the unapplied type argument

```data Two a b = Two a b deriving (Eq, Show)

data Or a b = First a | Second b deriving (Eq, Show)

-- error
instance Functor Two where fmap = undefined
instance Functor Or where fmap = undefined

-- ok
instance Functor (Two a) where
fmap f (Two a b) = Two a (f b)
instance Functor (Or a) where
fmap _ (First a) = First a
fmap f (Second b) = Second (f b)```

### 16.10 Intermission: Exercises

```newtype Identity a = Identity a

instance Functor Identity where
fmap f (Identity a) = Identity (f a)```
```data Pair a = Pair a a

instance Functor Pair where
fmap f (Pair a b) = Pair (f a) (f b)```
```data Two a b = Two a b

instance Functor (Two a) where
fmap f (Two a b) = Two a (f b)```
```data Three a b c = Three a b c

instance Functor (Three a b) where
fmap f (Three a b c) = Three a b (f c)```
```data Three' a b = Three' a b b

instance Functor (Three' a) where
fmap f (Three' a b c) = Two a (f b) (f c)```
```data Four a b c d = Four a b c d

instance Functor (Four a b c) where
fmap f (Four a b c d) = Two a b c (f d)```
```data Four' a b = Four' a a a b

instance Functor (Four' a) where
fmap f (Four' a b c d) = Two a b c (f d)```

### 16.11 Ignoring possibilities

#### Short Exercise

```data Possibly a = LolNope | Yeppers a deriving (Eq, Show)

instance Functor Possibly where
fmap _ LolNope = LolNope
fmap f (Yeppers a) = Yeppers (f a)```

#### Short Exercise

```data Sum a b = First a | Second b deriving (Eq, Show)

instance Functor (Sum a) where
fmap _ (First a) = First a
fmap f (Second a) = Second (f a)```

### 16.13 More structure, more functors

```data Wrap f a = Wrap (f a) deriving (Eq, Show)

instance Functor (Wrap f) where
fmap f (Wrap fa) = Wrap (f fa)
instance Functor (Wrap f) where
fmap f (Wrap fa) = Wrap (fmap f fa)
instance Functor f => Functor (Wrap f) where
fmap f (Wrap fa) = Wrap (fmap f fa)```

### 16.14 IO Functor

```getLine :: IO String

getInt :: IO Int

-- or
meTooIsm :: IO String
meTooIsm = do
input <- getLine
return (input + 1)```

### 16.15 What if we want to do something different?

natural transformations: transform the structure, but not the arguments

```nat :: (f -> g) -> f a -> g a

{-# LANGUAGE RankNTypes #-}
type Nat f g = forall a. f a -> g a

-- This'll work
maybeToList :: Nat Maybe []
maybeToList Nothing = []
maybeToList (Just a) = [a]

-- This will not work, not allowed.
degenerateMtl :: Nat Maybe []
degenerateMtl Nothing = []
degenerateMtl (Just a) = [a+1]```

### 16.17 Chapter exercises

```data Quant a b = Finance | Desk a | Bloor b

instance Functor (Quant a) where
fmap f (Bloor b) = Bloor (f b)
fmap _ (Desk a) = Desk a
fmap _ Finance = Finance```
```data K a b = K a

instance Functor (K a) where
fmap _ (K a) = K a```
```{-# LANGUAGE FlexibleInstances #-}
newtype Flip f a b = Flip (f b a) deriving (Eq, Show)

newtype K a b = K a

instance Functor (Flip K a) where
fmap f (Flip (K a)) = Flip (K (f b))```
```data EvilGoateeConst a b = GoatyConst b

instance Functor (EvilGoateeConst a) where
fmap f (GoatyConst b) = GoatyConst (f b)```
```data LiftItOut f a = LiftItOut (f a)

instance Functor f => Functor (LiftItOut f) where
fmap f (LiftItOut fa) = LiftItOut (fmap f fa)```
```data Parappa f g a = DaWrappa (f a) (g a)

instance (Functor f, Functor g) => Functor (Parappa f g) where
fmap f (DaWrappa fa ga) = DaWrappa (fmap f fa) (fmap f ga)```
```data IgnoreOne f g a b = IgnoringSomething (f a) (g b)

instance Functor g => Functor (IgnoreOne f g a) where
fmap f (IgnoringSomething fa gb) = IgnoringSomething fa (fmap f gb)```
```data Notorious g o a t = Notorious (g o) (g a) (g t)

instance Functor g => Functor (Notorious g o a) where
fmap f (Notorious go ga gt) = Notorious go ga (fmap f gt)```
```data List a = Nil | Cons a (List a)

instance List where
fmap f (Cons a (List a)) = Cons (f a) (List (f a))
fmap _ Nil = Nil```
```data GoatLord a = NoGoat
| OneGoat a
| MoreGoats (GoatLord a) (GoatLord a) (GoatLord a)

instance Functor GoatLoard where
fmap _ NoGoat = NoGoat
fmap f (OneGoat a) = OneGoat (f a)
fmap f MoreGoats ga1
ga2
ga3 = MoreGoats (fmap f ga1)
(fmap f ga2)
(fmap f ga3)```
```data TalkToMe a = Halt
| Print String a

instance Functor TalkToMe where
fmap _ Halt = Halt
fmap f (Print s a) = Print s (f a)

### 16.18 Definitions

1. Higher-kinded polymorphism

2. Functor

3. lifting

4. George Clinton

### 16.19 Follow-up resources

1. Haskell Wikibook; The Functor class.

2. Mark P. Jones; A system of constructor classes: overloading and implicit higher-order polymorphism.

3. Gabriel Gonzalez; The functor design pattern.

## CHAPTER17. APPLICATIVE

### 17.2 Defining Applicative

```class Functor f => Applicative f where
pure :: a -> f a
(<*>) :: f (a -> b) -> f a -> f b
-- Could call <*> tie-fighter or "ap" (short for apply)```

every type that can have an Applicative instance must also have a Functor instance.

pure: like `identity`, embed sth into `f`

<*>: ap,

```(<\$>) :: Functor f =>       (a -> b) -> f a -> f b
(<*>) :: Applicative f => f (a -> b) -> f a -> f b```

### 17.3 Functor vs. Applicative

```fmap :: (a -> b) -> f a -> f b
(<*>) :: f (a -> b) -> f a -> f b

fmap f x = pure f <*> x

fmap (+1) [1, 2, 3] -- [2, 3, 4]
pure (+1) <*> [1, 2, 3] -- [2, 3, 4]```

`pure` embed the value into the structure

```pure 1 :: [Int] -- [1]
pure 1 :: Maybe Int -- Just 1
pure 1 :: Either a Int -- Right 1
pure 1 :: ([a], Int) -- ([],1)

fmap (+1) (4, 5)```

### 17.4 Applicative functors are monoidal functors

```(\$) :: (a->b)-> a-> b
(<\$>) :: (a -> b) -> f a -> f b
(<*>) :: f (a -> b) -> f a -> f b```
```mappend :: Monoid a => a -> a -> a

mappend :: f             f      f
\$       :: (a -> b)      a      b
(<*>)   :: f (a -> b) -> f a -> f b```
```[(*2), (*3)] <*> [4, 5]
-- [8, 10, 12, 15]```
```Just (*2) <*> Just 2 = Just 4
Just (*2) <*> Nothing = Nothing
Nothing <*> Just 2 = Nothing
Nothing <*> Nothing = Nothing```

#### Show me the monoids

```:info (,)
data (,) a b = (,) a b  -- Defined in ‘GHC.Tuple’
...
instance Monoid a => Applicative ((,) a) -- Defined in ‘GHC.Base’
...
instance (Monoid a, Monoid b) => Monoid (a, b)

-- functor
fmap (+1) ("blah", 0)
-- ("blah",1)

-- ap
("Woo", (+1)) <*> (" Hoo!", 0)
-- ("Woo Hoo!", 1)

((Sum 2), (+1)) <*> ((Sum 0), 0)
-- (Sum {getSum = 2}, 1)

((Product 3), (+9)) <*> ((Product 2), 8)
-- (Product {getProduct = 6}, 17)

((All True), (+1)) <*> ((All False), 0)
-- (All {getAll = False}, 1)```

#### Tuple Monoid and Applicative side by side

```instance (Monoid a, Monoid b) => Monoid (a,b) where
mempty = (mempty, mempty)
(a, b) `mappend` (a', b') = (a `mappend` a', b `mappend` b')

instance Monoid a => Applicative ((,) a) where
pure x = (mempty, x)
(u, f) <*> (v, x) = (u `mappend` v, f x)
```

#### Maybe Monoid and Applicative

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

instance Applicative Maybe where
pure = Just
Nothing <*> _ = Nothing
_ <*> Nothing = Nothing
Just f <*> Just a = Just (f a)```

### 17.5 Applicative in use

#### List Applicative

```-- f ~ []
(<*>) :: f (a -> b) -> f a -> f b
(<*>) :: [] (a -> b) -> [] a -> [] b
-- more syntactically typical
(<*>) :: [(a -> b)] -> [a] -> [b]

pure :: a -> f a
pure :: a -> [] a```

#### What’s the List applicative do?

```(<*>) :: Applicative f => f (a -> b) -> f a -> f b
-- f ~ []
listApply :: [(a -> b)] -> [a] -> [b]
listFmap :: (a -> b) -> [a] -> [b]```

functor: a function to a plurality of values:

```fmap (2^) [1, 2, 3]
-- [2,4,8]
fmap (^2) [1, 2, 3]
-- [1,4,9]```

ap: a plurality of function to a plurality of values:

```[(+1), (*2)] <*> [2, 4]
-- [3,5,4,8]```
```(,) <\$> [1, 2] <*> [3, 4]
-- [(1,3),(1,4),(2,3),(2,4)]```

#### Short Exercises

```added :: Maybe Integer
added = (+3) <\$> (lookup 3 \$ zip [1, 2, 3] [4, 5, 6])```
```y :: Maybe Integer
y = lookup 3 \$ zip [1, 2, 3] [4, 5, 6]
z :: Maybe Integer
z = lookup 2 \$ zip [1, 2, 3] [4, 5, 6]
tupled :: Maybe (Integer, Integer)
tupled = (,) <\$> y <*> z```
```import Data.List (elemIndex)
x :: Maybe Int
x = elemIndex 3 [1, 2, 3, 4, 5]
y :: Maybe Int
y = elemIndex 4 [1, 2, 3, 4, 5]
max' :: Int -> Int -> Int
max' = max
maxed :: Maybe Int
maxed = max' <\$> x <*> y```

#### Exercise

```newtype Identity a = Identity a deriving (Eq, Ord, Show)

instance Functor Identity where
fmap f (Identity a)= Identity (f a)

instance Applicative Identity where
pure = Identity
(<*>) (Identity f) (Identity b)= Identity (f b)```

#### Specializing the types

```-- f ~ Constant e

(<*>) :: f (a -> b) -> f a -> f b
(<*>) :: Constant e (a -> b) -> Constant e a -> Constant e b

pure :: a -> f a
pure :: a -> Constant e a```

#### Exercise

```newtype Constant a b = Constant { getConstant :: a } deriving (Eq, Ord, Show)

instance Functor (Constant a) where
fmap _ (Constant a) = Constant a

instance Monoid a => Applicative (Constant a) where
pure = Constant
(<*>) (Constant a) (Constant b) = Constant (a b)```

#### Specializing the types

```-- f ~ Maybe
(<*>) :: f (a -> b) -> f a -> f b
(<*>) :: Maybe (a -> b) -> Maybe a -> Maybe b

pure :: a -> f a
pure :: a -> Maybe a```
```validateLength :: Int -> String -> Maybe String
validateLength maxLen s = if (length s) > maxLen
then Nothing
else Just s

newtype Name = Name String deriving (Eq, Show)

mkName :: String -> Maybe Name
mkName s = fmap Name \$ validateLength 25 s

data Person = Person Name Address deriving (Eq, Show)

mkPerson :: String -> String -> Maybe Person
mkPerson n a = case mkName n of
Nothing -> Nothing
Just n' -> case mkAddress a of
Nothing -> Nothing
Just a' -> Just \$ Person n' a'

--usage:
Person <\$> (mkName "Babe") <*> (mkAddress 1)```

#### Maybe Functor and the Name constructor

```instance Functor Maybe where
fmap _ Nothing = Nothing
fmap f (Just a) = Just (f a)

instance Applicative Maybe where
pure = Just
Nothing <*> _ = Nothing
_ <*> Nothing = Nothing
Just f <*> Just a = Just (f a)```

#### Exercise

`const <\$> Just "Hello" <*> pure "World"`
`(,,,) <\$> Just 90 <*> Just 10 <*> Just "Tierness" <*> pure [1, 2, 3]`

### 17.6 Applicative laws

#### 1. Identity

```id v = v
fmap id v = v
pure id <*> v = v```

#### 2. Composition

`pure (.) <*> u <*> v <*> w = u <*> (v <*> w)`

#### 3. Homomorphism

`pure f <*> pure x = pure (f x)`

#### 4. Interchange

```u <*> pure y = pure (\$ y) <*> u
(\$ 1) (*1) = 1```

### 17.8 ZipList Monoid

#### Zero vs. Identity

```Sum 1 `mappend` ??? -> Sum 1

instance Monoid a => Monoid (ZipList a) where
mempty = pure mempty
mappend = liftA2 mappend```

#### List Applicative Exercise

```data List a = Nil | Cons a (List a) deriving (Eq, Show)

instance Functor List where
fmap _ Nil = Nil
fmap f (Cons a az) = Cons (f a) (fmap f az)

instance Applicative List where
pure a = Cons a Nil
(<*>) Nil _ = Nil
(<*>) _ Nil = Nil
(<*>) (Cons f a) bz = fmap f bz <> (a <*> bz)

-- usage:
functions = Cons (+1) (Cons (*2) Nil)
values = Cons 1 (Cons 2 Nil)
functions <*> values
-- Cons 2 (Cons 3 (Cons 2 (Cons 4 Nil)))```
```append :: List a -> List a -> List a
append Nil ys = ys
append (Cons x xs) ys = Cons x \$ xs `append` ys

fold :: (a -> b -> b) -> b -> List a -> b
fold _ b Nil = b
fold f b (Cons h t) = f h (fold f b t)

concat' :: List (List a) -> List a
concat' = fold append Nil

-- write this one in terms of concat' and fmap
flatMap :: (a -> List b) -> List a -> List b
flatMap f (a:as) = f a ++ (flatMap f as)
flatMap _ [] = []```

### Exercise

```data List a = Nil | Cons a (List a) deriving (Eq, Show)

take' :: Int -> List a -> List a
take' 0 _ = Nil
take' _ Nil = Nil
take' n (Cons a az) = Cons a (take' (n-1) az)

instance Monoid (List a) where
mempty = Nil
mappend Nil a = a
mappend a Nil = a
mappend (Cons x xs) ys = Cons x (mappend xs ys)

instance Functor List where
fmap _ Nil = Nil
fmap f (Cons a az) = Cons (f a) (fmap f az)

instance Applicative List where
pure a = Cons a Nil
(<*>) Nil _ = Nil
(<*>) _ Nil = Nil
(<*>) (Cons x xs) ys = fmap x ys <> (xs <*> ys)

newtype ZipList' a = ZipList' (List a) deriving (Eq, Show)

instance Eq a => EqProp (ZipList' a) where
xs =-= ys = xs' `eq` ys'
where xs' = let (ZipList' l) = xs
in take' 3000 l
ys' = let (ZipList' l) = ys
in take' 3000 l

instance Functor ZipList' where
fmap f (ZipList' xs) = ZipList' \$ fmap f xs

repeatList :: a -> (List a)
repeatList x = xs
where xs = Cons x xs

zipListWith :: (a -> b -> c) -> (List a) -> (List b) -> (List c)
zipListWith _ Nil _ = Nil
zipListWith _ _ Nil = Nil
zipListWith f (Cons a as) (Cons b bs) = Cons (f a b) (zipListWith f as bs)

instance Applicative ZipList' where
pure = ZipList' . repeatList
(<*>) (ZipList' fs ) (ZipList' xs) = ZipList' (zipListWith id fs xs)```

#### Either and Validation Applicative

```-- f ~ Either e
(<*>) :: f (a -> b) -> f a -> f b
(<*>) :: Either e (a -> b) -> Either e a -> Either e b

pure :: a -> f a
pure :: a -> Either e a```

#### Either versus Validation

```pure 1 :: Either e Int
-- Right 1
Right (+1) <*> Right 1
-- Right 2
Right (+1) <*> Left ":("
-- Left ":("```

#### Exercise

``````
data Validation e a = Error e
| Success a deriving (Eq, Show)

instance Functor (Sum a) where
fmap _ (First a) = First a
fmap f (Second b) = Second b

instance Applicative (Sum a) where
pure = Second
(<*>) (First a) _ = First a
(<*>) _ (First a) = First a
(<*>) (Second b) (Second c) = Second (b c)

instance Functor (Validation e) where
fmap _ (Error e) = Error e
fmap f (Success a) = Success a

instance Monoid e => Applicative (Validation e) where
pure = Success
(<*>) (Error e) (Error e') = Error (e <> e')
(<*>) _ (Error e) = Error e
(<*>) (Error e) _ = Error e
(<*>) (Success f) (Success b) = Success (f b)
``````

### 17.9 Chapter Exercises

#### Combinations

```newtype Identity a = Identity a deriving Show

instance Applicative Identity where
pure = Identity
(<*>) (Identity f) (Identity a) = Identity (f a)```
```data Pair a = Pair a a deriving Show

instance Applicative Pair where
pure a = Pair a a
(<*>) (Pair f f') (Pair a a') = Pair (f a) (f' a')```
```data Two a b = Two a b

instance Monoid a => Applicative (Two a) where
pure x = Two mempty x
(<*>) (Two a f) (Two a' b) = Two (a <> a') (f b)```
```data Three a b c = Three a b c

instance (Monoid a, Monoid b) => Applicative (Three a b) where
pure x = Three mempty mempty x
(<*>) (Three a b f) (Three a' b' c) = Three (a <> a')
(b <> b')
(f c)```
```data Three' a b = Three' a b b

instance Monoid a => Applicative (Three' a) where
pure x = Three' mempty x x
(<*>) (Three' a f g) (Three' a' b b') = Three' (a <> a')
(f b)
(g b')```
```data Four a b c d = Four a b c d

instance (Monoid a,
Monoid b,
Monoid c) => Applicative (Four a b c) where
pure x = Four mempty mempty mempty x
(<*>) (Four a b c f) (Four a' b' c' d) = Four (a <> a')
(b <> b')
(c <> c')
(f d)```
```data Four' a b = Four' a a a b

instance Monoid a => Applicative (Four' a) where
pure x = Four' mempty mempty mempty x
(<*>) (Four' a b c f) (Four' a' b' c' d) = Four' (a <> a')
(b <> b')
(c <> c')
(f d)```

1. Applicative

### 17.11 Follow-up resources

1. Tony Morris; Nick Partridge; Validation library

2. Conor McBride; Ross Paterson; Applicative Programming with Effects

3. Jeremy Gibbons; Bruno C. d. S. Oliveira; Essence of the Iterator Pattern

4. Ross Paterson; Constructing Applicative Functors

5. Sam Lindley; Philip Wadler; Jeremy Yallop; Idioms are oblivious, arrows are meticulous, monads are promiscuous.

#### 18.2 Sorry — Monad is not a burrito

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

#### Applicative m

`fmap f xs = xs >>= return . f`

#### The novel part of Monad

```fmap :: Functor f => (a -> b) -> f a -> f b
<*> :: Applicative f => f (a -> b) -> f a -> f b
>>= :: Monad f => f a ->(a -> f b) -> f b```

monad is a generalization of `concat`

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

concat :: Foldable t => t [a] -> [a]```
```import Control.Monad (join)
join :: Monad m => m (m a) -> m a

bind :: Monad m => (a -> m b) -> m a -> m b
bind = join . fmap```

1. Impure
2. for imperative programming
3. value

### 18.3 Do syntax and monads

```(*>) :: Applicative f => f a -> f b -> f b
(>>) :: Monad m =>       m a -> m b -> m b```
```getLine :: IO String
putStrLn :: String -> IO ()

binding :: IO ()
binding = do
name <- getLine
putStrLn name

binding' :: IO ()
binding' = getLine >>= putStrLn```

#### When fmap alone isn’t enough

```getLine <\$> putStrLn :: IO (IO ())
join \$ getLine <\$> putStrLn :: IO ()
```

with and without `do` syntax:

```bindingAndSequencing :: IO ()
bindingAndSequencing = do
putStrLn "name pls:"
name <- getLine
putStrLn ("y helo thar: " ++ name)

bindingAndSequencing' :: IO ()
bindingAndSequencing' =
putStrLn "name pls:" >>
getLine >>=
\name -> putStrLn ("y helo thar: " ++ name)```

### 18.4 Examples of Monad use

#### List

##### Specializing the types
```(>>=) :: Monad m => m a -> (a -> m b) -> m b
(>>=) :: [a] -> (a -> [b]) -> [b]

return :: Monad m => a -> m a
return :: a -> [a]```

#### Example of the List Monad in use

```twiceWhenEven :: [Integer] -> [Integer]
twiceWhenEven xs = do
x <- xs
if even x
then [x * x, x * x]
else [x * x]

twiceWhenEven [1..3] -- [1,4,4,9]

twiceWhenEven :: [Integer] -> [Integer]
twiceWhenEven xs = do
x <- xs
if even x
then [x*x, x*x]
else []```

#### Maybe

##### Specializing the types
```-- m ~ Maybe
(>>=) :: Monad m => m a -> (a -> m b) -> m b
(>>=) :: Maybe a -> (a -> Maybe b) -> Maybe b

-- same as pure
return :: Monad m => a -> m a
return :: a -> Maybe a```

#### Exploding a spherical cow

```instance Monad Maybe where
return x = Just x
(Just x) >>= k = k x
Nothing >>= _ = Nothing```

#### Fail fast, like an overfunded startup

bottom:

```Nothing >>= undefined
-- Nothing```

#### Either

##### Specializing the types
```-- m ~ Either e
(>>=) :: Monad m => m a -> (a -> m b) -> m b
(>>=) :: Either e a -> (a -> Either e b) -> Either e b

-- same as pure
return :: Monad m => a -> m a
return :: a -> Either e a
```

```(<*>) :: Applicative f => f (a -> b) -> f a -> f b
ap    ::       Monad m => m (a -> b) -> m a -> m b

ap :: (Monad m) => m (a -> b) -> m a -> m b
ap m m' = do
x <- m
x' <- m'
return (x x')```

#### Exercise

```data Sum a b = First a
| Second b deriving (Eq, Show)

instance Functor (Sum a) where
fmap _ (First a)= First a
fmap f (Second b) = Second (f b)

instance Applicative (Sum a) where
pure = Second
(<*>) (First a) _ = First a
(<*>) _ (First a) = First a
(<*>) (Second f) (Second b) = Second (f b)

return = pure
(>>=) (First a) _ = First a
(>>=) (Second b) f = f b```

#### Identity laws

```-- right identity
m >>= return = m
-- left identity
return x >>= f = f x```

#### Associativity

`(m >>= f) >>= g = m >>= (\x -> f x >>= g)`

### 18.6 Application and composition

```mcomp :: Monad m => (b -> m c) -> (a -> m b) -> a -> m c
mcomp f g a = join (f <\$> (g a))
mcomp'' f g a = g a >>= f```
```(>=>) :: Monad m => (a -> m b) -> (b -> m c) -> a -> m c
flip (.) :: (a -> b) -> (b -> c) -> a -> c```

### 18.7 Chapter Exercises

```data Nope a = NopeDotJpg

return = pure
(>>=) NopeDotJpg _ = NopeDotJpg```
```data PhhhbbtttEither b a = Left a | Right b

return = pure
(>>=) (Right b) _ = Right b
(>>=) (Left a) f = f a```
```newtype Identity a = Identity a deriving (Eq, Ord, Show)

instance Functor Identity where
fmap f (Identity a) = Identity (f a)

instance Applicative Identity where
pure = Identity
(<*>) (Identity f) (Identity a)= Identity (f a)

return = pure
(>>=) (Identity a) f = f a```
```data List a = Nil | Cons a (List a)

return a = pure
(>>=) Nil _ = Nil
(>>=) (Cons a l) f = f a <> (l >>= f)```
```j :: Monad m => m (m a) -> m a
j = join

j [[1, 2], [], [3]]
-- [1,2,3]
j (Just (Just 1))
-- Just 1
j (Just Nothing)
-- Nothing
j Nothing
-- Nothing```
```l1 :: Monad m => (a -> b) -> m a -> m b
l1 = liftM```
```l2 :: Monad m => (a -> b -> c) -> m a -> m b -> m c
l2 = liftM2```
```a :: Monad m => m a -> m (a -> b) -> m b
a = flip ap```
```meh :: Monad m => [a] -> (a -> m b) -> m [b]
meh [] _ = return []
meh (x:xs) f = (meh xs f) >>= (\xs -> fmap (:xs) (f x))
-- or
meh (x:xs) f = (fmap (\a -> (a:)) \$ f x) <*> (meh xs f)
-- or
meh (x:xs) f = (++) <\$> (fmap (\a -> [a]) \$ f x) <*> (meh xs f)```
```flipType :: (Monad m) => [m a] -> m [a]
flipType [] = return []
flipType (x:xs) = (:) <\$> x <*> (flipType xs)```

### 18.8 Definition

2. monadic function: `a -> m b`

3. bind

```-- lifting (a -> b) over f in f a
fmap :: (a -> b) -> f a -> f b

-- binding (a -> m b) over m in m a
(>>=) :: m a -> (a -> m b) -> m b```

### 18.9 Follow-up resources

1. What a Monad is not
2. Gabriel Gonzalez; How to desugar Haskell code
3. Stephen Diehl; What I wish I knew when Learning Haskell
5. Brent Yorgey; Typeclassopedia

## CHAPTER20. FOLDABLE

### 20.1 Foldable

• the Foldable class and its core operations;
• the monoidal nature of folding;
• standard operations derived from folding.

### 20.3 Revenge of the monoids

```class Foldable (t :: * -> *) where
fold :: Data.Monoid.Monoid m => t m -> m
foldMap :: Data.Monoid.Monoid m => (a -> m) -> t a -> m```

`fold` does not have a Monoid specified:

``````fold [1, 2, 3, 4, 5]

-- ok
fold [Sum 1, Sum 2, Sum 3, Sum 4, Sum 5]
-- Sum {getSum = 15}

-- or this
fold [1, 2, 3, 4, 5 :: Sum Integer]
-- Sum {getSum = 15}
``````

#### And now for something different

```foldMap (*5) [1, 2, 3 :: Product Integer]
-- Product {getProduct = 750}
-- 5 * 10 * 15 = 750

foldMap (*5) [1, 2, 3 :: Sum Integer]
-- Sum {getSum = 30}
-- 5 + 10 + 15 = 30

foldMap (*5) Nothing :: Sum Integer
-- Sum {getSum = 0}
foldMap (*5) Nothing :: Product Integer
-- Product {getProduct = 1}```

### 20.4 Demonstrating Foldable instances

#### Identity

```data Identity a = Identity a

instance Foldable Identity where
foldr f z (Identity x) = f x z
foldl f z (Identity x) = f z x
foldMap f (Identity x) = f x```

#### Maybe

```instance Foldable Optional where
foldr _ z Nada = z
foldr f z (Yep x) = f x z
foldl _ z Nada = z
foldl f z (Yep x) = f z x
foldMap f (Yep a) = f a

-- error
-- ok
foldMap (+1) Nada :: Sum Int
-- Sum {getSum = 0}```

### 20.5 Some basic derived operations

#### Exercises

```sum :: (Foldable t, Num a) => t a -> a
sum = getSum . foldMap Sum```
```product :: (Foldable t, Num a) => t a -> a
product = getProduct . foldMap Product```
```elem :: (Foldable t, Eq a) => a -> t a -> Bool
elem el = getAny . foldMap (Any . (el==))```
```newtype Min a = Min {getMin :: Maybe a}

instance Ord a => Monoid (Min a) where
mempty = Min Nothing
m `mappend` Min Nothing = m
Min Nothing `mappend` n = n
(Min m@(Just x)) `mappend` (Min n@(Just y))
| x <= y    = Min m
| otherwise = Min n

minimum :: (Foldable t, Ord a) => t a -> Maybe a
minimum = getMin . foldMap (\a -> Min {getMin = Just a})```
```null :: (Foldable t) => t a -> Bool
null = (==0) . length
-- or
null = foldr (\_ _ -> False) True```
```length :: (Foldable t) => t a -> Int
length = foldr (\_ acc -> acc + 1) 0```
```toList :: (Foldable t) => t a -> [a]
toList = foldr (:) []```
```fold :: (Foldable t, Monoid m) => t m -> m
fold = foldMap id```
```foldMap :: (Foldable t, Monoid m) => (a -> m) -> t a -> m
foldMap f = foldr (\a acc -> f a <> acc) mempty```

### 20.6 Chapter Exercises

```data Constant a b = Constant a

instance Foldable (Constant a) where
foldMap _ _ = mempty```
```data Two a b = Two a b

instance Foldable (Two a) where
foldMap f (Two a b) = f b```
```data Three a b c = Three a b c

instance Foldable (Three a b) where
foldMap f (Three a b c) = f c```
```data Three' a b = Three' a b b

instance Foldable (Three' a) where
foldMap f (Three' a b c) = f b <> f c```
```data Four' a b = Four' a b b b

instance Foldable (Four' a) where
foldMap f (Four' a b c d) = f b <> f c <> f d```
``````filterF f = foldMap fb
where fb x
| f x = pure x
| otherwise = mempty
``````

### 20.8 Follow-up resources

1. Jakub Arnold, Foldable and Traversable

## CHAPTER21. TRAVERSABLE

### 21.2 The Traversable typeclass definition

```class (Functor t, Foldable t) => Traversable t where

traverse :: Applicative f => (a -> f b) -> t a -> f (t b)
traverse f = sequenceA . fmap f

sequenceA :: Applicative f => t (f a) -> f (t a)
sequenceA = traverse id```

### 21.4 traverse

```fmap :: (a -> b) ->fa->fb
(=<<) :: (a -> m b) -> m a -> m b -- flip bind
traverse :: (a -> f b) -> t a -> f (t b)```
`traverse = sequenceA . fmap`

#### mapM is just traverse

traverse is more generic:

```mapM :: Monad m => (a -> m b) -> [a] -> m [b]
-- contrast with
traverse :: Applicative f => (a -> f b) -> t a -> f (t b)

sequence :: Monad m => [m a] -> m [a]
-- contrast with
sequenceA :: (Applicative f, Traversable t) => t (f a)
-> f (t a)```

### 21.6 Morse code revisited

```-- we want this
(sequence .) . fmap = \ f xs -> sequence (fmap f xs)
-- not this
sequence . fmap = \ f -> sequence (fmap f)

traverse morseToChar (morse "julie")
-- Just "julie"```

### 21.7 Axing tedious code

```data Query     = Query
data SomeObj   = SomeObj
data IoOnlyObj = IoOnlyObj
data Err       = Err

decodeFn :: String -> Either Err SomeObj
decodeFn = undefined

fetchFn :: Query -> IO [String]
fetchFn = undefined

makeIoOnlyObj :: [SomeObj] -> IO [(SomeObj, IoOnlyObj)] makeIoOnlyObj = undefined

-- before
pipelineFn :: Query -> IO (Either Err [(SomeObj, IoOnlyObj)])
pipelineFn query = do
a <- fetchFn query
case sequence (map decodeFn a) of
(Left err) -> return \$ Left \$ err
(Right res) -> do
a <- makeIoOnlyObj res
return \$ Right a

-- after
pipelineFn :: Query -> IO (Either Err [(SomeObj, IoOnlyObj)])
pipelineFn query = do
a <- fetchFn query
traverse makeIoOnlyObj (mapM decodeFn a)

-- or
pipelineFn :: Query -> IO (Either Err [(SomeObj, IoOnlyObj)])
pipelineFn = (traverse makeIoOnlyObj . mapM decodeFn =<<) . fetchFn

-- or mapM = traverse
pipelineFn :: Query -> IO (Either Err [(SomeObj, IoOnlyObj)])
pipelineFn =
(traverse makeIoOnlyObj . traverse decodeFn =<<) . fetchFn
```

### 21.9 Traversable instances

#### Either

```data Either a b = Left a
| Right b deriving (Eq, Ord, Show)

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

instance Applicative (Either e) where
pure = Right
Left e <*> _ = Left e
Right f <*> r = fmap f r

instance Foldable (Either a) where
foldMap _ (Left _) = mempty
foldMap f (Right y) = f y
foldr _ z (Left _) = z
foldr f z (Right y) = f y z

instance Traversable (Either a) where
traverse _ (Left x) = pure (Left x)
traverse f (Right y) = fmap Right \$ f y
```

#### Tuple

```instance Functor ((,) a) where
fmap f (x,y) = (x, f y)

instance Monoid a => Applicative ((,) a) where
pure x = (mempty, x)
(u, f) <*> (v, x) = (u `mappend` v, f x)

instance Foldable ((,) a) where
foldMap f (_, y) = f y
foldr f z (_, y) = f y z

instance Traversable ((,) a) where
traverse f (x, y) = (,) x <\$> f y
```

1. Naturality