Contents
- Introduction
- TypeScript Environment
- Representing Data Through Functions
- Euclidean Plane
- Fractals
- Unit Tests
You can find source code here: https://github.com/aelassas/functional-ts
Introduction
In TypeScript, functions are nothing but objects. Hence, functions can be constructed, passed as parameter, returned from functions or assigned into variables. Thus, TypeScript has first-class functions. More precisely, TypeScript supports the following:
- Higher-order functions arguments
- Higher-order functions results
- Nested functions
- Anonymous functions
- Closures
- Partial application (ECMAScript 5)
This article will not discuss the basics of functional programming, as you can find numerous resources on this topic. Instead, it will talk about functional programming in TypeScript applied to algebra, numbers, the Euclidean plane, and fractals. The examples provided in this article will start from simple to more complex but always illustrated in a simple, straightforward and easy-to-understand manner.
TypeScript Environment
To run the source code, you'll need to install Node.js. Once Node.js is installed, clone the GitHub repository:
git clone https://github.com/aelassas/functional-ts.git
Go to the source code folder, set up TypeScript environment and install all necessary dependencies with the following commands:
cd functional-ts
npm install
To run numbers demo, run the following command:
npm run numbers
To run Euclidean plane demo, run the following command:
npm run plane
To run fractals demo, run the following command:
npm run fractals
To run unit tests, run the following command:
npm test
Representing Data Through Functions
Let S
be any set of elements a
, b
, c
... (for instance, the books on the table or the points of the Euclidean plane) and let S'
be any subset of these elements (for instance, the green books on the table or the points in the circle of radius 1 centered at the origin of the Euclidean plane).
The Characteristic Function S'(x)
of the set S'
is a function which associates either true
or false
with each element x
of S
.
S'(x) = true if x is in S'
S'(x) = false if x is not in S'
Let S
be the set of books on the table and let S'
be the set of green books on the table. Let a
and b
be two green books, and let c
and d
be two red books on the table. Then:
S'(a) = S'(b) = true
S'(c) = S'(d) = false
Let S
be the set of the points in the Euclidean plane and let S'
be the set of the points in the circle of radius 1 centered at the origin of the Euclidean plane (0, 0) (unit circle). Let a
and b
be two points in the unit circle, and let c
and d
be two points in a circle of radius 2 centered at the origin of the Euclidean plane. Then:
S'(a) = S'(b) = true
S'(c) = S'(d) = false
Thus, any set S'
can always be represented by its Characteristic Function. A function that takes as argument an element and returns true
if this element is in S'
, false
otherwise. In other words, a set (abstract data type) can be represented through a function in TypeScript.
type Set<T> = (x: T) => boolean
In the next sections, we will see how to represent some fundamental sets in the algebra of sets through TypeScript in a functional way, then we will define generic binary operations on sets. We will then apply these operations on numbers then on subsets of the Euclidean plane. Sets are abstract data structures, the subsets of numbers and the subsets of the Euclidean plane are the representation of abstract data-structures, and finally the binary operations are the generic logics that works on any representation of the abstract data structures.
Sets
This section introduces the representation of some fundamental sets in the algebra of sets through TypeScript.
Empty set
Let E
be the empty set and Empty
its Characteristic function. In algebra of sets, E
is the unique set having no elements. Therefore, Empty
can be defined as follows:
Empty(x) = false if x is in E
Empty(x) = false if x is not in E
Thus, the representation of E
in TypeScript can be defined as follows:
const empty = <T>() => (e: T) => false
In algebra of sets, Empty
is represented as follows:
Thus, running the code below:
console.log('\nEmpty set:')
console.log('Is 7 in {}?', common.empty<number>()(7))
gives the following results:
Set All
Let S
be a set and S'
be the subset of S
that contains all the elements and All
its Characteristic function. In algebra of sets, S'
is the full set that contains all the elements. Therefore, All
can be defined like this:
All(x) = true if x is in S
Thus, the representation of S'
in TypeScript can be defined as follows:
const all = <T>() => (e: T) => true
In algebra of sets, All
is represented as follows:
Thus, running the code below:
console.log('\nSet All:')
console.log('Is 7 in integers set?', common.all<number>()(7))
gives the following results:
Singleton Set
Let E
be the Singleton set and Singleton
its Characteristic function. In algebra of sets, E
also known as unit set, or 1-tuple is a set with exactly one element e
. Therefore, Singleton
can be defined as follows:
Singleton(x) = true if x is e
Singleton(x) = false if x is not e
Thus, the representation of E
in TypeScript can be defined as follows:
const singleton = <T>(x: T) => (y: T) => x === y
Thus, running the code below:
console.log('\nSingleton set:')
console.log('Is 7 in the singleton set {0}?', common.singleton(0)(7))
console.log('Is 7 in the singleton set {7}?', common.singleton(7)(7)
gives the following results:
Other Sets
This section presents subsets of the integers set.
Even Numbers
Let E
be the set of even numbers and Even
its Characteristic function. In mathematics, an even number is a number which is a multiple of two. Therefore, Even
can be defined as follows:
Even(x) = true if x is a multiple of 2
Even(x) = false if x is not a multiple of 2
Thus, the representation of E
in TypeScript can be defined as follows:
const even = (x: number) => x % 2 === 0
Thus, running the code below:
console.log('\nEven numbers set:')
console.log('Is 99 in even numbers set?', numbers.even(99))
console.log('Is 998 in even numbers set?', numbers.even(998))
gives the following results:
Odd Numbers
Let E
be the set of odd numbers and Odd
its Characteristic function. In mathematics, an odd number is a number which is not a multiple of two. Therefore, Odd
can be defined as follows:
Odd(x) = true if x is not a multiple of 2
Odd(x) = false if x is a multiple of 2
Thus, the representation of E
in TypeScript can be defined as follows:
const odd = (x: number) => x % 2 === 1
Thus, running the code below:
console.log('\nOdd numbers set:')
console.log('Is 99 in odd numbers set?', numbers.odd(99))
console.log('Is 998 in odd numbers set?', numbers.odd(998))
gives the following results:
Multiples of 3
Let E
be the set of multiples of 3 and MultipleOfThree
its Characteristic function. In mathematics, a multiple of 3 is a number divisible by 3. Therefore, MultipleOfThree
can be defined as follows:
MultipleOfThree(x) = true if x is divisible by 3
MultipleOfThree(x) = false if x is not divisible by 3
Thus, the representation of E
in TypeScript can be defined as follows:
jsconst multipleOfThree = (x: number) => x % 3 === 0
Thus, running the code below:
console.log('\nMultiples of 3 set:')
console.log('Is 99 in multiples of 3 set?', numbers.multipleOfThree(99))
console.log('Is 998 in multiples of 3 set?', numbers.multipleOfThree(998))
gives the following results:
Multiples of 5
Let E
be the set of multiples of 5 and MultipleOfFive
its Characteristic function. In mathematics, a multiple of 5 is a number divisible by 5. Therefore, MultipleOfFive
can be defined as follows:
MultipleOfFive(x) = true if x is divisible by 5
MultipleOfFive(x) = false if x is not divisible by 5
Thus, the representation of E
in TypeScript can be defined as follows:
jsconst multipleOfFive = (x: number) => x % 5 === 0
Thus, running the code below:
console.log('\nMultiples of 5 set:')
console.log('Is 15 in multiples of 5 set?', numbers.multipleOfFive(15))
console.log('Is 998 in multiples of 5 set?', numbers.multipleOfFive(998))
gives the following results:
Prime Numbers
A long time ago, when I was playing with Project Euler problems, I had to resolve the following one:
By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13,
we can see that the 6th prime is 13.
What is the 10 001st prime number?
To resolve this problem, I first had to write a fast algorithm that checks whether a given number is prime or not. Once the algorithm written, I wrote an iterative algorithm that iterates through primes until the 10 001st prime number was found.
Let E
be the set of primes and Prime
its Characteristic function. In mathematics, a prime is a natural number greater than 1 that has no positive divisors other than 1 and itself. Therefore, Prime
can be defined as follows:
Prime(x) = true if x is prime
Prime(x) = false if x is not prime
Thus, the representation of E
in TypeScript can be defined as follows:
const prime = (x: number) => {
if (x <= 1) return false
if (x < 4) return true
if (x % 2 === 0) return false
if (x < 9) return true
if (x % 3 === 0) return false
const sqrt = Math.sqrt(x)
for (let i = 5; i <= sqrt; i += 6) {
if (x % i === 0) return false
if (x % (i + 2) === 0) return false
}
return true
}
Thus, running the code below to resolve our problem:
console.log('\nPrimes set:')
console.log('Is 2 in primes set?', numbers.prime(2))
console.log('Is 4 in primes set?', numbers.prime(4))
console.log('The 10 001st prime number is', numbers.getPrime(10001))
where getPrime
is defined below:
const getPrime = (p: number) => {
for (let i = 1, count = 0; ; i++) {
if (prime(i)) count++
if (count === p) return i
}
}
gives the following results:
Binary Operations
This section presents several fundamental operations for constructing new sets from given sets and for manipulating sets. Below the Ven diagram in the algebra of sets.
Union
Let E
and F
be two sets. The union of E
and F
, denoted by E U F
is the set of all elements which are members of either E
and F
.
Let Union
be the union operation. Thus, the Union
operation can be implemented as follows in TypeScript:
const union = <T>(e: Set<T>, f: Set<T>) => (x: T) => e(x) || f(x)
Running the code below:
console.log('\nUnion:')
console.log('Is 7 in the union of Even and Odd Integers Set?', core.union(numbers.even, numbers.odd)(7))
gives the following results:
Intersection
Let E
and F
be two sets. The intersection of E
and F
, denoted by E n F
is the set of all elements which are members of both E
and F
.
Let Intersection
be the intersection operation. Thus, the Intersection
operation can be implemented as follows in TypeScript:
jsconst intersection = <T>(e: Set<T>, f: Set<T>) => (x: T) => e(x) && f(x)
Running the code below:
console.log('\nIntersection:')
const multiplesOfThreeAndFive = core.intersection(numbers.multipleOfThree, numbers.multipleOfFive)
console.log('Is 15 a multiple of 3 and 5?', multiplesOfThreeAndFive(15))
console.log('Is 10 a multiple of 3 and 5?', multiplesOfThreeAndFive(10))
gives the following results:
Cartesian Product
Let E
and F
be two sets. The cartesian product of E
and F
, denoted by E × F
is the set of all ordered pairs (e, f)
such that e
is a member of E
and f
is a member of F
.
Let CartesianProduct
be the cartesian product operation. Thus, the CartesianProduct
operation can be implemented as follows in TypeScript:
const cartesianProduct = <T1, T2>(e: Set<T1>, f: Set<T2>) => (x: T1, y: T2) => e(x) && f(y)
Running the code below:
console.log('\nCartesian Product:')
const cp = core.cartesianProduct(numbers.multipleOfThree, numbers.multipleOfFive)
console.log('Is (9, 15) in MultipleOfThree x MultipleOfFive? ', cp(9, 15))
gives the following results:
Complements
Let E
and F
be two sets. The relative complement of F
in E
, denoted by E \ F
is the set of all elements which are members of E
but not members of F
.
Let Complement
be the relative complement operation. Thus, the Complement
operation can be implemented as follows in TypeScript:
const complement = <T>(e: Set<T>, f: Set<T>) => (x: T) => e(x) && !f(x)```
Running the code below:
```js
console.log('\nComplement:')
const c = core.complement(numbers.multipleOfThree, numbers.multipleOfFive)
console.log('Is 15 in MultipleOfThree \\ MultipleOfFive set? ', c(15))
console.log('Is 9 in MultipleOfThree \\ MultipleOfFive set? ', c(9))
gives the following results:
Symmetric Difference
Let E
and F
be two sets. The symmetric difference of E
and F
, denoted by E Δ F
is the set of all elements which are members of either E
and F
but not in the intersection of E
and F
.
Let SymmetricDifference
be the symmetric difference operation. Thus, the SymmetricDifference
operation can be implemented in two ways in TypeScript. A trivial way is to use the union and complement operations as follows:
const symmetricDifferenceWithoutXor = <T>(e: Set<T>, f: Set<T>) =>
(x: T) => union(complement<T>(e, f), complement(f, e))(x)
Another way is to use the XOR
binary operation as follows:
const symmetricDifferenceWithXor = <T>(e: Set<T>, f: Set<T>) => (x: T) => e(x) !== f(x)
Running the code below:
console.log('\nSymmetricDifference without XOR:')
const sdWithoutXor = core.symmetricDifferenceWithoutXor(numbers.prime, numbers.even)
console.log('Is 2 in the symetric difference of prime and even Sets? ', sdWithoutXor(2))
console.log('Is 4 in the symetric difference of prime and even Sets? ', sdWithoutXor(4))
console.log('Is 7 in the symetric difference of prime and even Sets? ', sdWithoutXor(7))
console.log('\nSymmetricDifference with XOR:')
const sdWithXor = core.symmetricDifferenceWithXor(numbers.prime, numbers.even)
console.log('Is 2 in the symetric difference of prime and even Sets? ', sdWithXor(2))
console.log('Is 4 in the symetric difference of prime and even Sets? ', sdWithXor(4))
console.log('Is 7 in the symetric difference of prime and even Sets? ', sdWithXor(7))
gives the following results:
Other Operations
This section presents other useful binary operations on sets.
Contains
Let Contains
be the operation that checks whether or not an element is in a set. This operation is a function that takes as parameter an element and returns true
if the element is in the set, false
otherwise.
Thus, this operation is defined as follows in TypeScript:
const contains = <T>(e: Set<T>, x: T) => e(x)
Therefore, running the code below:
console.log('\nContains:')
console.log('Is 7 in the singleton {0}? ', core.contains(common.singleton(0), 7))
console.log('Is 7 in the singleton {7}? ', core.contains(common.singleton(7), 7))
gives the following result:
Add
Let Add
be the operation that adds an element to a set. This operation is a function that takes as parameter an element and adds it to the set.
Thus, this operation is defined as follows in TypeScript:
const add = <T>(e: Set<T>, y: T) => (x: T) => x === y || e(x)
Therefore, running the code below:
console.log('\nAdd:')
console.log('Is 7 in {0, 7}? ', core.add<number>(common.singleton(0), 7)(7))
console.log('Is 0 in {1, 0}? ', core.add<number>(common.singleton(1), 0)(0))
console.log('Is 7 in {19, 0}? ', core.add<number>(common.singleton(19), 0)(7))
gives the following result:
Remove
Let Remove
be the operation that removes an element from a set. This operations is a function that takes as parameter an element and removes it from the set.
Thus, this operation is defined as follows in TypeScript:
const remove = <T>(e: Set<T>, y: T) => (x: T) => x !== y && e(x)
Therefore, running the code below:
console.log('\nRemove:')
console.log('Is 7 in {}? ', core.remove<number>(common.singleton(0), 0)(7))
console.log('Is 0 in {}? ', core.remove<number>(common.singleton(7), 7)(0))
gives the following result:
For Those Who Want To Go Further
You can see how easy we can do some algebra of sets in TypeScript through Functional Programming. In the previous sections was shown the most fundamental definitions. But, If you want to go further, you can think about:
- Relations over sets
- Abstract algebra, such as monoids, groups, fields, rings, K-vectorial spaces and so on
- Inclusion-exclusion principle
- Russell's paradox
- Cantor's paradox
- Dual vector space
- Theorems and Corollaries
Euclidean Plane
In the previous section, the fundamental concepts on sets were implemented in TypeScript. In this section, we will practice the concepts implemented on the Euclidean plane.
Drawing a Disk
A disk is a subset of a plane bounded by a circle. There are two types of disks. Closed disks which are disks that contain the points of the circle that constitutes its boundary, and Open disks which are disks that do not contain the points of the circle that constitutes its boundary.
In this section, we will set up the Characterstic function of the Closed disk and draw it in a HTML5 page.
To set up the Characterstic function, we first need a function that calculates the Euclidean Distance between two points in the plane. This function is implemented as follows:
function distance(p1: Point, p2: Point) {
return Math.sqrt((p1.x - p2.x) ** 2 + (p1.y - p2.y) ** 2)
}
where Point
is defined below:
class Point {
x: number
y: number
constructor(x: number, y: number) {
this.x = x
this.y = y
}
}
This formula is based on Pythagoras' Theorem.
where c
is the Euclidean distance, a²
is (p1.X - p2.X)²
and b²
is (p1.Y - p2.Y)²
.
Let Disk
be the Characteristic function of a closed disk. In algebra of sets, the definition of a closed disk in the reals set is as follows:
where a
and b
are the coordinates of the center and R
the radius.
Thus, the implementation of Disk
in TypeScript is as follows:
const disk = (center: Point, radius: number) => (p: Point) => distance(p, center) <= radius
In order to view the set in a HTML5 page, I decided to implement a function draw
that draws a set in the Euclidean plane. I chose HTML5 and thus used the canvas
element for drawing.
Thus, I've built the Euclidean plane illustrated below through the method draw
.
Below the implementation of the plane.
class Plane {
width: number
height: number
constructor(width: number, height: number) {
this.width = width
this.height = height
}
draw(set: PlaneSet, canvasId: string) {
const canvas = document.getElementById(canvasId) as HTMLCanvasElement
if (!canvas) throw new Error(`Canvas with id ${canvasId} not found`)
canvas.width = this.width
canvas.height = this.height
const context = canvas.getContext('2d') as CanvasRenderingContext2D
const semiWidth = this.width / 2
const semiHeight = this.height / 2
const xMin = -semiWidth
const xMax = semiWidth
const yMin = -semiHeight
const yMax = semiHeight
for (let x = 0; x < this.width; x++) {
const xp = xMin + (x * (xMax - xMin)) / this.width
for (let y = 0; y < this.height; y++) {
const yp = yMax - (y * (yMax - yMin)) / this.height
if (set(new Point(xp, yp))) context.fillRect(x, y, 1, 1)
}
}
}
clear(canvasId: string) {
const canvas = document.getElementById(canvasId) as HTMLCanvasElement
if (!canvas) throw new Error(`Canvas with id ${canvasId} not found`)
const context = canvas.getContext('2d') as CanvasRenderingContext2D
context.clearRect(0, 0, this.width, this.height)
}
}
In the draw
function, a canvas
having the same width and the same height as the Euclidean plane container is created. Then each point in pixels (x,y)
of the canvas
is replaced by a black point if it belongs to the set
. xMin
, xMax
, yMin
and yMax
are the bounding values illustrated in the figure of the Euclidean plane above.
Running the code below:
euclideanPlane = new Plane(200, 200)
euclideanPlane.draw(disk(new Point(0, 0), 50), 'disk')
where disk
is the id
of the canvas:
<canvas id="disk"></canvas>
gives the following result:
Drawing Horizontal and Vertical Half-planes
A horizontal or a vertical half-plane is either of the two subsets into which a plane divides the Euclidean space. A horizontal half-plane is either of the two subsets into which a plane divides the Euclidean space through a line perpendicular with the Y axis like in the figure above. A vertical half-plane is either of the two subsets into which a plane divides the Euclidean space through a line perpendicular with the X axis.
In this section, we will set up the Characteristic functions of the horizontal and vertical half-planes, draw them in a HTML5 page and see what we can do if we combine them with the disk subset.
Let HorizontalHalfPlane
be the Characteristic function of a horizontal half-plane. The implementation of HorizontalHalfPlane
in TypeScript is as follows:
const horizontalHalfPlane = (y: number, isLowerThan: boolean) =>
(p: Point) => (isLowerThan ? p.y <= y : p.y >= y)
Thus, running the code below:
euclideanPlane.draw(horizontalHalfPlane(0, true),'hhp')
where hhp
is the id
of the canvas:
<canvas id="hhp"></canvas>
gives the following result:
Let VerticalHalfPlane
be the Characteristic function of a vertical half-plane. The implementation of VerticalHalfPlane
in TypeScript is as follows:
jsconst verticalHalfPlane = (x: number, isLowerThan: boolean) =>
(p: Point) => (isLowerThan ? p.x <= x : p.x >= x)
Thus, running the code below:
euclideanPlane.draw(verticalHalfPlane(0, false),'vhp')
where vhd
is the id
of the canvas:
<canvas id="vhd"></canvas>
gives the following result:
In the first section of the article, we set up basic binary operations on sets. Thus, by combining the intersection of a disk
and a half-plane
for example, we can draw the half-disk subset.
Therefore, running the sample below:
euclideanPlane.draw(set.intersection(disk(new Point(0, 0), 50),
verticalHalfPlane(0, false)), 'hd')
where hd
is the id
of the canvas:
<canvas id="hd"></canvas>
gives the following result:
Functions
This section presents functions on the sets in the Euclidean plane.
Translate
Let translatePoint
be the function that translates a point in the plane. In Euclidean geometry, translatePoint
is a function that moves a given point a constant distance in a specified direction. Thus the implementation in TypeScript is as follows:
const translatePoint = (deltax: number, deltay: number) =>
(p: Point) => new Point(p.x + deltax, p.y + deltay)
where (deltax, deltay)
is the constant vector of the translation.
Let translate
be the function that translates a set in the plane. This function is simply implemented as follows in TypeScript:
const translate = (e: PlaneSet, deltax: number, deltay: number) =>
(p: Point) => e(translatePoint(-deltax, -deltay)(p))
translate
takes as parameters deltax
which is the delta distance in the first Euclidean dimension and deltay
which is the delta distance in the second Euclidean dimension. If a point P (x, y) is translated in a set S, then its coordinates will change to (x', y') = (x, delatx, y, deltay). Thus, the point (x' - delatx, y' - deltay) will always belong to the set S. In set algebra, translate
is called isomorph, in other words, the set of all translations forms the translation group T, which is isomorphic to the space itself. This explains the main logic of the function.
Thus, running the code below in our HTML5 page:
let translate_timer: ReturnType<typeof setInterval>
function translate_op() {
let deltay = 0
clearTimeout(scale_timer)
clearTimeout(rotate_timer)
translate_timer = setInterval(() => {
deltay = deltay <= euclideanPlane.height ? deltay + 20 : 0
euclideanPlane.draw(translate(disk(new Point(0, -50), 50), 0, deltay), 'ep_op')
}, 1000)
}
where ep_op
is the id
of the canvas:
<canvas id="ep_op"></canvas>
gives the following result:
Homothety
Let scalePoint
be the function that sends any point M to another point N such that the segment SN is on the same line as SM, but scaled by a factor λ. In algebra of sets, Scale
is formulated as follows:
Thus the implementation in TypeScript is as follows:
const scalePoint = (lambdax: number, lambday: number, deltax: number, deltay: number)
=> (p: Point) => new Point(lambdax * p.x + deltax, lambday * p.y + deltay)
where (deltax, deltay)
is the constant vector of the translation and (lambdax, lambday)
is the lambda vector.
Let scale
be the function that applies an homothety on a set in the plan. This function is simply implemented as follows in TypeScript:
const scale = (e: PlaneSet, lambdax: number, lambday: number, deltax: number,
deltay: number) => (p: Point) => e(scalePoint(1 / lambdax, 1 / lambday,
-deltax / lambdax, -deltay / lambday)(p))
scale
takes as parameters deltax
which is the delta distance in the first Euclidean dimension, deltay
which is the delta distance in the second Euclidean dimension and (lambdax, lambday)
which is the constant factor vector λ. If a point P (x, y) is transformed through scale
in a set S, then its coordinates will change to (x', y') = (lambdax * x, delatx, lambday * y, deltay). Thus, the point ((x'- delatx)/lambdax, (y' - deltay)/lambday) will always belong to the set S, If lambda is different from the vector 0, of course. In algebra of sets, scale
is called isomorph, in other words, the set of all homotheties forms the Homothety group H, which is isomorphic to the space itself \ {0}. This explains the main logic of the function.
Thus, running the code below in our HTML5 page:
let scale_timer: ReturnType<typeof setInterval>
function scale_op() {
let deltay = 0
let lambday = 0.05
clearTimeout(translate_timer)
clearTimeout(rotate_timer)
scale_timer = setInterval(() => {
deltay = deltay <= euclideanPlane.height ? deltay + 20 : 0
lambday = deltay <= euclideanPlane.height ? lambday + 0.05 : 0.05
euclideanPlane.draw(scale(disk(new Point(0, -50), 50), 1, lambday, 0, deltay), 'ep_op')
}, 1000)
}
gives the following result:
Rotate
Let rotatePoint
be the function that rotates a point with an angle θ. In matrix algebra, rotatePoint
is formulated as follows:
where (x', y') are the co-ordinates of the point after rotation, and the formula for x' and y' is as follows:
The demonstration of this formula is very simple. Have a look at this rotation.
Below the demonstration:
Thus the implementation in TypeScript is as follows:
const rotatePoint = (theta: number) => (p: Point) => new Point(p.x * Math.cos(theta)
- p.y * Math.sin(theta), p.x * Math.sin(theta) + p.y * Math.cos(theta))
Let rotate
be the function that applies a rotation on a set in the plane with the angle θ. This function is simply implemented as follows in TypeScript.
const rotate = (e: PlaneSet, theta: number) => (p: Point) => e(rotatePoint(-theta)(p))
rotate
is a function that takes as parameter theta
which is the angle of the rotation. If a point P (x, y) is transformed through rotate
in a set S, then its coordinates will change to (x', y') = (x * cos(theta) - y * sin(theta), x * sin(theta), y * cos(theta)). Thus, the point (x' * cos(theta), y' * sin(theta), y' * cos(theta) - x' * sin(theta)) will always belong to the set S. In algebra of sets, rotate
is called isomorph, in other words, the set of all rotations forms the Rotation group R, which is isomorphic to the space itself. This explains the main logic of the function.
Thus, running the code below in our HTML5 page:
let rotate_timer: ReturnType<typeof setInterval>
function rotate_op() {
let theta = 0
clearTimeout(translate_timer)
clearTimeout(scale_timer)
rotate_timer = setInterval(() => {
euclideanPlane.draw(rotate(horizontalHalfPlane(-90, true), theta), 'ep_op')
theta = (theta + Math.PI / 2) % (2 * Math.PI)
}, 1000)
}
gives the following result:
For Those Who Want to Go Further
Very simple, isn't it? For those who want to go further, you can explore these:
- Ellipse
- Three-dimensional Euclidean space
- Ellipsoide
- Paraboloid
- Hyperboloid
- Spherical harmonics
- Superellipsoid
- Haumea
- Homoeoid
- Focaloid
Fractals
Fractals are sets that have a fractal dimension that usually exceeds their topological dimension and may fall between the integers. For example, the Mandelbrot set is a fractal defined by a family of complex quadratic polynomials:
Pc(z) = z^2 + c
where c
is a complex. The Mandelbrot fractal is defined as the set of all points c
such that the above sequence does not escape to infinity. In algebra of sets, this is formulated as follows:
Fractals (abstract data type) can always be represented as follows in TypeScript:
type Fractal = (z: Complex, c: Complex) => Complex
Complex Numbers and Drawing
In order to be able to draw fractals, I needed to manipulate Complex numbers. Thus, I created the Complex
class below:
class Complex {
x: number
y: number
static zero = new Complex(0, 0)
constructor(x: number, y: number) {
this.x = x
this.y = y
}
abs() {
return Math.sqrt(this.x * this.x + this.y * this.y)
}
toString() {
return this.x + ' + i * ' + this.y
}
}
function add(z1: Complex, z2: Complex) {
return new Complex(z1.x + z2.x, z1.y + z2.y)
}
function substract(z1: Complex, z2: Complex) {
return new Complex(z1.x - z2.x, z1.y - z2.y)
}
function multiply(z1: Complex, z2: Complex) {
return new Complex(z1.x * z2.x - z1.y * z2.y, z1.x * z2.y + z1.y * z2.x)
}
Mandelbrot Fractal
I created a Mandelbrot Fractal (abstract data type representation) P(z) = z^2 + c
that is available below.
const mandelbrot = (z: Complex, c: Complex) => add(multiply(z, z), c)
In order to be able to draw Complex numbers, I created a ComplexPlane
class. Below is the implementation in TypeScript.
class ComplexPlane {
width: number
height: number
real_min: number
real_max: number
imaginary_min: number
imaginary_max: number
boundary: number
fractalIterationsPerPixel: number
canvasId: string
constructor(
width: number,
height: number,
real_min: number,
real_max: number,
imaginary_min: number,
imaginary_max: number,
boundary: number,
fractalIterationsPerPixel: number,
canvasId: string,
) {
this.width = width
this.height = height
this.real_min = real_min
this.real_max = real_max
this.imaginary_min = imaginary_min
this.imaginary_max = imaginary_max
this.boundary = boundary
this.fractalIterationsPerPixel = fractalIterationsPerPixel
this.canvasId = canvasId
}
draw(fractal: Fractal) {
const canvas = document.getElementById(this.canvasId) as HTMLCanvasElement
canvas.width = this.width
canvas.height = this.height
const context = canvas.getContext('2d') as CanvasRenderingContext2D
context.fillStyle = 'white'
for (let x = 0; x < this.width; x++) {
const xp = this.real_min + (x * (this.real_max - this.real_min)) / this.width
for (let y = 0; y < this.height; y++) {
const yp = this.imaginary_max - (y * (this.imaginary_max - this.imaginary_min)) / this.height
const c = new Complex(xp, yp)
let z = Complex.zero
for (let k = 0; k < this.fractalIterationsPerPixel; k++) z = fractal(z, c)
if (z.abs() < this.boundary) context.fillRect(x, y, 1, 1)
}
}
}
/*
* Display 'Please wait...' at the center of the canvas
*
*/
pleaseWait() {
const canvas = document.getElementById(this.canvasId) as HTMLCanvasElement
canvas.width = this.width
canvas.height = this.height
const context = canvas.getContext('2d') as CanvasRenderingContext2D
context.fillStyle = 'white'
context.fillText('Please wait...', this.width / 2 - 30, this.height / 2)
}
}
Thus, running the code below:
const complexPlane = new ComplexPlane(300, 300, -1.5, 1.5, -1.5, 1.5, 1.5, 20, 'fractal')
const mandelbrot = (z: Complex, c: Complex) => add(multiply(z, z), c)
complexPlane.pleaseWait()
setTimeout(() => complexPlane.draw(mandelbrot), 500)
where fractal
is the id
of the canvas:
<canvas id="fractal"></canvas>
gives the following result:
For Those Who Want to Go Further
For those who want to go further, you can explore these:
- Newton Fractals
- Julia Fractals
- Other Fractals
Unit Tests
Below are the unit tests for sets of numbers.
import * as core from '../src/set.core'
import * as common from '../src/set.common'
import * as numbers from '../src/set.numbers'
describe('Test empty set', () => {
it('should test empty set', () => {
expect(common.empty<number>()(7)).toBeFalsy()
})
})
describe('Test set all', () => {
it('should test set all', () => {
expect(common.all<number>()(7)).toBeTruthy()
})
})
describe('Test singleton set', () => {
it('should test singleton set', () => {
expect(common.singleton(0)(7)).toBeFalsy()
expect(common.singleton(7)(7)).toBeTruthy()
})
})
describe('Test even numbers set', () => {
it('should test even numbers set', () => {
expect(numbers.even(99)).toBeFalsy()
expect(numbers.even(998)).toBeTruthy()
})
})
describe('Test odd numbers set', () => {
it('should test odd numbers set', () => {
expect(numbers.odd(99)).toBeTruthy()
expect(numbers.odd(998)).toBeFalsy()
})
})
describe('Test Multiples of 3 set', () => {
it('should test Multiples of 3 set', () => {
expect(numbers.multipleOfThree(99)).toBeTruthy()
expect(numbers.multipleOfThree(998)).toBeFalsy()
})
})
describe('Test Multiples of 5 set', () => {
it('should test Multiples of 5 set', () => {
expect(numbers.multipleOfFive(15)).toBeTruthy()
expect(numbers.multipleOfFive(998)).toBeFalsy()
})
})
describe('Test Primes set', () => {
it('should test Primes set', () => {
expect(numbers.prime(2)).toBeTruthy()
expect(numbers.prime(4)).toBeFalsy()
expect(numbers.getPrime(10001)).toBe(104743)
})
})
describe('Test union', () => {
it('should test union', () => {
expect(core.union(numbers.even, numbers.odd)(7)).toBeTruthy()
})
})
describe('Test intersection', () => {
it('should test intersection', () => {
const multiplesOfThreeAndFive = core.intersection(numbers.multipleOfThree, numbers.multipleOfFive)
expect(multiplesOfThreeAndFive(15)).toBeTruthy()
expect(multiplesOfThreeAndFive(10)).toBeFalsy()
})
})
describe('Test Cartesian product', () => {
it('should test Cartesian product', () => {
const cp = core.cartesianProduct(numbers.multipleOfThree, numbers.multipleOfFive)
expect(cp(9, 15)).toBeTruthy()
expect(cp(10, 15)).toBeFalsy()
expect(cp(9, 10)).toBeTruthy()
})
})
describe('Test Complement', () => {
it('should test Complement', () => {
const c = core.complement(numbers.multipleOfThree, numbers.multipleOfFive)
expect(c(15)).toBeFalsy()
expect(c(9)).toBeTruthy()
})
})
describe('Test Symetric difference without Xor', () => {
it('should test Symetric difference without Xor', () => {
const sdWithoutXor = core.symmetricDifferenceWithoutXor(numbers.prime, numbers.even)
expect(sdWithoutXor(2)).toBeFalsy()
expect(sdWithoutXor(4)).toBeTruthy()
expect(sdWithoutXor(7)).toBeTruthy()
})
})
describe('Test Symetric difference with Xor', () => {
it('should test Symetric difference with Xor', () => {
const sdWithXor = core.symmetricDifferenceWithXor(numbers.prime, numbers.even)
expect(sdWithXor(2)).toBeFalsy()
expect(sdWithXor(4)).toBeTruthy()
expect(sdWithXor(7)).toBeTruthy()
})
})
describe('Test Contains', () => {
it('should test Contains', () => {
expect(core.contains(common.singleton(0), 7)).toBeFalsy()
expect(core.contains(common.singleton(7), 7)).toBeTruthy()
})
})
describe('Test Add', () => {
it('should test Add', () => {
expect(core.contains(common.singleton(0), 7)).toBeFalsy()
expect(core.add<number>(common.singleton(0), 7)(7)).toBeTruthy()
expect(core.add<number>(common.singleton(1), 0)(0)).toBeTruthy()
expect(core.add<number>(common.singleton(19), 0)(7)).toBeFalsy()
})
})
describe('Test Remove', () => {
it('should test Remove', () => {
expect(core.remove<number>(common.singleton(0), 0)(7)).toBeFalsy()
expect(core.remove<number>(common.singleton(7), 7)(0)).toBeFalsy()
expect(core.remove<number>(common.all<number>(), 0)(0)).toBeFalsy()
expect(core.remove<number>(common.all<number>(), 0)(7)).toBeTruthy()
})
})
After running the unit tests with the following command:
npm test
We reach 100% of code coverage.
The coverage report is written in ./coverage
folder.
That's it! I hope you enjoyed reading.
Top comments (2)
gcanti.github.io/fp-ts/
Thanks, this is awesome! Did you find that these prime checking/generation implementations here were sufficient for some of the more involved project Euler problems?