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

[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

First Taste of Functions¶

-- 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(x, y) = x + y$

Let's take more Haskell functions!

Haskell Tools¶

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 * r^{2}$

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

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

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

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]

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

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!

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]

[3,4,5,6,7]

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

Let's take a function:

$f(x, y) \rightarrow x^2 + y^2$

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

$(x, y) \rightarrow x^2 + y^2$

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

$x \rightarrow (y \rightarrow x^2 + y^2)$

Later, we will discuss this topic in Evaluation Strategies

f x y = x^2 + y^2

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

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

5

5

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!

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

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

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

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

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

-- playground

-- 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 (Node Nil 2 Nil) 1 Nil

#2#1#

Where Constructions

the where clause allow us to introduce local variables and functions

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

Let Bindings

syntax:

let bindings in expression

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

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

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

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

Using pattern matching will simplify your program a lot!

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

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

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

List Comprehension¶

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

-- *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)]

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

Ref: 1) Church Rosser Theorems 2) Lambda Calculus

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$ to $v$

2) Evaluate $f$ to $\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$ to $\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

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 $[\ 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 ...

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.

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.

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

Functor, Applicative, Monad¶

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)

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

[2,3,4,5,6]

Just 3

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

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

pure (+) <*> (Just 1) <*> (Just 1)

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

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

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

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