Functional Programming

Radu Răzvan Slăvescu

Technical University of Cluj-Napoca

Department of Computer Science
Outline

Lists, tuples and records

Identifiers, Constants, Primitive types
Defining functions
Lists
Tuples and records

Functions and operators

Tail recursion
Local declarations
Infix operators
Mutually Recursive Functions
Identifiers in Haskell and ML

Definition
A letter followed by letters, digits, , ’

Example

long_name_from_FP
x’’
a_b_3

Remark
The length of the name is arbitrary.
Basics: Constants

Used in order to avoid hardcoding in programs.

Example (Haskell, batch style)

pi = 3.14

Example (ML, conversational style)

> val pi = 3.14;

val pi = 3.14 : real

Primitive types: Integers

Definition
Type = collection of values + functions over them
Type inference = calculate an expression’s type at compile time

Integer types in Haskell

I Int : fixed precision integers
I Integer : arbitrary precision integers
I binary operations: + - * ‘div‘ ‘mod‘
I relational operators: <, >, <=, >=, ==, / =
Primitive types: Integers

Integer type in ML
I int : arbitrary precision
I binary operations: + - * div mod
I relational operators: <, >, <=, >=, =, <>
Primitive types: Real

Real type in Haskell

I Float or Double (simple or double precision)
I operations: + - * /
I relational operators: <, >, <=, >=, ==, / =

Example

3.14
-10.0
1.0E-2
1.4142135 or 1.4142135623730951
Basic types: Real

Real type in ML
I real
I operations: + - * /
I relational operators: <, >, <=, >=
I relational operators <> and = are implemented using
<, >, <=, >=

Example

3.14
˜10.0
1.0E˜2
Primitive types: Boolean

Boolean type in Haskell

I type: Bool; values:True, False
I logical operations: not, &&, ||
I conditional expression: if E then ET else EF

Boolean type in ML
I type: bool; values: true, false
I logical operations: not, andalso, orelse
I conditional expression: if E then ET else EF
Character

Definition (Haskell Char)

Enclosed between quotes (’) and ordered by ASCII code

Example (Haskell:Char)

’a’,’b’,...,’z’,’3’
’\n’,’\\’

Example (ML)
char type in ML is based on strings of length 1.
#"a" introduces a char in ML.
String

