This tutorial is aimed at this basic concepts of pure programming in Haskell with no complex mathematical concepts... Just for fun... This basic tutorial is based on the books listed below

Some useful books you might want to read :)

[0] Learn you a Haskell for great good (Online) `prefered`

[1] Progrmming in Haskell `prefered`

[3] Write you a Haskell (Oneline)

[4] Real World Haskell (Library)

[5] awesome-haskell

In [1]:

```
-- defination of function: plus one to some number x
plusOne x = x + 1
-- apply it to a given number
plusOne 1 -- please complete me! (replace ? by a number)
-- Tip: Try to press Shift+Enter to run the code segment
plusOne' = (+1)
```

Haskell's function definition is very simple, for example:

`f x y = x + y`

means $f(x,y)=x+y$

Let's take more Haskell functions!

Hugs:

- usually used for teaching

GHC (Glasgow Haskell Compiler):

support parallel excution

either directly generate native code or using llvm as back-end

ghc -> compile for generating fast native code

ghci -> interpreter and debugger

comes with several libraries, thousands of libraries are available on Hackage

Cabal (Common Architecture for Building Applications and Libraries):

- a system for building and packaging Haskell libraries and programs

Stack (preferred):

a cross-platform program for developing Haskell projects.

Installing GHC automatically, in an isolated location.

Installing packages needed for your project.

Building your project.

Testing your project.

*Exercise*: Write a function that return the area of a given circle

$circleArea(r)=pi\ast {r}^{2}$

In [2]:

```
-- circleArea ? -- complete me!
pi
1^2
```

In this section, we will discuss some useful built-in *types* in Haskell and the usage of these types. Besides, *class* will be discussed as well.

Haskell is a strongly, statically typed programming language where types can be infered.

Strongly typed:

Cannot cast one type from another

Some type errors could be avoided

Statically typed:

- types are known at compilation time by the compiler / interpreter

types can be inferred

- types can always be inferred by compiler or interpreter, but you can specify them.

In [3]:

```
-- try to run these command
:t 'a' -- 'a' :: Char
:t "a" -- "a" :: String / [Char]
:t True -- True :: Bool
:t False -- False :: Bool
:t not -- not :: Bool -> Bool
```

`'a' :: Char`

means `'a'`

is a value of type `Char`

`"a" :: [Char]`

means `"a"`

is a value of type `String`

or `[Char]`

list of Char

`True :: Bool`

means `True`

is a value of type `Bool`

`False :: Bool`

means `False`

is a value of type `Bool`

`not :: Bool -> Bool`

means `not`

is a function of type `Bool -> Bool`

(map a value of type `Bool`

to a value of type `Bool`

)

Here, we introduce some basic types of Haskell

`Char`

signle characters

`Bool`

Logic values

`String`

[Char]

`Int`

$from\text{}(-{2}^{63})\text{}to\text{}({2}^{63}-1)$ fixed-precision integers

`Integer`

arbitrary-precision integers

`Float`

single-precision floating-point numbers

`Double`

double-precision floating-point numbers

`[T]`

list types

`(T0, T1, T2)`

tuple types

`(T -> T')`

function types

In [4]:

```
let c = 'a'
let f = False
let p = "hello, world"
let s = "hello, world" :: String
let n = 0 :: Int
let x = 0 :: Integer
let y = 1.0 :: Float
let z = 1.0 :: Double
:t c
:t f
:t p
:t s
:t n
:t x
:t y
:t z
```

In [5]:

```
take 2 [1, 2, 3, 4, 5] -- take first 2 elements of a list
drop 2 [1..5] -- drop 2 elements from list
init [0.0, 0.1..1.0] -- init xs = take (length xs - 1) xs
last ['a'..'d'] -- last xs = drop (length xs - 1) xs
head [1..] -- head xs = take 1 xs, [1..] means a infinity list!
tail [1..5] -- tail xs = drop 1 xs
```

In [6]:

```
-- add a constraint for function
plusOne :: Int -> Int
plusOne x = x + 1
```

In [7]:

```
add :: Int -> Int -> Int
add x y = x + y
:t add 1
```

