 # A Brief Introduction on Haskell

##### Learn you a Haskell for great good!

@Higuoxing | 2018.03.30

This .ipynb file is available here

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

### Reference¶

Some useful books you might want to read :)

 Learn you a Haskell for great good (Online) prefered

 Progrmming in Haskell prefered

 Write you a Haskell (Oneline)

### First Taste of Functions¶

In :
-- 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)

2

### Basic Concenpts¶

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

f x y = x + y means $f\left(x,y\right)=x+y$$f(x, y) = x + y$

Hugs:

• usually used for teaching

• 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.

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

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

In :
-- circleArea ? -- complete me!
pi
1^2

3.141592653589793
1

### Types& Classes¶

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 :
-- 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
"a" :: [Char]
True :: Bool
False :: Bool
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\ (-2^{63})\ to\ (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 :
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

c :: Char
f :: Bool
p :: [Char]
s :: String
n :: Int
x :: Integer
y :: Float
z :: Double
In :
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

[1,2]
[3,4,5]
[0.0,0.1,0.2,0.30000000000000004,0.4000000000000001,0.5000000000000001,0.6000000000000001,0.7000000000000001,0.8,0.9]
'd'
1
[2,3,4,5]
In :
-- add a constraint for function
plusOne :: Int -> Int
plusOne x = x + 1

In :
add :: Int -> Int -> Int
add x y = x + y


add 1 :: Int -> Int

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 :
add :: Int -> Int -> Int
add x y = x + y

-- function *add* is partially applied
-- curring function is named after Haskell Curry

[3,4,5,6,7]

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

Let's take a function:

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

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

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

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

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

Later, we will discuss this topic in Evaluation Strategies

In :
f x y = x^2 + y^2

(\x y -> x^2 + y^2) 1 2

(\x -> (\y -> x^2 + y^2)) 1 2

Collapse lambdas
Found:
\ x -> (\ y -> x ^ 2 + y ^ 2)
Why Not:
\ x y -> x ^ 2 + y ^ 2
5
5

In general, take a n arguments function for example,

$f\left({x}_{1},{x}_{2},{x}_{3},...,{x}_{n}\right)={f}^{n-1}\left({x}_{1}\right)\left({x}_{2}\right)...\left({x}_{n}\right)$$f(x_1, x_2, x_3, ..., x_n) = f^{n-1}(x_1)(x_2)...(x_n)$

In :
-- 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 :
-- 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

<interactive>:2:14: error:
• No instance for (Eq a) arising from a use of ‘==’
Possible fix:
add (Eq a) to the context of
the type signature for:
equal' :: forall a. a -> a -> Bool
• In the expression: x == y
In an equation for ‘equal'’: equal' x y = x == y
In :
equal' :: Eq a => a -> a -> Bool
equal' x y = x == y

In :
-- 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

False

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

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 :
-- playground

In :
-- 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

Node :: forall a. Tree a -> a -> Tree a -> Tree a
Node (Node Nil 2 Nil) 1 Nil
#2#1#

Where Constructions

the where clause allow us to introduce local variables and functions

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


Let Bindings

syntax:

let bindings in expression

In :
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 :
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 :
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 :
judge' :: Bool -> String
judge' b
| b == True = "logic true"
| otherwise = "logic false"


Using pattern matching will simplify your program a lot!

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

(&-&) :: Bool -> Bool -> Bool
(&-&) True True = True
(&-&) _    _    = False

In :
-- tuple patterns
fst' :: (a, b) -> a
fst' (x, _) = x

-- list patterns
length' :: [a] -> Int
length' []      = 0
length' (x: xs) = 1 + length' xs

head' []     = error "ERROR: I don't accept empty list!"

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"


### List Comprehension¶

In :
-- 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]

[1,4,9,16,25]
[(1,2),(1,3),(2,2),(2,3),(3,2),(3,3),(4,2),(4,3),(5,2),(5,3)]
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 :
-- *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]

[3,4,5]
[(3,3),(4,3),(5,3)]
In :
-- 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


### Evaluation Strategies¶

In this section, we will discuss evaluation strategies of Haskell, and this will help you write high performance code!

#### Evaluation Models¶

Here, take 3 dominant evaluation models for consideration.

• Call-by-value (strict)

arguments are evaluated before a function is called

1) Evaluate $x$$x$ to $v$$v$

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

3) Evaluate $[\ y\ /\ v\ ]e$

Example:

$(\lambda\ x.\ \lambda\ y.\ y\ x)\ (2\ +\ 2)\ (\lambda\ x.\ x\ +\ 1)$

$\rightarrow\ (\lambda\ x. \lambda\ y.\ y\ x)\ (4)\ (\lambda\ x.\ x\ +\ 1)$

$\rightarrow\ (\lambda\ y.\ y\ 4)\ (\lambda\ x.\ x\ +\ 1)$

$\rightarrow\ (\lambda\ x.\ x\ +\ 1)\ 4$

$\rightarrow\ 5$

• Call-by-name

arguments are passed unevaluated, the subroutine receives the unevaluated argument expression and must evaluate it.

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

2) Evaluate $[\ y\ /\ v\ ]e$

Example:

$(\lambda\ x.\ \lambda\ y.\ y\ x)\ (2\ +\ 2)\ (\lambda\ x.\ x\ +\ 1)$

$\rightarrow\ (\lambda\ y.\ y\ (2\ +\ 2))\ (\lambda\ x.\ x\ +\ 1)$

$\rightarrow\ (2\ +\ 2)\ +\ 1$

$\rightarrow\ 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

1) Allocate a thunk $v$$v$ for $x$$x$. Tip: The term thunk originated as a jocular derivative of "think"

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

3) Evaluate $[\ y\ /\ v\ ]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 : 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..]  [1,2,3,4,5] ### Recursion¶ In functional programming, recursion replace the well-known for and while loop that imperative languages have. In : 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 :
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 :
fmap (+1) [1..5]
fmap (+1) (Just 2)

[2,3,4,5,6]
Just 3
In :
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

Node (Node Nil 3 Nil) 2 Nil

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 :
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)

Just 2

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 :
pure (+) <*> (Just 1) <*> (Just 1)

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

Redundant bracket
Found:
pure (+) <*> (Just 1)
Why Not:
pure (+) <*> Just 1
Redundant bracket
Found:
pure (+) <*> (Just 1) <*> (Just 1)
Why Not:
pure (+) <*> (Just 1) <*> Just 1
Just 2
[2,3,4,5,6]
class Applicative m => Monad m where
return :: a -> m a
-- bind
(>>=) :: m a -> (a -> m b) -> m b
return = pure

-- (>>=) :: 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...

### Pure and Impure¶

-- 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