Definition (String)
Sequence of 0 or more characters between double quotes (").

Example (Haskell: String / ML: string)

"abc","a1b2",""

Operators
1. relational:
I Haskell: <, >, <=, >=, ==, /=
I ML: <, >, <=, >=, =, <>
2. concatenation:
I Haskell: ++
I ML: ˆ
Enumerative type

Definition
It is meant to express alternative data.

Example (Haskell: data)

data Color = Red | Green | Blue

Example (ML: datatype)

datatype color = Red | Green | Blue;

Defining functions
Example (Haskell, batch style)

pi3 = 3.14
area::Double -> Double
area r = pi3 * r * r

Example (ML, conversational style)

> val pi = 3.14;

val pi = 3.14 : real

> fun area r = pi * r * r;

val area = fn : real -> real
Inferring types

Example

> fun sq x = x * x;

val sq = fn : int -> int

Example

> fun sq (x:real) = x * x;

val sq = fn : real -> real

Enumerative type

Example (ML: new bool)

datatype new_bool = new_true | new_false;

Example (functions on an enumerative type)

They are defined by a case analysis:

fun new_not new_true = new_false

| new_not new_false = new_true;

> val new_not = fn : new_bool -> new_bool

Recursive functions

Recursion
It is used to express repetitions in FP

Example (Greatest common divisor: Euclid’s Algorithm)

fun gcd m n = if m = 0 then n

else gcd (n mod m) m;

Remark
gcd has only one recursive call in its body. It is linear recursive.
Recursive functions

Fibonacci numbers
F0 = 0, F1 = 1, Fn = Fn−1 + Fn−2

Example (Fibonacci)

fib n = if n==0 then 0

else if n==1 then 1
else fib (n-1) + fib (n-2)

Remark
fib has more than one recursive calls in its body.
Recursive functions

Example (Ackermann’s function)

ack m n = if m==0 then (n+1)

else if n==0 then ack (m-1) 1
else ack (m-1) (ack m (n-1))

Remark
The number of recursive calls of this function increases
extremely rapidly with its arguments.
A little bit of lists and functions

Definition (List)
A list is a sequence of values of a specific type.

Example (Haskell)

Prelude> :set +t --ask ghci to tell type

Prelude> [1,2,3]
[1,2,3] :: [Integer]

Example (ML)

> [1,2,3];
val it = [1, 2, 3] : int list
A little bit of lists and functions

Observations
1. the length of the list is not limited
2. the types of list elements are not restricted
3. however, the elements must have the same type
A little bit of lists and functions
Definition (Function)
A function is a mapping from values of one type to values of
some other type.

Example (Haskell’s Boolean function not)

Prelude> :t not

not :: Bool -> Bool

Example (ML’s Boolean function not)

> not;

val it = fn : bool -> bool

Calling functions

Calling functions

Math: f(x, y*z, g(t))

FP: f x (y*z) (g t)

Note
1. as a rule, no parentheses separate the function name and
arguments; however, in ML we might have this separation
2. pay attention to the precedence: fact n - 1 versus
fact (n-1); if not sure, use parentheses
A little bit of lists and functions

Example
1. Prelude> head [1,2,3]
1
2. Prelude> tail [1,2,3]
[2,3]
3. Prelude> length [1,2,3]
3
4. Prelude> [1,2,3] ++ [4,5]
[1,2,3,4,5]
5. Prelude> 1:[2,3]
[1,2,3]
6. Prelude> [1,2,3] !! 1
2
A little bit of lists and functions

Example
1. > hd [1,2,3];
val it = 1: int
2. > tl [1,2,3];
val it = [2, 3]: int list
3. > length [1,2,3];
val it = 3: int
4. > [1,2,3] @ [4,5];
val it = [1, 2, 3, 4, 5]: int list
5. > 1::[2,3];
val it = [1, 2, 3]: int list
6. > List.nth ([1,2,3],1);
val it = 2: int
Tuples

Definition
A tuple is an anonymous constructor containing at least two
components; component order matters.

Example (Haskell pair)

Prelude> (1.3, 3.4)

(1.3,3.4)

Example (ML pair)

> (1.3, 29.5);

val it = (1.3, 29.5) : real * real
Tuples

Example (Define a Haskell vector)

type Vector = (Double, Double)

Example (Define an ML vector)

> type vector = real * real;

type vector = real * real

Observation
But: this is just a shortcut for a pair of real numbers.
Tuples

Tuples: where do we use them

Tuples are useful when a function needs to be applied on any
number of arguments and to return any number of results

Example

> fun scvec r (x,y):vector = (r*x,r*y);

> scvec 2.0 (3.5, 4.0);

val it = (7.0, 8.0) : vector
Building and accessing tuples in Haskell

Example (A person has name, age, gender, location)

data Gender = M | F

--a vector stores these components

type Person = (String, Int, Gender, String)
Building and accessing tuples in Haskell

Example (A person has name, age, gender, location)

--let me introduce Brad

a1 :: Person
a1 = ("Brad", 54, M, "L. A.")
Building and accessing tuples in Haskell

Example (Accessing components of a tuple)

--let’s learn something about a1

(name, age, gender, location) = a1
Main> age
54 :: Int
Printing components of a tuple

Example (The system can print a String...)

Main> location
"L.A." :: [Char]

Example (...but not a user-defined data...)

Main> gender
ERROR - Cannot find "show" function for:
*** Expression : gender
*** Of type : Gender
Printing components of a tuple

Example (..so we should teach him)

printGender :: Gender -> String

printGender s = case s of
M -> "Male"
F -> "Female"

Main> printGender gender

Male :: [Char]
Tuples

Example (Brad again)

datatype gender = m | f;

type person = string * int * gender * string;

val a1 : person = ("Brad", 54, m, "L. A.");

val n = #1 a1;

> n;
val it = "Brad" : string
Records in ML
Components of a record
A record is composed of a number of fields. Each field has a
name, called tag. Field order does not matter.

Example (Let’s introduce Brad to the ML prompter)

> datatype gender = male | female;

> val a1 = {a = 54, l = "L.A.", g = male};
val a1 = {a = 54, l = "L.A.", g = male} :
{a: int, l: string, g: gender}

Example (location, pls)

> #l a1;
val it = "L.A." : string
Recursion: express repetition in FP

Ouroboros snake (with permission from Wikimedia Commons)

Recursive functions

Definition
A function is tail recursive if it returns either something
computed directly or something returned by its recursive call
(the last thing it does is to call itself)

Example

fun fact n = if n = 0 then 1

else n * fact (n-1);

Example

fun factacc n a = if n = 0 then a

else factacc (n-1) (n*a);
fact: successive calls waste stack space and time

Example

fact(3) =

3*fact(3-1) = 3*fact(2) =

3*(2*fact(2-1)) = 3*(2*fact(1)) =

3*(2*(1*fact(1-1))) = 3*(2*(1*fact(0))) =

3*(2*1) = 3*2 =

6
factacc: no space and time wasted

Example

factacc(3,1) =

factacc(3-1,3*1) = factacc(2,3) =

factacc(2-1,2*3) = factacc(1,6) =

factacc(1-1,1*6) = factacc(0,6) =

6
Tail recursive functions are important

Reasons
1. we can see a tail recursive function as being equivalent to
an iteration
2. a tail recursive function could automatically be re-written in
an iterative manner
3. writing tail recursive functions helps saving space (of the
stack) and time (for stacking and un-stacking values)
Local declarations: Haskell

Example (Bottom-up approach)

f x = let
doubleof z = 2 * z
ten = 10
(a,b) = x
in
doubleof(ten * (a + b))

Prelude> f(2,3)
100
Local declarations: Haskell

Example (Top-down approach)

qs [] = []
qs (x:xs) = qs smalls ++ [x] ++ qs bigs
where
smalls = [s | s <- xs, s<=x]
bigs = [b | b <- xs, b>x]

Notes
1. don’t forget that in Haskell indentation is important.
2. Local declarations enter the scope in the same time. Their
types are infered by the system.
Local declarations: ML

Example (Bottom-up approach)

fun gcd (m, n) = if m = 0 then n

else gcd (n mod m, m);

fun ratio (n, d) =

let
val c = gcd (n, d)
in
(n div c, d div c)
end;
Local declarations: ML

Example (Bottom-up, another way)

local
fun fibit n p c =
if n=0 then c
else fibit (n-1) c (p+c)
in
fun fib n = fibit n 1 0
end;

Note
fibit is a private function of fib
Local declarations: ML

Example (Simultaneous declarations)

> val x=1;

val x = 1 : int
> val y=2;
val y = 2 : int

> val x=y and y=x;

val x = 2 : int
val y = 1 : int

Note
All values on the right hand side are evaluated and after the
identifiers on the left hand side get the corresponding values.
Operators

Definition
An infix operator is a function written between its arguments.
The reason for doing this is syntactic sugaring.

Example

> infix xor;

> fun x xor y = (x orelse y) andalso
# not (x andalso y);
val xor = fn : bool * bool -> bool

> true xor true;

val it = false : bool
Operators

Note
In ML, infix, infixr mean left and right associativity
respectively. We can also specify the operator’s precedence
(e.g. in the example below, the operator’s precedence is 6).

Example

> infix 6 plus;

> fun x plus y = "(" ˆ x ˆ "+" ˆ y ˆ ")";
val plus = fn : string * string -> string

>"1" plus "2" plus "3";

val it = "((1+2)+3)" : string
Operators

Example

> infixr 6 plusr;

> fun x plusr y = "(" ˆ x ˆ "+" ˆ y ˆ ")";
val plusr = fn : string * string -> string

> "1" plusr "2" plusr "3";

val it = "(1+(2+3))" : string
Operators

Note
In Haskell, infix, infixl and infixr mean free, left and
right associativity respectively.

Example

infixl 6 ##

x ## y = "(" ++ x ++ "+" ++ y ++ ")"

Prelude> "1" ## "2" ## "3"

"((1+2)+3)" :: [Char]
Operators

Note
An infix operator could be used as prefix function.

Example (ML string concatenation)

> op ˆ("John ", "Doe");

"John Doe" : string

Example (Haskell division)

3 ‘div‘ 2 same as
div 3 2
Mutually Recursive Functions

A mathematical series
π 1 1 1 1 1
4 =1− 3 + 5 − 7 + ··· + 4k+1 − 4k+3 + ...

Example (ML mutually recursive functions use an and)

fun pos (d:real) = neg (d-2.0) + 1.0/d

and neg (d:real) = if d>0.0
then pos (d-2.0) - 1.0/d
else 0.0;
Mutually Recursive Functions

Partial sums up to a positive term

pos 1 = 1
pos 5 = 1 − 13 + 15
pos 9 = 1 − 13 + 15 − 17 + 19

Partial sums up to a negative term

neg 3 = 1 − 13
neg 7 = 1 − 13 + 15 − 17
neg 11 = 1 − 13 + 15 − 17 + 19 − 11
1
Mutually Recursive Functions

Relation between pos and neg

neg d = pos(d − 2) − d1 , for d = 4k + 3, k ≥ 0

pos d = neg(d − 2) + d1 , for d = 4k + 1, k ≥ 1
pos 1 = 1
neg − 1 = 0

Example

fun pos (d:real) = neg (d-2.0) + 1.0/d

and neg (d:real) = if d>0.0
then pos (d-2.0) - 1.0/d
else 0.0;
Mutually Recursive Functions

Example

fun pos (d:real) = neg (d-2.0) + 1.0/d

and neg (d:real) = if d>0.0
then pos (d-2.0) - 1.0/d
else 0.0;

> pos 665.0;

val it = 0.7861489125 : real
A procedure has a functional equivalent

Example (Summing up the first 10 numbers)

n = 10; i = 1; s = 0;
sum: if i<=n then s = s+i; goto sum1
else stop
sum1: i = i+1;
goto sum

Example (Equivalent functional code)

fun sum (n,i,s) = if i <= n then sum1 (n,i,s+i)

else (n,i,s)
and sum1(n,i,s) = sum (n,i+1,s);
Summary

I In Haskell and ML, we have basic types: integer, real,

boolean, char, string, enumeration, as well as tuples and
records
I Recursion and function composition are employed for
writing complex functional programs.
I Tuples increase functions flexibility
I Many functions are recursive; tail recursion has greater
performance
I Infix operators provide syntax sugaring
That’s all, folks!

Thanks for your attention...Questions?