Something interesting happens!

What's the exact meaning of `Int -> Int -> Int`

?

1) a function that takes 2 `Int`

type parameter and return a `Int`

type number

2) a function that takes one `Int`

type parameter and return a `function`

which takes one `Int`

type paramter and return a `Int`

type parameter

Useful ? Yes!

In [8]:

```
add :: Int -> Int -> Int
add x y = x + y
-- function *add* is partially applied
-- curring function is named after Haskell Curry
-- https://en.wikipedia.org/wiki/Haskell_Curry
map (add 2) [1..5]
```

Curring function and lambda calculus are used to simplified the conception of functions.

Let's take a function:

$f(x,y)\to {x}^{2}+{y}^{2}$

Is the name of a function important ? no...

$(x,y)\to {x}^{2}+{y}^{2}$

Is it essential to distinguish a multi-arguments function and a single-argument function? no...

$x\to (y\to {x}^{2}+{y}^{2})$

Later, we will discuss this topic in `Evaluation Strategies`

In [9]:

```
f x y = x^2 + y^2
(\x y -> x^2 + y^2) 1 2
(\x -> (\y -> x^2 + y^2)) 1 2
```

In general, take a `n arguments function`

for example,

$f({x}_{1},{x}_{2},{x}_{3},...,{x}_{n})={f}^{n-1}({x}_{1})({x}_{2})...({x}_{n})$

This is *exactly* what Haskell do when analyzing your code!

In [10]:

```
-- Polymorphic types
empty' :: [a] -> Bool -- I don't know the actual type of a, but I want to use it!
empty' [] = True
empty' _ = False
```

Classes are a collection of types that support overloaded functions called *methods*. Haskell provides some basic built-in classes and we will discuss them below...

In [11]:

```
-- for example, if you write something like equal'
-- and this will produce a error
-- because in the function, we use the (==) operator
-- without put a constraint on type `a`
-- (==) is defined in `Eq` class
equal' :: a -> a -> Bool
equal' x y = x == y
```

In [12]:

```
equal' :: Eq a => a -> a -> Bool
equal' x y = x == y
```

In [13]:

```
-- class Eq a where
-- (==) :: a -> a -> Bool
-- (/=) :: a -> a -> Bool
-- instance Eq Int where
-- ...
-- instance Eq Float where
-- ...
-- yet another Eq
class YAEq a where
(=-=) :: a -> a -> Bool
(/=-=) :: a -> a -> Bool
data Natural = Nat Int
instance YAEq Natural where
Nat m =-= Nat n = m == n
Nat 1 =-= Nat 2
```

Some basic types are listed below

Eq- equality types

Methods:

```
(==) :: a -> a -> Bool
(/=) :: a -> a -> Bool
```

all basic types are instances of `Eq`

: `Bool`

, `Char`

, `String`

, `Int`

, `Integer`

, `Float`

, `Double`

Ord- ordered types

Methods:

```
(<) :: a -> a -> Bool
(>) :: a -> a -> Bool
(<=) :: a -> a -> Bool
(>=) :: a -> a -> Bool
```

all basic types are instances of `Eq`

: `Bool`

, `Char`

, `String`

, `Int`

, `Integer`

, `Float`

, `Double`

Show- show types

Methods: show

all basic types are instances of `Eq`

: `Bool`

, `Char`

, `String`

, `Int`

, `Integer`

, `Float`

, `Double`

Read-- readable types

Method:

```
read :: String -> a
```

all basic types are instances of `Eq`

: `Bool`

, `Char`

, `String`

, `Int`

, `Integer`

, `Float`

, `Double`

Num-- numeric types

Method:

```
(+) :: a -> a -> a
(-) :: a -> a -> a
(*) :: a -> a -> a
negate :: a -> a
abs :: a -> a
signum :: a -> a -- sign of a number, abs x * signum x == x
```

basic types that are instances of `Num`

: `Int`

, `Integer`

, `Float`

, `Double`

Integral-- integral types

Method:

```
div :: a -> a -> a
mod :: a -> a -> a
```

basic types that are instances of `Num`

