# Functional Programming Concepts

• Index
• Repository
• ## 1 Concepts

### 1.1 Overview

Functional Programming

Functional Programming is all about programming with functions.

Functional Programming Features

• Pure Functions / Referential Transparency / No side effect
• Function Composition
• Lambda Functions/ Anonymous Functions
• High Order Functions
• Currying/ Partial Function Application
• Closure - Returning functions from functions
• Data Immutability
• Pattern Matching
• Lists are the fundamental data Structure

Non Essential Features:

• Static Typing
• Type Inference
• Algebraic Data Types

Functional Programming Design Patterns

• Curry/ Partial function application - Creating new functions by holding a parameter constant
• Closure - Return functions from functions
• Pure Functions: separate pure code from impure code.
• Function composition
• Composable functions
• High Order Functions
• MapReduce Algorithms - Split computation in multiple computers cores.
• Lazy Evaluation ( aka Delayed evaluation)
• Pattern Matching

### 1.2 First-Class Function

Functions can be passed as arguments to other functions, returned from functions, stored in variables and data structures and built at run time. The majority of languages supports first-class functions like Scheme, Javascript, Python, Haskell, ML, OCaml and many others some exceptions are C, Java, Matlab (Octave open source implementation), Bash, and Forth.

Functions can be passed as arguments and returned from functions

• Example in Python: The function f is passed as argument to the derivate function that returns a new function named _, that computes the derivate of f at x.
```def derivate (f, dx=1e-5):
def _(x):
return (f(x+dx) - f(x))/dx
return _

#  Algebraic derivate:
#
#  df(x) = 2*x - 3
#
>>> def f(x): return x**2 - 3*x + 4
...

# Numerical derivate of f
>>> df = derivate(f)
>>>

# Algebraic derivate of f
>>> def dfa (x): return 2*x - 3
...
>>>

;; Functions can be stored in variables
>>> func = f
>>> func(5)
14
>>>

>>> df = derivate(f)
>>> df(3)
3.000009999887254
>>> df(4)
5.000009999633903
>>>

>>> dfa(3)
3
>>> dfa(4)
5
>>>

>>> f(3)
4
>>> f(10)
74
>>>
```

Functions can be stored in data structures

Example: Python - Functions stored in a dictionary hash-table

```import math

def myfun2(x):
return 5.68 * x - 5.0

dispatchTable = {
"sin": math.sin,
"cos": math.cos,
"exp": math.exp,
"tan": math.tan,
"myfun": lambda x: 10.2 * x - 5.0,
"myfun2": myfun2
}

>>> dispatchTable["sin"](math.pi)
1.2246467991473532e-16
>>> dispatchTable["cos"](math.pi)
-1.0
>>> dispatchTable["tan"](math.pi)
-1.2246467991473532e-16
>>> dispatchTable["exp"](math.pi)
23.140692632779267
>>>
>>>
>>> dispatchTable["exp"](1.0)
2.718281828459045
>>>

>>>
>>> dispatchTable["myfun"](1.0)
5.199999999999999
>>> dispatchTable["myfun2"](1.0)
0.6799999999999997
```

Example: Haskell - Functions stored in a list.

```> let funlist = [sin, cos, exp, \x -> 10.0 * x - 3.0]
>
> :t funlist
funlist :: Floating a => [a -> a]
> funlist

> (funlist !! 0) 0
0.0
> (funlist !! 0) (pi / 2.0)
1.0
>
> (funlist !! 3) 10.0
97.0

> (funlist !! 3) 4.0
37.0
>

-- Apply all functions to a single arguments:
--
> map (\f -> f 4.0) funlist
[-0.7568024953079282,-0.6536436208636119,54.598150033144236,37.0]
>

> let funlist2 = [\x -> 2.0 * x, (*3.0), (+10.0)] ;;
>
> map (\f -> f 4.0) funlist2
[8.0,12.0,14.0]
>

-- Functions can be generated at run-time.
--
--
> let flist = map (*) [1, 2, 3, 4]

> :t flist
flist :: Num a => [a -> a]
>

> map (\f -> f 3) flist
[3,6,9,12]
>
```

Example: Haskell functions stored in a Map (aka dictionary or hash table)

```import qualified Data.Map as M

>  :t M.fromList
M.fromList :: Ord k => [(k, a)] -> M.Map k a
>

:{
dispatchTable = M.fromList [("sin", sin)
,("cos", cos)
,("exp", exp)
,("myfun", \x -> 10.5 * x - 3.0)
]

:}

>  M.keys dispatchTable
["cos","exp","myfun","sin"]
>

>  :t M.lookup "sin" dispatchTable
M.lookup "sin" dispatchTable :: Floating a => Maybe (a -> a)
>

>  fmap (\f -> f 1.0) (M.lookup "sin" dispatchTable)
Just 0.8414709848078965
>
>  fmap (\f -> f 1.0) (M.lookup "cos" dispatchTable)
Just 0.5403023058681398
>  fmap (\f -> f 1.0) (M.lookup "exp" dispatchTable)
Just 2.718281828459045
>
>  fmap (\f -> f 1.0) (M.lookup "notfound" dispatchTable)
Nothing

:{
applyFun dict key x =
case M.lookup key dict of
Just f   -> Just (f x)
Nothing  -> Nothing
:}

>  :t applyFun
applyFun :: Ord k => M.Map k (t -> a) -> k -> t -> Maybe a

>

>  applyFun dispatchTable "sin" 2.0
Just 0.9092974268256817
>  applyFun dispatchTable "sin" 0.0
Just 0.0
Nothing
>

>  let dispatchFun = applyFun dispatchTable
>  dispatchFun "sin" 3.1415
Just 9.265358966049026e-5
>  dispatchFun "cos" 3.1415
Just (-0.9999999957076562)
>
>  dispatchFun  "myfun" 2.30
Just 21.15
>

:{
applyHmap dict x =
M.fromList \$ map (\ (k, fn) -> (k, fn x))
\$ zip (M.keys dict) (M.elems dict)
:}

>  :t applyHmap
applyHmap :: Ord k => M.Map k (t -> a) -> t -> M.Map k a
>

>  applyHmap dispatchTable  2.0
fromList [("cos",-0.4161468365471424),("exp",7.38905609893065),("myfun",18.0),("sin",0.9092974268256817)]
>

-- Formatted for better display
--
>  map (applyHmap dispatchTable) [1.0, 2.0, 3.0, 4.0]
[fromList [("cos",0.5403023058681398),("exp",2.718281828459045),("myfun",7.5),("sin",0.8414709848078965)],
fromList [("cos",-0.4161468365471424),("exp",7.38905609893065),("myfun",18.0),("sin",0.9092974268256817)],
fromList [("cos",-0.9899924966004454),("exp",20.085536923187668),("myfun",28.5),("sin",0.1411200080598672)],
fromList [("cos",-0.6536436208636119),("exp",54.598150033144236),("myfun",39.0),("sin",-0.7568024953079282)]]
```

Many examples of first class functions in several languages.

### 1.3 Pure Functions

Pure functions:

• Are functions without side effects, like mathematical functions.
• For the same input the functions always returns the same output.
• The result of any function call is fully determined by its arguments.
• Pure functions don't rely on global variable and don't have internal states.
• They don't do IO, i.e .:. don't print, don't write a file …
• Pure functions are stateless
• Pure functions are deterministic

Why Pure Functions:

• Composability, one function can be connected to another.
• Can run in parallel, multi-threading, multi-core, GPU and distributed systems.
• Better debugging and testing.
• Predictability

Example of pure functions

```def min(x, y):
if x < y:
return x
else:
return y
```

Example of impure function

• Impure functions doesn't have always the same output for the same
• Impure functions does IO or has Hidden State or Global Variables
```exponent = 2

def powers(L):
for i in range(len(L)):
L[i] = L[i]**exponent
return L
```

The function min is pure. It always produces the same result given the same inputs and it does not affect any external variable.

The function powers is impure because it not always gives the same output for the same input, it depends on the global variable exponent:

```>>> exponent = 2
>>>
>>> def powers(L):
...     for i in range(len(L)):
...         L[i] = L[i]**exponent
...     return L
...
>>> powers([1, 2, 3])
[1, 4, 9]
>>> exponent = 4
>>> powers([1, 2, 3])  # (It is impure since it doesn't give the same result )
[1, 16, 81]
>>>
```

Another example, purifying an impure Language:

```>>> lst = [1, 2, 3, 4]  # An pure function doesn't modify its arguments.
>>>                     # therefore lst reverse is impure
>>> x = lst.reverse()
>>> x
>>> lst
[4, 3, 2, 1]

>>> lst.reverse()
>>> lst
[1, 2, 3, 4]
```

Reverse list function purified:

```>>> lst = [1, 2, 3, 4]
>>>
>>> def reverse(lst):
...     ls = lst.copy()
...     ls.reverse()
...     return ls
...
>>>
>>> reverse(lst)
[4, 3, 2, 1]
>>> lst
[1, 2, 3, 4]
>>> reverse(lst)
[4, 3, 2, 1]
>>> lst
[1, 2, 3, 4]
```

### 1.4 Referential Transparency

Referential Transparency means that any sub-expression can be replaced by its value within an expression at any time without changing the evaluation of the whole expression. This property is a characteristic of mathematical expressions that allows program transformation, program manipulation and equational reasoning. It can be basically be stated as "replace equals by equals".

If there is referential transparency the expression below is valid:

`f(x) + f(x) = 2 * f(x)`

The function f is referentially transparent only if it is a pure function. The application of the function can be replaced by its value without change the meaning of the expression and it yields always the same result for the same input.

Referential transparency is only possible in the absence of side-effects. Haskell is one the few language which is referencially transparent owing to the fact that it enforces purity.

Benefits:

• Program transformation
• Equational reasoning
• Every expression can replaced by its value.
• Reasoning about the result of a function can be done by replacing its definition at the place of the application regardless of the context.
• Evaluation order doesn't matter.
• More opportunities for compiler optimization
• Computations can be safely distributed over multiple processors/threads.
• Previous evaluated expressions can be memoized.
• Programs with referential transparency can be easier to reason about its behavior due to the reader does not have to think about the side-effects like global states, internal states and IO.
• Help change the code without breaking it, easier refactoring.

Example: referential transparency in Python. Note: Python as ML variants and Scheme doesn't enforce it.

```>>> def square (x):
...   return x * x
...
>>>
>>> square (3) + square (3)
18
>>> 2 * square (3)
18
>>> square (3) + square (3) == 2 * square (3)
True
>>>
>>> x  = square (3)
>>> x
9
>>> x + x  == 2 * square (3)
True
```

Example:violation of referential transparency or referential opacity due to global state side-effect in Python.

```state = 1

def f(x):
global state
state = state + 1
return x + state

>>> f(2)
4
>>> f(2)
5
>>> 2 * f(2)
12
>>>

# Resetting the world:
#
>>> state = 1
>>>
>>> f(2) + f(2) == 2 * f(2)
False
>>>

>>> import random
>>>
>>> random.random() + random.random () ==  2 * random.random()
False
>>>

>>> state = 0

>>> def counter ():
...    global state
...    state = state + 1
...    return state
...
>>> counter () + counter () == 2 * counter ()
False
>>> counter ()
4
>>> counter ()
5
>>>
```

References:

### 1.5 Closure

Closure is a function that remembers the environment at which it was created.

```>>> x = 10

# The function adder remembers the environment at which it was created
# it remembers the value of x
#
return x + y

>>>
9
>>> list(map(add5, [1, 2, 3, 4, 5]))
[6, 7, 8, 9, 10]

>>> x
10
>>>

>>> list(map(add10, [1, 2, 3, 4, 5]))
[11, 12, 13, 14, 15]

#

def make_printer(msg):
def printer():
print(msg)
return printer

>>> p1 = make_printer ("Hello world")
>>> p2 = make_printer ("FP programming Rocks!!")
>>>
>>> p1()
Hello world
>>> p2()
FP p

# Mutable state with closure

idx = 100

def make_counter():
idx = -1
def _():
nonlocal idx
idx = idx + 1
return idx
return _

>>> idx = 100
>>> counter1 = make_counter()
>>> counter1()
0
>>> counter1()
1
>>> counter1()
2
>>> counter1()
3

>>> idx
100
>>> counter2 = make_counter ()
>>> counter2()
0
>>> counter2()
1
>>> counter2()
2

>>> counter1()
5
>>>

>>> del make_counter
>>> make_counter
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
NameError: name 'make_counter' is not defined
>>>
>>> counter1()
6
>>> counter1()
7
```

Example of closure in Clojure:

```(defn make-adder [x]
(fn [y] (+ x y)))

user=>
user=>
15
30
([6 11] [7 12] [8 13] [9 14] [10 15] [11 16])
user=>

(defn make-printer [message]

(fn [] (println message)))

user=> (def printer-1 (make-printer "Hello world"))
#'user/printer-1
user=>
user=> (def printer-2 (make-printer "Hola Mundo"))
#'user/printer-2
user=>
user=> (printer-1)
Hello world
nil
user=> (printer-2)
Hola Mundo
nil
user=>
```

Example of closure in F# (F sharp):

```let make_adder x =
fun y -> x + y

val make_adder : x:int -> y:int -> int

val add5 : (int -> int)

val add10 : (int -> int)

val it : int = 25
>
val it : int = 40
>
- List.map add5 [1 ; 2; 3; 4; 5; 6] ;;
val it : int list = [6; 7; 8; 9; 10; 11]
>

//  As F# have currying like OCaml and Haskell
//  it could be also be done as
//

- let make_adder x y = x + y ;;

val make_adder : x:int -> y:int -> int

val add10 : (int -> int)

val it : int = 30
>
```

### 1.6 Currying and Partial Application

#### 1.6.1 Currying

##### 1.6.1.1 Overview

Currying is the decomposition of a function of multiples arguments in a chained sequence of functions of a single argument. The name currying comes from the mathematician Haskell Curry who developed the concept of curried functions. Curried functions can take one argument at a time and a uncurried function must have all arguments passed at once.

Let a function `f(x, y) = 10*x - 3*y` which is uncurryied. This function can only take two arguments at once.

This function can be rewritten in a curried form as:

• `f(x)(y) = 10*x - 3*y`

By applying it to a value of x = 4 creates a function with parameter y:

• g(y) = f(4) = 10*4 - 3*y
• g(3) = f(4)(3) = 10*4 - 3*3 = 31
```    f (x, y) = 10*x - 3*y

f (4, 3)  = 10* 4 - 3*3 = 40 - 9 = 31
f (4, 3)  = 31

In the curried form becomes:

g(x) = (x -> y -> 10 * x - 3*y)

To evaluate f(4, 3):

h(y)  = f(4) = (x -> y -> 10 * x - 3*y) 4  -- x = 4
= ( y -> 10 * 4 -  3*y )
=  y -> 40 - 3*y

h(3)  = (y -> 40 - 3*y) 3
= 40 - 3*3
= 31

Or:
(x -> y -> 10 * x - 3*y) 4 3
= (x -> (y -> 10 * x - 3*y)) 4 3
= ((x -> (y -> 10 * x - 3*y)) 4) 3
= (y -> 10 * 4 - 3 * y) 3
= 10 * 4 - 3 * 3
= 31
```

The same function h(y) can be reused: applied to other arguments, used in mapping, filtering and another higher order functions.

```Ex1
h(y) = (y -> 40 - 3*y)

h(10) = 40 - 3*10 = 40 - 30 = 10

Ex2
map(h, [2, 3, 4])
= [h 2, h 3, h 4]
= [(y -> 40 - 3*y) 2, (y -> 40 - 3*y) 3, (y -> 40 - 3*y) 4]
= [34, 31, 28]
```
##### 1.6.1.2 Example in Haskell GHCI

In Haskell, Standard ML, OCaml and F# all functions are curried by default and in most of programming languages they are uncurried by default.

```> let f x y = 10 * x - 3 * y
> :t f
f :: Num a => a -> a -> a
>
> f 4 3
31

--- Fix the value of x = 4 --> h(y) = f(x=4) = 10 * 4 - 3 * y
--                                            = 40 - 3 *  y
---
> let h_y = f 4
> :t h_y
h_y :: Integer -> Integer
>
> h_y 3
31

{-
34 = h_y 2 = 40 - 3*2 = 34
31 = h_y 3 = 40 - 3*3 = 31
28 = h_y 4 = 40 - 3*4 = 28
-}
> map h_y [2, 3, 4]
[34,31,28]
>

> -- It is evaluated as:

> ((f 4) 3)
31
>

{-
The function f can be also seen in this way
-}

> let f' = \x -> \y -> 10 * x - 3 * y
>

> :t f'
f' :: Integer -> Integer -> Integer
>

> f' 4 3
31
>

> (f' 4 ) 3
31
>

> let h__x_is_4_of_y = f' 4

> h__x_is_4_of_y 3
31
>
{-
(\x -> \y -> 10 * x - 3 * y) 4 3
=  (\x -> (\y -> 10 * x - 3 * y) 4) 3
=  (\y -> 10 * 4 - 3 * y) 3
=  (10 * 4 - 3 * 3)
=  40 - 9
=  31
-}
> (\x -> \y -> 10 * x - 3 * y) 4 3
31
>

> ((\x -> (\y -> 10 * x - 3 * y)) 4) 3
31
>

{-
Curried functions are suitable for composition, pipelining
(F#, OCaml with the |> operator),  mapping/ filtering operations,
and to create new function from previous defined increasing code reuse.

-}

> map (f 4) [2, 3, 4]
[34,31,28]
>

> map ((\x -> \y -> 10 * x - 3 * y) 4) [2, 3, 4]
[34,31,28]
>

> -- -----------------

> let f_of_x_y_z x y z = 10 * x + 3 * y + 4 * z
>

> :t f_of_x_y_z
f_of_x_y_z :: Num a => a -> a -> a -> a

> f_of_x_y_z 2 3 5
49
>

> let g_of_y_z = f_of_x_y_z 2

> :t g_of_y_z
g_of_y_z :: Integer -> Integer -> Integer
>

> g_of_y_z 3 5
49
>

> let h_of_z = g_of_y_z 3
> :t h_of_z
h_of_z :: Integer -> Integer
>

> h_of_z 5
49
>

> -- So it is evaluated as
> (((f_of_x_y_z 2) 3) 5)
49
>
```

Uncurried functions can also be defined in Haskell.

```let f (x, y) = 10 * x - 3 * y

Prelude> :t f
f :: Num a => (a, a) -> a
Prelude>

{- | Uncurried function cannot be applied to one argument at a time -}
Prelude> f 3 5

<interactive>:9:1: error:
• Non type-variable argument
in the constraint: Num (t -> t1, t -> t1)
(Use FlexibleContexts to permit this)
• When checking the inferred type
it :: forall t t1.
(Num (t -> t1, t -> t1), Num (t -> t1), Num t) =>
t1
Prelude>

Prelude> f(3, 4)
18
Prelude> f(3, 1)
27
Prelude> f(3, 2)
24
Prelude> f(3, 5)
15

Prelude> map f [(1, 2), (3, 4), (5, 6), (7, 8)]
[4,18,32,46]
Prelude>
```
##### 1.6.1.3 Example in Ocaml and F#
```# let f x y = 10 * x - 3 * y ;;
val f : int -> int -> int = <fun>

# f 4 3 ;;
- : int = 31

# f 4 ;;
- : int -> int = <fun>

# (f 4) 3 ;;
- : int = 31
#

# let h_y = f 4 ;;
val h_y : int -> int = <fun>

# h_y 3 ;;
- : int = 31
#

# List.map h_y [2; 3; 4] ;;
- : int list = [34; 31; 28]
#

# List.map (f 4) [2; 3; 4] ;;
- : int list = [34; 31; 28]

# let f' = fun x -> fun y -> 10 * x - 3 * y ;;
val f' : int -> int -> int = <fun>

# (f' 4) 3 ;;
- : int = 31

# (fun x -> fun y -> 10 * x - 3 * y) 4 3 ;;
- : int = 31
#

# List.map ((fun x -> fun y -> 10 * x - 3 * y) 4) [2; 3; 4] ;;
- : int list = [34; 31; 28]
```
##### 1.6.1.4 Example in Python 3
``` # In Python, the functions are not curried by default as in Haskell,
# Standard ML, OCaml and F#
#
>>> def f(x, y): return 10 * x - 3*y

>>> f(4, 3)
31

# However the user can create the curried form of the function f:

>>> curried_f = lambda x: lambda y: 10*x - 3*y

>>> curried_f(4)
<function __main__.<lambda>.<locals>.<lambda>>

>>> curried_f(4)(3)
31

>>> h_y = curried_f(4) # x = 4 constant

>>> h_y(3)
31

>>> h_y(5)
25

>>> mapl = lambda f_x, xs: list(map(f_x, xs))

>>> mapl(h_y, [2, 3, 4])
[34, 31, 28]

# Or

>>> mapl(curried_f(4), [2, 3, 4])
[34, 31, 28]

# Without currying the mapping would be:

>>> mapl(lambda y: f(4, y), [2, 3, 4])
[34, 31, 28]

########################################

>> f_of_x_y_z = lambda x, y, z: 10 * x + 3 * y + 4 * z

## Curried form:

>>> curried_f_of_x_y_z = lambda x: lambda y: lambda z: 10 * x + 3 * y + 4 * z

>>> f_of_x_y_z (2, 3, 5)
49

>>> curried_f_of_x_y_z (2)(3)(5)
49

>>> g_of_y_z = curried_f_of_x_y_z(2)

>>> g_of_y_z
<function __main__.<lambda>.<locals>.<lambda>>

>>> g_of_y_z (3)(5)
49

>>> h_of_z = g_of_y_z(3)

>>> h_of_z
<function __main__.<lambda>.<locals>.<lambda>.<locals>.<lambda>>

>>> h_of_z(5)
49
```
##### 1.6.1.5 Example in Scala

The function `f(x, y) = 10 * x - 3 * y` is defined in a uncurried form.

```def f(x: Int, y: Int) = 10 * x - 3 * y

scala> f(3, 4)
res0: Int = 18

scala> f(3)
<console>:13: error: not enough arguments for method f: (x: Int, y: Int)Int.
Unspecified value parameter y.
f(3)

scala> List(1, 2, 3, 4).map( y => f(4, y))
res5: List[Int] = List(37, 34, 31, 28)
```

Scala provides a syntax that makes easier to define functions in curried form:

```def f(x: Int) (y: Int) = 10 * x - 3 * y

scala> f(4)(1)
res14: Int = 37

scala> f(4)(2)
res15: Int = 34

scala> f(4)(3)
res16: Int = 31

scala> f(4)(4)
res17: Int = 28

scala> List(1, 2, 3, 4).map(f(4))
res13: List[Int] = List(37, 34, 31, 28)

scala> f(4) _
res11: Int => Int = <function1>

scala> f _
res12: Int => (Int => Int) = <function1>

scala>

scala> val g = (y: Int) => f(4)(y)
g: Int => Int = <function1>

scala> g(3)
res18: Int = 31

scala> g(4)
res19:
```

This function in curried form could also be defned in this way:

```scala> val f = (x: Int) => (y: Int) => 10 * x - 3 * y
f: Int => (Int => Int) = <function1>

scala> f(4)(3)
res2: Int = 31

scala> f(4)(2)
res3: Int = 34

scala> f(4)(5)
res4: Int = 25

scala>

scala> val g = f(4)
g: Int => Int = <function1>

scala> g(5)
res5: Int = 25

scala> g(3)
res6: Int = 31

scala> g(2)
res7: Int = 34

scala> g(5)
res8: Int = 25

scala> List(1, 2, 3, 4).map(f(4))
res9: List[Int] = List(37, 34, 31, 28)

scala> List(1, 2, 3, 4).map(g)
res11: List[Int] = List(37, 34, 31, 28)
```

#### 1.6.2 Partial Application

A function of multiple arguments is converted into a new function that takes fewer arguments, some arguments are supplied and returns function with signature consisting of remaining arguments. Partially applied functions must not be confused with currying.

Example in Python:

```>>> from functools import partial

>>> def f(x, y, z): return 10 * x + 3 * y + 4 * z

>>> f(2, 3, 5)
49

>>> f_yz = partial(f, 2) # x = 2
>>> f_yz(3, 5)
49

>>> f_z = partial(f_yz, 3)

>>> f_z(5)
49

>>> partial(f, 2, 3)(5)
49

>>> list(map(partial(f, 2, 3), [2, 3, 5]))
[37, 41, 49]

#
# Alternative implementation of partial
#
def partial(f, *xs):
return lambda x: f( * (tuple(xs) + (x,)))

>>> list(map(partial(f, 2, 3), [2, 3, 5]))
[37, 41, 49]
>>>
```

In languages like Haskell, Standard ML, OCaml and F# currying is similar to partial application.

Example in OCaml:

```# let f x y z = 10 * x + 3 *y + 4 * z ;;
val f : int -> int -> int -> int = <fun>
#

# (f 2 3) ;;
- : int -> int = <fun>

# let f_z = f 2 3 ;;
val f_z : int -> int = <fun>

# f_z 5 ;;
- : int = 49
#

(** Write (f 2 3) is the same as write (f 2)(3)  *)
# List.map (f 2 3) [2; 3; 5] ;;
- : int list = [37; 41; 49]
#
```

### 1.7 Tail Call Optimization and Tail Recursive Functions

#### 1.7.1 Tail Call

A tail call is a function call which is the last action performed by a function.

Examples of tail calls and non tail calls:

Example 1: Tail call

```def func1(x):
return  tail_call_function (x * 2) # It is a tail call
```

Example 2: Tail recursive call or tail recursive function.

```def tail_recursive_call (n, acc);
if n = 0:
return acc
return tai_recursive_acll (n - 1, n * acc) # Tail recursive call, the
# function call is the last
# thing the function does.
```

Example 3: Non tail call

```def non_tail_call_function(x):
return 1 + non_tail_call_function (x + 3)
```

#### 1.7.2 Tail Call Optimization

Tail call optimization - TCO. (aka. tail call elimination - TCE or tail recursion elimination - TRE) is a optimization that replaces calls in tail positions with jumps which guarantees that loops implemented using recursion are executed in constant stack space. {Schinz M. and Odersky M. - 2001}

Without tail call optimization each recursive call creates a new stack frame by growing the execution stack. Eventually the stack runs out of space and the program has to stop. To support iteration by recursion functional languages need tail call optimization. {Schwaighofer A. 2009} 1

If the language doesn't support TCO it is not possible to perform recursion safely. A big number of calls will lead to a stack overflow exception and the program will crash unexpectedly.

Sometimes non tail recursive functions can be changed to tail recursive by adding a new function with extra parameters (accumulators) to store partial results (state).

Languages with TCO support:

• Scheme
• Common Lisp
• Ocaml
• F# (F sharp)
• C# (C sharp)
• Scala
• Erlang

Languages without TCO support:

• Python 2 , 3
• Ruby
• Java (Note: The JVM doesn't support TCO)
• Clojure
• JavaScript
• R 4
• Elisp - Emacs Lisp

#### 1.7.3 Summary

1. To perform recursion safely a language must support TCO - Tail Call Optimization.
2. Even if there is TCO support a non tail recursive function can lead to an unexpected stack overflow.
3. Recursion allow greater expressiveness and many algorithms are better expressed with recursion.
4. Recursion must be replaced by loops constructs in languages that doesn't support TCO.

#### 1.7.4 Examples

Example of non tail recursive function in Scheme (GNU Guile):

```(define (factorial n)
(if (or (= n 0) (= n 1))
1
(* n  (factorial (- n 1)))))

> (factorial 10)
\$1 = 3628800
>

;;  For a very big number of iterations, non tail recursive functions
;;  will cause a stack overflow.
;;
> (factorial 20000000)
warnings can be silenced by the --no-warnings (-n) option
Aborted (core dumped)

;;
;; This execution requires 5 stack frames
;;
;;  (factorial 5)
;;  (* 5 (factorial 4))
;;  (* 5 (* 4 (factorial 3)))
;;  (* 5 (* 4 (3 * (factorial 2))))
;;  (* 5 (* 4 (* 3 (factorial 2))))
;;  (* 5 (* 4 (* 3 (* 2 (factorial 1)))))
;;
;;  (* 5 (* 4 (* 3 (* 2 1))))
;;  (* 5 (* 4 (* 3 2)))
;;  (* 5 (* 4 6))
;;  (* 5 24)
;;  120
;;
;;
;;
;;
> ,trace (factorial 5)
trace: |  (#<procedure 99450c0> #(#<directory (guile-user) 95c3630> …))
trace: |  #(#<directory (guile-user) 95c3630> factorial)
trace: (#<procedure 9953350 at <current input>:8:7 ()>)
trace: (factorial 5)
trace: |  (factorial 4)
trace: |  |  (factorial 3)
trace: |  |  |  (factorial 2)
trace: |  |  |  |  (factorial 1)
trace: |  |  |  |  1
trace: |  |  |  2
trace: |  |  6
trace: |  24
trace: 120
>

;;
;; It requires 10 stack frames
;;
;;
> ,trace (factorial 10)
trace: |  (#<procedure 985cbd0> #(#<directory (guile-user) 95c3630> …))
trace: |  #(#<directory (guile-user) 95c3630> factorial)
trace: (#<procedure 9880800 at <current input>:6:7 ()>)
trace: (factorial 10)
trace: |  (factorial 9)
trace: |  |  (factorial 8)
trace: |  |  |  (factorial 7)
trace: |  |  |  |  (factorial 6)
trace: |  |  |  |  |  (factorial 5)
trace: |  |  |  |  |  |  (factorial 4)
trace: |  |  |  |  |  |  |  (factorial 3)
trace: |  |  |  |  |  |  |  |  (factorial 2)
trace: |  |  |  |  |  |  |  |  |  (factorial 1)
trace: |  |  |  |  |  |  |  |  |  1
trace: |  |  |  |  |  |  |  |  2
trace: |  |  |  |  |  |  |  6
trace: |  |  |  |  |  |  24
trace: |  |  |  |  |  120
trace: |  |  |  |  720
trace: |  |  |  5040
trace: |  |  40320
trace: |  362880
trace: 3628800
>
```

This function can be converted to a tail recursive function by using an accumulator:

```(define (factorial-aux n acc)
(if (or (= n 0) (= n 1))
acc
(factorial-aux (- n 1) (* n acc))))

> (factorial-aux 6 1)
\$1 = 720

> ,trace (factorial-aux 6 1)
trace: |  (#<procedure 9becf10> #(#<directory (guile-user) 984c630> …))
trace: |  #(#<directory (guile-user) 984c630> factorial-aux)
trace: (#<procedure 9bec320 at <current input>:26:7 ()>)
trace: (factorial-aux 6 1)
trace: (factorial-aux 5 6)
trace: (factorial-aux 4 30)
trace: (factorial-aux 3 120)
trace: (factorial-aux 2 360)
trace: (factorial-aux 1 720)
trace: 720
scheme@(guile-user)>

> (define (factorial2 n) (factorial-aux n 1))

scheme@(guile-user)> (factorial2 5)
\$3 = 120

;; This function could also be implemented in this way:
;;
;;
(define (factorial3 n)
(define (factorial-aux n acc)
(if (or (= n 0) (= n 1))
acc
(factorial-aux (- n 1) (* n acc))))
(factorial-aux n 1))

> (factorial3 6)
\$4 = 720

> (factorial3 5)
\$5 = 120
```

Example: Summation of a range of numbers:

```;;  Non tail recursive function:
;;
(define (sum-ints a b)
(if (> a b)
0
(+ a (sum-ints (+ a 1) b))))

;;
;; Using the trace command is possible to notice the growing amount of
;; stack frame In this case it requires 11 stack frames.

> ,trace (sum-ints 1 10)
trace: |  (#<procedure 9c42420> #(#<directory (guile-user) 984c630> …))
trace: |  #(#<directory (guile-user) 984c630> sum-ints)
trace: (#<procedure 9c4b8c0 at <current input>:56:7 ()>)
trace: (sum-ints 1 10)
trace: |  (sum-ints 2 10)
trace: |  |  (sum-ints 3 10)
trace: |  |  |  (sum-ints 4 10)
trace: |  |  |  |  (sum-ints 5 10)
trace: |  |  |  |  |  (sum-ints 6 10)
trace: |  |  |  |  |  |  (sum-ints 7 10)
trace: |  |  |  |  |  |  |  (sum-ints 8 10)
trace: |  |  |  |  |  |  |  |  (sum-ints 9 10)
trace: |  |  |  |  |  |  |  |  |  (sum-ints 10 10)
trace: |  |  |  |  |  |  |  |  |  |  (sum-ints 11 10)
trace: |  |  |  |  |  |  |  |  |  |  0
trace: |  |  |  |  |  |  |  |  |  10
trace: |  |  |  |  |  |  |  |  19
trace: |  |  |  |  |  |  |  27
trace: |  |  |  |  |  |  34
trace: |  |  |  |  |  40
trace: |  |  |  |  45
trace: |  |  |  49
trace: |  |  52
trace: |  54
trace: 55

;;  Stack Overflow Error
;;
> (sum-ints 1 10000)
> <unnamed port>:4:13: In procedure sum-ints:
<unnamed port>:4:13: Throw to key `vm-error' with args `(vm-run "VM: Stack overflow" ())'.

;;
;; Safe summation
;;
(define (sum-ints-aux a b acc)
(if (> a b)
acc
(sum-ints-aux (+ a 1) b (+ a acc))))

(define (sum-ints-aux a b acc)
(if (> a b)
acc
(sum-ints-aux (+ a 1) b (+ a acc))))

> (sum-ints-aux 1 10 0)
\$4 = 55
>

> (sum-ints-aux 1 10000 0)
\$6 = 50005000

;;
;; It uses only one stack frame each call
;;
> ,trace (sum-ints-aux 1 10 0)
trace: |  (#<procedure 985a270> #(#<directory (guile-user) 93fd630> …))
trace: |  #(#<directory (guile-user) 93fd630> sum-ints-aux)
trace: (#<procedure 98646a0 at <current input>:31:7 ()>)
trace: (sum-ints-aux 1 10 0)
trace: (sum-ints-aux 2 10 1)
trace: (sum-ints-aux 3 10 3)
trace: (sum-ints-aux 4 10 6)
trace: (sum-ints-aux 5 10 10)
trace: (sum-ints-aux 6 10 15)
trace: (sum-ints-aux 7 10 21)
trace: (sum-ints-aux 8 10 28)
trace: (sum-ints-aux 9 10 36)
trace: (sum-ints-aux 10 10 45)
trace: (sum-ints-aux 11 10 55)
trace: 55
>

;; It can also be implemented in this way:
;;
(define (sum-ints-safe a b)
(define (sum-ints-aux a b acc)
(if (> a b)
acc
(sum-ints-aux (+ a 1) b (+ a acc))))
(sum-ints-aux a b 0))

> scheme@(guile-user)> (sum-ints-safe 1 1000)
\$2 = 500500

> (sum-ints-safe 1 10000)
\$7 = 50005000

>  (sum-ints-safe 1 100000)
\$8 = 5000050000
scheme@(guile-user)>
```

Example: of summation in a language without TCO: python

```def sum_ints_aux (a, b, acc):
if a > b:
return acc
else:
return sum_ints_aux (a + 1, b, a + acc)

# Until now works
>>>
>>> sum_ints_aux(1, 10, 0)
55
>>> sum_ints_aux(1, 100, 0)
5050

# Now it is going to fail: Stack Overflow!

>>> sum_ints_aux(1, 1000, 0)
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
File "<stdin>", line 5, in sum_ints_aux
File "<stdin>", line 5, in sum_ints_aux
...
File "<stdin>", line 5, in sum_ints_aux
File "<stdin>", line 2, in sum_ints_aux
RuntimeError: maximum recursion depth exceeded in comparison
>>>

#  Solution: Turn the recursion into a loop:
#
def sum_ints (a, b):
x  = a
acc = 0

while x < b:

x = x + 1
acc = acc + x

return acc + 1

>> sum_ints (1, 1000)
500500

>> sum_ints (1, 10000)
50005000
```

Example: Implementing map with tail recursion.

```(define (map2 f xs)
(if (null? xs)
'()
(cons  (f (car xs))
(map2 f (cdr xs)))))

(define (inc x) (+ x 1))

;; It will eventually lead to an stack overflow for a big list.
;;
> ,trace (map2 inc '(1 2 3))
trace: |  (#<procedure 9e14500> #(#<directory (guile-user) 984c630> …))
trace: |  #(#<directory (guile-user) 984c630> map2 inc (1 2 3))
trace: (#<procedure 9e48360 at <current input>:109:7 ()>)
trace: (map2 #<procedure inc (x)> (1 2 3))
trace: |  (inc 1)
trace: |  2
trace: |  (map2 #<procedure inc (x)> (2 3))
trace: |  |  (inc 2)
trace: |  |  3
trace: |  |  (map2 #<procedure inc (x)> (3))
trace: |  |  |  (inc 3)
trace: |  |  |  4
trace: |  |  |  (map2 #<procedure inc (x)> ())
trace: |  |  |  ()
trace: |  |  (4)
trace: |  (3 4)
trace: (2 3 4)

,trace (map2 inc '(1 2 3 4 5 6 7 8 9))
trace: |  (#<procedure 9cdcb00> #(#<directory (guile-user) 984c630> …))
trace: |  #(#<directory (guile-user) 984c630> map2 inc (1 2 3 4 5 6 …))
trace: (#<procedure 9ceebf0 at <current input>:104:7 ()>)
trace: (map2 #<procedure inc (x)> (1 2 3 4 5 6 7 8 9))
trace: |  (inc 1)
trace: |  2
trace: |  (map2 #<procedure inc (x)> (2 3 4 5 6 7 8 9))
trace: |  |  (inc 2)
trace: |  |  3
trace: |  |  (map2 #<procedure inc (x)> (3 4 5 6 7 8 9))
trace: |  |  |  (inc 3)
trace: |  |  |  4
trace: |  |  |  (map2 #<procedure inc (x)> (4 5 6 7 8 9))
trace: |  |  |  |  (inc 4)
trace: |  |  |  |  5
trace: |  |  |  |  (map2 #<procedure inc (x)> (5 6 7 8 9))
trace: |  |  |  |  |  (inc 5)
trace: |  |  |  |  |  6
trace: |  |  |  |  |  (map2 #<procedure inc (x)> (6 7 8 9))
trace: |  |  |  |  |  |  (inc 6)
trace: |  |  |  |  |  |  7
trace: |  |  |  |  |  |  (map2 #<procedure inc (x)> (7 8 9))
trace: |  |  |  |  |  |  |  (inc 7)
trace: |  |  |  |  |  |  |  8
trace: |  |  |  |  |  |  |  (map2 #<procedure inc (x)> (8 9))
trace: |  |  |  |  |  |  |  |  (inc 8)
trace: |  |  |  |  |  |  |  |  9
trace: |  |  |  |  |  |  |  |  (map2 #<procedure inc (x)> (9))
trace: |  |  |  |  |  |  |  |  |  (inc 9)
trace: |  |  |  |  |  |  |  |  |  10
trace: |  |  |  |  |  |  |  |  |  (map2 #<procedure inc (x)> ())
trace: |  |  |  |  |  |  |  |  |  ()
trace: |  |  |  |  |  |  |  |  (10)
trace: |  |  |  |  |  |  |  (9 10)
trace: |  |  |  |  |  |  (8 9 10)
trace: |  |  |  |  |  (7 8 9 10)
trace: |  |  |  |  (6 7 8 9 10)
trace: |  |  |  (5 6 7 8 9 10)
trace: |  |  (4 5 6 7 8 9 10)
trace: |  (3 4 5 6 7 8 9 10)
trace: (2 3 4 5 6 7 8 9 10)

(define (map-aux f xs acc)

(if (null? xs)

(reverse acc)

(map-aux f
(cdr xs)
(cons (f (car xs))
acc)
)
)
)

> ,trace (map-aux inc '(1 2 3 4 5) '())
trace: |  (#<procedure 9e0c420> #(#<directory (guile-user) 984c630> …))
trace: |  #(#<directory (guile-user) 984c630> map-aux inc (1 2 3 4 5))
trace: (#<procedure 9e4c070 at <current input>:180:7 ()>)
trace: (map-aux #<procedure inc (x)> (1 2 3 4 5) ())
trace: |  (inc 1)
trace: |  2
trace: (map-aux #<procedure inc (x)> (2 3 4 5) (2))
trace: |  (inc 2)
trace: |  3
trace: (map-aux #<procedure inc (x)> (3 4 5) (3 2))
trace: |  (inc 3)
trace: |  4
trace: (map-aux #<procedure inc (x)> (4 5) (4 3 2))
trace: |  (inc 4)
trace: |  5
trace: (map-aux #<procedure inc (x)> (5) (5 4 3 2))
trace: |  (inc 5)
trace: |  6
trace: (map-aux #<procedure inc (x)> () (6 5 4 3 2))
trace: (reverse (6 5 4 3 2))
trace: (2 3 4 5 6)

;; Finally
;;

(define (map-safe f xs)
(map-aux f xs '()))

> (map-safe inc '(1 2 3 3 4 5))
\$14 = (2 3 4 4 5 6)
```

Example in F#:

```> let inc x = x +  1 ;;

val inc : x:int -> int

let rec map_aux f xs acc =
match xs with
| []    ->  List.rev acc
| hd::tl ->  map_aux f tl ((f hd)::acc)
;;

val map_aux : f:('a -> 'b) -> xs:'a list -> acc:'b list -> 'b list

> map_aux inc [1; 2; 3; 4; 5] [] ;;
val it : int list = [2; 3; 4; 5; 6]

let map2 f xs =
map_aux f xs [] ;;

val map2 : f:('a -> 'b) -> xs:'a list -> 'b list

> map2 inc [1; 2; 3; 4; 5] ;;
val it : int list = [2; 3; 4; 5; 6]
>

//  map_aux without pattern matching
//
let rec map_aux f xs acc =
if List.isEmpty xs
then  List.rev acc
else (let hd, tl = (List.head xs, List.tail xs) in
map_aux f tl ((f hd)::acc))
;;

val map_aux : f:('a -> 'b) -> xs:'a list -> acc:'b list -> 'b list

>  map2 inc [1; 2; 3; 4; 5] ;;
val it : int list = [2; 3; 4; 5; 6]
>

//  Another way:
//
//
let map3  f xs =

let rec map_aux f xs acc =
match xs with
| []    ->  List.rev acc
| hd::tl ->  map_aux f tl ((f hd)::acc)

in map_aux f xs []

;;

val map3 : f:('a -> 'b) -> xs:'a list -> 'b list

> map3 inc [1; 2; 3; 4; 5; 6] ;;
val it : int list = [2; 3; 4; 5; 6; 7]
>
```

Example: Tail recursive filter function.

```let rec filter_aux f xs acc =
match xs with
| []      ->  List.rev acc
| hd::tl  ->  if (f hd)
then  filter_aux f tl (hd::acc)
else  filter_aux f tl acc
;;

val filter_aux : f:('a -> bool) -> xs:'a list -> acc:'a list -> 'a list

> filter_aux (fun x -> x % 2 = 0) [1; 2; 3; 4; 5; 6; 7; 8] [] ;;
val it : int list = [2; 4; 6; 8]
>

let filter f xs =
filter_aux f xs []
;;
val filter : f:('a -> bool) -> xs:'a list -> 'a list

> filter (fun x -> x % 2 = 0) [1; 2; 3; 4; 5; 6; 7; 8] ;;
val it : int list = [2; 4; 6; 8]
>
```

### 1.8 Fundamental Higher Order Functions

#### 1.8.1 Overview

The functions map, filter and reduce (fold left) are ubiquitous in many programming languages and also the most used higher order functions.

They can be strict evaluated like in Scheme and JavaScript or lazy evaluated like in Python and Haskell.

#### 1.8.2 Map

1. Overview

The function map applies a function to each element of a sequence: list, vector, hash map or dictionary and trees.

```map :: ( a -> b) -> [a] -> [b]
|
|
|----> f :: a -> b

f :: a -> b
a   ------------------------>>>  b

map f :: [a] -> [b]
[a] ------------------------->>> [b]
```

The function map is lazy evaluated.

```> let fun1 x = 3 * x + 1
> fun1 2
7
> map fun1 [1, 2, 3]
[4,7,10]
>

-- The sequence 1 to 1000000 is not evaluated at all,
--
> take 10 (map fun1 [1..1000000])
[4,7,10,13,16,19,22,25,28,31]

> take 10 (map fun1 [1..10000000000])
[4,7,10,13,16,19,22,25,28,31]
>
>

--
-- When applied to a function without a list, it creates
-- another function that operates over lists because all
-- Haskell functions are curried by default.
--
--         f :: (a -> b)
--  map    :: (a -> b) -> [a] -> [b]
--
-- It can be seen as:
--
--  When map is applied to f, it will create the function fs
--  that take list of type a and returns list of type b.
--
--  map    :: (a -> b) -> ([a] -> [b])
--                |            |
--                |            |------ fs :: [a] -> [b]
--                |
--                -------------------- f  :: a -> b
--
> :t map
map :: (a -> b) -> [a] -> [b]

> let f x = 3 * x + 6
> :t f
f :: Num a => a -> a
>

> map f [1, 2, 3]
[9,12,15]
>

-- Note: let is only needed in the REPL
--
> let fs = map f

> :t fs
fs :: [Integer] -> [Integer]

> fs [1, 2, 3]
[9,12,15]
>
```
3. Map in Scala

In Scala the higher order function map is encoded as a higher order method, a method that accept a function as argument. Many Scala's data structures, also known as collections, provide the method .map to apply a function to its elements.

Examples:

```scala> List(1, 2, 3, 4, 5).map(x => x * 3)
res0: List[Int] = List(3, 6, 9, 12, 15)

scala> Array(1, 2, 3, 4, 5).map(x => x * 3)
res1: Array[Int] = Array(3, 6, 9, 12, 15)

// Dictionary or Hash map
//
scala> val dict =  Map("x" -> 1,  "y" -> 2,  "z" -> 3)
dict: scala.collection.immutable.Map[String,Int] = Map(x -> 1, y -> 2, z -> 3)

scala> dict("x")
res7: Int = 1

scala> dict("y")
res8: Int = 2

scala> dict.map{ case (k, v) => (k, v * 3) }
res9: scala.collection.immutable.Map[String,Int] = Map(x -> 3, y -> 6, z -> 9)

scala> dict2("z")
res10: Int = 9

scala> dict2("x")
res11: Int = 3
```
4. Map in Dynamically Typed Languages

In dynamic typed languages like Python, Clojure and Scheme the function map can take multiple arguments. In typed languages the function takes only one argument.

Map in Python:

```>>> list(map (lambda a, b, c: 100 * a + 10 * b + c, [1, 2, 3, 4, 5], [8, 9, 10, 11, 12], [3, 4, 7, 8, 10]))
[183, 294, 407, 518, 630]
>>>
```

Map in Scheme:

```(map (lambda (a b c) (+ (* 100 a) (* 10 b) c))
'(1 2 3 4 5)
'(8 9 10 11 12)
'(3 4 7 8 10))

\$1 = (183 294 407 518 630)
```

Map in Clojure:

```;; f a b c = 100 * a + 10 * b + c
;;
;; 183 = f 1 8 3
;; 294 = f 2 9 4
;; ...
;; 630 = f 6 3 0
;;
user=> (map (fn [a b c] (+ (* 100 a) (* 10 b) c)) [1 2 3 4 5] [8 9 10 11 12] [3 4 7 8 10])
(183 294 407 518 630)
user=>

;;
;; The Clojure map is Polymorphic it can be applied to any collection
;; of seq abstraction like lists, vectors and hash maps.
;;

;; Map applied to a list
;;
user=> (map inc '(1 2 3 4 5 6))
(2 3 4 5 6 7)
user=>

;; Map applied to a vector
;;
user=> (map inc [1 2 3 4 5 6])
(2 3 4 5 6 7)
user=>

;; Map applied to a hash map
;;
user=> (map identity {:a 10 :b 20 :c "hello world"})
([:a 10] [:b 20] [:c "hello world"])
user=>

;; The function mapv is similar to map, but returns a vector:
;;
user=> (mapv identity {:a 10 :b 20 :c "hello world"})
[[:a 10] [:b 20] [:c "hello world"]]
user=>

;; Clojure also has destructuring
;;
user=> (map (fn [[[a b] c]] (+ (* 100 a ) (* 10 b) c))  [[[1 2] 3] [[3 4] 5] [[1 2] 4]])
(123 345 124)
user=>
```
5. Map in Python

In Python 3 map and filter are lazy evaluated, they return a generator.

```>>> def fun1 (x):
return 3*x + 6
...
>>> g = map(fun1, [1, 2, 3])
>>> g
<map object at 0xb6b4a76c>
>>> next (g)
9
>>> next (g)
12
>>> next (g)
15
>>> next (g)
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
StopIteration
>>> g
<map object at 0xb6b4a76c>
>>>

# Force the evaluation:
#
>>> list(map(fun1, [1, 2, 3]))
[9, 12, 15]

# Strict Version of map
#
# s_ stands for strict map.

def s_map (f, xs):
return list(map(f, xs))

>>> s_map (fun1, [1, 2, 3])
[9, 12, 15]
>>>

# As python doesn't have tail call optimization
# therefore recursion must be avoided because
# a big number of function calls
# can lead to stack overflow.

def strict_map (f, xs):
return [f (x) for x in xs]

>>> strict_map (fun1, [1, 2, 3])
[9, 12, 15]
>>> strict_map (fun1, range(5))
[6, 9, 12, 15, 18]
>>>

# Lazy map implementation:
# Note: the python native map is implemented in C, so
# it is faster.
#

def lazy_map (f, xs):
for x in xs:
yield x

>>> g = lazy_map (fun1, [1, 2, 3])
>>> next(g)
1
>>> next(g)
2
>>> next(g)
3
>>> next(g)
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
StopIteration
>>> list(lazy_map (fun1, [1, 2, 3]))
[1, 2, 3]
>>>

#
# In order for the map function work in the same way
# as Haskell and ML it is must be curried.
#

curry2 = lambda f: lambda x: lambda y: f(x, y)

# The function curry2 currify a function of two arguments
#
>>> strict_map_c = curry2(strict_map)

>>> strict_map_c(fun1)
<function <lambda>.<locals>.<lambda>.<locals>.<lambda> at 0xb6afc0bc>

>>> strict_map_c(fun1)([1, 2, 3, 4])
[9, 12, 15, 18]
>>>

>>> fun1_xs = strict_map_c(fun1)
>>> fun1_xs ([1, 2, 3, 4])
[9, 12, 15, 18]
>>>
```

#### 1.8.3 Filter

Python

``` ;;; Filter returns by default a
>>> g = filter (lambda x: x > 10, [1, 20, 3, 40, 4, 14, 8])
>>> g
<filter object at 0xb6b4a58c>
>>> [x for x in g]
[20, 40, 14]
>>> [x for x in g]
[]
>>> list(filter (lambda x: x > 10, [1, 20, 3, 40, 4, 14, 8]))
[20, 40, 14]
>>>

# Strict Version of the filter function
#
>>> _filter = lambda f, xs: list(filter(f, xs))
>>>
>>> _filter (lambda x: x > 10,  [1, 20, 3, 40, 4, 14, 8])
[20, 40, 14]
>>>

# Filter implementation without recursion:
#

def strict_filter (f, xs):
result = []
for x in xs:
if f(x):
result.append(x)
return result

def lazy_filter (f, xs):
for x in xs:
if f(x):
yield x

>>> strict_filter (lambda x: x > 10, [1, 20, 3, 40, 4, 14, 8])
[20, 40, 14]

>>> lazy_filter (lambda x: x > 10, [1, 20, 3, 40, 4, 14, 8])
<generator object lazy_filter at 0xb6b0f1bc>

>>> g = lazy_filter (lambda x: x > 10, [1, 20, 3, 40, 4, 14, 8])
>>> g
<generator object lazy_filter at 0xb6b0f194>
>>> next(g)
20
>>> next(g)
40
>>> next(g)
14
>>> next(g)
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
StopIteration
>>>

>>> list(lazy_filter (lambda x: x > 10, [1, 20, 3, 40, 4, 14, 8]))
[20, 40, 14]
>>>
```

#### 1.8.4 Reduce or Fold

##### 1.8.4.1 Overview

The function fold or reduce is one of the most important higher order functions as it can be used to implement many other higher order functions, eliminate recursion and operate over many data structures or collections.

Fold Left

The function fold left is tail recursive, whereas the function fold right is not. This functions is also known as reduce or inject (in Ruby). The function fold left is often called just fold like in F# or reduce (Python, Javascript, Clojure) and also Inject (Ruby).

`foldl :: (State -> x -> State) -> State -> [x] -> State` `foldl (f :: S -> x -> S) S [x]`

```Sn = foldl f S0 [x0, x1, x2, x3 ... xn-1]

S1   = f S0 x0
S2   = f S1 x1     = f (f S0 x0) x1
S3   = f S2 x2     = f (f (f S0 x0) x1) x2
S4   = f S3 x3     = f (f (f (f S0 x0) x1) x2) x3
...
Sn-1 = f Sn-2 Xn-2 = ...
Sn   = f Sn-1 Xn-1 = f ...(f (f (f (f S0 x0) x1) x2) x3 ... xn

;;; -> Result
```

Fold Right

`foldr :: (x -> acc -> acc) -> acc -> [x] -> acc`

```S1   = f xn-1 S0
S2   = f xn-2 S1     = f xn-2 (f xn-1 S0)
S3   = f xn-3 S2     = f xn-3 (f xn-2 (f xn-1 S0))
S4   = f xn-4 S3     = f xn-4 (f xn-3 (f xn-2 (f xn-1 S0)))
....
Sn-1 = f x1   Sn-2   = ...
Sn   = f x0   Sn-1   = f x0 (f x1 ... (f xn-2 (f xn-1 S0)))
```

Fold Left:

```foldl :: (acc -> x -> acc) -> acc -> [x] -> acc

|             |      |       |
|             |      |       |---> Returns the accumulated
|             |      |             value
|             |      |----- xs
|             |
|             |     Inital Value of accumulator
|             |---  acc0
|
|-----------------  f :: acc -> x -> acc
|
|--- Element of list

foldl :: (b -> a -> b) -> b -> [a] -> b
foldl f z []     = z
foldl f z (x:xs) = foldl f (f z x) xs
```
```> :t foldl
foldl :: (a -> b -> a) -> a -> [b] -> a
>
> foldl (\acc x -> 10 * acc + x) 0 [1, 2, 3, 4, 5]
12345
>
```

It is equivalent to:

```> let f acc x = 10 * acc + x
>
> (f 0 1)
1
> (f (f 0 1) 2)
12
> (f (f (f 0 1) 2) 3)
123
>
> (f (f (f (f 0 1) 2) 3) 4)
1234
> (f (f (f (f (f 0 1) 2) 3) 4) 5)
12345
>
```

Evaluation of Fold left:

```> foldl (\acc x -> 10 * acc + x ) 0 [1, 2, 3, 4, 5]
12345

S0 = 0

f = \acc x -> 10 * acc + x

x  acc
S1 = f S0 x0 = f 0   1 = 10 * 0  + 1 = 1
S2 = f S1 x1 = f 10  2 = 10 * 1    + 2 = 12
S3 = f S2 x2 = f 12  3 = 10 * 12   + 3 = 123
S4 = f S3 x3 = f 123 4 = 10 * 123  + 4 = 1234
S5 = f S3 x3 = f 123 4 = 10 * 1234 + 5 = 12345
```

Fold right

```foldr :: (x -> acc -> acc) -> acc -> [x] -> acc

foldr :: (a -> b -> b) -> b -> [a] -> b
foldr f z []     = z
foldr f z (x:xs) = f x (foldr f z xs)
```
```> foldr (\x acc -> 10 * acc + x) 0 [1, 2, 3, 4, 5]
54321

> (f 0 5)
5
> (f (f 0 5) 4)
54
> (f (f (f 0 5) 4) 3)
543
> (f (f (f (f 0 5) 4) 3) 2)
5432
> (f (f (f (f (f 0 5) 4) 3) 2) 1)
54321
>

--
-- Derive fold_right from foldl (fold left)
--

> let fold_right f acc xs = foldl (\x acc -> f acc x) acc (reverse xs)
>
> :t fold_right
fold_right :: (b -> a -> a) -> a -> [b] -> a
>
>
> fold_right (\x acc -> 10 * acc + x) 0 [1, 2, 3, 4, 5]
54321
>
```

Evaluation of Fold Right:

```Example:

> foldr (\x acc -> 10 * acc + x ) 0 [1, 2, 3, 4, 5]
54321
>

f  = \x acc -> 10 * acc + x
S0 = 0
n = 5
x acc
S1   = f x4 S0     = f 5  0    = 10 * 0    + 5 = 5
S2   = f x3 S1     = f 4  5    = 10 * 5    + 4 = 54
S3   = f x2 S2     = f 3  54   = 10 * 54   + 3 = 543
S4   = f x1 S3     = f 2  543  = 10 * 543  + 2 = 5432
S5   = f x0 S4     = f 1  5432 = 10 * 5432 + 1 = 54321
```
##### 1.8.4.3 F# Fsharp
```// Fold left for Lists
//
//

// List.fold (acc -> 'x -> 'acc) -> acc -> 'x list -> 'acc
//
- List.fold ;;
val it : (('a -> 'b -> 'a) -> 'a -> 'b list -> 'a)

- List.fold (fun acc x -> 10 * acc + x) 0 [1; 2; 3; 4; 5]  ;;
val it : int = 12345
>

// Array.fold
//
//
- Array.fold ;;
val it : (('a -> 'b -> 'a) -> 'a -> 'b [] -> 'a)
>

- Array.fold (fun acc x -> 10 * acc + x) 0 [| 1; 2; 3; 4; 5 |]  ;;
val it : int = 12345
>

// Fold left for Arrays
```

Example: Implementing Higher Order Functions and recursive functions with fold.

```// Implementing fold_left for lists
//
let rec fold_left f xs acc =
match xs with
| []      ->   acc
| hd::tl  ->   fold_left f tl (f acc hd)
;;

val fold_left : f:('a -> 'b -> 'a) -> xs:'b list -> acc:'a -> 'a

- fold_left (fun acc x -> 10 * acc + x) [1; 2; 3; 4 ; 5] 0 ;;
val it : int = 12345
>

let length xs = fold_left (fun acc x -> acc + 1) xs 0

> length ["a"; "b"; "c"; "d" ] ;;
val it : int = 4
> length [ ] ;;
val it : int = 0
>

- let sum xs  = fold_left (fun acc x -> acc + x) xs 0 ;;

> sum [1; 2; 3; 4; 5; 6] ;;
val it : int = 21
>

> let product xs = fold_left (fun acc x -> acc * x) xs 1 ;;

val product : xs:int list -> int

> product [1; 2; 3; 4; 5; 6] ;;
val it : int = 720
>

- let reverse xs = fold_left (fun acc x -> x :: acc) xs []
- ;;

val reverse : xs:'a list -> 'a list

> reverse [1; 2; 3; 4; 5 ] ;;
val it : int list = [5; 4; 3; 2; 1]
>

let fold_right f xs acc =
fold_left (fun acc x -> f x acc) (reverse xs) acc
;;

val fold_right : f:('a -> 'b -> 'b) -> xs:'a list -> acc:'b -> 'b

- fold_right (fun x acc -> 10 * acc + x) [1; 2; 3; 4; 5] 0 ;;
val it : int = 54321
>

// Reverse map
//
- let rev_map f xs = fold_left (fun acc x -> (f x)::acc) xs [] ;;

val rev_map : f:('a -> 'b) -> xs:'a list -> 'b list

- rev_map (fun x -> x * 2) [1; 2; 3; 4; 5; 6] ;;
val it : int list = [12; 10; 8; 6; 4; 2]
>

- let map f xs = reverse ( fold_left (fun acc x -> (f x)::acc) xs [] ) ;;

val map : f:('a -> 'b) -> xs:'a list -> 'b list

- map (fun x -> x * 2) [1; 2; 3; 4; 5; 6] ;;
val it : int list = [2; 4; 6; 8; 10; 12]
>

// Or
//
let rev_fold_left f  xs acc = reverse (fold_left f xs acc) ;;

val rev_fold_left :
f:('a list -> 'b -> 'a list) -> xs:'b list -> acc:'a list -> 'a list

// Map with fold left and reverse
//
//
> let map f xs = rev_fold_left (fun acc x -> (f x)::acc) xs [] ;;

val map : f:('a -> 'b) -> xs:'b list -> 'b list

- map (fun x -> x * 2) [1; 2; 3; 4; 5; 6] ;;
val it : int list = [2; 4; 6; 8; 10; 12]
>

// Map with fold right
//
> let map f xs = fold_right (fun x acc -> (f x)::acc) xs [] ;;

val map : f:('a -> 'b) -> xs:'a list -> 'b list

> map (fun x -> x * 2) [1; 2; 3; 4; 5; 6] ;;
val it : int list = [2; 4; 6; 8; 10; 12]
>

// Filter with fold left and reverse
//
let filter f xs = rev_fold_left (fun acc x -> if (f x) then (x::acc) else acc) xs [] ;;

val filter : f:('a -> bool) -> xs:'a list -> 'a list

- filter (fun x -> x % 2 = 0) [1; 2; 3; 4; 5; 6; 7; 8; 9 ] ;;
val it : int list = [2; 4; 6; 8]
>

// Filter with fold right
//
let filter f xs =
fold_right (fun x acc ->  if (f x)
then x::acc
else acc
)
xs
[]
;;

-  filter (fun x -> x % 2 = 0) [1; 2; 3; 4; 5; 6; 7; 8; 9 ] ;;
val it : int list = [2; 4; 6; 8]
>

let take n xs =
let _, result =
fold_left (fun acc x -> let (c, xss) = acc in
if c = 0
then  (0, xss)
else  (c - 1, x::xss))
xs
(n, [])

in reverse result

;;

- take ;;
val it : (int -> 'a list -> 'a list) = <fun:clo@202-3>
>

> take 3 [1; 2; 3 ; 4; 5; 6; 7; 8] ;;
val it : int list = [1; 2; 3]
>

- take 18 [1; 2; 3 ; 4; 5; 6; 7; 8] ;;
val it : int list = [1; 2; 3; 4; 5; 6; 7; 8]
>

// drop with fold left
//
let drop n xs =
let _, result =
fold_left (fun acc x -> let (c, xss) = acc in
if c = 0
then  (0, x::xss)
else  (c - 1, xss))
xs
(n, [])

in reverse result

;;

val drop : n:int -> xs:'a list -> 'a list

- drop 3 [1; 2; 3 ; 4; 5; 6; 7; 8] ;;
val it : int list = [4; 5; 6; 7; 8]
>
- drop 13 [1; 2; 3 ; 4; 5; 6; 7; 8] ;;
val it : int list = []
>

let take_while f xs =
fold_right   (fun x acc ->  if (f x)
then  x::acc
else  acc )

xs
[]
;;

let take_while f xs =
fold_right   (fun x acc ->  if (f x)
then  x::acc
else  match acc with
|  []     -> []
|  _::tl -> tl
)

xs
[]
;;
val take_while : f:('a -> bool) -> xs:'a list -> 'a list

> take_while (fun x -> x < 10) [2; 8 ; 9 ; 26 ; 7; 10; 53] ;;
val it : int list = [2; 8; 9]
>

let find f xs =
fold_left (fun acc x -> if (f x)
then Some x
else None
)
xs
None
;;

val find : f:('a -> bool) -> xs:'a list -> 'a option

- find (fun x -> x * x > 40) [1; 2; 6; 5; 4; 8; 10; 20 ; 9 ] ;;
val it : int option = Some 9
>

- find (fun x -> x * x > 400) [1; 2; 6; 5; 4; 8; 10; 20 ; 9 ] ;;
val it : int option = None
>

// Map with side-effect
//
let for_each f xs =
fold_left (fun acc x -> f x)
xs
()
;;

val for_each : f:('a -> unit) -> xs:'a list -> unit

> for_each (fun x -> printfn "x = %d" x) [2; 3; 4; 5; 6] ;;
x = 2
x = 3
x = 4
x = 5
x = 6
val it : unit = ()
>

// Filter map - fusion / optimization
//
// (Eliminate intermediate data structure )
//

let filter_map f_filter f_map xs =
fold_right (fun x acc ->  if (f_filter x)
then (f_map x)::acc
else acc
)
xs
[]
;;

val filter_map :
f_filter:('a -> bool) -> f_map:('a -> 'b) -> xs:'a list -> 'b list

- filter_map (fun x -> x % 2 = 0) (fun x -> x + 3) [1; 5; 2; 6; 8; 7]
- ;;
val it : int list = [5; 9; 11]
>

// Without optimization
- map (fun x -> x + 3) (filter (fun x -> x % 2 = 0) [1; 5; 2; 6; 8; 7]) ;;
val it : int list = [5; 9; 11]
>
-
```
##### 1.8.4.4 Scala

In Scala, this function is encoded as a higher order method common to many collections.

```scala> List(1, 2, 3, 4, 5, 6).foldLeft(0)((acc, x) => 10 * acc + x)
res17: Int = 123456

scala> List(1, 2, 3, 4, 5, 6).foldRight(0)((x, acc) => 10 * acc + x)
res19: Int = 654321

scala> val files = new java.io.File("/").listFiles()
files: Array[java.io.File] = Array(/lost+found, /boot,  ...)

// Count the number of files in the root / *nix, Linux directory
//
scala> files.foldLeft(0)((acc, x) => acc + 1)
res21: Int = 22

// Dictionary Collection
//
scala> val dict = Map("x" -> 20.24, "y" -> 30.5, "z" -> 100.23)
dict: scala.collection.immutable.Map[String,Double] = Map(x -> 20.24, y -> 30.5, z -> 100.23)

/// Get the sum of hash table values
///
scala> dict.foldLeft(0.0){ case (acc, (k, v)) => acc + v }
res34: Double = 150.97

scala> 20.24 + 30.5 + 100.23
res36: Double = 150.97

/// Print hash table values
///
scala> dict.foldLeft(()){ case (acc, (k, v)) => println(v)}
20.24
30.5
100.23
```
##### 1.8.4.5 Python

In Python 3 the function reduce is not default anymore, however it can be found in the native library functools, that has a lot of built-in functions for functional programming. The function reduce is equivalent to Haskell function foldl (fold left) which is tail recursive.

```reduce(function, sequence[, initial]) -> value

reduce :: (acc -> x -> acc) -> [x] ?acc0  -> acc
```
```>>> from functools import reduce
>>>

>>> reduce (lambda acc, x: 10 *  acc + x , [1, 2, 3, 4, 5], 0)
12345
>>>

>>> f = lambda acc, x: 10 *  acc + x
>>>
>>> f(0, 1)
1
>>> f( f(0, 1), 2)
12
>>> f( f( f(0, 1), 2), 3)
123
>>> f( f( f( f(0, 1), 2), 3), 4)
1234
>>> f( f( f( f( f(0, 1), 2), 3), 4), 5)
12345
>>>

def my_reduce (f, xs, acc0=None):
"Non recursive implementation of reduce (fold_left)
with optional initial accumulator value.
"

if acc0 is None:
acc = xs
xss = xs[1:]
else:
acc = acc0
xss = xs

for x in xss:
acc = f (acc, x)

return acc

>>>
>>> my_reduce(lambda acc, x: 10 * acc + x, [1, 2, 3, 4, 5], 0)
12345
>>> my_reduce(lambda acc, x: 10 * acc + x, [1, 2, 3, 4, 5])
12345
>>> my_reduce(lambda acc, x:  acc + x, [1, 2, 3, 4, 5], 0)
15
>>> my_reduce(lambda acc, x:  acc * x, [1, 2, 3, 4, 5], 1)
120
>>>

#
# Implementation without recursion.
#

def fold_left (f_acc_x_to_acc, acc0, xs):

fold_left :: (acc -> x -> acc) -> acc -> [x]
"
acc = acc0

for x in xs:
acc = f_acc_x_to_acc (acc, x)

return acc

>>> fold_left (lambda acc, x: 10 * acc + x, 0, [1, 2, 3, 4, 5])
12345
>>>

def fold_right (f, acc0, xs):
return fold_left ((lambda acc, x: f(x, acc)), acc0, reversed(xs))

>>> fold_right (lambda x, acc: 10 * acc + x, 0, [1, 2, 3, 4, 5])
54321
>>>

def fold_right2 (f, acc0, xs):
acc = acc0

for x in reversed(xs):
acc = f(x, acc)

return acc

>>> fold_right2 (lambda x, acc: 10 * acc + x, 0, [1, 2, 3, 4, 5])
54321
>>>
```

Usefulness of Fold

Many functions and recursive algorithms can be implemented using the fold function, including map, filter, sum, product and others.

It is based in the paper:

In the paper was used fold right, here was used fold left.

```def fold_left (f_acc_x_to_acc, acc0, xs):

fold_left :: (acc -> x -> acc) -> acc -> [x]
"
acc = acc0

for x in xs:
acc = f_acc_x_to_acc (acc, x)

return acc

;;; Function fold in curried form

curry3 = lambda f: lambda x: lambda y: lambda z: f(x, y, z)

fold = curry3(fold_left)

>>> summation = fold(lambda acc, x: acc + x)(0)
>>>
>>> summation([1, 2, 3, 4, 5, 6])
21
>>>

>>> product = fold(lambda acc, x: acc * x)(1)
>>> product([1, 2, 3, 4, 5])
120
>>>

>>> f_or = fold(lambda acc, x: acc or x)(False)
>>> f_or([False, False, False])
False
>>>
>>> f_or([False, False, True])
True
>>>

>>> f_and = fold(lambda acc, x: acc and x)(True)
>>>
>>> f_and([False, True, True])
False
>>> f_and([True, True, True])
True
>>>

>>> length = fold(lambda acc, x: acc + 1)(0)
>>> length ([1, 2, 3, 4, 5])
5

>>> _map = lambda f, xs: fold(lambda acc, x: acc + [f(x)] )([])(xs)
>>> _map (lambda x: x * 3, [1, 2, 3, 4])
[3, 6, 9, 12]
>>>

>>> _filter = lambda p, xs: fold(lambda acc, x: (acc + [x]) if p(x) else  acc )([])(xs)
>>>
>>> _filter(lambda x: x > 10, [10, 3, 8, 2, 20, 30])
[20, 30]
>>>

#
# Function composition
#
#  (f3 (f2 (f1 (f0 x))))
#
#  (f3 . f2 . f1 . f0) x
#
#  or using, forward composition:
#
#  (f0 >> f2 >> f1 >> f0) x
#

>>> f1 = lambda x: 3 * x
>>> f2 = lambda x: 5 + x
>>> f3 = lambda x: 2 ** x

>>> _fcomp = lambda functions: lambda x: fold(lambda acc, f: f(acc)) (x) (functions)

>>> _fcomp([f1, f2, f3])(3)
16384

>>> (f3 (f2 (f1 (3))))
16384
>>>
```
##### 1.8.4.6 Clojure

The function reduce is similar to Haskell fold left and Python reduce. This function is Polymorphic. It works on any collection of seq abstraction: lists, vectors and hash maps.

Signature:

```(reduce f coll)      -> reduce :: (f :: acc -> x -> acc) -> [x]

Or

(reduce f val coll)  -> reduce :: (f :: acc -> x -> acc) -> acc -> [x]

f :: acc -> x -> acc
```
```;; Applying fold/reduce to a list
;;
;;
user=> (reduce (fn [acc x] (+ (* 10 acc) x)) 0 '(1 2 3 4 5))
12345

;; Applying fold/reduce to a vector
;;
user=> (reduce (fn [acc x] (+ (* 10 acc) x))  0 [1 2 3 4 5])
12345
user=>

user=> (reduce (fn [acc x] (+ (* 10 acc) x)) 0 [])
0

;; Applyind fold/reduce to a Hash map
;;
user=> (reduce (fn [acc x] (cons x  acc )) '()  { :a 10 :b 20 :c 30 })
([:c 30] [:b 20] [:a 10])
user=>

;; Without Initial value of accumulator it will fail on a empty list.
;;
user=> (reduce (fn [acc x] (+ (* 10 acc) x)) [1 2 3 4 5])
12345

user=> (reduce (fn [acc x] (+ (* 10 acc) x)) [])
ArityException Wrong number of args (0) passed to: user/eval44/fn--45  clojure.lang.AFn.throwArity (AFn.java:429)
user=>

;; Implementing fold right
;;
(defn foldr
([f xs]       (reduce (fn [acc x] (f x acc))     (reverse xs)))
([f acc xs]   (reduce (fn [acc x] (f x acc)) acc (reverse xs)))
)

user=> (foldr (fn [x acc] (+ (* 10 acc) x)) 0 [1 2 3 4 5])
54321

;; Clojure has destructuring
;;
user=> (reduce (fn [acc [a b]] (conj acc (+ (* 10 a) b) )) '[] [[1 2] [3 4] [5 8]] )
[12 34 58]
user=>

;; Implementing map with fold left (reduce)
;;
user=> (defn map2 [f xs]
(reverse (reduce (fn [acc x] (cons (f x) acc))
()
xs)))
#'user/map2
user=>
user=> (map2 inc '(1 2 3 3 4 5))
(2 3 4 4 5 6)
user=>

;; Implementing map with fold right
;;
;;

(defn map2 [f xs]
(foldr (fn [x acc] (cons (f x) acc))
()
xs
))

user=> (map2 inc '(1 2 3 4 5 6))
(2 3 4 5 6 7)
user=>
```

#### 1.8.5 For Each, Imperative map

##### 1.8.5.1 Overview

For each is an impure higher order function which performs side-effect on each element of a list, array or sequence. Unlike map this function neither have a standard name nor returns anything.

##### 1.8.5.2 Scheme
```> (for-each (lambda (i) (display i) (newline))  '(1 2 3 4 5 6))
1
2
3
4
5
6
>

> (for-each
(lambda (a b c)
(display a) (display b) (display c)
(newline)
)
'(a b c d e f)
'(1 2 3 4 5 6)
'("x" "y" "z" "w" "h" "k"))
a1x
b2y
c3z
d4w
e5h
f6k
```
```> import qualified Control.Monad as M

> :t M.mapM_
M.mapM_ :: Monad m => (a -> m b) -> [a] -> m ()
>

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

> M.mapM_ putStrLn ["string 0", "string 1", "string 2", "string 3"]
string 0
string 1
string 2
string 3
>

> M.mapM_ (\ x -> putStrLn (show x))  [1, 2, 3, 4, 5]
1
2
3
4
5
```
##### 1.8.5.4 Common Lisp
```> (mapc #'print '(1 2 3 3 4))

1
2
3
3
4
```
##### 1.8.5.5 Scala

In Scala, this the higher order function is encoded as method of many Scala's data structures or collections.

```// Collection List
//
scala> var xs = List(1.0, 2.0, 3.0, 4.0, 5.0, 6.0)
xs: List[Double] = List(1.0, 2.0, 3.0, 4.0, 5.0, 6.0)

scala> xs.foreach(println)
1.0
2.0
3.0
4.0
5.0
6.0

scala> xs.foreach(x => println( "x = %.3f".format(x)))
x = 1,000
x = 2,000
x = 3,000
x = 4,000
x = 5,000
x = 6,000

// Collection Map, Hash map, Hashtable or dictionary.
//
scala> val dict =  Map("x" -> 1,  "y" -> 2,  "z" -> 3)
dict: scala.collection.immutable.Map[String,Int] = Map(x -> 1, y -> 2, z -> 3)

scala> dict.foreach(println)
(x,1)
(y,2)
(z,3)

scala> dict.foreach{ case (k, v) => println(s"key = \$k, value = \$v") }
key = x, value = 1
key = y, value = 2
key = z, value = 3

// A more practical Scala example:
//
scala> val files = new java.io.File("/").listFiles()
files: Array[java.io.File] = Array(/lost+found, /boot, /run, ...)

scala> files.foreach(println)
/lost+found
/boot
/run
/usr
/etc
/sbin
/tmp
/mnt
... ... .... ..
```
##### 1.8.5.6 Ocaml
```> List.iter ;;
- : ('a -> unit) -> 'a list -> unit = <fun>

> List.iter (fun x -> print_int x ; print_string "\n") [1 ; 2; 3; 4; 5] ;;
1
2
3
4
5
- : unit = ()
```
##### 1.8.5.7 F# or FSharp
```> List.iter ;;
val it : (('a -> unit) -> 'a list -> unit) = <fun:clo@1>

> List.iter (fun x -> printfn "x = %d" x) [1; 2; 3; 4; 5] ;;
x = 1
x = 2
x = 3
x = 4
x = 5
val it : unit = ()
>

> List.iter2 ;;
val it : (('a -> 'b -> unit) -> 'a list -> 'b list -> unit) = <fun:clo@1>
>

- List.iter2 (fun a b -> printfn "a = %d b = %d" a b) [2; 3; 4; 5] [1; 2; 3; 4] - ;;
a = 2 b = 1
a = 3 b = 2
a = 4 b = 3
a = 5 b = 4
val it : unit = ()
>

- Array.iter ;;
val it : (('a -> unit) -> 'a [] -> unit) = <fun:it@6-4>
>
-

- Array.iter (fun x -> printfn "x = %d" x) [| 1; 2; 3; 4 |] ;;
x = 1
x = 2
x = 3
x = 4
val it : unit = ()
>
```
##### 1.8.5.8 Python

This function is not in Python standard library however, it can be defined as this.

```def for_each(f, * xss):
for xs in zip(* xss):
f(*xs)

>>> for_each (print, [1, 2, 4, 5, 6])
1
2
4
5
6

>>> for_each (lambda a, b: print (a, b), [1, 2, 3, 4, 5, 6], ["a", "b", "c", "d", "e", "f"])
1 a
2 b
3 c
4 d
5 e
6 f
```

Clojure

```user=> (defn f [a b] (println (format "a = %s , b = %s" a b)))
#'user/f

(defn for-each [f & xss]
(doseq [args (apply map vector xss)]  (apply f args)))

user=> (for-each println [1 2 3 4])
1
2
3
4
nil

user=> (for-each f [1 2 3 4] [3 4 5 6])
a = 1 , b = 3
a = 2 , b = 4
a = 3 , b = 5
a = 4 , b = 6
nil
user=>
```

#### 1.8.6 Apply

The function apply applies a function to a list or array of arguments. It is common in dynamic languages like Lisp, Scheme, Clojure, Javascript and Python.

Example:

Scheme

```> (define (f1 x y z) (+ (* 2 x) (* 3 y) z))

> (apply f1 '(1 2 3))
\$1 = 11

> (apply f1 1 2 '(3))
\$2 = 11

> (apply f1 1 '(2 3))
\$3 = 11

> (apply + '(1 2 3 4 5))
\$1 = 15

;;; The function apply can be used to transform a function of
;;; multiple arguments into a function of a single argument that
;;; takes a list of arguments
;;;

(define (f-apply f)
(lambda (xs) (apply f xs)))

> (map (f-apply f1) '((1 2 3) (3 4 5) (6 7 8)) )
\$2 = (11 23 41)

;;  It can be also used to create a function that  maps a function
;;  of multiple arguments over a list of arguments.
;;
(define (map-apply f xss)
(map (lambda (xs) (apply f xs)) xss))

> (map-apply f1  '((1 2 3) (3 4 5) (6 7 8)))
\$1 = (11 23 41)
```

Clojure

```user=> (defn f1 [x y z] (+ (* 2 x) (* 3 y) z))
#'user/f1
user=>

;; The higher order function apply is polymorphic.
;;
user=> (apply f1 '(1 2 3))
11
user=> (apply f1 [1 2 3])
11
user=> (apply f1 1 [2 3])
11
user=> (apply f1 1 2 [ 3])
11
user=> (apply f1 1 2 3 [ ])
11

user=> (apply + [1 2 3 4 5])
15

user=> (defn map-apply [f xss]
(map (fn [xs] (apply f xs)) xss))
#'user/map-apply
user=>

user=> (map-apply f1 [[1 2 3] [3 4 5] [6 7 8]])
(11 23 41)
user=>
```

Python

```# In Python the * asterisk notation is used to expand
# a list into function arguments.
#
>>> f1 = lambda x, y, z: 2 * x + 3 * y + z
>>>
>>> f1(1, 2, 3)
11
>>> f1(*[1, 2, 3])
11
>>>

>>> def apply (f, xs): return f(*xs)
...
>>>

>>> apply (f1, [1, 2, 3])
11

#
# The function apply can also be defined  as:
#

def apply2 (f, * args):
return f(*(tuple(args[:-1]) + tuple(args[-1])))

>>> apply2 (f1, [1, 2, 3])
11
>>> apply2 (f1, 1, [2, 3])
11
>>> apply2 (f1, 1, 2, )
11
>>> apply2 (f1, 1, 2, 3, [])
11
>>>

>>> f_apply = lambda f: lambda xs: f(*xs)
>>>

>>> list(map (f_apply(f1), [[1, 2, 3], [3, 4, 5], [6, 7, 8]]))
[11, 23, 41]
>>>

def map_apply (f, xss):
return map(lambda xs: f(*xs), xss)

>>> map_apply(f1, [[1, 2, 3], [3, 4, 5], [6, 7, 8]])
<map object at 0xb6daaaac>
>>>
>>> list(map_apply(f1, [[1, 2, 3], [3, 4, 5], [6, 7, 8]]))
[11, 23, 41]
>>>
```

### 1.9 Lazy Evaluation

#### 1.9.1 Overview

"Lazy evaluation" means that data structures are computed incrementally, as they are needed (so the trees never exist in memory all at once) parts that are never needed are never computed. Haskell uses lazy evaluation by default.

Benefits

• Avoid unecessary computations
• Infinite data structure
• Separate generation from consumption
• Control-flow structures can be defined as functions
• Cyclic programming
• Ability to use Functiosn as control structures
• Define control flow (structures) as abstractions instead of primitives

Drawbacks

• Hard to predict performance
• Hard to predict space leaks
• Difficult to predict when the memory is freed
• Can lead to space leaks (aka memory leak) if not used without care (see foldl).
```> let lazylist = [2..1000000000]
>
> let f x = x^6
>
> take 5 lazylist
[2,3,4,5,6]
>
>
> {- Only the terms needed are computed. -}
> take 5 ( map f lazylist )
[64,729,4096,15625,46656]
>
```

Example in Python:

• Python uses eager evaluation by default. In order to get lazy evaluation in python the programmer must use iterators or generators. The example below uses generator.
```def lazy_list():
""" Infinite list """
x = 0
while True:
x += 2
yield x

>>> gen = lazy_list()
>>> next(gen)
2
>>> next(gen)
4
>>> next(gen)
6
>>> next(gen)
8
>>> next(gen)
10
>>>

def take(n, iterable):
return [next(iterable) for i in range(n)]

def mapi(func, iterable):
while True:
yield func(next(iterable))

f = lambda x: x**5

>>> take(5, lazy_list())
[2, 4, 6, 8, 10]
>>> take(10, lazy_list())
[2, 4, 6, 8, 10, 12, 14, 16, 18, 20]
>>>

>>> take(5, mapi(f, lazy_list()))
[32, 1024, 7776, 32768, 100000]
>>>
>>> take(6, mapi(f, lazy_list()))
[32, 1024, 7776, 32768, 100000, 248832]
>>>
```

#### 1.9.2 Evaluation Strategy / Parameter Passing

##### 1.9.2.1 Call-by-value

Call-by-value (aka pass-by-value, eager evaluation, strict evaluation or applicative-order evaluation) Evaluation at the point of call, before the function application application. This evaluation strategy is used by most programming languages like Python, Scheme, Ocaml and others.

```let add2xy x y = x + x + y

add2xy (3 * 4) ( 2 + 3)
=  12 + 12 + 5
=  29
```

Example in Python:

```>>> def add(x, y):
...   sum = x + y
...   x = sum
...   return (x, sum)
...
>>>

>>> x = 10
>>> y = 20

# In call-by-value strategy. The function doesn't change its arguments.
#
(30, 30)

# They remain unchanged.
#
>>> x
10
>>> y
20

# Arguments are evaluated before the function invocation.
#
# add((10 + 20), (3 * 3))
# (39, 39)
#
>>> add((10 + 20),(3 * 3))
(39, 39)
>>>
>>> add((10 + 20),(3 / 0))
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
ZeroDivisionError: division by zero
>>>
```
##### 1.9.2.2 Call-by-name

Call-by-name (aka pass-by-name): It is a non-memoized lazy evaluation. Arguments are passed non evaluated, they are only evaluated when it is needed. The arguments are substituted in the function. This evaluation strategy can be inefficient when the arguments are evaluated many times.

Example:

```// Each use of x y and replaced in the function by (3 * 4) and (2 + 3)
// respectively. The arguments are evaluated after substituted
// in the function

let add2xy x y = x + x + y
let add2xy (3 * 4) (2 + 3)
= (3 * 4) + (3 * 4) + (2 + 3)
= 12 + 12 + 5
= 29
```

Call-by-name can be simulated using thunks (functions without arguments).

Example in Python:

```>>> def add2xy (x, y):
...     return x() + x() + y()
...
>>> add2xy (lambda : (3 * 4), lambda: (2 + 3))
29
>>>
```

Example in Scheme:

```>  (define (add2xy x y) (+ (x) (x) (y)))
>
;; The parameter is evaluated every time it is used.
;;
> (define (displayln msg)
(display msg)
(newline))

> (add2xy (lambda () (displayln "Eval x") (* 3 4))
(lambda () (displayln "Eval y") (+ 2 3))
)
Eval x
Eval x
Eval y
29
>
```
##### 1.9.2.3 Call-by-need

Call-by-need_ (aka lazy evaluation, non-strict evaluation or normal-order evaluation): Memoized lazy-evaluation. It is a memoized version of call-by-name, after its argument is evaluated, the values are stored for further computations. When the argument evaluation has no side-effects, in other words, always yields the same output when evaluated many times it produces the same result as call-by-name. This strategy is used in Haskell.

Example: In Haskell the parameters are not evaluated at the point they are passed to the function. They are only evaluated when needed.

```> let add_xy x y z = x + y
>
add_xy :: Num a => a -> a -> t -> a
>

>>> div 10 2
5
>>> div 10 0
*** Exception: divide by zero
>>>

-- The parameter z: (3 / 0) is not evaluated
-- because it is not needed.
--
> add_xy 3 4 (3 / 0)
7
>

>>> add_xy 3 4 (div 10 0)
7
>>>

-- sum [1 ..] is not evaluated.
-- If it were evaluated the computer would hang
-- or trow an arithmetic overflow exception
--
>>> add_xy 3 4 (sum [1 ..])
7
>>>

>>> add_xy 3 4 (div (sum [1 ..]) 0)
7
>>>

-- The infinite list is not fully evaluated
--
> let ones = 1:ones

> take 10 ones
[1,1,1,1,1,1,1,1,1,1]
>
> take 20 ones
[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]
>
```
##### 1.9.2.4 Call-by-reference
• Call-by-reference (aka pass-by-reference): The function changes the value of the argument. Supported in: C++, Pascal, Python Objects.

Example in C:

```// The function add10 changes it argument.
//
#include <stdio.h>

*x = *x + 10 ;
}

void main (){

int x = 5;
printf("x = %d\n", x);
}
```

Test:

```\$ gcc /tmp/test.c
\$ ./a.out
x = 15

\$ tcc -run /tmp/test.c
x = 15
```

#### 1.9.3 Lazy Evaluation implementation in strict languages

In strict languages with first-class function it is possible to implement lazy evaluation with "thunks" or function with no arguments wrapping an expression.

Example in F#.

```// Ordinary Value
//----------------------------------------
- let a = 1 + 2 + 3 + 5 + 5 ;;

val a : int = 16

// Lazy Value - implementation 1
//-----------------------------------------
- let b = fun () -> 1 + 2 + 3 + 4 + 5 ;;

val b : unit -> int

> b () ;; // Force evalution ;;
val it : int = 15
>

// Lazy Valye - Implementation 2
//-----------------------------------
-
- type Lazy<'T> = Lazy of (unit -> 'T) ;;

- let force (Lazy thunk) = thunk () ;
- ;;

val force : Lazy<'a> -> 'a

> let lazyValue = Lazy(fun () -> 1 + 2 + 3 + 5) ;;

val lazyValue : Lazy<int>

- force lazyValue ;;
val it : int = 11
>

- let lazyValue2 = Lazy(fun () -> 10 / 0 ) ;;

val lazyValue2 : Lazy<int>

> force lazyValue2 ;;
System.DivideByZeroException: Attempted to divide by zero.
at FSI_0021+lazyValue2@37.Invoke (Microsoft.FSharp.Core.Unit unitVar0) [0x00001] in <edb3af9a5a774c15bfbce9f877c6be59>:0
```

Lazy lists or streams like can implemented with thunks. All Haskell lists and expressions are lazy by default.

Example in F#.

```/// Almost equivalent to Haskell lists
type stream<'a> =
| Nil
| Cons of 'a * (unit -> stream<'a>)
;;

> let xs0 = Nil
;;
val xs0 : stream<'a>

> let xs1 = Cons(10, fun () -> Nil) ;;
;;
val xs1 : stream<int>

>

let xs2 = Cons(10, fun () -> Cons (20, fun () -> Nil))
;;
val xs2 : stream<int>

let toList (xs: stream<'a>) =
let rec aux acc xs =
match xs with
| Nil            -> List.rev acc
| Cons(a, thunk) -> aux (a::acc) (thunk())
aux [] xs
;;

val toList : xs:stream<'a> -> 'a list

- toList xs1 ;;
val it : int list = 
>

- toList xs2 ;;
val it : int list = [10; 20]
>

let take n (xs: stream<'a>) =
let rec aux acc xs n =
match (n, xs) with
| 0, _               ->  List.rev acc
| _, Nil             ->  List.rev acc
| k, Cons(a, thunk)  ->  aux (a::acc) (thunk()) (k - 1)
aux [] xs n
;;

val take : n:int -> xs:stream<'a> -> 'a list

let sumSt (xs: stream<int>) =
let rec aux acc xs =
match xs with
| Nil             -> acc
| Cons(a, thunk)  -> aux (acc + a) (thunk())
aux 0 xs
;;

val sumSt : xs:stream<int> -> int

let rec mapSt fn (xs: stream<'a>): stream<'b> =
match xs with
| Nil            -> Nil
| Cons(a, thunk) -> Cons(fn a, fun () -> mapSt fn (thunk()))
;;

let takeSt n (xs: stream<'a>) =
let rec aux n xs =
match n, xs with
| 0, _               -> Nil
| _, Nil             -> Nil
| k, Cons(a, thunk)  -> Cons(a, fun () -> aux (k - 1) (thunk()))
aux n xs
;;

val takeSt : n:int -> xs:stream<'a> -> stream<'a>

/// Create an infinite list/stream with some value
//
let rec repeat x = Cons (x, fun () -> repeat x)

val repeat : x:'a -> stream<'a>

> let ones = repeat 1 ;;

val ones : stream<int>

> take 3 ones ;;
val it : int list = [1; 1; 1]
>
- take 15 ones ;;
val it : int list = [1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1]
>

let numbers =
let rec aux n = Cons(n, fun () -> aux (n + 1))
aux 0
;;

> take 2 numbers ;;
val it : int list = [0; 1]
>
- take 12 numbers ;;
val it : int list = [0; 1; 2; 3; 4; 5; 6; 7; 8; 9; 10; 11]
>

- takeSt 5 numbers |> toList ;;
val it : int list = [0; 1; 2; 3; 4]
>
- takeSt 10 numbers |> toList ;;
val it : int list = [0; 1; 2; 3; 4; 5; 6; 7; 8; 9]
>

> takeSt 5 numbers |> sumSt ;;
val it : int = 10
>

- sumSt <| takeSt 5 numbers  ;;
val it : int = 10
>

> takeSt 10 numbers |> sumSt ;;
val it : int = 45

- numbers |> mapSt (fun x -> 3 * x + 4) |> takeSt 5 |> toList ;;
val it : int list = [4; 7; 10; 13; 16]
>

- numbers |> mapSt (fun x -> 3 * x + 4) |> takeSt 5 |> sumSt ;;
val it : int = 50
>

let rec unfold (fn: 'state -> ('output * 'state) option)  (state: 'state) : stream<'output>=
match fn state with
| None            -> Nil
| Some (out, st)  -> Cons(out, fun () -> unfold fn st)
;;

val unfold :
fn:('state -> ('output * 'state) option) -> state:'state -> stream<'output>

let naturals = unfold (fun s -> Some (s + 1, s + 1)) 0

- takeSt 10 naturals |> toList ;;
val it : int list = [1; 2; 3; 4; 5; 6; 7; 8; 9; 10]
>

let fibSerie = unfold (fun (an, an1) -> let next = an + an1 in Some (next, (an1, next))) (0, 1)

>
- fibSerie |> takeSt 10 |> toList ;;

val it : int list = [1; 2; 3; 5; 8; 13; 21; 34; 55; 89]
>

- fibSerie |> takeSt 20 |> sumSt ;;
val it : int = 28655
>
```

Lazy Evaluation in OCaml and Strams (Lazy Lists)

Lazy Evaluation in SML

Matlab

Misc

### 1.10 Terminology

#### 1.10.1 Predicates

Any function that returns a boolean value, true or false. It is often used as argument to higher order functions that perform selection, decision and filtering.

Example in Scala:

```// Some predicates

val isEven = (x: Int) => (x % 2) == 0

val isOdd = (x: Int) => (x % 2) != 0

scala> List(1, 2, 4, 5, 6, 7, 9, 10).filter(isOdd)
res1: List[Int] = List(1, 5, 7, 9)

scala> List(1, 2, 4, 5, 6, 7, 9, 10).filter(isEven)
res2: List[Int] = List(2, 4, 6, 10)

//  Example: traversing a directory.
//
import java.nio.file.{Files, Paths, Path}
import java.util.stream.{Stream => JStream}

def walkDirectory(path: String, pred: Path => Boolean)(action: Path => Unit) =
Files.walk(Paths.get(path))
.filter(p => pred(p))
.forEach(p => action(p))

// Sample predicates for directory navigation
//
scala> val isDirectory = (p: Path) => p.toFile.isDirectory()
isDirectory: java.nio.file.Path => Boolean = \$\$Lambda\$1387/1448675410@3562b3f

scala> val isFile = (p: Path) => p.toFile.isFile()
isFile: java.nio.file.Path => Boolean = \$\$Lambda\$1388/696602804@29ed425e

scala> val pAll = (p: Path) => true
pAll: java.nio.file.Path => Boolean = \$\$Lambda\$1393/1337725291@705ea29

scala> def hasExtension(ext: String) = (p: Path) => p.toFile.getName.endsWith(ext)
hasExtension: (ext: String)java.nio.file.Path => Boolean

// Print only directories
//
scala> walkDirectory("/boot", isDir){ println}
/boot
/boot/grub
/boot/grub/locale
/boot/grub/themes
/boot/grub/themes/starfield
/boot/grub/i386-pc
/boot/grub/fonts
/boot/memtest86+

// Print only files
//
scala> walkDirectory("/boot", isFile){ println}
/boot/initramfs-4.11-rt-x86_64-fallback.img
/boot/intel-ucode.img
/boot/linux316-x86_64.kver
/boot/vmlinuz-3.16-x86_64
/boot/grub/locale/zh_CN.mo
/boot/grub/locale/ru.mo
/boot/grub/locale/hu.mo
/boot/grub/locale/de@hebrew.mo
/boot/grub/locale/nl.mo
/boot/grub/locale/it.mo
... ... ... ... ... ... .. .

// Print all entries
//
scala> walkDirectory("/boot", pAll){ println}
/boot
/boot/initramfs-4.11-rt-x86_64-fallback.img
/boot/intel-ucode.img
/boot/linux316-x86_64.kver
/boot/vmlinuz-3.16-x86_64
/boot/grub
/boot/grub/locale
/boot/grub/locale/zh_CN.mo
/boot/grub/locale/ru.mo
/boot/grub/locale/hu.mo
/boot/grub/locale/de@hebrew.mo
/boot/grub/locale/nl.mo
/boot/grub/locale/it.mo
... ... ... ... ... ... .. .

// Print all files with a given extension
//
scala> walkDirectory("/boot", hasExtension(".img")) { file => println(s"file = \$file") }
file = /boot/initramfs-4.11-rt-x86_64-fallback.img
file = /boot/intel-ucode.img
file = /boot/grub/i386-pc/core.img
file = /boot/grub/i386-pc/boot.img
file = /boot/initramfs-3.16-x86_64-fallback.img
file = /boot/initramfs-4.9-x86_64-fallback.img
file = /boot/initramfs-3.16-x86_64.img
file = /boot/initramfs-4.9-x86_64.img
file = /boot/initramfs-4.11-rt-x86_64.img

scala> walkDirectory("/boot", hasExtension(".png")) { file => println(s"file = \$file") }
file = /boot/grub/themes/starfield/terminal_box_n.png
file = /boot/grub/themes/starfield/slider_c.png
file = /boot/grub/themes/starfield/starfield.png
file = /boot/grub/themes/starfield/terminal_box_nw.png
... ... ... ... ... ... ... ... ...
```

#### 1.10.2 Thunks

A thunk is a function without any arguments that is used to delay the execution of some expression or action. Thunks allows to create higher order functions that works as control structures.

Example in Scala:

In the example below, the function doTimes has a thunk as the second argument and executes the thunk function n times.

```def doTimes(n: Int, fn: () => Unit) =
for(i <- 1 to n) fn()

// Thunk:
//
// It delays the execution of the <<expression>>
// () => <<expression>>
//
scala> val thunk1 = () => println("Functional programming is awesome!")
thunk1: () => Unit = \$\$Lambda\$1470/249666914@79d07834

scala> doTimes(5, thunk1)
Functional programming is awesome!
Functional programming is awesome!
Functional programming is awesome!
Functional programming is awesome!
Functional programming is awesome

scala> doTimes(5, () => println("Functional programming is awesome!"))
Functional programming is awesome!
Functional programming is awesome!
Functional programming is awesome!
Functional programming is awesome!
Functional programming is awesome!

def doIf[A](ifTrueFn: () => Unit, ifFalseFn: () => Unit) =
(flag: Boolean) => if(flag)
ifTrueFn()
else
ifFalseFn()

scala> val action = doIf(() => println("Received true"), () => println("Received false"))
action: Boolean => Unit = \$\$Lambda\$1461/1941122645@3d400897

scala> action(true)

scala> action(false)

```

#### 1.10.3 Identity Function

The identity function is a polymorphic function which returns the value of its argument.

``` -- This is a built-in Haskell function
> :t id
id :: a -> a
>

> id 10
10
> id (Just 100)
Just 100
>
> let identity x = x
> identity 200
200
>
```

#### 1.10.4 Constant Function

The constant function returns the value of the first argument (the constant) regardless of the value of second argument.

```> :t const
const :: a -> b -> a

> let const10 = const 10
> const10 100
10
> const10 300
10
> map const10 ["a", "b", "c", "d"]
[10,10,10,10]
>
```

Python Implementation:

```>>> constant = lambda const: lambda x: const
>>>

>>> const10 = constant(10)
>>>
>>> const10(100)
10
>>> const10("hello world")
10
>>>
```

#### 1.10.5 Combinators

A combinator are a set of primitive functions, operatores and higher order functions that can be combined in order to create more complex functions out of simple functions. Combinators are widespread in Haskell and one of the most famous case is Parsec the parser combinator libraries which provides parser combinator functions which allows the user build more complex parsers out of primitive parsers.

Combinators can be used to build EDSL - Embedded Domain Specific languages which are Domain Specific Language embedded in a host language or basically a library with convenient names and syntax that fits the problem domain. Parsec can be regarded as an EDSL to build parsers.

"One of the distinguishing features of functional programming is the widespread use of combinators to construct programs. A combinator is a function which builds program fragments from program fragments; in a sense the programmer using combinators constructs much of the desired program automatically, rather that writing every detail by hand."

• Function combinators
• id - Identity function
• const - Constant function
• (.) - Function composition
• (\$) - Function application
• flip f a b = f b a
• List processing functions: map, filter, zip, fold
• return, (>>=), >=> …
• Control.Monad (mapM, mapM_, forM, forM, liftM, liftM2)
• Parsec - Parser combinator library which provides higher order functions, operators and primitive functions (primitive parsers) that combined to build more complex parsers.
• Lava - Combinator library for digital circuits description and simulatioin – https://archive.alvb.in/msc/thesis/reading/lava-1999.pdf

Combinators building blocks:

• Primitive functions
• Higher order functions
• Algebraic data types
• Custom binary operators

References:

### 1.11 Special Functions

#### 1.11.1 List Constructor (Cons)

The cons operator is widely used in list recursive functions and higher order functions that operates on lists.

Scheme:

```> (cons 1 (cons 2 (cons 3 (cons 4 '()))))
(1 2 3 4)
```

``` -- Cons Operator
--
> :t (:)
(:) :: a -> [a] -> [a]

> 1:[]


> 1:2:3:4:[]
[1,2,3,4]

> let cons = (:)

> (cons 1 (cons 2 (cons 3 (cons 4 []))))
[1,2,3,4]
```

Ocaml and F#

```> 1::[] ;;
val it : int list = 
>
- 1::2::3::[] ;;
val it : int list = [1; 2; 3]
>

- let cons x xs = x::xs ;;

val cons : x:'a -> xs:'a list -> 'a list

cons 1 (cons 2 (cons 3 (cons 4 []))) ;;

> cons 1 (cons 2 (cons 3 (cons 4 []))) ;;
val it : int list = [1; 2; 3; 4]
>
```

#### 1.11.2 Zip

##### 1.11.2.1 Overview

The function zip and its variants combine two or more sequence into one sequence.

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

> zip [1, 2, 3, 4] ["a", "b", "c"]
[(1,"a"),(2,"b"),(3,"c")]
>

> zip [1, 2, 3, 4] ["a", "b", "c"]
[(1,"a"),(2,"b"),(3,"c")]
>

-- Zip a list and a infinite list

> zip ["a", "b", "c"] [1 ..]
[("a",1),("b",2),("c",3)]
>
>

> zip ["a", "b", "c", "d"] [1, 2, 3]
[("a",1),("b",2),("c",3)]
>

> :t zip3
zip3 :: [a] -> [b] -> [c] -> [(a, b, c)]
>

> zip3 ["a", "b", "c", "d"] [1, 2, 3, 4, 5, 6] [Just 10, Just 100, Nothing]
[("a",1,Just 10),("b",2,Just 100),("c",3,Nothing)]
>

-- There is more zip functions in the module Data.List
--
> import Data.List (zip4, zip5, zip6)
>

> :t zip4
zip4 :: [a] -> [b] -> [c] -> [d] -> [(a, b, c, d)]
>
> :t zip5
zip5 :: [a] -> [b] -> [c] -> [d] -> [e] -> [(a, b, c, d, e)]
>
```
##### 1.11.2.3 Zip in Python

The Python zip function is inspired by Haskell. The Python zip functions can take a variable number of arguments.

Python 2: In python2 this function is evaluated eagerly.

```>>> zip([1, 2, 3], ["a", "b", "c", "d", "e"])
[(1, 'a'), (2, 'b'), (3, 'c')]
>>>

>>> zip([1, 2, 3], ["a", "b", "c", "d", "e"], ["x", "y", "z"])
[(1, 'a', 'x'), (2, 'b', 'y'), (3, 'c', 'z')]
>>>

>>> zip([1, 2, 3], ["a", "b", "c", "d", "e"], ["x", "y", "z"], range(1, 20))
[(1, 'a', 'x', 1), (2, 'b', 'y', 2), (3, 'c', 'z', 3)]
>>>

>>> for x, y in zip([1, 2, 3, 4, 5], ["a", "b", "c", "d", "e"]):
...   print "x = ", x, "y = ", y
...
x =  1 y =  a
x =  2 y =  b
x =  3 y =  c
x =  4 y =  d
x =  5 y =  e
```

Python 3: In python3 this function returns a generator. It is evaluated lazily.

```>>> zip([1, 2, 3, 4, 5], ["a", "b", "c", "d", "e"])
<zip object at 0xb6d01ecc>
>>>

>>> list(zip([1, 2, 3, 4, 5], ["a", "b", "c", "d", "e"]))
[(1, 'a'), (2, 'b'), (3, 'c'), (4, 'd'), (5, 'e')]
>>>

>>> g = zip([1, 2, 3, 4, 5], ["a", "b", "c", "d", "e"])
>>> g
<zip object at 0xb6747e8c>
>>> next(g)
(1, 'a')
>>> next(g)
(2, 'b')
>>> next(g)
(3, 'c')
>>> next(g)
(4, 'd')
>>> next(g)
(5, 'e')
>>> next(g)
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
StopIteration
>>>

>>> g = zip([1, 2, 3, 4, 5], ["a", "b", "c", "d", "e"], range(1, 1000000000))
>>> g
<zip object at 0xb6747f2c>
>>> list(g)
[(1, 'a', 1), (2, 'b', 2), (3, 'c', 3), (4, 'd', 4), (5, 'e', 5)]
>>> list(g)
[]
>>>

>>> for x, y in zip([1, 2, 3, 4, 5], ["a", "b", "c", "d", "e"]):
...    print ("x = ", x, "y = ", y)
...
x =  1 y =  a
x =  2 y =  b
x =  3 y =  c
x =  4 y =  d
x =  5 y =  e
```
##### 1.11.2.4 Zip in Scheme

It can be defined as:

```(define (zip . lists)
(apply map  vector lists))

> (zip '(1 2 3 4) '("a" "b" "c" "d"))
(#(1 "a") #(2 "b") #(3 "c") #(4 "d"))
>

;; Or

(define (zip . lists)
(apply map  list lists))

> (zip '(1 2 3 4) '("a" "b" "c" "d"))
((1 "a") (2 "b") (3 "c") (4 "d"))
>

> (zip '(1 2 3 4) '("a" "b" "c" "d") '(89 199 100 43))
((1 "a" 89) (2 "b" 199) (3 "c" 100) (4 "d" 43))
>
```
##### 1.11.2.5 Zip in Clojure
```;; Zip returning list
;;
(defn zip [& seqs]
(apply map list seqs))

user=> (zip '(1 2 3 4 5) '(x y z w k m n))
((1 x) (2 y) (3 z) (4 w) (5 k))

user=> (zip '(1 2 3 4 5) '(x y z w k m n) (range 10 1000000))
((1 x 10) (2 y 11) (3 z 12) (4 w 13) (5 k 14))

user=> (zip '[1 2 3 4 5] '(x y z w k m n) (range 10 1000000))
((1 x 10) (2 y 11) (3 z 12) (4 w 13) (5 k 14))

user=> (zip '[1 2 3 4 5] '(x y z w k m n) {:key_x "hello" :key_y "world" :key_z "clojure"})
((1 x [:key_x "hello"]) (2 y [:key_y "world"]) (3 z [:key_z "clojure"]))
user=>

;; Zip returning vector
;;
(defn zipv [& seqs]
(apply mapv vector seqs))

user=> (zipv '(1 2 3 4 5) '(x y z w k m n))
[[1 x] [2 y] [3 z] [4 w] [5 k]]
user=>

user=>  (zipv '[1 2 3 4 5] '(x y z w k m n) (range 10 1000000))
[[1 x 10] [2 y 11] [3 z 12] [4 w 13] [5 k 14]]
user=>
```

### 1.12 Function Composition

#### 1.12.1 Overview

Function composition promotes shorter code, code reuse and higher modularity by creating new functions from previous defined ones. They also allow optimization of functional code when there is many maps. Only pure functions can be composed, function composition works like math functions, the output of one function is the input of another function. Haskell, ML, Ocaml and F# has features that makes easier to use function composition, like a lightweight syntax, currying, partially applied functions, static typing and composition operators that are built in to the language. In Haskell the operator (.) dot is used for composing functions.

#### 1.12.2 Function Composition in Haskell

```(.) :: (b -> c) -> (a -> b) -> a -> c

Given:

f :: b -> c
g :: a -> b

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

h = f . g
h :: a -> c
```

Function Composition Block Diagram

```                f . g
................................
. /------\        /------\     .
a -->   . |  g   |  -->   |  f   | --> .---> c
. \------/   b    \------/  c  .
................................
g :: a -> b   f :: b -> c

(.) :: (b -> c) -> (a -> b) -> a -> c
```

Composition Law

```id . f = f                  Left  identity law
f . id = f                  Right identity law
(f . g) . h = f . (g . h)   Associativity

Constant Function Composition
f       . const a = const (f a)
const a . f       = const a

dentity function            -->  id x = x
const - Constant Function   --> const a b =  a
```

Simplifying Code with function composition:

```    h( f ( g( x)))  ==>  (h . f . g ) x   OR  h . f . g  \$ x
OR
h \$ f \$ g x     ==>   h . f . g \$ x

Point Free Style
composed x = h . f . g \$ x ==>   composed = h . f . g
```

Function Composition with Map

```    (map g (map f xs) == (map g . map f) xs = (map g . f) xs

OR
map g . map f  == map (g . f)

Generalizing

map f1 (map f2 (map f3 (map f4 xs)))
= (map f1)
=  map (f1 . f2 . f3 . f4)  xs
=  f xs

Where f = map \$ f1 . f2 . f3 . f4

Example:

> map  (+3) [1, 2, 3, 4]
[4,5,6,7]
> map  (*2) [4, 5, 6, 7]
[8,10,12,14]
>
> map  (*2) (map (+3)  [1, 2, 3, 4])
[8,10,12,14]
>
> map  (*2) . map (+3) \$  [1, 2, 3, 4]
[8,10,12,14]
>

> map ((*2) . (+3)) [1, 2, 3, 4]
[8,10,12,14]

> let f = map \$ (*2) . (+3)
> f [1, 2, 3, 4]
[8,10,12,14]
```
```h :: c -> [a]
f :: a -> b

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

map     f (h c) = map    f . h \$ c
filter  f (h c) = filter f . h \$ c
```

Inverting Predicate Functions

```inverted_predicate == not . predicate
```
```> not True
False
> not False
True
>

> (>5) 10
True
> (>5) 3
False

> not . (>5) \$ 10
False
> not . (>5) \$ 3
True
>

> let f = not . (>5)
> f 10
False
> f 5
True

> import Data.List
>
> filter ( isPrefixOf "a" ) ["a","ab","cd","abcd","xyz"]
["a","ab","abcd"]
>
> filter ( not . isPrefixOf "a" ) ["a","ab","cd","abcd","xyz"]
["cd","xyz"]
>
```

Example:

```> let f = (+4)
> let g = (*3)
>
>
> f (g 6) -- (+4) ((*3) 6) = (+4) 18 = 22
22
>
> (f . g) 6
22
>
> (.) f g 6
22
>
> let h = f . g
>
> h 6
22
>

> id 10
10
> id 3
3
>
> id Nothing
Nothing
> id 'a'
'a'
> id (Just 10)
Just 10
>

> (f . id) 10
14
> (id . f) 10
14
>

> const 10 20
10
> const 10 3
10
>

> (f . (const 10)) 4
14
> (f . (const 10)) 3
14
> const 10 . f \$ 7
10
> const 10 . f \$ 3
10
>

{- Avoiding Parenthesis with composition -}
> let g x = x * 2
> let f x = x + 10
> let h x = x - 5
>
> h (f (g 3))
11
> h \$ f \$ g 3
11
>
> (h . f . g ) 3
11
> h . f . g \$ 3
11
>

{- Function Composition with curried functions -}

> let f1 x y = 10*x + 4*y
> let f2 a b c = 4*a -3*b + 2*c
> let f3 x = 3*x

> (f1 3 ( f3 5))
90
>
> f1 3 \$ f3 5
90
>
> f1 3 . f3 \$ 5
90
>
> let f = f1 3 . f3
>
> f 5
90
> f 8
126
>

> (f1 4 (f2 5 6 (f3 5)))
168
>
> f1 4 \$ f2 5 6 \$ f3 5
168
>
> f1 4 . f2 5 6 . f3 \$ 5
168
>
> let g = f1 4 . f2 5 6 . f3 {- You can also create new functions -}
> :t g
g :: Integer -> Integer
> g 5
168
> g 10
288
>

{- Function Composition with Map and Filter -}

> import Data.Char

> :t ord
ord :: Char -> Int

> :t ordStr
ordStr :: [Char] -> [Int]
>

> ordStr "curry"
[99,117,114,114,121]
>
> let r x= x + 30
>
> map r (ordStr "curry")
[129,147,144,144,151]
>
> map r \$ ordStr "curry"
[129,147,144,144,151]
>
> map r . ordStr \$ "curry"
[129,147,144,144,151]
>
> sum . map r . ordStr \$ "curry"
715
>

> let s =  map r . ordStr
> s "curry"
[129,147,144,144,151]
[134,127,145,137,131,138,138]
>

let sum_ord = sum . map r . ordStr

> sum_s "curry"
715
950
>
> sum_ord "curry"
715
950
>

> map ord (map toUpper "haskell")
[72,65,83,75,69,76,76]
>
> map ord . map toUpper \$ "haskell"
[72,65,83,75,69,76,76]
>

> map (flip (-) 10) . map ord . map toUpper \$ "haskell"
[62,55,73,65,59,66,66]
>

> map chr . map (flip (-) 10) . map ord . map toUpper \$ "haskell"
">7IA;BB"
>

{- The function f is in point free style -}

> let f = map chr . map (flip (-) 10) . map ord . map toUpper
>
">7IA;BB"
>
```

#### 1.12.3 Function Composition in Python

```def compose(funclist):

def _(x):
y = x

for f in reversed(funclist):
y = f(y)
return y

return _

>>> add10 = lambda x: x + 10

>>> mul3 = lambda x: x * 3

>>> x = 3
>>> a
13
>>> b = mul3(a)
>>> b
39

>>> def f_without_composition (x):
...    b = mul3(a)
...    return b
...

>>> f_without_composition(3)
39

>>> f_without_composition(4)
42

# It will create the function f = (mul3 ° add10)(x)
# The flow is from right to left
#
#
#   =  mul3 13
#   =  39
#
>>> f = compose ([mul3, add10])

>>> f(3)
39

>>> f(4)
42

>>> f
<function __main__.compose.<locals>._>

39

42

#
# Composition is more intuitive when the flow is from
# left to right, the functions in the left side are
# executed first.
#
#

# Compose Forward
def composef (funclist):

def _(x):
y = x
for f in funclist:
y = f(y)
return y

return _

#
#   The symbol (>>) from F# will be used to mean forward composition
#   here
#
#    = mul3 13
#    = 39
#    Input  .................................................  Output
#           .    |----------|           |---------|         .   39
#   3  ---> .--> |  add10   | --------> |   mul3  | ------->.  ------->
#           .  3 |----------| 13 =(10+3)|---------|  39     .
#           .                                39 = 3 * 13    .
#           .................................................
#
#  The execution flow is from left to right, in the same order as the
#  functions are written in the code.
#

>>> g = composef ([add10, mul3])

>>> g(3)
39

>>> g(4)
42

>>> ### A more useful example: parse the following table:

text = """
12.23,30.23,892.2323
23.23,90.23,1000.23
3563.23,100.23,45.23

"""

# Unfortunately Python, don't have a favorable syntax to function
# composition like: composition operator, lightweight lambda and function
# application without parenthesis.
#

>>> mapl = lambda f: lambda xs: list(map(f, xs))
>>> filterl = lambda f: lambda xs: list(filter(f, xs))

>>> splitlines = lambda s: s.splitlines()
>>> reject_empty = lambda xs: list(filter(lambda x: x, xs))
>>> strip = lambda s: s.strip()
>>> split = lambda sep: lambda s: s.split(sep)

>>> composef([splitlines])(text)
['',
' 12.23,30.23,892.2323',
' 23.23,90.23,1000.23',
' 3563.23,100.23,45.23',
'']

>>> composef([splitlines, reject_empty])(text)
[' 12.23,30.23,892.2323',
' 23.23,90.23,1000.23',
' 3563.23,100.23,45.23']

>>> composef([splitlines, reject_empty, mapl(strip)])(text)
['12.23,30.23,892.2323', '23.23,90.23,1000.23',
'3563.23,100.23,45.23']

>>> composef([splitlines, reject_empty, mapl(strip), mapl(split(","))])(text)
[['12.23', '30.23', '892.2323'],
['23.23', '90.23', '1000.23'],
['3563.23', '100.23', '45.23']]

>>> composef([splitlines, reject_empty, mapl(strip), mapl(split(",")), mapl(mapl(float))])(text)
[[12.23000, 30.23000, 892.23230],
[23.23000, 90.23000, 1000.23000],
[3563.23000, 100.23000, 45.23000]]

parse_csvtable =  composef(
[splitlines,
reject_empty,
mapl(strip),
mapl(split(",")),
mapl(mapl(float))]
)

>>> parse_csvtable(text)
[[12.23000, 30.23000, 892.23230],
[23.23000, 90.23000, 1000.23000],
[3563.23000, 100.23000, 45.23000]]

#  Notice there is three maps together, so that it can be optimized
#  each map is like a for loop, by composing the functions in map1,
#  map2 and map3 the code can be more faster.
#
# parse_csvtable =  composef(
# [splitlines,
# reject_empty,
# mapl(strip),          ---> map1
# mapl(split(",")),     ---> map2
# mapl(mapl(float))]    ---> map3
# )

parse_csvtable_optmized =  composef(
[splitlines,
reject_empty,
mapl(composef([strip, split(","), mapl(float)]))
])

>>> parse_csvtable_optmized(text)
[[12.23000, 30.23000, 892.23230],
[23.23000, 90.23000, 1000.23000],
[3563.23000, 100.23000, 45.23000]]
```

#### 1.12.4 Function Composition in F#

F# uses the operator (<<) for composition which is similar to Haskell composition operator (.) dot. It also uses the operator (>>) for forward composition that performs the operation in the inverse order of operator (<<).

Composition Operator (<<):

```- (<<) ;;
val it : (('a -> 'b) -> ('c -> 'a) -> 'c -> 'b)
>

> let h x = x + 3 ;;

val h : x:int -> int

> let g x = x * 5 ;;

val g : x:int -> int

- let m x = x - 4 ;;

val m : x:int -> int

// The composition is performed in the same way as math composition
// from right to left.
//
- h (g 4) ;;
val it : int = 23
>
-
- (h << g) 4 ;;
val it : int = 23
>

> m (h (g 4)) ;;
val it : int = 19
>
- (m << h << g) 4 ;;
val it : int = 19
>

// It is the same as math composition: f(x) = m ° h ° g
//
- let f = m << h << g ;;

val f : (int -> int)

> f 4 ;;
val it : int = 19
>
```

Forward Composition Operator (>>):

```> (>>) ;;
val it : (('a -> 'b) -> ('b -> 'c) -> 'a -> 'c)

> let h x = x + 3 ;;

val h : x:int -> int

> let g x = x * 5 ;;

val g : x:int -> int

- let m x = x - 4 ;;

val m : x:int -> int

- h (g 4) ;;
val it : int = 23
>

- (g >> h) 4 ;;
val it : int = 23
>
- let f = g >> h ;;

val f : (int -> int)

> f 4 ;;
val it : int = 23
>

- m (h (g 4)) ;;
val it : int = 19
>
-

- (g >> h >> m ) 4 ;;
val it : int = 19
>
-

// The argument is seen flowing from left to right, in the inverse
// order of math composition and Haskell composition operator (.) dot,
// which is more easier to read.
//
//  (g >> h >> m) 4 => It is seen as passing through each function
//
//   Evaluating:  g >> h >> m
//
//  Input              f =  g >> h >> m                          Output
//       .........................................................
//       .                                                       .
//       .   |-----------|      |-----------|     |-----------|  .
//     ----> |g = x * 5  ||---->| h = x + 3 |---->| m = x - 4 |----->
//   4   .   |-----------|  20  |-----------| 23  |-----------|  .  19
//       .       = 4 * 5 = 20    = 20 + 3 = 23    = 23 - 4 = 19  .
//       .........................................................
//

- let f = g >> h >> m ;;

val f : (int -> int)

> f 4 ;;
val it : int = 19
>
```

F# Argument Piping operator (|>)

```- let h x = x + 3 ;;

val h : x:int -> int

> let g x = x * 5 ;;

val g : x:int -> int

>  let m x = x - 4 ;;

val m : x:int -> int

>

// The piping operator feeds the function input forward.
//
- (|>) ;;
val it : ('a -> ('a -> 'b) -> 'b)
>

- (g 4) ;;
val it : int = 20
>
- 4 |> g ;;
val it : int = 20
>

// It is the same as:  4 |> g |> h
//
- h (g 4) ;;
val it : int = 23
>

- 4 |> g |> h ;;
val it : int = 23
>

// It is the same as:  4 |> g |> h |> m ;;
//
- m (h (g 4)) ;;
val it : int = 19
>

- 4 |> g |> h |> m ;;
val it : int = 19
>
```

Example of a non-trivial function composition.

```let text = "
12.23,30.23,892.2323
23.23,90.23,1000.23
3563.23,100.23,45.23

"
;;

// Negate predicate. Invert a predicate function.
//
> let neg pred = fun x -> not (pred x) ;;

val neg : pred:('a -> bool) -> x:'a -> bool

let split_string sep str =
List.ofArray  (System.Text.RegularExpressions.Regex.Split (str, sep))

> let split_lines = split_string "\n" ;;

val split_lines : (string -> string list)

> let trim_string (s: string) = s.Trim() ;;

val trim_string : s:string -> string

- let is_string_empty (s: string) = s.Length = 0
- ;;

val is_string_emtpy : s:string -> bool

- text |> split_lines ;;
val it : string list =
[""; " 12.23,30.23,892.2323"; " 23.23,90.23,1000.23";
" 3563.23,100.23,45.23"; ""; ""]
>

- text |> split_lines |> List.filter (neg is_string_empty) ;;
val it : string list =
[" 12.23,30.23,892.2323"; " 23.23,90.23,1000.23"; " 3563.23,100.23,45.23"]
>

- text |> split_lines |> List.filter (neg is_string_empty) |> List.map trim_stri- ng ;;
val it : string list =
["12.23,30.23,892.2323"; "23.23,90.23,1000.23"; "3563.23,100.23,45.23"]
>
-

- text |> split_lines |> List.filter (neg is_string_empty) |> List.map trim_stri- ng |> List.map (split_string ",") ;;
val it : string list list =
[["12.23"; "30.23"; "892.2323"]; ["23.23"; "90.23"; "1000.23"];
["3563.23"; "100.23"; "45.23"]]
>
-

- text |> split_lines |> List.filter (neg is_string_empty) |> List.map trim_stri- ng |> List.map (split_string ",") |> List.map (List.map float) ;;
val it : float list list =
[[12.23; 30.23; 892.2323]; [23.23; 90.23; 1000.23]; [3563.23; 100.23; 45.23]]
>

// Or in multiple lines:

text
|> split_lines
|> List.filter (neg is_string_empty)
|> List.map trim_string
|> List.map (split_string ",")
|> List.map (List.map float)
;;

val it : float list list =
[[12.23; 30.23; 892.2323]; [23.23; 90.23; 1000.23]; [3563.23; 100.23; 45.23]]
>

// Then transformed into a function:
//
let parse_csv text =
text
|> split_lines
|> List.filter (neg is_string_empty)
|> List.map trim_string
|> List.map (split_string ",")
|> List.map (List.map float)
;;

val parse_csv : text:string -> float list list

> parse_csv text ;;
val it : float list list =
[[12.23; 30.23; 892.2323]; [23.23; 90.23; 1000.23]; [3563.23; 100.23; 45.23]]
>
-

// This operation can be optimized with function (forward) composition.
//
let parse_csv2 text =
text
|> split_lines
|> List.filter (neg is_string_empty)
|> List.map (trim_string >> (split_string ",") >> (List.map float))
;;

val parse_csv2 : text:string -> float list list

> parse_csv2 text ;;
val it : float list list =
[[12.23; 30.23; 892.2323]; [23.23; 90.23; 1000.23]; [3563.23; 100.23; 45.23]]
>

// It could be implemented using the math compostion (<<) operator.
// in the same as in Haskell.
//
let parse_csv3 text =
text
|> split_lines
|> List.filter (neg is_string_empty)
|> List.map ((List.map float) << (split_string ",") << trim_string)
;;

val parse_csv3 : text:string -> float list list

- parse_csv3 text ;;
val it : float list list =
[[12.23; 30.23; 892.2323]; [23.23; 90.23; 1000.23]; [3563.23; 100.23; 45.23]]
>

//  934.6923 = 12.23 + 30.23 + 892.2323
//
- parse_csv3 text |> List.map List.sum ;;
val it : float list = [934.6923; 1113.69; 3708.69]
>
-

- parse_csv3 text |> List.map List.sum |> List.sum ;;
val it : float = 5757.0723
>

// This function can also be written in point-free style.
// It means only with function forward-composition.
//
let parse_csv4 =
split_lines
>> List.filter (neg is_string_empty)
>> List.map (trim_string
>> (split_string ",")
>> (List.map float))
;;

val parse_csv4 : (string -> float list list)

> parse_csv4 text ;;
val it : float list list =
[[12.23; 30.23; 892.2323]; [23.23; 90.23; 1000.23]; [3563.23; 100.23; 45.23]]
>

// With math composition (<<) or Haskell composition order.
//
let parse_csv5 =
List.map ((List.map float) << (split_string ",") << trim_string)
<<  List.filter (neg is_string_empty)
<<  split_lines
;;

val parse_csv5 : (string -> float list list)

> parse_csv5 text ;;
val it : float list list =
[[12.23; 30.23; 892.2323]; [23.23; 90.23; 1000.23]; [3563.23; 100.23; 45.23]]
>
```

### 1.13 Functors

#### 1.13.1 Overview

Functors are type constructors that can be mapped over like lists are mapped with map function. This concept from category theory and like many mathematical abstractions it is defined by the laws that it must satisfies, in this case Functor's laws.

In Haskell functors are instances of the type class Functor that must implement the function fmap for each functor implementation.

Note: Haskell functors must not be confused with C++ functor and ML-module functor (Higher order module).

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

f :: a -> b             =====>        f :: a -> b
a   ----------------------> b           a ------------------------> b

map f :: [a] -> [b]                   fmap f :: F a -> F b
[a] ----------------------> [b]       F a ----------------------> F b

Where F is a type constructor.
```

A functor must satisfy the laws:

• Identity Law.

fmap id == id

Where id is the identity function.

• Composition Law

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

The composition law can be generalized to:

fmap (f1 . f2 . f3 … fn) = fmap f1 . fmap f2 . fmap f3 … fmap fn

#### 1.13.2 Show all Functor instances

```> :info Functor
class Functor f where
fmap :: (a -> b) -> f a -> f b
(<\$) :: a -> f b -> f a
-- Defined in `GHC.Base'
instance Functor (Either a) -- Defined in `Data.Either'
instance Functor Maybe -- Defined in `Data.Maybe'
instance Functor ZipList -- Defined in `Control.Applicative'
-- Defined in `Control.Applicative'
instance Functor (Const m) -- Defined in `Control.Applicative'
instance Functor [] -- Defined in `GHC.Base'
instance Functor IO -- Defined in `GHC.Base'
instance Functor ((->) r) -- Defined in `GHC.Base'
instance Functor ((,) a) -- Defined in `GHC.Base'
>

> :info IO
newtype IO a
= GHC.Types.IO (GHC.Prim.State# GHC.Prim.RealWorld
-> (# GHC.Prim.State# GHC.Prim.RealWorld, a #))
-- Defined in `GHC.Types'
instance Monad IO -- Defined in `GHC.Base'
instance Functor IO -- Defined in `GHC.Base'
instance Applicative IO -- Defined in `Control.Applicative'
>
> :info Maybe
data Maybe a = Nothing | Just a     -- Defined in `Data.Maybe'
instance Eq a => Eq (Maybe a) -- Defined in `Data.Maybe'
instance Monad Maybe -- Defined in `Data.Maybe'
instance Functor Maybe -- Defined in `Data.Maybe'
instance Ord a => Ord (Maybe a) -- Defined in `Data.Maybe'
instance Show a => Show (Maybe a) -- Defined in `GHC.Show'
instance Applicative Maybe -- Defined in `Control.Applicative'
instance Alternative Maybe -- Defined in `Control.Applicative'
>
```

#### 1.13.3 Functor Implementations

##### 1.13.3.1 Identity
```-- File: identity.hs
--
data Id a = Id a  deriving (Show, Eq)

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

-- Specialized version of fmap
--
fmap_id :: (a -> b) -> (Id a -> Id b)
fmap_id f = fmap f

-- -- End of file identity.hs ------
------------------------------------

> Id 10
Id 10

> fmap (\x -> x + 3) (Id 30)
Id 33
>

> let plus5 =  \x -> x + 5
> :t plus5
plus5 :: Integer -> Integer
>

> plus5 10
15
>

> fmap plus5 (Id 30)
Id 35
>

> let fmap_plus5 = fmap plus5

<interactive>:68:18:
No instance for (Functor f0) arising from a use of `fmap'
The type variable `f0' is ambiguous

-- Solution:

> let fmap_plus5 = fmap plus5 :: Id Integer -> Id Integer
> :t fmap_plus5
fmap_plus5 :: Id Integer -> Id Integer
>

> fmap_plus5 (Id 30)
Id 35
>

> :t fmap_id
fmap_id :: (a -> b) -> Id a -> Id b
>

> fmap_id sqrt (Id 100.0)
Id 10.0
>

> let sqrt_id = fmap_id sqrt
> :t sqrt_id
sqrt_id :: Id Double -> Id Double
>

> sqrt_id (Id 100.0)
Id 10.0
>
```
##### 1.13.3.2 List

For lists the function fmap is equal to map.

```instance Functor [] where
fmap = map

> map (\x -> x + 3) [1, 2, 3]
[4,5,6]
> fmap (\x -> x + 3) [1, 2, 3]
[4,5,6]
>

> let f = fmap (\x -> x + 3) :: [Int] -> [Int]
> :t f
f :: [Int] -> [Int]

> f [1, 2, 3, 4]
[4,5,6,7]
>
```

Alternative Implementation of list functor:

```-- File: list_functor.hs
--

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

instance Functor List where

fmap f xss = case xss of
Nil          -> Nil
Cons x xs    -> Cons (f x) (fmap f xs)

-- End of file -------------
---------------------------

> Cons 10 (Cons 20 (Cons 30 Nil))
Cons 10 (Cons 20 (Cons 30 Nil))
>

> let xs = Cons 10 (Cons 20 (Cons 30 Nil))
> xs
Cons 10 (Cons 20 (Cons 30 Nil))
> :t xs
xs :: List Integer
>

> fmap (\x -> x + 5) xs
Cons 15 (Cons 25 (Cons 35 Nil))
>

> let fm = fmap (\x -> x + 5) :: List Integer -> List Integer

> fm  xs
Cons 15 (Cons 25 (Cons 35 Nil))
>
```
##### 1.13.3.3 Maybe / Option
```data Maybe a = Just a | Nothing deriving (Eq, Show)

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

Example:

```> fmap (\x -> x + 10) (Just 5)
Just 15
>
> fmap (\x -> x + 10) Nothing
Nothing
>

> let f = \x -> x + 10
> :t f
f :: Integer -> Integer
>

> let fmap_f = fmap f :: Maybe Integer -> Maybe Integer
> fmap_f (Just 20)
Just 30
>

> fmap_f Nothing
Nothing
>

> readMaybe "100" :: Maybe Integer
Just 100
>
> readMaybe "asd100" :: Maybe Integer
Nothing
>

> let parseInteger str = readMaybe str :: Maybe Integer
>
> :t parseInteger
parseInteger :: String -> Maybe Integer
>

> parseInteger "100"
Just 100
>
> parseInteger "Not a number"
Nothing
>

> fmap (\x -> x + 10) (parseInteger "200")
Just 210
>
> fmap (\x -> x + 10) (parseInteger "2sadas00")
Nothing
>

-- Specialized version of fmap
--
fmap_maybe :: (a -> b) -> (Maybe a -> Maybe b)
fmap_maybe func = fmap func

> fmap_maybe (\x -> x + 10) (Just 10)
Just 20
>

> fmap_maybe (\x -> x + 10) Nothing
Nothing
>
```
##### 1.13.3.4 Either

The type constructor Either is similar to Maybe and it can short circuit a computation in the similar way to Maybe, however it allows to attach an error value.

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

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

Example:

```--
-- File: either_functor.hs
-------------------------

--  Specialized version of fmap to Either type
--  constructor like map is specialized for lists.
--
fmap_either :: (a -> b) -> (Either s a -> Either s b)
fmap_either f = fmap f

data ErrorCode =
ParserError
| InvalidInput
deriving (Eq, Show)

describeErrorCode ParserError  = "The parser failed."
describeErrorCode InvalidInput = "Input out function domain."

describeError (Right x)    = Right x
describeError (Left  code) = Left (describeErrorCode code)

parseDouble :: String -> Either String Double
parseDouble  str =
case (readMaybe str :: Maybe Double) of
Just x  ->  Right x
Nothing ->  Left  "Error: Not a Double"

sqrt_safe :: Double -> Either String Double
sqrt_safe x =
if x >= 0
then (Right x)
else (Left "Error: Square root of negative number")

parseDouble2 :: String -> Either ErrorCode Double
parseDouble2  str =
case (readMaybe str :: Maybe Double) of
Just x  ->  Right x
Nothing ->  Left  ParserError

sqrt_safe2 :: Double -> Either ErrorCode Double
sqrt_safe2 x =
if x >= 0
then (Right x)
else (Left InvalidInput)

---------------------------------------
--             End of file            -
---------------------------------------

> sqrt_safe 100
Right 100.0
>
> sqrt_safe (-100)
Left "Error: Square root of negative number"
>

> sqrt_safe2 100
Right 100.0
>
> sqrt_safe2 (-100)
Left InvalidInput
>

> parseDouble "100.25e3"
Right 100250.0
>

> parseDouble "not a double"
Left "Error: Not a Double"
>

> parseDouble2 "-200.3"
Right (-200.3)
>

> parseDouble2 "Not a double"
Left ParserError
>

> fmap sqrt (Right 100.0)
Right 10.0
>
>

> let fmap_sqrt = fmap sqrt :: Either String Double -> Either String Double
> fmap_sqrt (parseDouble "400.0")
Right 20.0
>
Left "Error: Not a Double"
>

> describeError (sqrt_safe2 100)
Right 100.0
>
> describeError (sqrt_safe2 (-100))
Left "Input out function domain."
>

> describeError (parseDouble2 "200.23")
Right 200.23
>

> describeError (parseDouble2 "2dsfsd00.23")
Left "The parser failed."
>

> fmap_either (\x -> x + 10) (Right 200)
Right 210
>

> let sqrt_either = fmap_either sqrt
>
> :t sqrt_either
sqrt_either :: Either s Double -> Either s Double
>

> sqrt_either (Right 100.0)
Right 10.0
>
> sqrt_either (Left "Failed to fetch data")
Left "Failed to fetch data"
>
```
##### 1.13.3.5 IO

```instance Functor IO where
fmap f action = do
result <- action
return (f result)
```
```-- File: fmap_io.hs
--

fmap_io :: (a -> b) -> (IO a -> IO b)
fmap_io f = fmap f

--
------------------

> import System.Directory (getDirectoryContents)
>

> :t getDirectoryContents "/etc/R"
getDirectoryContents "/etc/R" :: IO [FilePath]
>

> getDirectoryContents "/etc/R"
["Renviron",".","ldpaths","..","repositories","Makeconf","Renviron.site","Rprofile.site"]
>

-- It will fail because the data is inside an IO container
-- and can only be extracted inside another IO container
--
> length (getDirectoryContents "/etc/R")

<interactive>:165:9:
Couldn't match expected type `[a0]'
with actual type `IO [FilePath]'
In the return type of a call of `getDirectoryContents'
In the first argument of `length', namely
`(getDirectoryContents "/etc/R")'
In the expression: length (getDirectoryContents "/etc/R")

> fmap length (getDirectoryContents "/etc/R")
8
> :t fmap length (getDirectoryContents "/etc/R")
fmap length (getDirectoryContents "/etc/R") :: IO Int
>

> fmap_io length (getDirectoryContents "/etc/R")
8
>

> :t length
length :: [a] -> Int
>

> let length_io = fmap_io length
>

> :t length_io
length_io :: IO [a] -> IO Int
>

> fmap_io length (getDirectoryContents "/etc/R")
8

-- In the REPL is possible to extract the data wrapped inside an IO
-- type constructor.
--

> dirlist <- getDirectoryContents "/etc/R"
> :t dirlist
dirlist :: [FilePath]
>
> dirlist
["Renviron",".","ldpaths","..","repositories","Makeconf","Renviron.site","Rprofile.site"]
>
> length dirlist
8
>

> :t length dirlist
length dirlist :: Int
>
```

#### 1.14.1 Overview

A monad is a concept from Category Theory, which is defined by three things:

• a type constructor m that wraps a, parameter a;
• a return (unit) function: takes a value from a plain type and puts it into a monadic container using the constructor, creating a monadic value. The return operator must not be confused with the "return" from a function in a imperative language. This operator is also known as unit, lift, pure and point. It is a polymorphic constructor.
• a bind operator (>>=). It takes as its arguments a monadic value and a function from a plain type to a monadic value, and returns a new monadic value.

In Haskell the type class Monad specifies the type signature of all its instances. Each Monad implementation must have the type signature that matches the Monad type class.

```class Monad m where

-- Constructor (aka unit or lift)
--
return :: a -> m a

-- Bind operator
--
(>>=)  :: m a -> (a -> m b) -> m b

(>>)   :: m a -> m b -> m b

fail   :: String -> m a
```

```newtype Identity a = Identity { runIdentity :: a }
deriving (Eq, Ord, Data, Traversable, Generic, Generic1)

return   = Identity
m >>= k  = k (runIdentity m)

instance Functor Identity where
fmap     = coerce

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

Example:

```>>> :info Identity
newtype Identity a = Identity {runIdentity :: a}
-- Defined in ‘Data.Functor.Identity’
instance Eq a => Eq (Identity a)
-- Defined in ‘Data.Functor.Identity’
instance Monad Identity -- Defined in ‘Data.Functor.Identity’
instance Functor Identity -- Defined in ‘Data.Functor.Identity’
instance Ord a => Ord (Identity a)
-- Defined in ‘Data.Functor.Identity’
-- Defined in ‘Data.Functor.Identity’
instance Show a => Show (Identity a)
-- Defined in ‘Data.Functor.Identity’
instance MonadFix Identity -- Defined in ‘Data.Functor.Identity’
instance Applicative Identity -- Defined in ‘Data.Functor.Identity’
instance Foldable Identity -- Defined in ‘Data.Functor.Identity’
instance Traversable Identity -- Defined in ‘Data.Functor.Identity’
>>>

>>> :t Identity
Identity :: a -> Identity a
>>>

>>> Identity 10
Identity 10
>>> :t Identity 10
Identity 10 :: Num a => Identity a
>>>

>>> :t runIdentity
runIdentity :: Identity a -> a
>>>

>>> runIdentity \$ Identity 10
10
>>> runIdentity \$ Identity 20
20
>>>

>>> return 10 :: Identity Int
Identity 10
>>>

>>> runIdentity \$ (return 10 :: Identity Int)
10

>>> return [1, 2, 3, 4] :: Identity [Int]
Identity [1,2,3,4]
>>>

>>> fmap (\x -> x + 5) \$ Identity 10
Identity 15
>>>

>>> fmap (\x -> x * 4) \$ fmap (\x -> x + 5) \$ Identity 10
Identity 60
>>>

>>> fmap  ((\x -> x * 4) . (\x -> x + 5)) \$ Identity 10
Identity 60
>>>

>>> (return 10 :: Identity Int) >>= \x -> return \$ x * 4
Identity 40
>>>

>>> Identity 10 >>= \x -> return (x * 4)  >>= \a -> return ( a + 5)
Identity 45
>>>

testidentityDO :: Identity Int -> Identity Int -> Identity Int
testIdentityDO ma mb = do
a <- ma
b <- mb
return \$ a * b

{- Repl friendly version -}

:set +m

:{

let testIdentityDO :: Identity Int -> Identity Int -> Identity Int
testIdentityDO ma mb = do
a <- ma
b <- mb
return \$ a * b
:}

>>> testIdentityDO (Identity 10) (Identity 20)
Identity 200
>>> testIdentityDO (Identity 4) (Identity 5)
Identity 20
>>>

{- It show how fmap can be derived from a monad. -}
:{
let fmapIdentity :: (a -> b) -> Identity a -> Identity b
fmapIdentity fn ma = do
a <- ma
return \$ fn a
:}

>>> :t fmapIdentity
fmapIdentity :: (a -> b) -> Identity a -> Identity b
>>>

>>> fmapIdentity (\x -> x + 5) (Identity 10)
Identity 15
>>>

:{
let fmapIdentity2 :: (a -> b) -> Identity a -> Identity b
fmapIdentity2 fn ma =
ma >>= \a ->
return \$ fn a
:}

>>> :t fmapIdentity2
fmapIdentity2 :: (a -> b) -> Identity a -> Identity b
>>>

>>> fmapIdentity2 (\x -> x + 5) (Identity 10)
Identity 15
>>>

>>> import Control.Monad (liftM2, liftM3, mapM)
>>>

>>> import Control.Monad (liftM2, liftM3, mapM)
>>>
>>> :t liftM2
liftM2 :: Monad m => (a1 -> a2 -> r) -> m a1 -> m a2 -> m r
>>>

>>> liftM2 (+)  (Identity 10) (Identity 30)
Identity 40
>>>

>>> let addIdentity = liftM2 (+)

>>> addIdentity (Identity 10) (Identity 20)
Identity 30
>>>

>> :t liftM3
liftM3
:: Monad m => (a1 -> a2 -> a3 -> r) -> m a1 -> m a2 -> m a3 -> m r
>>>

>>> let cubeVolume a b c = a * b * c

>>> liftM3 cubeVolume  (Identity 2) (Identity 4) (Identity 5)
Identity 40
>>>

>>> let idCubeVolume = liftM3 cubeVolume

>>> idCubeVolume (Identity 2) (Identity 4) (Identity 5)
Identity 40
>>>

>>> :t mapM
mapM :: (Monad m, Traversable t) => (a -> m b) -> t a -> m (t b)
>>>

>>> mapM (\x -> Identity \$ x + 4) [1, 2, 3, 4, 5]
Identity [5,6,7,8,9]
>>>
```

Documentation:

The list Monad is used for non-deterministic computations where there is a unknown number of results. It is useful for constraint solving: solve a problem by trying all possibilities by brute force. It is equivalent to List comprehension.

In Haskell it is defined as an instance of Monad type class:

```instance  Monad []  where
m >>= k          = concat (map k m)
return x         = [x]
fail s           = []
```

Examples:

• return wraps a value into a list
```> :t return
return :: Monad m => a -> m a
>
-- Wraps a value into a list
--
> return 10 :: [Int]

>
```

```> :t (>>=)
(>>=) :: Monad m => m a -> (a -> m b) -> m b
>

>  [10,20,30] >>= \x -> [2*x, x+5]
[20,15,40,25,60,35]
>

-- It is equivalent to:
--
--

> map ( \x -> [2*x, x+5] ) [10, 20, 30]
[[20,15],[40,25],[60,35]]
>
> concat (map ( \x -> [2*x, x+5] ) [10, 20, 30])
[20,15,40,25,60,35]
>
```

Do notation:

```  The do notation is a syntax sugar to ->

Do Notation:                   Do Notation Dessugarized:

cartesianProduct  = do         cartesianProduct =
x <- [1, 2, 3, 4]             [1, 2, 3, 4] >>= \x ->
y <- ["a", "b"]               ["a", "b"]   >>= \y ->
return (x, y)                 return (x, y)

Or

cartesianProduct =
bind [1 2, 3, 4]  (\x ->
bind ["a", "b"]   (\y ->
unit (x, y)))
```

Do notation examples for List monad:

```-- file cartesian.hs
--
-- Run in the repl:
--

cartesianProduct = do
x <- [1, 2, 3, 4]
y <- ["a", "b"]
return (x, y)

--  End of file: cartesian.hs
-- -----------------

> cartesianProduct
[(1,"a"),(1,"b"),(2,"a"),(2,"b"),(3,"a"),(3,"b"),(4,"a"),(4,"b")]
>

-- Or it can be typed in the repl directly:
--

> :set +m  -- Enable multiline paste
>

--  Or copy the following code in the repl
--  by typing :set +m to enable multiline paste
--
:{

let cartesianProduct = do
x <- [1, 2, 3, 4]
y <- ["a", "b"]
return (x, y)
:}

> :set +m  -- paste
>
> let cartesianProduct = do
*Main Control.Exception E Text.Read|     x <- [1, 2, 3, 4]
*Main Control.Exception E Text.Read|     y <- ["a", "b"]
*Main Control.Exception E Text.Read|     return (x, y)
>

--
-- Or: Dessugarizing

> [1, 2, 3, 4] >>= \x -> ["a", "b"] >>= \y -> return (x, y)
[(1,"a"),(1,"b"),(2,"a"),(2,"b"),(3,"a"),(3,"b"),(4,"a"),(4,"b")]
>

cartesian :: [a] -> [b] -> [(a, b)]
cartesian xs ys = do
x <- xs
y <- ys
return (x, y)

> cartesian [1, 2, 3, 4] ["a", "b"]
[(1,"a"),(1,"b"),(2,"a"),(2,"b"),(3,"a"),(3,"b"),(4,"a"),(4,"b")]
>

>>> let cartesian2 xs ys = [(x, y) | x <- xs, y <- ys]

>>> cartesian2 [1, 2, 3, 4] ["a", "b"]
[(1,"a"),(1,"b"),(2,"a"),(2,"b"),(3,"a"),(3,"b"),(4,"a"),(4,"b")]
>>>

-- Returns all possible combinations between a, b and c
--
--
triples :: [a] -> [b] -> [c] -> [(a, b, c)]
triples  xs ys zs = do
x <- xs
y <- ys
z <- zs
return (x, y, z)

--   The triples have 24 results
--
--   x -> 2 possibilities
--   y -> 3 possibilities
--   z -> 4 possibilities
--
--  Total of possibilities:  2 * 3 * 4 = 24
--  the computation will return 24 results
--
--
> triples [1, 2] ["a", "b", "c"] ["x", "y", "z", "w"]
[(1,"a","x"),(1,"a","y"),(1,"a","z"),(1,"a","w"),(1,"b","x"),
(1,"b","y"),(1,"b","z"),(1,"b","w"),(1,"c","x"),(1,"c","y"),
(1,"c","z"),(1,"c","w"),(2,"a","x"),(2,"a","y"),(2,"a","z"),
(2,"a","w"),(2,"b","x"),(2,"b","y"),(2,"b","z"),(2,"b","w"),
(2,"c","x"),(2,"c","y"),(2,"c","z"),(2,"c","w")]

> length ( triples [1, 2] ["a", "b", "c"] ["x", "y", "z", "w"] )
24
>

>>> let triples2 xs ys zs = [(x, y, z) | x <- xs, y <- ys, z <- zs]
>>> :t triples2
triples2 :: [t] -> [t1] -> [t2] -> [(t, t1, t2)]
>>>
>>> take 3 \$ triples2 [1, 2] ["a", "b", "c"] ["x", "y", "z", "w"]
[(1,"a","x"),(1,"a","y"),(1,"a","z")]
>>>

--
--  Find all numbers for which a ^ 2 + b ^ 2 = c ^ 2
--  up to 100:
--
--  There is 100 x 100 x 100 = 1,000,000 of combinations
--  to be tested:
--
pthytriples = do
a <- [1 .. 100]
b <- [1 .. 100]
c <- [1 .. 100]

if (a ^ 2 + b ^ 2 == c ^ 2)
then (return (Just (a, b, c)))
else (return Nothing)

> import Data.Maybe (catMaybes)

> take 10 (catMaybes pthytriples)
[(3,4,5),(4,3,5),(5,12,13),(6,8,10),(7,24,25),(8,6,10),(8,15,17),(9,12,15),(9,40,41),(10,24,26)]
>

-- Example: Find all possible values of a functions applied
--          to all combinations possible of 3 lists:
--
applyComb3 = do
x <- [1, 2, 3]
y <- [9, 8]
z <- [3, 8, 7, 4]
return ([x, y, z], 100 * x + 10 *  y + z)

> applyComb3
[([1,9,3],193),([1,9,8],198),([1,9,7],197),([1,9,4],194) ...]

-- Example: Break a 4 letter password using brute force
--
--

import Data.List (find)
import Data.Maybe (isJust)

alphabet = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789"

make_password :: String -> String -> Bool

-- It will try 62 combinations for each letter
-- wich means it will try up to 62 x 62 x 62 x 62 = 14,776,336
-- (=~ 15 millions) combinations at the worst case.
--
--
crack_4pass  pass_function = do
ch0 <- alphabet
ch1 <- alphabet
ch2 <- alphabet
ch3 <- alphabet
let trial = [ch0, ch1, ch2, ch3] in
if   pass_function trial
then return (Just trial)
else return Nothing

crackpass pass_function =
find isJust (crack_4pass pass_function)

> :set +s

> crackpass passwd1
Just (Just "fX87")
(2.00 secs, 434045068 bytes)
>

Just (Just "2f8z")
(18.19 secs, 4038359812 bytes)
>
```
##### 1.14.3.2 List Monad in OCaml
```module ListM =
struct
let bind ma f = List.concat (List.map f ma)

let (>>=) = bind

(* return  *)
let unit a  = [a]

end
;;

module ListM :
sig
val bind : 'a list -> ('a -> 'b list) -> 'b list
val ( >>= ) : 'a list -> ('a -> 'b list) -> 'b list
val unit : 'a -> 'a list
end

(*

cartesian :: [a] -> [b] -> [(a, b)]              cartesian :: [a] -> [b] -> [(a, b)]
cartesian xs ys = do                             carteasian xs ys =
x <- xs                              ==>>        xs >>= \x ->
y <- ys                                          ys >>= \y ->
return (x, y)                                    return (x, y)

cartesian :: [a] -> [b] -> [(a, b)]
carteasian xs ys =
bind xs (\x ->
bind ys (\y ->
return (x, y)))

*)

let cartesian xs ys =
let open ListM in
xs >>= fun x ->
ys >>= fun y ->
unit (x, y)
;;

val cartesian : 'a list -> 'b list -> ('a * 'b) list = <fun>

>   cartesian [1; 2; 3; 4; ] ["a"; "b"; "c"]  ;;
- : (int * string) list =
[(1, "a"); (1, "b"); (1, "c"); (2, "a"); (2, "b"); (2, "c"); (3, "a");
(3, "b"); (3, "c"); (4, "a"); (4, "b"); (4, "c")]

(*

triples :: [a] [b] [c] -> [(a, b, c)]     triples :: [a] [b] [c] -> [(a, b, c)]
triples xs ys zs = do                     tripes xs ys zs =
x <- xs                                   xs >>= \x ->
y <- ys                     ==>           ys >>= \y ->
z <- zs                                   zs >>= \z ->
return (x, y, z)                          return (x, y, z)

*)

let triples (xs: 'a list) (ys: 'b list) (zs: 'c list) : ('a * 'b * 'c) list =
let open ListM in
xs >>= fun x ->
ys >>= fun y ->
zs >>= fun z ->
unit (x, y, z)
;;

val triples : 'a list -> 'b list -> 'c list -> ('a * 'b * 'c) list = <fun>

>  triples ["x"; "z"; "w"]  [Some 10; None] [1; 2; 3; 4; 5] ;;
- : (string * int option * int) list =
[("x", Some 10, 1); ("x", Some 10, 2); ("x", Some 10, 3); ("x", Some 10, 4);
("x", Some 10, 5); ("x", None, 1); ("x", None, 2); ("x", None, 3);
("x", None, 4); ("x", None, 5); ("z", Some 10, 1); ("z", Some 10, 2);
("z", Some 10, 3); ("z", Some 10, 4); ("z", Some 10, 5); ("z", None, 1);
("z", None, 2); ("z", None, 3); ("z", None, 4); ("z", None, 5);
("w", Some 10, 1); ("w", Some 10, 2); ("w", Some 10, 3); ("w", Some 10, 4);
("w", Some 10, 5); ("w", None, 1); ("w", None, 2); ("w", None, 3);
("w", None, 4); ("w", None, 5)]
```
##### 1.14.3.3 List Monad in F#

Example without syntax sugar:

```module ListM =

let bind ma f = List.concat (List.map f ma)

let (>>=) = bind

(* return  *)
let unit a  = [a]
;;

module ListM = begin
val bind : ma:'a list -> f:('a -> 'b list) -> 'b list
val ( >>= ) : ('a list -> ('a -> 'b list) -> 'b list)
val unit : a:'a -> 'a list
end

(*  Example:

cartesian :: [a] -> [b] -> [(a, b)]
cartesian xs ys = do
x <- xs
y <- ys
return (x, y)

> cartesian [1, 2, 3, 4] ["a", "b", "c"]
*)

let cartesian xs ys =
let (>>=) = ListM.(>>=) in
let unit  = ListM.unit in

xs >>= fun x ->
ys >>= fun y ->
unit (x, y)
;;

val cartesian : 'a list -> 'b list -> ('a * 'b) list = <fun>                                                           >

>
> cartesian [1; 2; 3; 4; ] ["a"; "b"; "c"]  ;;
val it : (int * string) list =
[(1, "a"); (1, "b"); (1, "c");
(2, "a"); (2, "b"); (2, "c");
(3, "a"); (3, "b"); (3, "c");
(4, "a"); (4, "b"); (4, "c")]
>

(*

F# List type is eager evaluated so the it will
really loop over 100 * 100 * 100 = 100,000,000
of combinations:

pthytriples = do
a <- [1 .. 100]
b <- [1 .. 100]
c <- [1 .. 100]

if (a ^ 2 + b ^ 2 == c ^ 2)
then (return (Just (a, b, c)))
else (return Nothing)

*)

(* Tail recursive function

*)
let range start stop step  =

let rec range_aux start acc =
if start >= stop
then  List.rev acc
else  range_aux (start + step)  (start::acc)

in range_aux start []
;;

val range : start:int -> stop:int -> step:int -> int list

>  range 1 11 1 ;;
- : int list = [1; 2; 3; 4; 5; 6; 7; 8; 9; 10]

let pthytriples () =
let (>>=) = ListM.(>>=) in
let unit  = ListM.unit in

range 1 101 1 >>= fun a ->
range 1 101 1 >>= fun b ->
range 1 101 1 >>= fun c ->
if (a * a + b * b = c * c)
then unit (Some (a, b, c))
else unit None
;;

val pthytriples : unit -> (int * int * int) option list

let option_to_list opt_list =
List.foldBack                     (* Fold right *)
(fun x acc -> match x with
| Some a -> a::acc
| None   -> acc
)
opt_list
[]
;;

- option_to_list (pthytriples ()) ;;

val it : (int * int * int) list =
[(3, 4, 5); (4, 3, 5); (5, 12, 13); (6, 8, 10); (7, 24, 25); (8, 6, 10);
(8, 15, 17); (9, 12, 15); (9, 40, 41); (10, 24, 26); (11, 60, 61);
(12, 5, 13); (12, 9, 15); (12, 16, 20); (12, 35, 37); (13, 84, 85);
(14, 48, 50); (15, 8, 17); (15, 20, 25); (15, 36, 39); (16, 12, 20);
(16, 30, 34); (16, 63, 65); (18, 24, 30); (18, 80, 82); (20, 15, 25);
(20, 21, 29); (20, 48, 52); (21, 20, 29); (21, 28, 35); (21, 72, 75);
(24, 7, 25); (24, 10, 26); (24, 18, 30); (24, 32, 40); (24, 45, 51);
(24, 70, 74); (25, 60, 65); (27, 36, 45); (28, 21, 35); (28, 45, 53);
(28, 96, 100); (30, 16, 34); (30, 40, 50); (30, 72, 78); (32, 24, 40);
(32, 60, 68); (33, 44, 55); (33, 56, 65); (35, 12, 37); (35, 84, 91);
(36, 15, 39); (36, 27, 45); (36, 48, 60); (36, 77, 85); (39, 52, 65);
(39, 80, 89); (40, 9, 41); (40, 30, 50); (40, 42, 58); (40, 75, 85);
(42, 40, 58); (42, 56, 70); (44, 33, 55); (45, 24, 51); (45, 28, 53);
(45, 60, 75); (48, 14, 50); (48, 20, 52); (48, 36, 60); (48, 55, 73);
(48, 64, 80); (51, 68, 85); (52, 39, 65); (54, 72, 90); (55, 48, 73);
(56, 33, 65); (56, 42, 70); (57, 76, 95); (60, 11, 61); (60, 25, 65);
(60, 32, 68); (60, 45, 75); (60, 63, 87); (60, 80, 100); (63, 16, 65);
(63, 60, 87); (64, 48, 80); (65, 72, 97); (68, 51, 85); (70, 24, 74);
(72, 21, 75); (72, 30, 78); (72, 54, 90); (72, 65, 97); (75, 40, 85);
(76, 57, 95); (77, 36, 85); (80, 18, 82); (80, 39, 89); ...]
>
```

Example with F# "workflow" or "computation expression" syntax:

```- List.concat [; []; [2; 3; 4; 5]; [10; 20]] ;;
val it : int list = [1; 2; 3; 4; 5; 10; 20]
>

(* The F# workflow works like Haskell do-noation

*)
type ListBuilder () =
member this.Bind(xs, f) = List.concat (List.map f xs)

member this.Return(x) = [x]
;;

type ListBuilder =
class
new : unit -> ListBuilder
member Bind : xs:'b list * f:('b -> 'c list) -> 'c list
member Return : x:'a -> 'a list
end

let listDo = ListBuilder () ;;

val listDo : ListBuilder

(*
cartesian :: [a] -> [b] -> [(a, b)]
cartesian xs ys = do
x <- xs
y <- ys
return (x, y)
*)

let cartesian xs ys =
listDo {
let! x = xs
let! y = ys
return (x, y)
}
;;

val cartesian : xs:'a list -> ys:'b list -> ('a * 'b) list

>  cartesian [1; 2; 3; 4; ] ["a"; "b"; "c"] ;;
val it : (int * string) list =
[(1, "a"); (1, "b"); (1, "c");
(2, "a"); (2, "b"); (2, "c");
(3, "a"); (3, "b"); (3, "c");
(4, "a"); (4, "b"); (4, "c")]
>
```
##### 1.14.3.4 List Monad in Python
```from functools import reduce

def concat(xss):
"concat :: [[a]] -> [a]"
return  reduce(lambda acc, x: acc + x, xss, [])

def listUnit (x):
"listUnit :: x -> [x]"
return [x]

def listBind (xss, f):
"listBind :: [a] -> (a -> [b]) -> [b] "
return concat(map(f, xss))

#
# cartesian :: [a] -> [b] -> [(a, b)]              cartesian :: [a] -> [b] -> [(a, b)]
# cartesian xs ys = do                             carteasian xs ys =
#    x <- xs                              ==>>        xs >>= \x ->
#    y <- ys                                          ys >>= \y ->
#    return (x, y)                                    return (x, y)
#
#
# cartesian :: [a] -> [b] -> [(a, b)]
# carteasian xs ys =
#   bind xs (\x ->
#   bind ys (\y ->
#   return (x, y)))
#
def cartesian(xs, ys):

return listBind(xs,
lambda x: listBind(ys,
lambda y: listUnit ((x, y))))

def triples(xs, ys, zs):

return listBind(xs,
lambda x: listBind(ys,
lambda y: listBind(zs,
lambda z: listUnit((x, y, z)))))

>>> cartesian([1, 2, 3, 4], ["a", "b", "c"])
[(1, 'a'), (1, 'b'), (1, 'c'),
(2, 'a'), (2, 'b'), (2, 'c'),
(3, 'a'), (3, 'b'), (3, 'c'),
(4, 'a'), (4, 'b'), (4, 'c')]
>>>

>>> triples([1, 2], ["a", "b", "c"], ["x", "y", "z"])
[(1, 'a', 'x'),
(1, 'a', 'y'),
(1, 'a', 'z'),
(1, 'b', 'x'),
(1, 'b', 'y'),
(1, 'b', 'z'),
(1, 'c', 'x'),
...
>>>

# Emulate ML module
#
class ListM ():

@classmethod
def bind(cls, xss, f):
return concat(map(f, xss))

@classmethod
def unit(cls, x):
return [x]

def cartesian (xs, ys):
return ListM.bind( xs, lambda x:
ListM.bind( ys, lambda y:
ListM.unit ((x, y))))

>>> cartesian([1, 2, 3, 4], ["a", "b", "c"])

[(1, 'a'), (1, 'b'), (1, 'c'),
(2, 'a'), (2, 'b'), (2, 'c'),
(3, 'a'), (3, 'b'), (3, 'c'),
(4, 'a'), (4, 'b'), (4, 'c')]
>>>
```

#### 1.14.4 Maybe / Option Monad

##### 1.14.4.1 Overview

The Maybe type (Haskell) or Option type (ML, F# and OCaml) is used to indicate that a function might return nothing, the value might not exists or that a computation maight fail. This is helpful to remove nested null checks, avoid null pointer or null object exceptions.

Some functions are a natural candidates to return a maybe or option type like parser function, user input validation, lookup functions that search an input in data structure or database and functions with invalid input.

The Maybe monad ends the computation if any step fails. The module Data.Maybe has useful function to deal with Maybe type.

```data Maybe a = Just a | Nothing

(Just x) >>= k = k x
Nothing  >>= k = Nothing

return = Just
```

Example: The function below parses two numbers and adds them.

```--- File: test.hs
--
import Data.List (lookup)

-- Parser functions

parseInt :: String -> Maybe Int
parseInt x = readMaybe x :: Maybe Int

parseDouble :: String -> Maybe Double
parseDouble x = readMaybe x :: Maybe Double

-- Function with invalid input

sqrtSafe :: Double -> Maybe Double
sqrtSafe x = if x > 0
then Just (sqrt x)
else Nothing

addSafe :: Maybe Double -> Maybe Double -> Maybe Double
x <- some_x
y <- some_y
return (x + y)

addOneSafe :: Maybe Double -> Double -> Maybe Double
sa <- a
let c =  3.0 * (b + sa)
return (sa + c)

-- s - stands for Some
--
addSqrtSafe :: Double -> Double -> Maybe Double
sx <- sqrtSafe x
sy <- sqrtSafe y
return (sx + sy)

--
sqrtSafe x >>= \sx ->
sqrtSafe y >>= \sy ->
return (sx +  sy)

-- End of test file
--------------------------------

>

> parseInt "100"
Just 100

-- Returns nothing if computation fails
-- instead of perform an exception
--
> parseInt "not an int."
Nothing
>

> parseDouble "1200"
Just 1200.0
> parseDouble "1200.232"
Just 1200.232
> parseDouble "12e3"
Just 12000.0
> parseDouble "not a valid number"
Nothing
>

-- This haskell function is safe, however in another language
-- it would yield a exception.
--
> sqrt (-100.0)
NaN
>

> sqrtSafe (-1000.0)
Nothing
>

> sqrtSafe 100.0
Just 10.0
>

-- Thea function fmap is a generalization of map and applies a function
-- to the value wrapped in the monad.
--

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

> fmap (\x -> x + 1.0) (Just 10.0)
Just 11.0
> fmap (\x -> x + 1.0) Nothing
Nothing
>
> fmap (\x -> x + 1.0) (parseDouble "10.233")
Just 11.233
> fmap (\x -> x + 1.0) (parseDouble "ase10.2x3")
Nothing
>

--   return function
--

> :t return
return :: Monad m => a -> m a
>

return 10 :: Maybe Int
Just 10
>

> return "hello world" :: Maybe String
Just "hello world"
>

-- Bind function
--
-- The bind operator or funciton short circuits the computation if
-- it fails at any point
--
--

> :t (>>=)
(>>=) :: Monad m => m a -> (a -> m b) -> m b
>

> Just "100.0" >>= parseDouble >>= sqrtSafe
Just 10.0
>
> Nothing  >>= parseDouble >>= sqrtSafe
Nothing
>

> return "100.0" >>= parseDouble >>= sqrtSafe
Just 10.0
>
> return "-100.0" >>= parseDouble >>= sqrtSafe
Nothing
>

-- Do noation
--
--
--   x <- some_x                        some_x >>= \x ->
--   y <- some_y                 ==>    some_y >>= \y ->
--   return (x + y)                           return (x + y)
--
--
--
--
--
addSafe :: Maybe Double -> Maybe Double -> Maybe Double
>

> addSafe (Just 100.0) (Just 20.0)
Just 120.0
>

Nothing
>

Nothing
>

Nothing
>

> addSafe (parseDouble "100.0") (sqrtSafe 400.0)
Just 120.0
>

> addSafe (Just 100.0) (sqrtSafe (-20.0))
Nothing
>

> addSafe (parseDouble "asd100.0") (sqrtSafe 400.0)
Nothing
>

addSqrtSafe :: Double -> Double -> Maybe Double
>

Just 30.0
>

Nothing
>

Nothing
Just 30.0
>

Just 100.0
>
Nothing
>

Just 460.0
>

Nothing
>
```
##### 1.14.4.3 Maybe Monad in OCaml

The maybe type is called Option in Ocaml and F#.

```-> Some 100 ;;
- : int option = Some 100

-> None ;;
- : 'a option = None

module OptM =
struct

let unit x = Some x

let bind ma f =
match ma with
| Some x  ->  f x
| None    ->  None

let (>>=) = bind

let map f ma =
match ma with
| Some x -> Some (f x)
| None   -> None

end

module OptM :
sig
val unit : 'a -> 'a option
val bind : 'a option -> ('a -> 'b option) -> 'b option
val ( >>= ) : 'a option -> ('a -> 'b option) -> 'b option
val map : ('a -> 'b) -> 'a option -> 'b option
end

#  OptM.unit ;;
- : 'a -> 'a option = <fun>

# OptM.bind ;;
- : 'a option -> ('a -> 'b option) -> 'b option = <fun>
#

# OptM.map ;;
- : ('a -> 'b) -> 'a option -> 'b option = <fun>
#

# OptM.map (fun x -> x + 3) (Some 10) ;;
- : int option = Some 13

#  OptM.map (fun x -> x + 3) None ;;
- : int option = None

#  float_of_string "100.23" ;;
- : float = 100.23
# float_of_string "a100.23" ;;
Exception: Failure "float_of_string".

let parseFloat x =
try Some (float_of_string x)
with _ -> None
;;

#  parseFloat "100.00" ;;
- : float option = Some 100.
#
#  parseFloat "asds100.00" ;;
- : float option = None
#

(*

addSafe :: Maybe Double -> Maybe Double -> Maybe Double
x <- some_x
y <- some_y
return (x + y)

some_x >>= \x ->
some_y >>= \y ->
return (x + y)

*)

let open OptM in
sx >>= fun x ->
sy >>= fun y ->
unit (x +. y)
;;

val addSafe : float option -> float option -> float option = <fun>

# addSafe (Some 10.0) (Some 20.0) ;;
- : float option = Some 30.
# addSafe None (Some 20.0) ;;
- : float option = None
- : float option = None
#

(*

If Haskell functions were impure it would work:

return (x + y + z)

return (x + y + z)
*)

let prompt  message =
print_string message ;
;;

val prompt : string -> float option = <fun>

let open OptM in
prompt "Enter x: "  >>= fun x ->
prompt "Enter y: "  >>= fun y ->
prompt "Enter z: "  >>= fun z ->
unit (print_float  (x +. y +. z))
;;

val addInputsSafe : unit -> unit option = <fun>

(* It will stop the computation if any input is invalid *)

Enter x: 10.0
Enter y: 20.0
Enter z: 30.0
60.- : unit option = Some ()
#

Enter x: 20.0
Enter y: dsfd
- : unit option = None
#

Enter x: 20.0
Enter y: 30.0
Enter z: a20afdf
- : unit option = None

Enter x: erew34
- : unit option = None
#
```
##### 1.14.4.4 Maybe Monad in Python

Implementation with Functions

```import collections

Option = collections.namedtuple("Option", ["value"])

# Nothing
none = Option(None)

# Just
some = Option

#
unit_option = some

def isOption(obj):
return isinstance(obj, Option)

def isOptionException(obj):
if isinstance (obj, Option):
return obj
else:
raise ValueError ("Expected an instance of Option")

# isJust
def isSome (opt):
return not (isOptionException(opt).value == None)

# isNothing
def isNone (opt):
return not(isSome (opt))

def fmap_option(fn, opt):
if isSome(opt):
return some(fn(opt.value))
else:
return none

def bind_option(opt, fn):
if isSome(opt):
return fn(opt.value)
else:
return none

def parseFloat (x):
"parseFloat :: string -> Option float"
try:
return some(float(x))
except ValueError:
return none

"
addSafe :: option float -> option float -> option float

addSafe Maybe Double -> Maybe Double -> Maybe Double
x <- opt_x
y <- opt_y
return (x + y)

opt_x >>= \x ->
opt_y >>= \y ->
return (x + y)

"
return bind_option(opt_x, lambda x:
bind_option(opt_y, lambda y:
unit_option (x + y)))

def prompt(message):

"prompt :: string -> Option float"

print (message)
return parseFloat(input ())

return bind_option(prompt("Enter x:"), lambda x:
bind_option(prompt("Enter y:"), lambda y:
bind_option(prompt("Enter z:"), lambda z:
unit_option (x + y + z))))

>>> some(100)
Option(value=100)
>>> none
Option(value=None)
>>>

>>> fmap_option(lambda x: x * 5, some(10))
Option(value=50)
>>>
>>> fmap_option(lambda x: x * 5, none)
Option(value=None)
>>>

Option(value=None)
Option(value=300)
Option(value=None)
>>>

>>> float("10asdas023")
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
ValueError: could not convert string to float: '10asdas023'
>>>

>>> parseFloat("100.0")
Option(value=100.0)
>>> parseFloat("10asda0.0")
Option(value=None)
>>>

Option(value=300.0)
>>>
Option(value=None)
>>>
>>>

Option(value=None)
>>>

#
#  Computation is stopped if any step go wrong
#
>>>
Enter x:
100
Enter y:
200
Enter z:
300
Option(value=600.0)
>>>
Enter x:
asdsa
Option(value=None)
>>>
Enter x:
100
Enter y:
Option(value=None)
>>>
```

Implementation with Class

```class Option():

def __init__(self, value):
self.value = value

def __str__(self):
if self.isSome():
return "some {}".format(self.value)
else:
return "none"

def __repr__(self):
return self.__str__()

def isSome (self):
return (self.value != None)

def isNone (self):
return (self.value == None)

# fmap
def map(self, fn):
if self.isSome():
return Option(fn(self.value))
else:
return Option(None)

def bind(self, fn):
if self.isSome():
return fn(self.value)
else:
return Option(None)

some = Option
none = Option(None)

def parseFloat (x):
"parseFloat :: string -> Option float"
try:
return some(float(x))
except ValueError:
return none

>>> parseFloat("100.23")
Option(value=100.23)

>>> parseFloat("100asdas.23")
Option(value=None)
>>>

>>> parseFloat("10.5").map(lambda x: x * 3)
some 31.5
>>> parseFloat("1sdfsd0.5").map(lambda x: x * 3)
none
>>>

>>>
(parseFloat("10.5")
.map(lambda x: x * 3)
.map(lambda x: x + 4)
.map(lambda x: x * x)
)
>>> ... ... ... ... some 1260.25
>>>

>>>
(parseFloat("10asdas.5")
.map(lambda x: x * 3)
.map(lambda x: x + 4)
.map(lambda x: x * x)
)
>>> ... ... ... ... none
>>>

>>> some("10.5").bind(parseFloat)
some 10.5
>>>

>>> some("1sdf0.5").bind(parseFloat)
none
>>>

>>> some("10.5").bind(parseFloat).map(lambda x: x + 10)
some 20.5
>>> some("10sdf.5").bind(parseFloat).map(lambda x: x + 10)
none
>>>

#
return opt_x.bind(lambda x:         #         opt_x >>= \x ->                bind opt_x (\x ->
opt_y.bind(lambda y:         #         opt_y >>= \y ->    ==>         bind opt_y (\y ->
Option(x + y)))   #         return (x + y)                 return (x + y)))

>>>
some 30
none
none
none
some 25.0
>>>
none
none
>>>
```

##### 1.14.5.1 Overview

The Either type is an extension of Maybe, it end a computation if any step fails. Unlike Maybe it can indicate the source of the error. It represents two values Right that holds a correct value (mneumonic "right" meaning correct) and the constructor Left that holds an error value.

The module Data.Either has combinators to manipulate the Either type.

```data Either a b = Left a | Right b deriving (Eq, Show)

return = Right

Right m >>= k = k m
Left e  >>= _ = Left e
```
##### 1.14.5.2 Example

```--  File: either_monad.hs
------------------------------

data ErrorCode =
ParserError
| InvalidInput
deriving (Eq, Show)

describeErrorCode ParserError  = "The parser failed."
describeErrorCode InvalidInput = "Input out function domain."

describeError (Right x)    = Right x
describeError (Left  code) = Left (describeErrorCode code)

parseDouble2 :: String -> Either ErrorCode Double
parseDouble2  str =
case (readMaybe str :: Maybe Double) of
Just x  ->  Right x
Nothing ->  Left  ParserError

sqrt_safe2 :: Double -> Either ErrorCode Double
sqrt_safe2 x =
if x >= 0
then (Right x)
else (Left InvalidInput)

addSafe1 :: Either err Double -> Either err Double -> Either err Double
x <- ex
y <- ey
return \$ x + y

addSafe2 :: Either err Double -> Either err Double -> Either err Double
ex >>= \x ->
ey >>= \y ->
return (x + y)

test1 input = do
x <- parseDouble2 input
y <- sqrt_safe2 x
return (x + y)

test2 input =
parseDouble2 input >>= \x ->
sqrt_safe2 x       >>= \y ->
return (x + y)

-- ----- End of File  --------------------
------------------------------------------
```

Repl:

```> :load /tmp/either_monad.hs

-- Playing with Return
--
> return 10 :: Either a Double
Right 10.0
>

> let returnEither x = Right x
>
> returnEither 10
Right 10

> returnEither 10.0
Right 10.0

> :t returnEither 10.0
returnEither 10.0 :: Fractional b => Either a b
>

> :t returnEither (10.0 :: Double)
returnEither (10.0 :: Double) :: Either a Double
>

---  Playing with bind operator
---

> Right 10 >>= \x -> Right (x + 5)
Right 15
>

> return 10 >>= \x -> Right (x + 5)
Right 15
>

> Right 10 >>= \x -> Left "It always will fail"
Left "It always will fail"
>

> Left "Computation failed" >>= \x -> Right (x + 5)
Left "Computation failed"
>

> return 5 >>= \x -> if x < 20 then Right (x + 5) else Left "Number out of range greater than 20"
Right 10
>
> return 30 >>= \x -> if x < 20 then Right (x + 5) else Left "Number out of range greater than 20"
Left "Number out of range greater than 20"
>

> return "100.23" >>= \x -> parseDouble2 x
Right 100.23
>
> return "1dsf00.23" >>= \x -> parseDouble2 x
Left ParserError
>

> test1 "100.0"
Right 200.0
>
>
> test1 "asd100.0"
Left ParserError
>
>
> test1 "-100"
Left InvalidInput
>

> test2 "100"
Right 200.0
>
> test2 "asdd10sd0"
Left ParserError
>
> test2 "-200"
Left InvalidInput
>

:: Either err Double -> Either err Double -> Either err Double
>

> addSafe1 (Right 100) (Right 200)
Right 300.0
>

> addSafe1 (Right 100) (Left "Error: second argument not a number")
Left "Error: second argument not a number"
>

> addSafe1 (Left "Error: first argument not a number") (Right 100)
Left "Error: first argument not a number"
>

> addSafe1 (parseDouble2 "200.0") (sqrt_safe2 100.0)
Right 300.0
>

> addSafe1 (parseDouble2 "200.0") (sqrt_safe2 (-100.0))
Left InvalidInput
>

> addSafe1 (parseDouble2 "2sdfs00.0") (sqrt_safe2 (-100.0))
Left ParserError
>

> addSafe2 (parseDouble2 "200.0") (sqrt_safe2 100.0)
Right 300.0
>

> describeError \$ addSafe2 (parseDouble2 "20asdas0.0") (sqrt_safe2 100.0)
Left "The parser failed."
>

> describeError \$ addSafe2 (parseDouble2 "2000.0") (sqrt_safe2 (-100.0))
Left "Input out function domain."
>

> import qualified Data.Either as E

-- Extracts from a list of Either all the Left elements All the Left
--   elements are extracted in order.
--
> E.lefts [Left "Error 1", Right 10, Left "Error 2", Right 200]
["Error 1","Error 2"]
>

-- Extracts from a list of Either all the Right elements All the Right
-- elements are extracted in order.
--
> E.rights  [Left "Error 1", Right 10, Left "Error 2", Right 200]
[10,200]
>

> E.partitionEithers  [Left "Error 1", Right 10, Left "Error 2", Right 200]
(["Error 1","Error 2"],[10,200])
>

--   Case analysis for the Either type. If the value is Left a, apply
--   the first function to a; if it is Right b, apply the second
--   function to b.
--

> :t E.either
E.either :: (a -> c) -> (b -> c) -> Either a b -> c
>

> E.either (\left -> left + 10) (\right -> right * 3) (Right 10)
30
>

> E.either (\left -> left + 10) (\right -> right * 3) (Left 10)
20
>

> let f = E.either (\left -> left + 10) (\right -> right * 3)
> :t f
f :: Either Integer Integer -> Integer
>

> f (Right 10)
30
> f (Left 10)
20
>
```

##### 1.14.6.1 IO Actions

The type IO indicates an action that when evaluated may perform some IO. The function `putChar :: Char -> IO ()` takes a char and returns an IO action that prints a char, no character is printed on the screen and no side-effect is performed. This IO action can be passed as a ordinary values to other IO actions and combined with other IO actions. IO actions only will be executed when called from the main IO action `main :: IO ()` or called from other IO actions called from main.

The values wrapped in an IO type like `getChar :: IO Char` can only be extracted inside an IO action.

Summary:

• The Haskell's IO is pure and lazy.
• The IO action type separates the definition from execution.
• All functions that returns IO actions are pure functions.
• There is no way to extract a value of an IO action outside an IO action.
• Only IO actions perform IO actions.
• The entry point of a Haskell program is the main IO action. Only the IO action executed from main will be executed.
• IO actions are not functions. IO actions are values that can be passed to functions and stored in data structures like any other value.
• IO Actions are commands. `_putSTrln "str"_` doesn't print a string. It actually creates a command to print a string that can be manipulated like a value, repeated, stored in data structures and passed to another IO actions.
• By typing the name of an IO action in the REPL (ghci) the user forces its execution.

• main is an IO action, not a function.
```main :: IO
main = do
putStrLn "hello"
```
• putStrLn is a function which takes a string and returns an IO action which produces nothing '()' unit value.
```putStrLn :: String -> IO ()
```
• printMsg is a IO action, that when executed, will print a string.
```printMsg :: IO ()
printMSg = putStrLn "Hello world"
```
• getLine is an IO action that when executed produces a string. It is not a function.
```getLine :: IO String
```
• readFile is a function that takes a string and returns an IO action which when executed produces a string.
```readFile :: FilePath -> IO String
```

Example: IO actions are execute only when forced to do so.

It is noticeable that:

• action2 neither action3 are executed and they don't print anything.
• Only the IO actions called from main are executed.
• The string returned by the IO action askQuestion can only be extracted inside an IO action.

```import System.IO (hFlush, stdout)

action1 :: IO ()
action1 = putStrLn "Say action 1 dummy"

-- action2 :: IO ()
action2 = putStrLn "Action2 won't be executed"

action3 :: IO ()
action3 = putStrLn "Action3 won't be executed"

newline :: IO ()
newline = putStrLn ""

-- prompt :: String -> IO String
prompt message = do
putStr message
hFlush stdout
line <- getLine
newline
newline
return line

askQuestion = prompt "> Enter a line: "

main :: IO ()
main = do
putStrLn "Hello world"
action1
putStrLn ("You entered the line: " ++ line)
```

Compiling and running:

```# Compiling

# Running the executable
#
Hello world
Say action 1 dummy
> Enter a line: Hola mundo. Muchas gracias Haskell!

You entered the line: Hola mundo. Muchas gracias Haskell!

# Executing in batch mode (script)
#
Hello world
Say action 1 dummy
> Enter a line: Hola mundo Haskell.

You entered the line: Hola mundo Haskell.
```

Example: IO Actions can be stored in data structures and passed as values

```:{
printFile :: String -> IO ()
printFile file = do
putStrLn content
:}

let printHello = putStrLn "Hello"
let printWorld = putStrLn "world"

let actionList = [printHello, printWorld, printFile "/etc/issue", print [1..10]]

Prelude> :t actionList
actionList :: [IO ()]
Prelude>

:{
runActions :: [IO()] -> IO ()
runActions ioList = do
case ioList of
[]              -> return ()
(ioAction:rest) -> do ioAction
runActions rest
:}

Prelude> runActions actionList
Hello
world
Manjaro Linux \r  (\n) (\l)

[1,2,3,4,5,6,7,8,9,10]
Prelude>

Prelude> let actions = [putStrLn "hello world (en)", putStrLn "hola mundo (es)", putStrLn "ola mundo (pt)"]
Prelude>

Prelude> :t actions
actions :: [IO ()]
Prelude>

Prelude> runActions actions
hello world (en)
hola mundo (es)
ola mundo (pt)
Prelude>

{- | Note that Haskell has a function for this: sequence_  -}

> :t sequence_
sequence_ :: (Foldable t, Monad m) => t (m a) -> m ()

> sequence_ actionList
Hello
world
Manjaro Linux \r  (\n) (\l)

[1,2,3,4,5,6,7,8,9,10]
>

> sequence_ actions
hello world (en)
hola mundo (es)
ola mundo (pt)
>

-- IO actions can be passed as values and manipulated as values
--
:{
doTimes :: Int -> IO () -> IO ()
doTimes n action = do
if n < 0
then error "Error: n cannot be negative"
else case n of
0   -> return ()
k   -> do action
doTimes (k - 1) action
:}

Prelude>  :t doTimes
doTimes :: Int -> IO () -> IO ()
Prelude>

Prelude> doTimes 3 (putStrLn "hello world")
hello world
hello world
hello world
Prelude>

Prelude> doTimes 8 (putStrLn "hello world")
hello world
hello world
hello world
hello world
hello world
hello world
hello world
hello world
Prelude>

> doTimes 3 (sequence_ actionList)
Hello
world
Manjaro Linux \r  (\n) (\l)

[1,2,3,4,5,6,7,8,9,10]
Hello
world
Manjaro Linux \r  (\n) (\l)

[1,2,3,4,5,6,7,8,9,10]
Hello
world
Manjaro Linux \r  (\n) (\l)

[1,2,3,4,5,6,7,8,9,10]
>
```

IO Actions allow to write functions that works like control structures.

```:{
myIF :: Bool -> IO () -> IO () -> IO ()
myIF cond actionThen actionElse =
if cond
then actionThen
else actionElse
:}

> myIF True (putStrLn "Turn on control valve") (putStrLn "Shutdown control valve")
Turn on control valve
>
> myIF False (putStrLn "Turn on control valve") (putStrLn "Shutdown control valve")
Shutdown control valve
>
>

:{
myWhen :: Bool -> IO () -> IO ()
myWhen cond action = if cond then action else return ()
:}

> myWhen True (putStrLn "Fire missiles")
Fire missiles
> myWhen False (putStrLn "Fire missiles")
>

>

{- | Read input from user until he provides a valid value. -}

:{
putStr prompt
input <- getLine
Nothing -> do putStrLn "Error: Enter a valid value."
Just x  -> return x
:}

>

> readUntil "> Enter a number: " :: IO Int
> Enter a number: dsfsd
Error: Enter a valid value.
> Enter a number: 234dsfsd
Error: Enter a valid value.
> Enter a number: 145
145
>
> readUntil "> Enter a Maybe number: " :: IO (Maybe Int)
> Enter a Maybe number: dsfsd
Error: Enter a valid value.
> Enter a Maybe number: 345sa
Error: Enter a valid value.
> Enter a Maybe number: 2343
Error: Enter a valid value.
> Enter a Maybe number: Just 100
Just 100
>

{- | IO Actions can be composed -}
:{
sumTwoNumbers :: IO ()
sumTwoNumbers = do
number1 <- readUntil "Enter number 1: " :: IO Int
number2 <- readUntil "Enter number 2: " :: IO Int
let s = number1 + number2
putStrLn ("The sum is equal to " ++ show s)
:}

> sumTwoNumbers
Error: Enter a valid value.
Enter number 1: 3423asd
Error: Enter a valid value.
Enter number 1:
Error: Enter a valid value.
Enter number 1: 1000^?^?
Error: Enter a valid value.
Enter number 1: 2-
Error: Enter a valid value.
Enter number 1: 200
Enter number 2: dsafs
Error: Enter a valid value.
Enter number 2: djgfh
Error: Enter a valid value.
Enter number 2: 300
The sum is equal to 500
>

>
> :t forever
forever :: Applicative f => f a -> f b
>
threadDelay :: Int -> IO ()
>

> forever (putStrLn "Hello world Haskell")
...  ... ... ...

-- 1s = 1e6 = 1000000 us delay
--
--
^CInterrupted.

--- Alternative way
---
:{
forever \$ do putStrLn "Hello world Haskell"
:}

>  :{
- forever \$ do putStrLn "Hello world Haskell"
- :}
... ... ... ...
```

It is not possible in a non-pure language. Example in F# (Fsharp).

```> let putStrLn s = printfn "%s" s ;;

val putStrLn : s:string -> unit

> let actions = [putStrLn "hello world" ; putStrLn "hola mundo" ; putStrLn "ola mundo"] ;;
hello world
hola mundo
ola mundo

val actions : unit list = [null; null; null]

(* It doesn't work.

myIF True (putStrLn "Turn on control valve") (putStrLn "Shutdown control valve")
*)

let myIF cond actionThen actionElse: unit =
if cond then actionThen else actionElse
;;

- myIF true (putStrLn "Turn on control valve") (putStrLn "Shutdown control valve") ;;
Turn on control valve
Shutdown control valve
val it : unit = ()

> myIF false (putStrLn "Turn on control valve") (putStrLn "Shutdown control valve") ;;
Turn on control valve
Shutdown control valve
val it : unit = ()
>

// It doesn't work
//
let myWhen cond fn = if cond then fn else ()

> myWhen true (putStrLn "Fire missiles") ;;
Fire missiles
val it : unit = ()

> myWhen false (putStrLn "Fire missiles") ;;
Fire missiles
val it : unit = ()
>
```

It is possible if the the function application is wrapped in a thunk:

```let putStrLn s = fun () -> printfn "%s" s
;;

val putStrLn : s:string -> unit -> unit

> let actions = [putStrLn "hello world" ; putStrLn "hola mundo" ; putStrLn "ola mundo"] ;;

val actions : (unit -> unit) list

let runActions actions =

runActions :: [IO()] -> IO ()
runActions ioList = do
case ioList of
[]              -> return ()
(ioAction:rest) -> do ioAction
runActions rest

*)

let rec runActions ioList = do
match ioList with
| []               -> ()
| (ioAction::rest) -> ioAction (); runActions rest
;;

- runActions ;;
val it : ((unit -> unit) list -> unit)

- runActions actions ;;
hello world
hola mundo
ola mundo
val it : unit = ()
>

let myIf cond actionThen actionElse : unit =
if cond
then actionThen ()
else actionElse ()
;;

val myIf : cond:bool -> actionThen:unit -> actionElse:unit -> unit

> myIf false (putStrLn "Turn on control valve") (putStrLn "Shutdown control valve") ;;
Shutdown control valve
val it : unit = ()

> myIf true (putStrLn "Turn on control valve") (putStrLn "Shutdown control valve") ;;
Turn on control valve
val it : unit = ()
>
```

The implementation details can abstracted by defining a type IO.

```type IO<'T> = IO of (unit -> 'T)

- let runIO (IO thunk) = thunk () ;;

val runIO : IO<'a> -> 'a

> let putStrLn s: IO<unit> = IO (fun () -> printfn "%s" s) ;;

val putStrLn : s:string -> IO<unit>

- putStrLn "hello world" ;;
val it : IO<unit>
>

- runIO (putStrLn "hello world") ;;
hello world
val it : unit = ()
>

- runIO <| putStrLn "hello world"  ;;
hello world
val it : unit = ()
>

let sequence_ (actions: IO<unit> list): IO<unit> =
let rec aux xs = match xs with
| []       -> ()
| io::rest -> runIO io ; aux rest
IO (fun () -> aux actions)
;;

val sequence_ : actions:IO<unit> list -> IO<unit>

>

- let actionList = [putStrLn "(en) hello world"; putStrLn "(es) hola mundo"; putStrLn "(pt) ola mundo"] ;;
val actionList : IO<unit> list =

// Creates a new IO actions that will execute each of the IO actions in the list
> let action = sequence_ actionList ;;

val action : IO<unit>

> runIO action ;;
(en) hello world
(es) hola mundo
(pt) ola mundo
val it : unit = ()
>

// F# operator (<|) is similar to Haskell operator (\$) dollar sign.
// To eliminate parenthesis.
//
- runIO <| sequence_  [putStrLn "(en) hello world"; putStrLn "(es) hola mundo"; putStrLn "(pt) ola mundo"] ;;
(en) hello world
(es) hola mundo
(pt) ola mundo
val it : unit = ()
>

let doTimes (n: int) (ioAction: IO<unit>): IO<unit> =
let rec aux n =
match n with
| _ when n < 0 -> failwith "Error: n cannot be negative"
| 0            -> ()
| k            -> runIO ioAction ; aux (k - 1)

IO (fun () -> aux n)

val doTimes : n:int -> ioAction:IO<unit> -> IO<unit>

> doTimes 3 (putStrLn "hello world") ;;
val it : IO<unit>

>
- doTimes 3 (putStrLn "hello world") |> runIO ;;
hello world
hello world
hello world
val it : unit = ()
>
```

The IO monad consists of the IO type constructor, the return (unit) function and the (>>=) bind operator implemented for the IO type constructor. It allows build IO actions from smaller IO actions and combine IO actions.

Description Function Signature
Bind operator (>>=) IO a -> (a -> IO b) -> IO b
Return function return a -> IO a
Operator >> (>>) IO a -> IO b -> IO b

Some IO Primitives:

Console Output Functions Console Input Functions
putChar :: Char -> IO () getChar :: Char -> IO ()
putStr :: String -> IO ()
putStrLn :: String -> IO () getLine :: IO String
print :: Show a => a -> IO () readLn :: Read a => IO a

Return function

The return function injects a value into an IO action or IO type constructor.

```return :: a -> IO a
```

Bind operator

The bind (>>=) operator extracts the value wrapped by the IO action and pass it to a monadic IO function.

```IO a >>= (a -> IO b) :: IO b
|        |
|        |
|         \----> Pass the value wrapped by type constructor to the monadic
|                function (fn :: a -> IO b) returning a new IO action of type IO b.
|
\----> Extracts the value (a) wrapped by the IO action

ma = mb >>= fn
```

Example:

```:{
dupLine = do
line <- getLine
putStrLn line
:}

Prelude M> dupLine
Prelude M>

{- | The value of IO action getLine is passed to the function putStrLn -}
let dupLine2 = getLine >>= putStrLn

Prelude M> dupLine2
Prelude M>

Prelude M> :t getLine
getLine :: IO String

Prelude M> :t putStrLn
putStrLn :: String -> IO ()
Prelude M>

readFile :: FilePath -> IO String
Prelude M> :t putStrLn
putStrLn :: String -> IO ()
Prelude M>

Prelude M> let showFile file = readFile file >>= putStrLn
Prelude M> showFile "/etc/issue"
Manjaro Linux \r  (\n) (\l)

:{
showFile2 file = do
putStrLn content
:}

Prelude M> showFile2 "/etc/issue"
Manjaro Linux \r  (\n) (\l)
```

Bind operator with return:

```> return "Print this line" >>= putStrLn
Print this line

> return "/etc/issue" >>= readFile >>= putStrLn
Manjaro Linux \r  (\n) (\l)
```

Operator (>>)

The (>>) operators runs two IO actions sequentially returning the result of the second IO action.

It is defined as

```action1 >> action2 = action1 >>= (\_ -> action2)
```

It is equivalent to in do-notation:

```do
action1
action2
```

Example:

```> return 10 >> return 20 :: IO Int
20
>

> getLine >> putStrLn "The line is discarded"

> putStrLn "haskell" >> putStrLn "fp" >> putStrLn "rocks"
fp
rocks
>

>  :t putStrLn "haskell" >> putStrLn "fp" >> putStrLn "rocks"
putStrLn "haskell" >> putStrLn "fp" >> putStrLn "rocks" :: IO ()

:{
action1 =
putStrLn "fp"      >>
putStrLn "rocks"
:}

>  :t action1
action1 :: IO ()
>  action1
fp
rocks
>

-- Equivalent code in do-notation
:{
action2 = do
putStrLn "fp"
putStrLn "rocks"
:}

> action2
fp
rocks
>
```

```:{
showFile :: IO ()
showFile = do
putStr "Enter a file: "
file    <- getLine
putStrLn content
:}

Prelude M> showFile
Enter a file: /etc/issue
Manjaro Linux \r  (\n) (\l)
```

The Haskell code above like is equivalent to the code below:

```:{
showFile :: IO ()
showFile =
putStr "Enter a file: "  >>= \ _       ->
getLine                  >>= \ file    ->
readFile file            >>= \ content ->
putStrLn content
:}

Prelude M> showFile
Enter a file: /etc/issue
Manjaro Linux \r  (\n) (\l)
```

Code:

```:{
sumTwoNumbers = do
putStr "Enter the first number: "
line1 <- getLine
putStr "Enter the second number: "
line2 <- getLine
let  x1 = read line1 :: Integer
let  x2 = read line2  :: Integer
let sum = x1 + x2
putStrLn ("The sum is " ++ show sum)
return sum
:}

-- SumTwonumbers dessugarized
--
:{
sumTwoNumbers_v2 =
putStr "Enter the first number: "     >>= \_      ->
getLine                               >>= \line1  ->
putStr "Enter the second number: "    >>= \_      ->
getLine                               >>=  \line2 ->
let x1 = read line1 :: Integer in
let x2 = read line2 :: Integer in
let sum = x1 + x2 in
putStrLn  ("The sum is " ++ show sum) >>= \_ ->
return sum
:}

--  Do-notation dessugarized simplified with operators (>>)
--
:{
sumTwoNumbers_v3 =
putStr "Enter the first number: "     >>
getLine                               >>= \line1  ->
putStr "Enter the second number: "    >>
getLine                               >>= \line2 ->
let x1 = read line1 :: Integer in
let x2 = read line2 :: Integer in
let sum = x1 + x2 in
putStrLn  ("The sum is " ++ show sum) >>
return sum
:}

:{
showResult :: IO Integer ->  IO ()
showResult inputAction = do
x <- inputAction
putStrLn ( "The result is " ++ show x)
:}
```

Running in the REPL:

```> sumTwoNumbers
Enter the first number: 100
Enter the second number: 200
The sum is 300
300
>
> :t sumTwoNumbers
sumTwoNumbers :: IO Integer
>

> sumTwoNumbers_v2
Enter the first number: 100
Enter the second number: 200
The sum is 300
300
>

> sumTwoNumbers_v3
Enter the first number: 100
Enter the second number: 200
The sum is 300
300

> :t sumTwoNumbers_v2
sumTwoNumbers_v2 :: IO Integer
>

> :t showResult
showResult :: IO Integer -> IO ()
>

-- It creates a new IO action.
--
> let action = showResult sumTwoNumbers
>
> action
Enter the first number: 100
Enter the second number: 200
The sum is 300
The result is 300
>

> :t action
action :: IO ()
>

-- The IO actions can be manipulated like values:
--
-------------------------------------------------
> :t mapM_
mapM_ :: Monad m => (a -> m b) -> [a] -> m ()
>

> mapM_ putStrLn ["line 0", "line 1", "line2", "line 3"]
line 0
line 1
line2
line 3
>

> let forEachPrint = mapM_ putStrLn
>
> :t forEachPrint
forEachPrint :: [String] -> IO ()
>
> forEachPrint put
putChar   putStr    putStrLn
> forEachPrint ["line 0", "line 1", "line2", "line 3"]
line 0
line 1
line2
line 3
>

> :t replicateM
replicateM :: Monad m => Int -> m a -> m [a]
>

> let askTwoTimes = replicateM 2 sumTwoNumbers
>

Enter the first number: 100
Enter the second number: 200
The sum is 300
Enter the first number: 300
Enter the second number: 90
The sum is 390
[300,390]
>
```
##### 1.14.6.3 IO Monad in OCaml

The IO monad cannot be implemented in Haskell since it is a primitive type. However by implementing it in OCaml is possible to understand how it works and get some intuition about IO actions and also understand how the monad combinators like (>>), sequence, sequence_ works. This implementation was designed to by as simple as possible.

```let replicate n x =
let rec aux count acc =
if count = 0
then acc
else aux (count - 1) (x::acc)

in aux n []
;;

module IO =
struct

(* Wraps an imperative function like
print_string into a thunk
*)
type 'a io = IO of (unit -> 'a)

(* Forces the evaluation of an IO action *)
let run: 'a io -> 'a =
fun (IO thunk) -> thunk ()

(* The same as Haskell return :: a -> m a *)
let unit: 'a -> 'a io  =
fun a -> IO ( fun () -> a)

let bind: 'a io -> ('a -> 'b io) -> 'b io =
fun io_a fn_io ->
IO (fun () -> let a = run io_a in
run (fn_io a))

let (>>=) = bind

(* (>>) :: m a -> m b -> m b
(>>) ma mb =
ma >>= \_ -> mb
*)
let (>>) ma mb =
ma >>= fun _ -> mb

(* Converts an output function into a
*)
let lift_output: ('a -> unit) -> ('a -> unit io) =
fun output_fn a -> IO (fun () -> output_fn a)

(* Converts an input function into a
*)
let lift_input: (unit -> 'a) -> 'a io =
fun fn_input -> IO fn_input

(*  fmap derived from IO Monad

fmap :: (a -> b) -> IO a -> IO b
fmap fn ma = do
a <- ma
return (fn a)

*)
let map fn ma =
ma   >>= fun a ->
unit (fn a)

sequence :: Monad m => [m a] -> m [a]
sequence = foldr mcons (return [])
where
mcons p q =
p >>= \x ->
q >>= \y ->
return (x:y)
*)
let sequence mlist =
let mcons p q =
p >>= fun x ->
q >>= fun y ->
unit (x::y)

in List.fold_right mcons mlist (unit [])

let sequence_ mlist =
List.fold_right (>>) mlist (unit ())

let replicateM_ n ma =
sequence_ (replicate n ma)

let replicateM n ma =
sequence (replicate n ma)

forever :: IO () -> IO *)
let rec forever (ma: unit io) =
(* let open IO in *)
IO ( fun () -> run  ma ;
let _ = run (forever ma)
in ()
)

let mapM: ('a -> 'b io) -> 'a list -> ('b list) io =
fun fn alst ->  sequence (List.map fn alst)

let mapM_: ('a -> unit io) -> 'a list -> unit io =
fun fn alst -> sequence_ (List.map fn alst)

(* ----- Primitive IO Functions --------- *)

let print_string = lift_output Pervasives.print_string

let print_char = lift_output Pervasives.print_char

let read_char = lift_input (fun ch ->
Pervasives.input_char  stdin)

(* val input_line : in_channel -> string *)

let input_line chan =
IO (fun () -> Pervasives.input_line chan)

let input_char chan =
IO (fun () -> Pervasives.input_char chan)

let open_in filename =
IO (fun () -> Pervasives.open_in filename)

let close_in chan =
IO (fun () -> Pervasives.close_in chan)
end
;;

module IO :
sig
type 'a io = IO of (unit -> 'a)
val run : 'a io -> 'a
val unit : 'a -> 'a io
val bind : 'a io -> ('a -> 'b io) -> 'b io
val ( >>= ) : 'a io -> ('a -> 'b io) -> 'b io
val ( >> ) : 'a io -> 'b io -> 'b io
val lift_output : ('a -> unit) -> 'a -> unit io
val lift_input : (unit -> 'a) -> 'a io
val map : ('a -> 'b) -> 'a io -> 'b io
val sequence : 'a io list -> 'a list io
val sequence_ : 'a io list -> unit io
val replicateM_ : int -> 'a io -> unit io
val replicateM : int -> 'a io -> 'a list io
val forever : unit io -> unit io
val mapM : ('a -> 'b io) -> 'a list -> 'b list io
val mapM_ : ('a -> unit io) -> 'a list -> unit io
val print_string : string -> unit io
val print_char : char -> unit io
val input_line : in_channel -> string io
val input_char : in_channel -> char io
val open_in : string -> in_channel io
val close_in : in_channel -> unit io
end
```

Tests:

```>  IO.print_string "\nHello world\n" ;;
- : unit IO.io = IO.IO <fun>

> let action = IO.print_string "\nHello world\n" ;;
val action : unit IO.io = IO.IO <fun>

>  action ;;
- : unit IO.io = IO.IO <fun>

>  IO.run action ;;

Hello world
- : unit = ()

> let open IO in print_string "Hello world" ;;
- : unit IO.io = IO.IO <fun>

> let open IO in run (print_string "Hello world") ;;
Hello world- : unit = ()

(*
echoDup = do
c <- getChar
putChar c
putChar c

echoDup = do                echoDup = do
getChar     >>= \c ->       getChar    >>= \c ->
putChar   c >>= \_ ->       putChar c  >>
putChar c                   putChar c

*)
let echoDup =
let open IO in
print_char c  >>
print_char c
;;

val echoDup : unit IO.io = IO.IO <fun>

#  echoDup ;;
- : unit IO.io = IO.IO <fun>

#  IO.run echoDup ;;
a
aa- : unit = ()

#   IO.run echoDup ;;
b
bb- : unit = ()
#

let make_prompt1 prompt =
let open IO in
print_string prompt            >>= fun _    ->
print_string "The line is :\n" >>= fun _    ->
print_string line              >>= fun _    ->
unit (String.length line)
;;
val make_prompt1 : string -> int IO.io = <fun>
#

let make_prompt2 prompt =
let open IO in
print_string prompt            >>
print_string "The line is :\n" >>
print_string line              >>
unit (String.length line)
;;
val make_prompt2 : string -> int IO.io = <fun>

let do3Times action =
let open IO in
action    >>
action    >>
action
;;
val do3Times : 'a IO.io -> 'a IO.io = <fun>

# let act = IO.print_string "\nHello world" ;;
val act : unit IO.io = IO.IO <fun>

# IO.run act ;;

Hello world- : unit = ()

# let act3times = do3Times act ;;
val act3times : unit IO.io = IO.IO <fun>

#  IO.run act3times ;;
Hello world
Hello world
Hello world- : unit = ()
#

#  IO.run action1 ;;
Tell your name :My name is Jack
The line is :
My name is Jack- : int = 15

>  IO.run (do3Times action1) ;;
The line is :
The line is :
The line is :
Caesar- : int = 6
#

let open IO in
unit (2 *a + b)
;;
val readTwoNumbers : int IO.io = IO.IO <fun>

# IO.replicateM_  5 (IO.print_string "\nHello World\n") ;;
- : unit IO.io = IO.IO <fun>
#
IO.run (IO.replicateM_  5 (IO.print_string "\nHello World\n")) ;;

Hello World

Hello World

Hello World

Hello World

Hello World
- : unit = ()
#

232
- : int = 232

- : int list IO.io = IO.IO <fun>

#  IO.run (IO.replicateM 4 IO.read_int) ;;
2
43
34
100
- : in

let echoLine =
let open IO in
print_string line
;;

val echoLine : unit IO.io = IO.IO <fun>

#  IO.run echoLine ;;
Hello world
Hello world- : unit = ()
#

#  IO.forever echoLine ;;
- : unit IO.io = IO.IO <fun>

# let echoLoop = IO.forever echoLine ;;
val echoLoop : unit IO.io = IO.IO <fun>

#  IO.run echoLoop ;;
line1
line1
line2
line2
line3
line3   (* Hit Ctrl + D *)
Exception: End_of_file.

#  IO.mapM ;;
- : ('a -> 'b IO.io) -> 'a list -> 'b list IO.io = <fun>

#  IO.mapM IO.print_string ["a"; "b"; "c"; "d"] ;;
- : unit list IO.io = IO.IO <fun>
#

#  IO.run (IO.mapM_ IO.print_string ["a"; "b"; "c"; "d"] );;
abcd- : unit = ()

# let open IO in replicateM_ 6 (print_string "\ntest") |> run ;;

test
test
test
test
test
test- : unit = ()
#
```

##### 1.14.7.1 Overview

The state monad represents stateful in purely functional way.

The state monad in Haskell 2010 standard is not implemented in a simple way like in Haskell 98 which breaks legacy codes from papers and old books based on the 98 standards. Now it is implemented as a combination of StateT monad transformer and Identity monad. Despite the implementation changes the behavior of State monad is the same as in the old one.

```type State s = StateT s Data.Functor.Identity.Identity

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

It is equivalent to:

`type State s a = s -> (a, s)`

```                      State tranformer function
|
----+------
type State s a = s -> (a, s)
|     |  |
|     |  +---> Next State
|     |
|     +------> Current Output
|
+------------> Current State

state transformer = s -> (a, s)
```

State transformer:

```  stateTransformer :: current state ->  (output, next state)

current  +---------------+
state    |  State        |    Next State
---> +               +-------->
|  Transformer  |
+---------+-----+
|
|
\ /
State output

StateFn :: State s a ==> s -> (a, s)

+---------+      +-----------+      +----------+       +----------+
S0    |         |   S1 |           |   S2 |          |    S3 |          |  S4 ...
---->+ StateFn +----->+  StateFn  +----->+ StateFn  +------>+ StateFn  +----->
|         |      |           |      |          |       |          |
+---+-----+      +-----+-----+      +----+-----+       +----+-----+
|  (a1, s1)        |     (a2, s2)    |    (a3, s3)      |
|                  |                 |                  |
\ /                \ /               \ /                \ /
a1                 a2                a3                a4

(a1, s1) = runState StateFn s0
(a2, s2) = runState StateFn s1
(a3, s3) = runState StateFn s2
...
```

state

Wraps a state transformer function of type `s -> (a, s)` into a State type constructor.

```state :: MonadState s m => (s -> (a, s)) -> m a

>>> let fnSt = (state \$ \s -> (s * 3, s + 2) ) :: State Int Int

>>> :t fnSt
fnSt :: State Int Int
>>>

>>> runState fnSt 1
(3,3)
>>> runState fnSt 0
(0,2)
>>> runState fnSt 2
(6,4)

{-
In the old implementation it was:

let fnSt = (State \$ \s -> (s * 3, s + 2)) :: State Int Int

It doesn't work anymore.
-}

>>> let fnSt = (State \$ \s -> (s * 3, s + 2) ) :: State Int Int

<interactive>:223:13:
Not in scope: data constructor ‘State’
Perhaps you meant one of these:
>>>
```

runState

Applies a state transformer type (State s a) to a current state and returns a new state and an output.

```runState :: State s a -> s -> (a, s)
```

evalState

Similar to runState, but returns only the output.

```evalState :: State s a -> s -> a
evalState = fst . runState
```

execState

Similar to runState, but returns only the next state.

```execState :: State s a -> s -> s
execState = snd . runState
```

return

Sets the output regardless of the current state:

```return a = State \$ \s ->  (a, s)

>>> let st = return 10 :: State Int Int
>>> runState st 0
(10,0)
>>> runState st 1
(10,1)
>>> runState st 2
(10,2)
>>>

>>> runState (return 10) 0
(10,0)
>>> runState (return 10) 1
(10,1)
>>> runState (return 10) 2
(10,2)
>>> runState (return 10) 3
(10,3)
>>> runState (return 10) 4
```

bind

Note: This is the old implementation with meaningful names. But with the same behavior as the new implementation.

```(>>=) :: State s a -> (a -> State s b) -> State s b
stateFn >>= stateMaker  =
State \$ \oldState -> let (result, newState) = runState stateFn oldState
in  runState (stateMaker result) newState
```

put

Set a state ignoring the output.

```put :: MonadState s m => s -> m ()

-- Old implementation:
--
put :: s -> State s ()
put s = State (\ _ -> ((), s))

>>> runState (put 10) 0
((),10)
>>> runState (put 10) 1
((),10)
>>> runState (put 10) 2
((),10)
>>> runState (put 10) 3
((),10)

>>> execState (put 10) 0
10
>>> execState (put 10) 1
10
>>> execState (put 10) 2
10
>>> execState (put 10) 3
10
>>>
```

get

Get the current state.

```get :: MonadState s m => m s

-- Old implementation:
--
get :: State s s
get = State (\s -> (s, s))

>>> runState get 0
(0,0)
>>> runState get 1
(1,1)
>>> runState get 2
(2,2)
>>> runState get 3
(3,3)
```

withstate

withState f m executes action m on a state modified by applying f. (Documentation)

```withState :: (s -> s) -> State s a -> State s a
withState f m = modify f >> m
```

fmap

Returns a new state transformer applying a function to the output of the old state transformer.

Note: This the old implementation without StateT. However it still works in the same way and still describes what the State functor does.

```instance Functor (State s) where

-- Applies a function to the state output.
--
-- fmap :: (a -> b) -> F a -> F b
--
-- fmap :: (a -> b) -> State s a -> State s b
fmap f fns =
State \$ \oldState -> let (output, newState) = runState fns oldState
in (f output, newState)
```

Example:

```>>> import Control.Monad.State
>>>

>>> :show language
with the following modifiers:
-XNoDatatypeContexts
-XNondecreasingIndentation
>>>

>>> :info State
type State s = StateT s Data.Functor.Identity.Identity

-- Check type signature
--
>>> :t state
state :: MonadState s m => (s -> (a, s)) -> m a
>>>

>>> :t evalState
evalState :: State s a -> s -> a
>>>

>>> :t evalState
evalState :: State s a -> s -> a
>>>

>>> :t runState
runState :: State s a -> s -> (a, s)
>>>

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

-- Code block to paste in the GHCI repl
--
--

>>> let postincrement = do { x <- get; put (x+1); return x }

>>> runState postincrement 1
(1,2)
>>> runState postincrement 2
(2,3)
>>> runState postincrement 3
(3,4)
>>>

:set +m

:{

let stFn :: Int -> (Int, Int)
stFn = \ currentState ->
let output = 2 * currentState in
let nextState = currentState + 1 in
(output, nextState)
:}

>>> :t stFn
stFn :: Int -> (Int, Int)
>>>

>>> stFn 1   -- S0 = 1 --> S1 = 2, output = 2
(2,2)
>>> stFn 2   -- S1 = 1 --> S2 = 3, output = 4
(4,3)
>>> stFn 3   -- S2 = 3 --> S3 = 4, output = 6
(6,4)
>>> stFn 4
(8,5)
>>> stFn 5
(10,6)
>>>

{- Now let's wrap inside the State type -}

:{
let stateFn1 ::  State Int Int
stateFn1 = state \$ \ st -> (2 * st, st + 1)
:}

>>> :t stateFn1
stateFn1 :: State Int Int
>>>

>>> runState stateFn1 1
(2,2)
>>> runState stateFn1 2
(4,3)
>>> runState stateFn1 3
(6,4)
>>> runState stateFn1 4
(8,5)
>>> runState stateFn1 5
(10,6)
>>>

>>> execState stateFn1 5 ---  snd (10, 6)
6
>>> evalState stateFn1 5 ---- fst (10, 6)
10
>>>

>>> runState (withState (\s -> s + 3) stateFn1) 1
(8,5)
>>> runState (withState (\s -> s + 3) stateFn1) 2
(10,6)
>>> runState (withState (\s -> s + 3) stateFn1) 3
(12,7)
>>> runState (withState (\s -> s + 3) stateFn1) 4
(14,8)
>>> runState (withState (\s -> s + 3) stateFn1) 5
(16,9)
>>>

type StState = Int
type StOutput = Int

:{
let stateFn2 :: State StState StOutput
stateFn2 =  state \$ \ st -> (2 * st, st + 1)

:}

>>> :t stateFn2
stateFn2 :: State StState StOutput
>>>

>>> runState stateFn2 0
(0,1)
>>> runState stateFn2 1
(2,2)
>>> runState stateFn2 2
(4,3)
>>> runState stateFn2 3
(6,4)
>>> runState stateFn2 4
(8,5)

>>> :t stateFn2
stateFn2 :: State StState StOutput
>>>

>>> :t runState stateFn2 4
runState stateFn2 4 :: (StOutput, StState)
>>>

:{

let stateFn3 :: State Int Int
stateFn3 = do
currentState <- get
put (currentState + 1)  --- put \$ currentState +  1
return (2 * currentState)
:}

>>> :t stateFn3
stateFn3 :: State Int Int
>>>

>>> runState stateFn3 0
(0,1)
>>> runState stateFn3 1
(2,2)
>>> runState stateFn3 2
(4,3)
>>> runState stateFn3 3
(6,4)
>>> runState stateFn3 4
(8,5)
>>> runState stateFn3 5
(10,6)
>>>

{- Do-notation dessugarized

cs : Stands for current state.
-}

:{
let stateFn4 :: State Int Int
stateFn4 =
get          >>= \  cs ->
put (cs + 1) >>= \  _  ->
return (2 * cs)
:}

>>> runState stateFn4 0
(0,1)
>>> runState stateFn4 1
(2,2)
>>> runState stateFn4 2
(4,3)
>>> runState stateFn4 3
(6,4)
>>> runState stateFn4 4
(8,5)
>>> runState stateFn4 5
(10,6)
>>>

>>> runState (fmap (\x -> x + 3) stateFn4) 0 -- 3 = (\x -> x + 3) 0
(3,1)
>>> runState (fmap (\x -> x + 3) stateFn4) 1 -- 5 = (\x -> x + 3) 2
(5,2)
>>> runState (fmap (\x -> x + 3) stateFn4) 2 -- 7 = (\x -> x + 4)
(7,3)
>>> runState (fmap (\x -> x + 3) stateFn4) 3
(9,4)
>>> runState (fmap (\x -> x + 3) stateFn4) 4
(11,5)
>>> runState (fmap (\x -> x + 3) stateFn4) 5
(13,6)

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

>>> let stateFnMap = fmap (\x -> x + 3) stateFn3
>>> :t stateFnMap
stateFnMap :: StateT Int Data.Functor.Identity.Identity Int
>>>

>>> runState stateFnMap 0
(3,1)
>>> runState stateFnMap 1
(5,2)
>>> runState stateFnMap 2
(7,3)
>>> runState stateFnMap 3
(9,4)
>>> runState stateFnMap 4
(11,5)
>>>
```

Example from the book Learn You a Haskell:

Simulating a stack:

```import Control.Monad.State

type Stack = [Int]

-- Each code block must be pasted into the repl (ghci)
--
:set +m

:{

let pop :: State Stack Int
pop = state \$ \(x:xs) -> (x, xs)
-- pop = State \$ \(x:xs) -> (x,xs)    (It doesn't work anymore in this way).
:}

>>> :t pop
pop :: State Stack Int
>>>

:{

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

:}

>>> :t push
push :: Int -> State Stack ()
>>>

:{
let stackManip = do
push 3
a <- pop
pop
:}

>>> :t stackManip
stackManip :: StateT Stack Data.Functor.Identity.Identity Int
>>>

>>> runState pop [1, 2, 3, 4]
(1,[2,3,4])
>>> runState pop [2, 3, 4]
(2,[3,4])
>>> runState pop [3, 4]
(3,)
>>> runState pop 
(4,[])
>>> runState pop []
*** Exception: <interactive>:20:19-36: Non-exhaustive patterns in lambda

>>> evalState pop [1, 2, 3, 4]
1
>>> evalState pop [2, 3, 4]
2

>>> execState pop [1, 2, 3, 4]
[2,3,4]
>>> execState pop [2, 3, 4]
[3,4]
>>>

>>> runState (push 3) [4, 5, 6]
((),[3,4,5,6])
>>> runState (push 10) [1, 4, 5, 6]
((),[10,1,4,5,6])
>>>

>>> runState stackManip [5,8,2,1]
(5,[8,2,1])
>>>

{-

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

-}

:{

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

:}

>>> :t stackStuff
stackStuff :: State Stack ()
>>>

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

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

Random numbers:

```>>> import Control.Monad.State
>>> import System.Random
>>>

{-
randomSt :: (RandomGen g, Random a) => State g a
randomSt = State random
-}
>>> let randomSt = state random
>>>
>>> :t randomSt
randomSt :: (MonadState s m, RandomGen s, Random a) => m a
>>>

>>> :t randomSt
randomSt :: (MonadState s m, RandomGen s, Random a) => m a
>>>

{-

threeCoins :: State StdGen (Bool,Bool,Bool)
threeCoins = do
a <- randomSt
b <- randomSt
c <- randomSt
return (a,b,c)
-}

:{

let threeCoins :: State StdGen (Bool,Bool,Bool)
threeCoins = do
a <- randomSt
b <- randomSt
c <- randomSt
return (a,b,c)
:}

>>> :t threeCoins
threeCoins :: State StdGen (Bool, Bool, Bool)
>>>

>>> runState threeCoins (mkStdGen 33)
((True,False,True),680029187 2103410263)
>>>
>>> runState threeCoins (mkStdGen 33)
((True,False,True),680029187 2103410263)
>>>

>>> import Data.List (unfoldr)
>>>
>>> :t unfoldr
unfoldr :: (b -> Maybe (a, b)) -> b -> [a]
>>>

{- Generates an infinite sequence of state output   -}

:{

let stateSeqOutput stateFn state0 =
unfoldr
( \s -> let (out, ns) = runState stateFn s
in Just (out, ns))
state0

:}

>>> :t stateSeqOutput
stateSeqOutput :: State b a -> b -> [a]
>>>

>>> take 4 \$ stateSeqOutput threeCoins (mkStdGen 33)
[(True,False,True),(True,True,True),(False,False,False),(True,False,True)]
>>>

>>> mapM_ print  \$  take 10 \$ stateSeqOutput threeCoins (mkStdGen 33)
(True,False,True)
(True,True,True)
(False,False,False)
(True,False,True)
(True,False,True)
(True,True,False)
(False,False,True)
(False,False,False)
(True,True,False)
(True,True,True)
>>>
```

Example: Fibonacci Sequence

The Fibonacci sequence is defined by the rule.

```a[n+2] = a[n+1] + a[n]

0
1
1 = 1 + 0
2  = 1 + 1
3  = 2 + 1
5 = 3 + 2
8 = 5 + 3
...

+-----+             +----+           +----+
S0   -->+ fn  +-----------> | fn +---------->| fn |------>  ....
(0, 1)   +--+--+ S1          +-+--+ S2        +-+--+ S3 (2, 3)
|  (1, 0 + 1)      |  (1, 2)        |
|  (1, 1)          |                |
\ /                \ /              \ /
output = 0 + 1     output = 1 + 1   output = 1 + 2
= 1                = 2              = 3
```

It needs to keep track of the two last numbers.

```import Control.Monad.State

--
fibgen :: State (Int, Int) Int
fibgen = do
a, b <- get
let c  = a + b
put (b, c)      -- set the new state
return c

-- Repl friendly version
--
:{
let fibgen :: State (Int, Int) Int
fibgen = do
(a, b) <- get
let c  = a + b
put (b, c)      -- set the new state
return c
:}

>>> :t fibgen
fibgen :: State (Int, Int) Int
>>>

>>> runState fibgen (0, 1)
(1,(1,1))
>>> runState fibgen (1, 1)
(2,(1,2))
>>> runState fibgen (1, 2)
(3,(2,3))
>>> runState fibgen (2, 3)
(5,(3,5))
>>> runState fibgen (3, 5)
(8,(5,8))
>>> runState fibgen (5, 8)
(13,(8,13))
>>>

>>> evalState fibgen (5, 8)
13
>>> execState fibgen (5, 8)
(8,13)
>>>

:{
let fibgen2 :: State (Int, Int) Int
fibgen2 = state \$ \ (a, b) -> let c = a + b in (c, (b, c))

:}

>>> runState fibgen2 (0, 1)
(1,(1,1))
>>> runState fibgen2 (1, 1)
(2,(1,2))
>>> runState fibgen2 (1, 2)
(3,(2,3))
>>> runState fibgen2 (2, 3)
(5,(3,5))
>>> runState fibgen2 (3, 5)
(8,(5,8))
>>> runState fibgen2 (5, 8)
(13,(8,13))
>>>

{- Generating the state sequence

-}

>>> import Data.List (unfoldr)
>>>
>>> :t unfoldr
unfoldr :: (b -> Maybe (a, b)) -> b -> [a]
>>>

:{
let fibseq =
unfoldr (\s -> let (out, ns) = runState fibgen s
in Just (out, ns)) (0, 1)
:}

>>> :t fibseq
fibseq :: [Int]
>>>

>>> take 20 fibseq
[1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946]
>>>
```
##### 1.14.7.3 State monad in OCaml

Implementation:

```(* stfn - Stands for state transformer *)

module State =
struct

type ('s, 'a) state = ST of ('s -> 'a * 's)

(* Runs  the state transformer

runState
*)
let run (ST stfnt) s = stfnt s

(* Gets only the result and discards the
the next state.

evalState
*)
let eval stfn s = fst (run stfn s)

(* Gets only the next state and drops the
result

execState
*)
let exec stfn s = snd (run stfn s)

let put s = ST (fun _ -> ((), s))

let get = ST (fun s -> (s, s))

(* return a = State \$ \s -> (a, s) *)
let unit a = ST (fun s -> (a, s))

let bind stfn stfnMaker =
ST ( fun currentState ->
let (result, newState) = run stfn currentState
in run (stfnMaker result) newState
)

(* fmap *)
let map fn stfn =
ST (fun currentState ->
let (result, newState) = run stfn currentState
in (fn result, newState)
)

let (>>=) = bind

let (<\$>) = map

let (>>) ma mb =
ma >>= fun _ -> mb

let sequence mlist =
let mcons p q =
p >>= fun x ->
q >>= fun y ->
unit (x::y)
in List.fold_right mcons mlist (unit [])

(* Applicative Functor - Haskell <\$>  *)
let (<*>) m_fn ma =
m_fn     >>= fun fn ->
ma       >>= fun a  ->
unit (fn a)

let liftM2 fn ma mb =
ma      >>= fun a ->
mb      >>= fun b ->
unit (fn a b)

let liftM3 fn ma mb mc =
ma     >>= fun a ->
mb     >>= fun b ->
mc     >>= fun c ->
unit (fn a b c)

let mapM fn alst =
sequence (List.map fn alst)

end
;;

module State :
sig
type ('s, 'a) state = ST of ('s -> 'a * 's)
val run : ('a, 'b) state -> 'a -> 'b * 'a
val eval : ('a, 'b) state -> 'a -> 'b
val exec : ('a, 'b) state -> 'a -> 'a
val put : 'a -> ('a, unit) state
val get : ('a, 'a) state
val unit : 'a -> ('b, 'a) state
val bind : ('a, 'b) state -> ('b -> ('a, 'c) state) -> ('a, 'c) state
val map : ('a -> 'b) -> ('c, 'a) state -> ('c, 'b) state
val ( >>= ) : ('a, 'b) state -> ('b -> ('a, 'c) state) -> ('a, 'c) state
val ( <\$> ) : ('a -> 'b) -> ('c, 'a) state -> ('c, 'b) state
val ( >> ) : ('a, 'b) state -> ('a, 'c) state -> ('a, 'c) state
val sequence : ('a, 'b) state list -> ('a, 'b list) state
val ( <*> ) : ('a, 'b -> 'c) state -> ('a, 'b) state -> ('a, 'c) state
val liftM2 :
('a -> 'b -> 'c) -> ('d, 'a) state -> ('d, 'b) state -> ('d, 'c) state
val liftM3 :
('a -> 'b -> 'c -> 'd) ->
('e, 'a) state -> ('e, 'b) state -> ('e, 'c) state -> ('e, 'd) state
val mapM : ('a -> ('b, 'c) state) -> 'a list -> ('b, 'c list) state
end
#
```

Tests:

Basic Example:

```let stFn =
let open State in
ST (fun s -> (2 * s, s + 1))
;;
val stFn : (int, int) State.state = State.ST <fun>

#  State.run stFn 1 ;;
- : int * int = (2, 2)
#
State.run stFn 2 ;;
- : int * int = (4, 3)
# State.run stFn 3 ;;
- : int * int = (6, 4)
# State.run stFn 4 ;;
- : int * int = (8, 5)
# State.run stFn 5 ;;
- : int * int = (10, 6)
# State.run stFn 6 ;;
- : int * int = (12, 7)
#

# State.eval stFn 6 ;;
- : int = 12
#
# State.exec stFn 6 ;;
- : int = 7
#

# let stFn2 =
let open State in
map (fun x -> x + 3) stFn
;;
val stFn2 : (int, int) State.state = State.ST <fu

#  State.run stFn2 1 ;;
- : int * int = (5, 2)

#  State.run stFn2 2 ;;
- : int * int = (7, 3)

# State.run stFn2 3 ;;
- : int * int = (9, 4)

# State.run stFn2 4 ;;
- : int * int = (11, 5)

# State.run stFn2 5 ;;
- : int * int = (13, 6)

# let fn x = x + 3 ;;
val fn : int -> int = <fun>

# State.run (State.map fn stFn) 1 ;;
- : int * int = (5, 2)
# State.run (State.map fn stFn) 2 ;;
- : int * int = (7, 3)
# State.run (State.map fn stFn) 3 ;;
- : int * int = (9, 4)
# State.run (State.map fn stFn) 4 ;;
- : int * int = (11, 5)
#

:{

let stateFn3 :: State Int Int
stateFn3 = do
currentState <- get
put (currentState + 1)  --- put \$ currentState +  1
return (2 * currentState)
:}

----------------------------------------

*)

let stFn3 =
let open State in
get          >>=  fun cs ->
put (cs + 1) >>=  fun _  ->
unit (2 * cs)
;;

val stFn3 : (int, int) State.state = State.ST <fun>

let stFn4 =
let open State in
get          >>=  fun cs ->
put (cs + 1) >>
unit (2 * cs)
;;

val stFn4 : (int, int) State.state = State.ST <fun>

# State.run stFn3 1 ;;
- : int * int = (2, 2)
# State.run stFn3 2 ;;
- : int * int = (4, 3)
# State.run stFn3 3 ;;
- : int * int = (6, 4)
# State.run stFn3 4 ;;
- : int * int = (8, 5)
# State.run stFn3 5 ;;
- : int * int = (10, 6)
#

# State.run stFn4 1 ;;
- : int * int = (2, 2)
# State.run stFn4 2 ;;
- : int * int = (4, 3)
# State.run stFn4 3 ;;
- : int * int = (6, 4)
# State.run stFn4 4 ;;
- : int * int = (8, 5)
# State.run stFn4 5 ;;
- : int * int = (10, 6)
#
```

Simulating a Stack:

```(* type Stack = [Int]  *)

type stack = int list

(* With type signature *)
let pop: (stack, int) State.state =
let open State in
ST ( fun (x::xs) -> (x, xs) )

;;
val pop : (stack, int) State.state = State.ST <fun>

(* Without type signature *)

let pop =
let open State in
ST (fun (x::xs) -> (x, xs))
;;

let push: int -> (stack, unit) State.state =
let open State in
fun a -> ST ( fun  xs -> ((), a::xs) )
;;

val push : int -> (stack, unit) State.state = <fun>

(*
:{
let stackManip = do
push 3
a <- pop
pop
:}
*)

let stackManip =
let open State in
push 3   >>
pop      >>= fun a ->
pop
;;

val stackManip : (stack, int) State.state = State.ST <fun>

#  State.run pop [1; 2; 3; 4] ;;
- : int * int list = (1, [2; 3; 4])

# State.run pop [2; 3; 4] ;;
- : int * int list = (2, [3; 4])

(*

:{

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

*)

let stackStuff =
let open State in
pop         >>= fun a ->
if a = 5
then push 5
else (
push 3  >>
push 8
)
;;

val stackStuff : (stack, unit) State.state = State.ST <fun>

# State.run stackStuff [9; 0; 2; 1; 0] ;;
- : unit * stack = ((), [8; 3; 0; 2; 1; 0])
#
```

##### 1.14.8.1 Overview

A common problem in software development is propagate configuration, or global immutable state throughout the code. For instance, modular arithmetic needs the modulus configuration; numerical code needs the tolerance and maximum number of iterations and a web server needs at least the database configuration and the directory which contains static files.

The problem of propagating and supporting multiple configurations (aka run-time preferences) is known as the configuration problem.

In many programming languages, a naive solution to the configuration problem would be global variables, however this approach doesn't allow multiple sets of configurations to coexist and also a global variable may be changed by any part of the program make it unpredictable and hard to understand. An alternative solution to this problem is to bundle all configuration parameters into a single configuration parameter and pass it around explicitly as a function argument or pass the configuration bundle implicitly with the Reader monad.

The reader monad solves the configuration problem by making the configuration (aka enviroment) or global immutable state implicit and hiding it.

As the new implementation of the Reader monad is based on monad transformer, this section will use a more simple implementation similar to the old one for the sake of making the concept easier to understand.

Signaures:

Signature Description

Reader r a - Encapsulates a function or computation from a to b.

runReader Reader r a -> r -> a Run computation encapsulated by Reader r a applying it to the configuration r.

return a -> (Reader r) a Returns a constant function wrapped by Reader that always returns a
,no matter the value r.

fmap (a -> b) -> (Reader r) a -> (Reader r) b Apply a function (a -> b) to the result of computation Reader r a.

local (r -> r) -> Reader r a -> Reader r a Modify environment by applying a function to it.

```newtype Reader r a = Reader {runReader :: r -> a}

--
-- fmap is the function compsition between function fn and
--
-- fmap :: (a -> b) -> (Reader r) a -> (Reader r) b
--
fmap fn (Reader rToA) = Reader \$ \ r -> fn \$ rToA r

{- |
pure :: Applicative f => a -> f a
pure :: a -> (Reader r) a
-}
pure a = Reader \$ \_ -> a

{- | (<*>) :: Applicative f => f (a -> b) -> f a -> f b
-}
Reader \$ (\r -> let a     = rToA r in
let fAtoB = fn r   in
fAtoB a
)

{- | return :: a -> (Reader r) a  -}
return a = Reader \$ \ _ -> a

{- |

(>>=) :: (Monad m) => m a -> (a -> m b) -> m b

-}
Reader \$ \ r -> let a = rToA r

{- | Read environment, aka configuration. -}

local :: (r -> r) -> Reader r a -> Reader r a
local fn (Reader rToA) = Reader \$ \ r -> rToA (fn r)
```

Load the code in the REPL:

```>
```
```> :t Reader
>

{-
returns a constant function which, regardless of the input, always
returns the same value.
-}

> let x = return 10 :: Reader Int Int
>
10
it :: Int
10
it :: Int
10
it :: Int
>

let greetUser1 user =  "Hello " ++ user ++ "! Welcome to the FP world!"

> greetUser1 "John"
"Hello John! Welcome to the FP world!"
it :: [Char]
>

:{
greetUser2  =  Reader (\ user ->
"Hello " ++ user ++ "! Welcome to the FP world!"
)
:}

"Hello Beowulf! Welcome to the FP world!"
it :: String
>

:{
greetUser3 = do
return \$ "Hello " ++ user ++ "! Welcome to the FP world!"
:}

"Hello Beowulf! Welcome to the FP world!"
it :: String
>

:{
talkToUser = do
msga <- greetUser2
msgb <- greetUser3
return \$ do
putStrLn \$ "User name is " ++ user
putStrLn msga
putStrLn msgb
:}

User name is John
Hello John! Welcome to the FP world!
Hello John! Welcome to the FP world!
it :: ()
>

-- Apply the function length to the output of greetUser3 computation
--
"Hello John! Welcome to the FP world!"
it :: String
> length \$ runReader greetUser3 "John"
36
it :: Int
>

> runReader (fmap length greetUser2) "John"
36
it :: Int
> runReader (fmap length greetUser3) "John"
36
it :: Int
>
```
##### 1.14.8.4 Example: Configuration problem example - Arithmetic

The goal of this example is to perform mudular arithmetic computations to be used with multiple moduli hiding the modulus parameter as much as possible.

Example 1: Configuration problem with parameter passing approach.

The configuration modulus which all computations depends on is passed as function argument instead of being passed as a global value or variable. Example taken from - Functional Pearl: Implicit Configurations http://okmij.org/ftp/Haskell/tr-15-04.pdf

```>

> add1 m a b = mod (a + b) m
add1 :: Integral a => a -> a -> a -> a
>

> mul1 m a b = mod (a * b) m
mul1 :: Integral a => a -> a -> a -> a
>

> test1 m a b = add1 m (mul1 m a a) (mul1 m b b)
test1 :: Integral a => a -> a -> a -> a
>

-- Modulus set to 120
--
48
it :: Integral a => a
>
> mul1 120 975 873
15
it :: Integral a => a
>

> test1 120 975 873
114
it :: Integral a => a
>

-- Modulus set to 327
--
213
it :: Integral a => a
>
> mul1 327 975 873
321
it :: Integral a => a
>
> test1 327 975 873
255
it :: Integral a => a
>
```

This approach allows the computation results to be reused easily with multiple modulus or configurations. In addition, new computations can be defined from previous computations with implicit modulus parameter.

```>

--

:{
add2 :: Integral a => a -> a -> Reader a a
add2 a b = Reader (\m -> mod (a + b) m)
:}

:{
mul2 :: Integral a => a -> a -> Reader a a
mul2 a b = do
return \$  mod (a * b) m
:}

-- The configuration modulus is passed implicitly.
--
:{
test2 :: Integral a => a -> a -> Reader a a
test2 a b = do
x <- mul2 a a
y <- mul2 b b
return s
:}

-- The result of the computations r1, r2 and r3 can be reused with
-- multiple modulus or multiple configurations.
--
> r1 = add2 975 873
r1 :: Integral a => Reader a a

48
it :: Integral a => a

213
it :: Integral a => a
>

> map (runReader r1) [120, 327, 28, 17]
[48,213,0,12]
it :: Integral b => [b]
>

> r2 = mul2 975 873
r2 :: Integral a => Reader a a
>

> r3 = test2 975 873
r3 :: Integral a => Reader a a
>

> map (runReader r3) [127, 327, 28, 17, 97]
[32,255,22,4,25]
it :: Integral b => [b]
>
```

Example 4: The modular arithmetic can be made less verbose if an instance of type class Num is defined for the type synonym Modulus.

• Note: The code below works with Control.Monad.Read too. Just replace the `:load src/readerMonad.hs` with `import Control.Monad.Read`.
```>

:set -XRankNTypes
type Modulus m = forall a. Integral a => Reader a a

:{
normalize :: Integral a => a -> Reader a a
normalize x = do
return \$ mod x m
:}

-- Modular arithmetic equality
--
:{
(===) :: (Integral a) => Modulus a -> Modulus a -> Reader a Bool
(===) ma mb = do
a <- ma
b <- mb
return \$ a == b
:}

{-

> :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 | (-)) #-}

-}

:{
instance (Integral a) => Num (Reader a a) where
fromInteger x = normalize (fromIntegral x)

ma + mb = do
a <- ma
b <- mb
normalize (a + b)

ma - mb = do
a <- ma
b <- mb
normalize (a - b)

ma * mb = do
a <- ma
b <- mb
normalize (a * b)

signum = error "Not implemented"
abs    = error "Not implemented"
:}

{- | --------- Tests ----------- -}

> let x = 38 :: Modulus a
x :: Integral a => Reader a a

> let y = 23 :: Modulus a
y :: Integral a => Reader a a

8
it :: Integral a => a

8
it :: Integral a => a
>

> m = 38 === 23
m :: Integral a => Reader a Bool
>
True
it :: Bool
>
> runReader (8 === 3) 5
True
it :: Bool
>

> let x = 975 + 873 :: Integral a => Reader a a
x :: Integral a => Reader a a
>
48
it :: Integral a => a
213
it :: Integral a => a
>

> let r1 = 975 + 873 :: Modulus a
r1 :: Integral a => Reader a a
>
48
it :: Integral a => a
213
it :: Integral a => a
>

:{
test3 :: Modulus a -> Modulus a -> Modulus a
test3 a b = a * a + b * b
:}

> let r3 = test3 975 873
r3 :: Integral a => Reader a a
>

114
it :: Integral a => a
>
255
it :: Integral a => a
>
>  map (runReader r3) [127, 327, 28, 17, 97]
[32,255,22,4,25]
it :: Integral b => [b]
>
```
##### 1.14.8.5 References

Solutions to Configuration Problem

Global Variables

The writer monad makes possible to compose functions which returns values and a log string.

The writer monad in no longer implemented in a simple way like in Haskell 98. It is now implemented as special case of the WriterT monad transformer.

New implementation of type constructor Writer:

```>>> import Control.Monad.Writer
>>>

>>> :info Writer
type Writer w = WriterT w Identity
>>>
```

Old implementation of type constructor Writer: (Book: Learn You a Haskell)

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

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

Example:

```-- Haskell v7.10.2
--
>>>

>>> :t writer
writer :: MonadWriter w m => (a, w) -> m a
>>>
>>> :t runWriter
runWriter :: Writer w a -> (a, w)
>>>
>>> :t execWriter
execWriter :: Writer w a -> w
>>>
>>> :t tell
tell :: MonadWriter w m => w -> m ()
>>>

>>> writer (10, "The value is " ++ show 10) :: Writer String Int
WriterT (Identity (10,"The value is 10"))
>>>

>>> let w = writer (10, "The value is " ++ show 10) :: Writer String Int
>>> w
WriterT (Identity (10,"The value is 10"))
>>>

>>> runWriter w
(10,"The value is 10")
>>>

>>> execWriter w
"The value is 10"
>>>

>>> :t tell
tell :: MonadWriter w m => w -> m ()
>>>

>>> :t writer
writer :: MonadWriter w m => (a, w) -> m a

:set +m

:{
let fn1 :: Int -> Writer String Int
fn1 x = writer (2 * x, "The value of x is : " ++ show x)
:}

>>> :t fn1
fn1 :: Int -> Writer String Int
>>>

>>> fn1 2
WriterT (Identity (4,"The value of x is : 2"))
>>>
>>> fn1 3
WriterT (Identity (6,"The value of x is : 3"))
>>>

>>> runWriter \$ fn1 2
(4,"The value of x is : 2")
>>> runWriter \$ fn1 3
(6,"The value of x is : 3")
>>>

>>> fst . runWriter \$ fn1 2
4
>>> fst . runWriter \$ fn1 3
6
>>>

>>> snd . runWriter \$ fn1 2
"The value of x is : 2"
>>> snd . runWriter \$ fn1 3
"The value of x is : 3"
>>>

>>> execWriter \$ fn1 3
"The value of x is : 3"
>>> execWriter \$ fn1 2
"The value of x is : 2"
>>>

>>> return 1 :: Writer String Integer
WriterT (Identity (1,""))
>>>
>>> return 100 :: Writer String Integer
WriterT (Identity (100,""))
>>>

>>> return (Just 100) :: Writer String (Maybe Integer)
WriterT (Identity (Just 100,""))
>>>

>>> runWriter (return 100 :: Writer String Integer)
(100,"")
>>>

--
-- This version must be loaded from a file.
--
fn2 :: Int -> Writer String Int
fn2 x = do --writer (2 * x, "The value of x is : " ++ show x)
tell ( "The value of x is : " ++ show x )
return ( 2 * x )

---
--- This version can be pasted in the repl
---
:{
let fn2 :: Int -> Writer String Int
fn2 x = do --writer (2 * x, "The value of x is : " ++ show x)
tell ( "The value of x is : " ++ show x )
return ( 2 * x )
:}

>>> :t fn2
fn2 :: Int -> Writer String Int
>>>

>>> fn2 2
WriterT (Identity (4,"The value of x is : 2"))
>>> fn2 3
WriterT (Identity (6,"The value of x is : 3"))
>>>

{- Example from Learn You a Haskell

logNumber :: Int -> Writer [String] Int
logNumber x = Writer (x, ["Got number: " ++ show x])
-}
:{

let logNumber :: Int -> Writer [String] Int
logNumber x = writer (x, ["Got number: " ++ show x])
:}

>>> :t logNumber
logNumber :: Int -> Writer [String] Int
>>>

>>> logNumber 1
WriterT (Identity (1,["Got number: 1"]))
>>>
>>> logNumber 2
WriterT (Identity (2,["Got number: 2"]))
>>>

>>> runWriter \$ logNumber 1
(1,["Got number: 1"])
>>>

-
multWithLog :: Writer [String] Int
multWithLog = do
a <- logNumber 3
b <- logNumber 5
return (a*b)

:{
let multWithLog :: Writer [String] Int
multWithLog = do
a <- logNumber 3
b <- logNumber 5
return (a*b)
:}

>>> :t multWithLog
multWithLog :: Writer [String] Int
>>>

>>> multWithLog
WriterT (Identity (15,["Got number: 3","Got number: 5"]))
>>>

>>> runWriter multWithLog
(15,["Got number: 3","Got number: 5"])
>>>

>>> execWriter multWithLog
["Got number: 3","Got number: 5"]
>>>

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

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

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

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

:{
let multWithLog2 :: Writer [String] Int
multWithLog2 =
logNumber 3                       >>= \a ->
logNumber 5                       >>= \b ->
tell ["Gonna multiply these two"] >>= \_ ->
return (a*b)
:}

>>> :t multWithLog2
multWithLog2 :: Writer [String] Int
>>>
>>> runWriter multWithLog2
(15,["Got number: 3","Got number: 5","Gonna multiply these two"])
>>>

gcd' :: Int -> Int -> Writer [String] Int
gcd' a b
| b == 0 = do
tell ["Finished with " ++ show a]
return a
| otherwise = do
tell [show a ++ " mod " ++ show b ++ " = " ++ show (a `mod` b)]
gcd' b (a `mod` b)

:{

let gcd' :: Int -> Int -> Writer [String] Int
gcd' a b
| b == 0 = do
tell ["Finished with " ++ show a]
return a
| otherwise = do
tell [show a ++ " mod " ++ show b ++ " = " ++ show (a `mod` b)]
gcd' b (a `mod` b)

:}

>>> :t gcd'
gcd' :: Int -> Int -> Writer [String] Int
>>>

>>> gcd' 100 40
WriterT (Identity (20,["100 mod 40 = 20","40 mod 20 = 0","Finished with 20"]))
>>>

>>> runWriter \$ gcd' 100 40
(20,["100 mod 40 = 20","40 mod 20 = 0","Finished with 20"])
>>>

>>>

>>>
>>> mapM_ putStrLn \$ snd \$ runWriter \$ gcd' 8 3
8 mod 3 = 2
3 mod 2 = 1
2 mod 1 = 0
Finished with 1
>>>

>>> mapM_ putStrLn \$ snd \$ runWriter \$ gcd' 100 68
100 mod 68 = 32
68 mod 32 = 4
32 mod 4 = 0
Finished with 4
>>>

gcdReverse :: Int -> Int -> Writer [String] Int
gcdReverse a b
| b == 0 = do
tell ["Finished with " ++ show a]
return a
| otherwise = do
result <- gcdReverse b (a `mod` b)
tell [show a ++ " mod " ++ show b ++ " = " ++ show (a `mod` b)]
return result

:{
let gcdReverse :: Int -> Int -> Writer [String] Int
gcdReverse a b
| b == 0 = do
tell ["Finished with " ++ show a]
return a
| otherwise = do
result <- gcdReverse b (a `mod` b)
tell [show a ++ " mod " ++ show b ++ " = " ++ show (a `mod` b)]
return result

:}

>>> :t gcdReverse
gcdReverse :: Int -> Int -> Writer [String] Int
>>>

>>> mapM_ putStrLn \$ snd . runWriter \$ gcdReverse 39 106
Finished with 1
5 mod 1 = 0
6 mod 5 = 1
11 mod 6 = 5
28 mod 11 = 6
39 mod 28 = 11
106 mod 39 = 28
39 mod 106 = 39
>>>
```

## 2 Functional Languages

Note: There is no consensus about what really is a functional language. In this table were selected programming languages which can be programmed in functional-style or favors this style.

Some Functional programming languages:

Language Evaluation Typing Type Inference Pattern Matching Syntax Sugars GIL TCO OO AGDT Platform Family Currying Feature
Haskell Lazy Static Yes Yes Yes No Yes No Yes NAT ML/SML Yes Concurrency, Parallelism and Purity
Ocaml Strict Static Yes Yes Yes Yes Yes Yes Yes NAT/BC ML/SML Yes
F# (F sharp) Strict Static Yes Yes Yes No Yes Yes Yes .NET ML/SML Yes .NET Integration
Scheme Strict Dynamic No No Yes/ Macros * Yes No No - Lisp No Minimalist Educational
Clojure Strict Dynamic No Yes. Destructuring and macros Yes/ Macros No No No No JVM Lisp No Java integration + Macros
Scala Strict Static Yes Yes Yes No Yes Yes Yes JVM   Yes Java integration + Type safety
Erlang Strict Dynamic ? Yes Yes No Yes ? ? VM/Bytecode   ? Telecommunications, Servers, Concurrency
Elixir Strict Dynamic ? Yes Yes No Yes ? ? Erlang VM - ? Erlang VM + macros
Python Strict Dynamic No No No Yes No Yes No VM/Bytecode - No Libraries and easier to use.

JavaScript Strict Dynamic No No No ?* No Yes No VM/Interpreted *Lisp/ Scheme No The only language allowed to run in the browser.
R Strict Dynamic No No No ? No Yes - VM/Bytecode *Lisp/ Scheme No DSL - Statistics
Mathematica Strict Dynamic Yes ? ? ? ?? ? ? ?   No DSL - Computer Algebraic System

Notes:

• AGDT - Algebraic Data Types
• GIL - Global Interpreter Locking. Languages with GIL cannot take advantage of multi-core processors.
• TCO - Tail Call Optimization. Languages without TCO cannot perform recursion safely. It can lead to a stack overflow for a big number of iterations.
• JVM - Java Virtual Machine / Java Platform
• .NET - Dot Net Platform: CLR - Virtual Machine
• NAT - Native Code. Native code is not portable like a virtual machine, its execution is constrained to the processor architecture and to the system calls of the operating system.
• VM - Virtual Machine
• OO - Object Orientated
• Currying - Curried functions like in Haskell, F# and Ocaml
• DSL - Domain Specific Language
• Syntax Sugars help increase expressiveness and to write shorter, concise and more readable code.
• Short lambda functions:
• Haskell: (\ x y -> 3 * x + y)
• Ocaml and F# (fun x y -> x + y)
• Function application.
• The operator (|>) from F# that pipes an argument into a function. 10 |> sin |> exp |> cos is equivalent to: (sin (exp (cos 10)))
• Clojure (->) macro: (-> 10 Math/sin Math/exp Math/cos) which is expanded to: (Math/cos (Math/exp (Math/sin 10)))
• Function composition operator: (>>) from F# and (.) dot from Haskell
• JavaScript: Is single-thread with event loop and uses asynchronous IO (non blocking IO) with callbacks.
• It is controversial that Javascript is based on scheme. According to Douglas Crockford JavaScript is Scheme on a C clothe. With a C-like syntax {Reference}.

## 3 Influential People

A selection of people who influenced functional programming:

• Alonzo Church, Mathematician -> Lambda Calculus
• Haskell Curry, Mathematician -> Concept of currying
• Robin Milner, Computer Scientist -> Type inference
• John McCarthy, Computer Scientist -> Creator of Lisp and the father of Artificial intelligence research.
• John Backus, Computer Scientist -> Backus-Naur form (BNF), Fortran Language,
• Philip Wadler, Theory behind functional programming and the use of monads in functional programming, the design of the purely functional language Haskell.
• Eugenio Moggi, Professor of computer science at the University of Genoa, Italy. - He first described the general use of monads to structure programs.
• Simon Peyton Jones, Computer Scientist -> Major contributor to the design of the Haskell programming language.
• John Hughes, Computer Scientist -> One of the most influentials papers in FP field: Why functional programing matters.

## 4 Miscellaneous

### 4.1 Selected Wikipedia Articles

General

Functions

First Class Functions

Composition

Scope

Currying and Partial Evaluation

Higher Order Functions, Closures, Anonymous Functions

Recursion

Lambda Calculus and Process Calculus

Evaluation

Related to Lazy Evaluation

Continuations

Fundamental Data Structures

Types

Concurrency

Miscellaneous

Functional Languages

### 4.3 Libraries and Frameworks

Python

• Useful Python libraries for functional programming:

Javascript

• Underscore.js: "Underscore is a JavaScript library that provides a whole mess of useful functional programming helpers without extending any built-in objects."