FIT2102
Programming Paradigms Workshop 3
Functional Programming Pure functions TypeScript
Faculty of Information Technology
Learning Outcomes
● Create programs in JavaScript in a functional style
● Explain the role of pure functional programming style in managing side effects
● Create programs in TypeScript using the types to ensure correctness at
compile time
● Explain how Generics allow us to create type safe but general and reusable
code
● Compare and contrast strongly, dynamically and gradually typed languages
● Describe how compilers that support type inference assist us in writing type
safe code
● Create linked-lists and functions that operate over them, using:
○ Objects and classes
○ Only functions (Church encoded lists)
Recap: Creating Objects from Classes
class Person {
constructor(name, occupation) {
this.name = name
this.occupation = occupation
}
sayHello() {
console.log(`Hi, my name’s ${this.name} and I ${this.occupation}!`)
} }
const tim = new Person(“Tim”,”lecture Programming Paradigms”)
tim.sayHello()
> Hi, my name’s Tim and I lecture Programming Paradigms!
Recap: Object-Oriented Polymorphism
class LoudPerson extends Person {
sayHello() {
console.log(this.greeting.toUpperCase())
}
}
const tims = [
new Person(“Tim”,”lecture Programming Paradigms”),
new LoudPerson(“Tim”,”shout about Programming Paradigms”)
]
tims.forEach(t => t.sayHello())
Hi, my name’s Tim and I lecture Programming Paradigms!
HI, MY NAME’S TIM AND I SHOUT ABOUT PROGRAMMING PARADIGMS!
Classic OO using subtyping to achieve polymorphism
A single interface for different types.
Later today we will be introducing another way of creating functions that operate over different types: parametric polymorphism
Recap: Dependency Injection with Functions
class Person {
constructor(name, occupation, voiceTransform = g => g) {
this.name = name
this.occupation = occupation
this.voiceTransform = voiceTransform
}
sayHello() {
console.log(this.voiceTransform(this.greeting))
}
}
const tims = [
new Person(“Tim”, “lecture Programming Paradigms”),
new Person(“Tim”, “shout about Programming Paradigms”, g => g.toUpperCase())
]
tims.forEach(t => t.sayHello())
Hi, my name’s Tim and I lecture Programming Paradigms!
HI, MY NAME’S TIM AND I SHOUT ABOUT PROGRAMMING PARADIGMS!
Default to “identity” function
We “inject” a dependency on toUpperCase from outside the Person class
Recap: Closures and higher-order functions
A function and the set of variables it accesses from its enclosing scope is called a closure
const multiply = =>
const double = multiply(2) [5,8,3,1,7,6,2].map(double)
> [ 10, 16, 6, 2, 14, 12, 4 ]
e.g., the closure returned by multiply(2) includes x=2
x
y=> *y
x
Functions that take other functions as parameters
or that return functions are called higher-order functions.
Recap: Arrow Function Syntax
A function is a transform from one set of things to another:
Input Set
Output Set
function(x) {
return x / 3
}
x => x/3
This function is a transform from number to number
In math we would be more precise: e.g. the set of integers Z
to (a subset of) rationals Q
Arrow function syntax – don’t panic
const multiply = x=> y=> x*y
function multiply(x) { return y => y * x;
}
function multiply(x) { return function(y) {
return x * y; }
}
Semantically all the same! (unless they refer to this)
const operationOnTwoNumbers = f => x => y => f(x,y)
function operationOnTwoNumbers(f) {
return function(x) {
return function(y) {
return f(x,y);
} }
}
Semantically the same!
const operationOnTwoNumbers = f => x => y => f(x,y)
const multiply = operationOnTwoNumbers((x,y) => x*y)
const double = multiply(2)
[5,8,3,1,7,6,2].map(double)
Currying
translating a function that takes multiple arguments into a sequence of unary functions.
const operationOnTwoNumbers = f => x => y => f(x,y)
const multiply = operationOnTwoNumbers((x,y) => x*y)
const double = multiply(2)
[5,8,3,1,7,6,2].map(double)
Named after the mathematician Haskell Curry.
Multiply is a curried function
TypeScript Type Annotations
TypeScript is a superset of JavaScript that introduces type annotations
Any time you declare a variable, function, parameter, etc you can add a type annotation:
let x : number;
The compiler can often infer types from the context, i.e. type inference.
let x = 1;
Here x is obviously a number so an annotation is redundant.
When a type cannot be inferred, the type is any
Thus, TypeScript’s default approach to type checking is gradually typed.
TypeScript Type Errors
let x = 1; // type number is inferred
x = ‘hello’
> error TS2322: Type ‘”hello”‘ is not assignable to type ‘number’.
TypeScript Foo
const operationOnTwoNumbers =
(f:(x:number, y:number)=>number) =>
(x:number) =>
(y:number) =>
f(x,y)
function operationOnTwoNumbers(f:(x:number, y:number)=>number) {
return function(x:number) {
return function(y:number) {
return f(x,y);
} }
}
Type Aliases
type BinaryNumberFunc = (x:number, y:number) => number
type CurriedNumberFunc = (x:number) => (y:number) => number
const operationOnTwoNumbers: (f:BinaryNumberFunc)=>CurriedNumberFunc
= f=>x=>y=>f(x,y)
function operationOnTwoNumbers(f:BinaryNumberFunc):CurriedNumberFunc {
return function(x) {
return function(y) {
return f(x,y)
} }
}
Generic Types: parametric polymorphism
type BinaryFunction
type CurriedFunction
T is a type parameter (or type variable)
const curry:
= f=>x=>y=>f(x,y)
function curry
return function(x) {
return function(y) {
return f(x,y)
} }
}
Generic Types
type BinaryFunction
type CurriedFunction
const curry:
= f=>x=>y=>f(x,y)
const twoToThe = curry(Math.pow)(2)
twoToThe(8)
> 256
const concat = Array.prototype.concat.bind([]),
curriedConcat = curry(concat)
[[1,2],[1,2],[1,2]].map(curriedConcat([0])))
> [[0,1,2],[0,1,2],[0,1,2]]
⇦ This still type checks This is just creating a standalone concat
function from the concat method on Array
⇦ But now so does this:
It works for numbers or arrays
Generic Types
type BinaryFunction
type CurriedFunction
const curry:
= f=>x=>y=>f(x,y);
const twoToThe = curry(Math.pow)(2)
twoToThe(8)
> 256
⇦ This still type checks
const repeat = (n: number, s: string) => s.repeat(n)
console.log([‘a’,’b’,’c’].map(curry(repeat)(3)))
> [“aaa”, “bbb”, “ccc”]
⇦ But now so does this! (T ≠ U, T ≠ V)
Lecture Activity 1
… to be announced
Linked Lists
interface IListNode
data: T;
next?: IListNode
}
const l:IListNode
data: 1,
next: {
data: 2,
next: {
data: 3,
next: null }
} }
function length
return !l ? 0 : 1+length(l.next);
}
> length(l)
3
function forEach
if (l) {
f(l.data);
forEach(f, l.next);
}
}
> forEach(console.log, l);
1
2
3
Linked Lists
interface IListNode
data: T;
next: List
}
Union Type
function length
return !l ? 0 : 1+length(l.next)
}
> length(l)
3
function forEach
if (l) {
f(l.data)
forEach(f, l.next)
}
}
> forEach(console.log, l)
1
2
3
type List
const l:IListNode
data: 1,
next: {
data: 2,
next: {
data: 3,
next: null }
} }
Linked Lists – map
interface IListNode
data: T;
next: List
}
type List
function map
return l ?
data: f(l.data),
next: map(f, l.next)
} : null
}
> forEach(console.log, map(x=>2*x, l))
2
4
6
Linked Lists – map with a class constructor
interface IListNode
data: T;
next: ListPtr
}
type List
}
class ListNode
constructor(
public data: T,
public next: List
}
const list = new ListNode(1,new ListNode(2, new ListNode(3, null)))
function map
{
return l ? new ListNode
: null
> forEach(console.log, map(x=>2*x, l))
2
4
6
Linked Lists – concat
interface IListNode
data: T;
next: List
}
type List
? = Optional parameter
⇩
function concat
return a ? new ListNode(a.data, concat(a.next, b))
class ListNode
constructor(
🙁
b ? concat(b)
: undefined )
}
public data: T,
public next: List
> forEach(console.log, concat(l,map(x=>3+x, l)))
1
2
3
4 5 6
}
Cons Lists (Church encoding)
Can we create lists with only lambda (anonymous) functions?
const cons = (head, rest) =>
const head = => list((head, rest)=> head)
const rest = list => list((head, rest)=> rest)
const aList = cons(‘Lists’, cons(“don’t”, cons(“get”, cons(‘any’,
cons(‘simpler’, cons(‘than’, cons(‘this’,
null))))))) head(rest(rest(aList))) ⇨ “get”
f
=> f(head, rest)
list
Types for Cons Lists
Make the shapes of functions we expect on the previous slide explicit
/**
* A ConsList is either a function created by cons, or empty (null)
*/
type ConsList
/**
* The return type of the cons function, is itself a function
* which can be given a selector function to pull out either the head or rest
*/
type Cons
/**
* a selector will return either the head or rest
*/
type Selector
Typed Cons List Functions
/**
* cons “constructs” a list node, if no second argument is specified it is the last node in the list */
function cons
return (selector: Selector
}
/**
* head returns the first element in the list
* @param list is a Cons (note, not an empty ConsList) */
function head
return
}
/**
* rest everything but the head
* @param list is a Cons (note, not an empty ConsList) */
function rest
return
}
How do we get stuff out?
const aList = cons(‘Lists’, cons(“don’t”, cons(“get”,
cons(‘any’, cons(‘simpler’,
cons(‘than’, cons(‘this’)))))))
function listToString(l:ConsList
if (!l) {
return ”
} else {
return head(l) + ‘ ‘ + listToString(rest(l))
}
}
How do we get stuff out?
const aList = cons(‘Lists’, cons(“don’t”, cons(“get”,
cons(‘any’, cons(‘simpler’,
cons(‘than’, cons(‘this’)))))))
const listToString: (l:ConsList
= l => l ? head(l) + ‘ ‘ + listToString(rest(l)) : ”
console.log(listToString(aList));
> Lists don’t get any simpler than this!
Lecture Activity 2
… to be announced
Conclusions: Avoid hand-coded loops
for ([initialization]; [condition]; [final-expression]) statement
The initialization can initialise to the wrong value (e.g. n instead of n-1, 1 instead of 0) or initialise the wrong variable.
The condition test can use = instead of ==, <= instead of < or test the wrong variable, etc. The final-expression can (again) increment the wrong variable.
The statement body might change the state of variables being tested in the termination condition since they are in scope.
Conclusions: Function Purity
Every function that we’ve looked at today (except console.log) has been pure.
A pure function does not change the state of the surrounding program, or the world. More than that, within the functions we did not reassign variables.
We say that these functions had referential transparency.
Referential transparency gives simple, reusable, safe functions.
Conclusions: Functions as a model of computation
The cons lists created only through functions are an example of “Church Encoding”
In the 1930s Alonzo Church created a model of computation which used only anonymous functions.
This model of computation became known as the “Lambda Calculus” We will meet the lambda calculus properly in coming weeks.