: `Int`

, `Integer`

Fractional-- fractional types

Method:

```
(/) :: a -> a -> a
recip :: a -> a
```

basic types that are instances of `Fractional`

: `Float`

, `Double`

In [14]:

```
-- playground
```

In [15]:

```
-- type declarations
type Pos = (Int, Int)
type String_ = [Char]
-- class declarations
data Tree a = Node (Tree a) a (Tree a) -- non-empty binary tree node
| Nil -- empty node
deriving (Show)
-- (1)
-- / \
-- 2 (Nil)
-- / \
-- (Nil)(Nil)
:t Node
Node (Node Nil 2 Nil) 1 Nil
-- instance <preconditions> => <class> <type> where
-- <method> = <definition>
-- yet another binary tree
data Tree' a = Node' (Tree' a) a (Tree' a)
| Nil'
instance Show a => Show (Tree' a) where
show (Node' l v r) = show l ++ show v ++ show r
show Nil' = "#"
Node' (Node' Nil' 2 Nil') 1 Nil'
-- newtype
-- usually, newtype is used to declare new class that has only one parameter
newtype Natural = N Int
data Natural' = N' Int
```

*Where* Constructions

the `where`

clause allow us to introduce local variables and functions

In [16]:

```
add :: Int -> Int -> Int
add x y = sumOfXY
where sumOfXY = x + y
```

*Let* Bindings

syntax:

```
let bindings in expression
```

In [17]:

```
add :: Int -> Int -> Int
add x y = let sumOfXY = x + y in sumOfXY
```

*Case* Expressions

syntax:

```
case expression of
pattern_0 -> result_0
pattern_1 -> result_0
...
pattern_n -> result_n
```

In [18]:

```
judge' :: Bool -> String
judge' b =
case b of
True -> "logic true"
False -> "logic false"
```

*if* expression

syntax:

```
if expression then
expression_0
else
expression_0
```

In [19]:

```
judge' :: Bool -> String
judge' b =
if b == True then
"logic true"
else
"logic false"
```

*guard*

syntax:

```
variable
| expression_0 = result_0
| expression_1 = result_1
...
| otherwise = result_n
```

In [20]:

```
judge' :: Bool -> String
judge' b
| b == True = "logic true"
| otherwise = "logic false"
```

Using pattern matching will simplify your program a lot!

In [21]:

```
-- logic (&&)
-- (&-&) :: Bool -> Bool -> Bool
-- (&-&) True True = True
-- (&-&) True False = False
-- (&-&) False True = False
-- ... hard coding
(&-&) :: Bool -> Bool -> Bool
(&-&) True True = True
(&-&) _ _ = False
```

In [22]:

```
-- tuple patterns
fst' :: (a, b) -> a
fst' (x, _) = x
-- list patterns
length' :: [a] -> Int
length' [] = 0
length' (x: xs) = 1 + length' xs
head' :: [a] -> a
head' [] = error "ERROR: I don't accept empty list!"
head' (x: _) = x
tail' :: [a] -> [a]
tail' [] = error "ERROR: I don't accept empty list!"
tail' (_: xs) = xs
-- class patterns
data Tree a = Node (Tree a) a (Tree a)
| Nil
deriving Show
-- getValue (Node Nil 1 Nil)
getValue :: Tree a -> a
getValue (Node _ v _) = v
getValue Nil = error "empty node"
```

In [23]:

```
-- Some examples of list comprehension
-- It's very similar to the concept of *set* from mathematics
[x^2 | x <- [1..5]]
[(x, y) | x <- [1..5], y <- [2, 3]]
length'' :: [a] -> Int
length'' xs = sum [1 | _ <- xs]
length'' [1..5]
```

The symbol `|`

is read as `such that`

, `<-`

is read as `is drawn from`

, and the expression `[x^2 | x <- [1..5]]`

is called a generator

In [24]:

```
-- *guard* in list comprehension
-- *guard* is very similar to filter
[x | x <- [1..5], x >= 3]
[(x, y) | x <- [1..5], y <- [3, 6], x >= 3, y <= 4]
```

In [25]:

```
-- quick sort in haskell
quicksort :: Ord a => [a] -> [a]
quicksort [] = []
quicksort (x:xs) = quicksort smaller ++ [x] ++ quicksort larger
where
smaller = [s | s <- xs, s < x]
larger = [l | l <- xs, l >= x]
quicksort' :: Ord a => [a] -> [a]
quicksort' [] = []
quicksort' (x:xs) = let smaller = [s | s <- xs, s < x]
larger = [l | l <- xs, l >= x]
in quicksort smaller ++ [x] ++ quicksort larger
```

In this section, we will discuss `evaluation strategies`

of Haskell, and this will help you write high performance code!

Ref: 1) Church Rosser Theorems 2) Lambda Calculus

Here, take 3 dominant evaluation models for consideration.

- Call-by-value (strict)
arguments are evaluated before a function is called

1) Evaluate $x$ to $v$

2) Evaluate $f$ to $\lambda y.e$

3) Evaluate $[\text{}y\text{}/\text{}v\text{}]e$

Example:

$(\lambda \text{}x.\text{}\lambda \text{}y.\text{}y\text{}x)\text{}(2\text{}+\text{}2)\text{}(\lambda \text{}x.\text{}x\text{}+\text{}1)$

$\to \text{}(\lambda \text{}x.\lambda \text{}y.\text{}y\text{}x)\text{}(4)\text{}(\lambda \text{}x.\text{}x\text{}+\text{}1)$

$\to \text{}(\lambda \text{}y.\text{}y\text{}4)\text{}(\lambda \text{}x.\text{}x\text{}+\text{}1)$

$\to \text{}(\lambda \text{}x.\text{}x\text{}+\text{}1)\text{}4$

$\to \text{}5$

- Call-by-name
arguments are passed unevaluated, the subroutine receives the unevaluated argument expression and must evaluate it.

1) Evaluate $f$ to $\lambda y.e$

2) Evaluate $[\text{}y\text{}/\text{}v\text{}]e$

Example:

$(\lambda \text{}x.\text{}\lambda \text{}y.\text{}y\text{}x)\text{}(2\text{}+\text{}2)\text{}(\lambda \text{}x.\text{}x\text{}+\text{}1)$

$\to \text{}(\lambda \text{}y.\text{}y\text{}(2\text{}+\text{}2))\text{}(\lambda \text{}x.\text{}x\text{}+\text{}1)$

$\to \text{}(2\text{}+\text{}2)\text{}+\text{}1$

$\to \text{}5$

- Call-by-need
arguments are not evaluated when a function is called, but when the arguments are needed, these arguments are evaluated and stored for next time

Ref: How Lazy Evaluation Works in Haskell

1) Allocate a `thunk`

$v$ for $x$. Tip: The term `thunk`

originated as a jocular derivative of "think"

2) Evaluate $f$ to $\lambda y.e$

3) Evaluate $[\text{}y\text{}/\text{}v\text{}]e$

Haskell uses `Call-by-need`

by default. That's exactly what we call `Lazy Evaluation`

.

And you could use `$!`

to force it to use `Call-by-value`

evaluation...

Tip: `Lazy`

and `non-strict`

are two slightly different conception ...

In [26]:

```
take' :: Int -> [a] -> [a]
take' _ [] = []
take' 0 _ = []
take' n (x:xs) = x: take' (n-1) xs
take' 5 [1..]
-- take' 5 [1..]
-- -> 1: take' (5-1) [2..]
-- -> 1: 2 take' (4-1) [3..]
-- -> 1: 2: 3 take' (3-1) [4..]
-- -> 1: 2: 3: 4 take' (2-1) [5..]
```

In functional programming, recursion replace the well-known *for* and *while* loop that imperative languages have.

In [27]:

```
factorial :: Int -> Int
factorial m = factorial' m 1
where
factorial' 0 y = y
factorial' m n = factorial' (m-1) (m*n)
```

There is one thing need to notice is that Haskell takes `Lazy Evaluation`

by default. Hence, when you calculate the factorial of 5, it goes like:

```
factorial 5
factorial' 5 1
factorial' 4 (5*1)
factorial' 3 (4*5*1)
factorial' 2 (3*4*5*1)
factorial' 1 (2*3*4*5*1)
factorial' 0 (1*2*3*4*5*1)
120
```

So, to improve our code performance, add `$!`

to force Haskell compiler to use `CBV`

evaluation.

In [28]:

```
factorial :: Int -> Int
factorial m = factorial' m 1
where
factorial' 0 y = y
factorial' m n = factorial' (m-1) $! (m*n)
```

So, when GHCI evaluate `factorial 5`

, it goes:

```
factorial 5
factorial' 5 1
factorial' 4 (5*1)
factorial' 3 (4*5)
factorial' 2 (3*20)
factorial' 1 (2*60)
factorial' 0 (1*120)
120
```

The `map`

function, actually, is not specific to the type of lists. It could applied to wide range of parameterised types

```
class Functor f where
fmap :: (a -> b) -> f a -> f b
instance Functor [] where
fmap = map
instance Functor Maybe where
fmap _ Nothing = Nothing
fmap g (Just x) = Just (g x)
```

In [29]:

```
fmap (+1) [1..5]
fmap (+1) (Just 2)
```

In [30]:

```
data Tree a = Node (Tree a) a (Tree a) -- non-empty binary tree node
| Nil -- empty node
deriving (Show)
instance Functor Tree where
fmap g Nil = Nil
fmap g (Node l v r) = Node (fmap g l) (g v) (fmap g r)
let myTree = Node (Node Nil 2 Nil) 1 Nil
fmap (+1) myTree
```

Let think about something like this using `functor`

```
fmap0 :: a -> f a
fmap1 :: (a -> b) -> f a -> f b
fmap2 :: (a -> b -> c) -> f a -> f b -> f c
...
```

In [31]:

```
class Functor2 f where
fmap2 :: (a -> b -> c) -> f a -> f b -> f c
instance Functor2 Maybe where
fmap2 _ Nothing _ = Nothing
fmap2 _ _ Nothing = Nothing
fmap2 f (Just x) (Just y) = Just (f x y)
fmap2 (+) (Just 1) (Just 1)
```

To allow wrapped functions applied on wrapped values like: `pure g <*> x1 <*> x2 <*> x3 ... <*> xn`

`Applicative Functor`

is a built-in class in Haskell...

```
class Applicative f where
pure :: a -> f a
-- <*> => ->
<*> :: f (a -> b) -> f a -> f b
instance Applicative [] where
pure x = [x]
gs <*> xs = [g x | g <- gs, x <- xs]
instance Applicative Maybe where
pure x = Just x
Nothing <*> _ = Nothing
(Just g) <*> ms = fmap g ms
```

In [32]:

```
pure (+) <*> (Just 1) <*> (Just 1)
pure (+1) <*> [1..5]
```

```
class Applicative m => Monad m where
return :: a -> m a
-- bind
(>>=) :: m a -> (a -> m b) -> m b
return = pure
instance Monad Maybe where
-- (>>=) :: Maybe a -> (a -> Maybe b) -> Maybe b
Nothing >>= _ = Nothing
(Just x) >>= f = f x
```

Don't worry if you cannot understand this slide immediately, having overall comprehension is enough!

With `Monad`

, we could write something like:

```
m1 >>= \x1 ->
m2 >>= \x2 ->
...
mn >>= \xn ->
f x1 x2 ... xn
-- or
do
x1 <- m1
x2 <- m2
...
xn <- mn
f x1 x2 x3 ... xn
```

With `Monad`

, we could handle impure functions easily...

-- Wikipedia

`Pure function`

The function always evaluates the same
result value given the same argument value(s). The function result value
cannot depend on any hidden information or state that may change while
program execution proceeds or between different executions of the
program, nor can it depend on any external input from I/O devices.
Evaluation of the result does not cause any semantically observable side
effect or output, such as mutation of mutable objects or output to I/O
devices.

Pure | Impure |
---|---|

produce same value when arguments are same | produce different value when arguments are same |

non-side-effect | side-effect |

never change the global state or program | xxx |