Forem: James Robb

What is a Monad?

James Robb — Fri, 12 Apr 2024 08:17:59 +0000

A monad is a monoid in the category of Endofunctors. Okay, post completed, need I say more?... Fine, okay then.

A monad is a very powerful concept allowing for data flow, transformation and control in a managed form. You can think of it as an isolated, self-contained, step within a computation stream. The key component to support this is the bind function:

(>>=) :: Monad m => m a -> (a -> m b) -> m b

You might call it map or pipe although both are slightly incorrect but thats just semantics.

A monad is defined as follows:

Monad, (from Greek monas “unit”), an elementary individual substance that reflects the order of the world and from which material properties are derived. The term was first used by the Pythagoreans as the name of the beginning number of a series, from which all following numbers derived.

Source: Britannica

Okay, so what about monoids vs monads?

A monad is focused on sequencing computations and handling side effects.
A monoid is focused on combining values, typically with an associative operation mappend, also known as (<>), and an identity initialiser mempty to create an empty instance.

What about an Endofunctor?

An Endofunctor is a specific type of Functor where the source and target categories are the same. In other words, it is a functor from a category to itself.

The core of all Functors is the fmap operation:

fmap :: Functor f => (a -> b) -> f a -> f b

So where a functor might fmap a Functor String to a Functor Int, an endofunctor would only ever fmap a Functor Something to Functor Something.

Now you know all the components of a Monad. It's incredibly powerful and you actually use them all the time without realising it. There are many common Monads like Maybe, Reader, Writer, Continuation, etc.

An example - The `Maybe` monad

The Maybe monad is a monadic data-structure which represents the possibility of a value existing. This is useful in cases where you have computations that may return zero or one value.

For example, if I have a function stringToInt(input: string): number then this would be wrongly typed since we cannot guarantee that the given string is a valid number and defaulting a bad string to 0 or any other number is disingenuous.

Instead we could utilise the type signature stringToInt(input: string): Maybe<number> which is far more correct and allows us to contain the possible presence of that value cleanly for future computations to handle.

In typescript I could write the Maybe monad as:

// Maybe Monad
class Maybe<T> {
  private value: T  | null;

  constructor(value: T | null = null) {
    this.value = value;
  }

  // Functor: map
  map<U>(f: (value: T) => U): Maybe<U> {
    return this.value !== null ? new Maybe<U>(f(this.value)) : new Maybe<U>();
  }

  // Monad: flatMap (bind)
  flatMap<U>(f: (value: T) => Maybe<U>): Maybe<U> {
    return this.value !== null ? f(this.value) : new Maybe<U>();
  }

  // Example non-required methods you may wish to add
  isJust(): boolean {
    return this.value !== null;
  }

  isNothing(): boolean {
    return this.value === null;
  }

  withDefault(fallback: T): T {
    return this.value !== null ? this.value : fallback;
  }

  // Other more advanced methods you may wish to add
  map2<U, R>(f: (ours: T, theirs: U) => Maybe<R>, other: Maybe<U>): Maybe<R> {
    if(this.value !== null && other.value !== null) {
        return f(this.value, other.value);
    }

    return new Maybe<R>();
  }
}

// Example Usage
const maybeValue: Maybe<number> = new Maybe(5);

// Endofunctor example: mapping over the Maybe value
const incrementedMaybe: Maybe<number> = maybeValue.map(value => value + 1);
console.log(incrementedMaybe); // Output: Maybe { value: 6 }

// Monad example: binding Maybe with another Maybe
const doubledMaybe: Maybe<number> = maybeValue.flatMap(value => new Maybe(value * 2));
console.log(doubledMaybe); // Output: Maybe { value: 10 }

// Monad example: is empty
const empty = new Maybe<string>();
console.log(empty.isNothing()); // Output: true
console.log(empty.isJust()); // Output: false
console.log(empty.withDefault("test")); // Output: "test"

// Monad example: has value
const withValue = new Maybe<string>("abc123");
console.log(withValue.isNothing()); // Output: false
console.log(withValue.isJust()); // Output: true
console.log(withValue.withDefault("test")); // Output: "abc123"

// Combinatory example: Mapping two monadic values
const first = new Maybe<string>("abc");
const second = new Maybe<number>(123);
const third = first.map2(
    (ours: string, theirs: number) => new Maybe<string>(ours + theirs.toString()),
    second
);
console.log(third); // Output: Maybe { value: "abc123" }

Conclusions

Now you should understand Monads. They simply wrap values, can map between values and bind values in a computational pipeline friendly manner: When you think of a Monad, think of type transformations running over time.

I hope that you found some value in todays post and if you have any questions, comments or suggestions, feel free to leave those in the comments area below the post!

Willans' Formula

James Robb — Thu, 01 Dec 2022 19:15:14 +0000

In todays post we will be implementing Willans’ Formula. This is an algorithm for finding the nth prime number in the set of prime numbers and was first described by Willans in his 1964 paper "On Formulae for the nth Prime Number" and the first version of the formula provided is as follows:

p_{n}=1+\sum _{i=1}^{2^{n}}\left\lfloor \left({\frac {n}{\sum _{j=1}^{i}\left\lfloor \left(\cos {\frac {(j-1)!+1}{j}}\pi \right)^{2}\right\rfloor }}\right)^{1/n}\right\rfloor

Don't panic at the sight of the formula, at its core it consists of basic arithmetic and trigonometric functions plus the numbers 1 and 2 and the constant PI. Pseudo code for the formula could be presented as follows:

fn X'(i, n) -> floor (Y'(i, n) ^ (1 / n))

fn Y'(i, n) -> n / sum ( floor ( cos ( ((j - 1)! + 1 / j) * PI ^ 2 ) ) )

n = 5
result = sum ( map i in range(1, power(2, n)) => 1 + X'(i, n) )

Sidenote 1:

This algorithm is not efficient, as per wikipedia:

In addition to the appearance of (j-1)!, it computes p ^ n by adding up p ^ n copies of 1; for example, p ^ 5 = 1+1+1+1+1+1+1+1+1+1+1+0+0...+0 = 11

Willans also presented us alternative formulas, we will be implementing the version shown above but be aware that due to its inefficiency and terrible runtime complexity, you may not be able to generate primes higher than those in a double digit order. Some of the other formulas presented to us by Willans are more efficient but for now we shall focus purely on formula number 1.

Sidenote 2:

For reference, you can see each version of Willans formula here.

Tests

For brevity we will test the numbers from 0 through 10, below are a collection of pytest tests covering these cases. Thus, in test_willans.py we have the following:

from main import willans
from pytest import raises

def test_0Throws():
    with raises(ZeroDivisionError):
       willans(0)

def test_1stPrimeIs2():
    assert willans(1) == 2

def test_2ndPrimeIs3():
    assert willans(2) == 3

def test_3rdPrimeIs5():
    assert willans(3) == 5

def test_4thPrimeIs7():
    assert willans(4) == 7

def test_5thPrimeIs11():
    assert willans(5) == 11

def test_6thPrimeIs13():
    assert willans(6) == 13

def test_7thPrimeIs17():
    assert willans(7) == 17

def test_8thPrimeIs19():
    assert willans(8) == 19

def test_9thPrimeIs23():
    assert willans(9) == 23

def test_10thPrimeIs29():
    assert willans(10) == 29

Implementation

In main.py we have the following implementation of Willans formula:

from math import cos, factorial, floor, pi


def X(i: int, n: int) -> int:
    y = Y(i, n)
    e = 1 / n
    r = pow(y, e)

    return floor(r)


def Y(i: int, n: int) -> float:
    def iterator(j: int) -> int:
        f = factorial(j - 1) + 1
        a = f / j
        b = a * pi
        c = cos(b)
        e = pow(c, 2)

        return floor(e)

    cs = [iterator(j) for j in range(1, i + 1)]

    return n / sum(cs)


def willans(n: int) -> int:
    xs = [X(i, n) for i in range(1, pow(2, n) + 1)]
    s = sum(xs)

    return 1 + floor(s)


lower_bound = 1
upper_bound = 6
result = [willans(n) for n in range(lower_bound, upper_bound + lower_bound)]

print(result)  # [2, 3, 5, 7, 11, 13]

Sidenote 3:

For the implementation of the algorithm I use pythons built in math module but this has issues with values over a certain size when conducting division operations on large integers and floats.

It would be worth using tools such as pandas or scikit learn if you wish to improve the efficiency and scale of the implementation.

Conclusions

I originally believed, as I am sure most people do, that there was no uniform algorithm or formula for generating the nth prime number but Willans does indeed stand up to scrutiny thus far. That said, it is so inefficient and exponentially slow as an algorithm that practically it is useless even if correct.

I came across this algorithm a few weeks ago when watching this fantastic video by Eric Rowland and I highly recommend giving it a watch.

After watching, I did further research as outlined in the links above and came up with the implementation of the formula seen in this article over that time. I find such algorithms and formulae to be utterly fascinating and perhaps in the future I will write more mathematics based algorithms in this series but for now, the article is at an end.

I hope that you found some value in todays post and if you have any questions, comments or suggestions, feel free to leave those in the comments area below the post!

Substring search

James Robb — Tue, 05 Apr 2022 21:39:43 +0000

One common task we do daily as software engineers is working with strings to parse inputs, validate values and the like.

In this article we will be writing a function to check if a given string contains a given substring. This process is commonly known as a substring search and is usually a built-in feature of most languages but we will implement the functionality for ourselves to understand the process at hand!

For todays article we will be working with Rust as our language of choice and Cargo which is the Rust package manager.

To begin we must execute the following in the command line:

mkdir substring_search
cd substring_search
cargo init --name substring_search

This will create a directory called substring_search, move into that directory and then initialise a new Rust project via Cargo named substring_search.

Tests

As always, lets begin first with the tests!

In src/main.rs we can write the following:

#[cfg(test)]
mod tests {
    const SEARCH_STRING_SLICE: &'static str = "abcdefg";

    #[test]
    fn returns_true_for_substring_at_start_of_string() {
        let haystack = SEARCH_STRING_SLICE.to_string();
        let needle = String::from("ab");

        assert_eq!(super::contains(haystack, needle), true);
    }

    #[test]
    fn returns_true_for_substring_at_middle_of_string() {
        let haystack = SEARCH_STRING_SLICE.to_string();
        let needle = String::from("d");

        assert_eq!(super::contains(haystack, needle), true);
    }

    #[test]
    fn returns_true_for_substring_at_end_of_string() {
        let haystack = SEARCH_STRING_SLICE.to_string();
        let needle = String::from("fg");

        assert_eq!(super::contains(haystack, needle), true);
    }

    #[test]
    fn returns_false_for_invalid_substring() {
        let haystack = SEARCH_STRING_SLICE.to_string();
        let needle = String::from("hij");

        assert_eq!(super::contains(haystack, needle), false);
    }
}

Walking through this, we begin by declaring an attribute which states that when the configured environment is test, we should run the code within the tests module.

Inside the tests module we declare a constant which is to be the search string used across each of our tests.

Sidenote 1:

Rust has two kinds of string, for want of a better term, these are known as strings _and _slices. A _string _is of the String type and a _slice _is of the &str type.

In the case of our SEARCH_STRING_SLICE constant it is declared as a slice.

Sidenote 2:

The reason it is declared as a slice initially is because rust cannot compile static Strings since strings are mutable but it can compile static &str slices but this is a side topic which I will be covering in my other series on the Rust programming language in the near future when we tackle the topic of compound types in Rust.

With this constant defined, we implemented our test cases:

A substring that is at the beginning of the search string.
A substring that is in the middle of the search string.
A substring that is at the end of the search string.
A substring that does not exist in the search string.

Sidenote 3:

When we want to run our contains function, which we will implement in the next section, we use super::contains to call it.

This is because super is a module scope keyword which tells rust to look in the parent scope of the module for the function and not in the current tests module scope for example.

If we had defined the contains function in the tests module itself, we would instead use the self::contains syntax.

To run the tests we can run the following via the command line: cargo test.

Implementation

fn contains(haystack: String, needle: String) -> bool {
    if haystack.len() < needle.len() {
        return false;
    }

    if haystack.chars().take(needle.len()).collect::<String>() == needle {
        return true;
    }

    return contains(haystack.chars().skip(1).collect(), needle);
}

For this implementation of the contains function we require two String instances:

The haystack that we will be searching within for the needle
The needle which we will be searching for within the haystack

If the haystack is smaller than the needle, it cannot contain the needle and thus it will return false.

If the haystacks characters from the start of the haystack to the size of the needle is equal to the needle then we return true.

Otherwise we slice off the first character of the haystack and use that as the new haystack to search within for the needle.

A successful substring check could be visualised like so:

Recursive iteration #1:

haystack = "abc"
needle = "bc"

haystack length < needle length ❌
"ab" is equal to the needle ❌

Recursive iteration #2:

haystack = "bc"
needle = "bc"

haystack length < needle length ❌
"bc" is equal to the needle ✔️

Return true

An unsuccessful substring check could be visualised like so:

Recursive iteration #1:

haystack = "abc"
needle = "de"

haystack length < needle length ❌
"ab" is equal to the needle ❌

Recursive iteration #2:

haystack = "bc"
needle = "de"

haystack length < needle length ❌
"bc" is equal to the needle ❌

Recursive iteration #3:

haystack = "c"
needle = "de"

haystack length < needle length ✔️

Return false

We can implement the same recursive functionality using any language, for example with JavaScript it is effectively the same code:

function contains(haystack, needle) {
  if(haystack.length < needle.length) {
    return false;
  }

  if(haystack.slice(0, needle.length) == needle) {
    return true;
  }

  return contains(haystack.slice(1), needle);
}

Conclusions

Compared to some of the other algorithms we have looked at in this series such as generating permutations or approximating PI, this is a relatively simple algorithm. In some sense though it is a more important one to understand since we use strings, substrings, etc on a daily basis and, by and large, take for granted the underlying algorithms at play.

I hope that you found some value in todays post and if you have any questions, comments or suggestions, feel free to leave those in the comments area below the post!

Data types in Rust

James Robb — Sun, 24 Oct 2021 22:36:06 +0000

Following on from the previous article in this series we will now take a look at the data types rust supports.

First let's define what a data type is:

In computer science and computer programming, a data type or simply type is an attribute of data which tells the compiler or interpreter how the programmer intends to use the data. [...] A data type constrains the values that an expression, such as a variable or a function, might take. This data type defines the operations that can be done on the data, the meaning of the data, and the way values of that type can be stored.

Source: Data Type Wikipedia Page

With this definition we can see that data types provide meaning to our code and allow us to set expectations of what data should come in and flow out of our applications.

There are 2 overarching categories of data types supported by Rust. These categories are scalar types and compound types. We will look at both of these categories in this article and explain what types lay within each category.

Scalar Types

A scalar type can be defined as any type that represents a single value. Rust supports four primary scalar types: integers, floating-point numbers, Booleans, and characters.

Integers

An integer represents a whole number with no fractional component. This means that 100 and -27 are integers but 123.45 and -91.2 are not.

Integer Types

The supported integer types are:

Bit Length	Signed Type	Unsigned Type
8-bit	i8	u8
16-bit	i16	u16
32-bit	i32	u32
64-bit	i64	u64
128-bit	i128	u128
arch	isize	usize

Sidenote 1:

The isize and usize types allow us to let the system decide what size our integers should be. For example if we are on a 32 bit system then an isize integer would be equivalent to an i32 whereas on a 64 bit system it would be equivalent to an i64, etc.

Signed integers hold a range from $2^{n-1})$ to $2^{n-1} - 1$ inclusive, where n is the bit length that variant uses. Unsigned integers on the other hand hold a range from 0 to $2^{n-1}$ .

As an example we can see the range of an i8 and u8 integer below:

Type	Lower Bound	Upper Bound
i8	-128	127
u8	0	255

It is important to be aware of these ranges because if you enter an integer that is out of range for the given type then Rust will panic as an integer overflow error will occur. The compiler tries to catch as many cases as possible for you but try to always consider which type is most suitable for the use case at hand to avoid any issues that could come up such as when working with third party data for example.

Sidenote 2:

One caveat to understand is that when Rust is compiled in release mode, it doesn't panic with an integer overflow error.

This behaviour is described within the integer overflow documentation. In short though, instead of panicking, in release mode, Rust will opt to allow the integer overflow to occur using two’s complement wrapping.

This simply means that when a value is too high for a specific signed or unsigned integer type, it will roll forwards to the lowest possible value for that type. If however a value is too low for a specific signed or unsigned integer type then it will roll backwards to the highest possible value for that type

Example 1 (u8: 0 to 255): 256 -> 0
Example 2 (u8: 0 to 255): 257 -> 1
Example 3 (i8: -128 to 127): -129 -> 127
Example 4 (i8: -128 to 127): -130 -> 126
Example 5 (i8: -128 to 127): 130 -> -127

Please refer to the integer overflow documentation for more information on this topic.

Sidenote 3:

Rust integers have methods that can check for overflow via the checked_* functions, for example: checked_mul.

All of the checked_* functions will return an Option where the value could be Some(value) or None. The None type in this case would represent an overflow occurring. This means that we can be sure in advance that if an overflow occurs, we have handled it properly!

Another variation on handling overflows can be seen in the saturating_* functions such as saturating_mul for example.

All of the saturating_* functions will just stop at the upper or lower limit instead of returning an Option.

Example usage of each integer type:

  // Signed integers
  let signed_8: i8 = -1;
  let signed_16: i16 = 2;
  let signed_32: i32 = -3;
  let signed_64: i64 = 4;
  let signed_128: i128 = -5;
  let signed_size: isize = -5;

  // Unsigned integers
  let unsigned_8: u8 = 1;
  let unsigned_16: u16 = 2;
  let unsigned_32: u32 = 3;
  let unsigned_64: u64 = 4;
  let unsigned_128: u128 = 5;
  let unsigned_size: usize = 5;

Here we have declared a list of signed and unsigned integers of each possible type variation. The type is declared by using the : <type> declaration after each variable name but when declaring variables we don't always have to manually add the type because rust will automatically assume an integer to be of type i32 unless otherwise stated.

Sidenote 4:

A signed integer is an integer that can be negative or positive whereas an unsigned integer can only ever be positive.

Sidenote 5:

Signed integers are stored using the two’s complement method.

Integer Literals

Integer literals are a way of writing integers in different notations, rust supports 5 notations out of the box:

Number Literal Type	Example	Decimal Equivelant
Binary	0b1111_0000	240
Byte (u8 only)	b'A'	65
Decimal	253	253
Hexadecimal	0xff	255
Octal	0o77	63

Sidenote 6:

All integer literals except the byte literal allow a type suffix to be used, such as -29i8 to cast -29 to an i8 or 254u8 to cast 254 as a u8.

Integer literals also support _ as a visual separator, such as 2_53 for 253 or 1_021_000 for 1,021,000. This separator can be of any length meaning that, for example, 1_________0 is perfectly acceptable, to the compiler at least, as a representation for 10.

Floating Point Numbers

A floating point number or float for short is any number with a fractional component. For example 12.75 and 3.1 are floats but 10 and 287 are not.

There are two kinds of floating point numbers supported in rust:

Bit Length	Type
32-bit	f32
64-bit	f64

The default type used by Rust, if no type decorator is added, is f64 because on a modern CPU it’s roughly the same speed as an f32 but is capable of far more precision.

Example usage of each floating point type:

 let float_32: f32 = 1.1;
 let float_64: f64 = 3.5;
 let another_float_64 = 3.5;

Floating-point numbers are represented according to the IEEE-754 standard by Rust. The f32 type is a single-precision float, and f64 is a double-precision float.

Sidenote 7:

Floating point numbers support can use _ as a visual separator just like integers, for example: 1_234.56.

Booleans

Booleans represent either a true or false value and take up exactly 1 byte of memory due to true being represented as a 1 and false as a 0 internally.

We can see below how we can assign booleans with or without a type prefix:

  let boolean_true = true;
  let boolean_false: bool = false;

Boolean data allows us to test if a statement is true or false and booleans are generally used within a control flow.

Most of the time you won't manually write true or false either but instead use logical operators against values to test their truthiness, for example:

  let number = 3;

  if number == 3 {
    println!("condition was true");
  } else {
    println!("condition was false");
  }

In this example we state that if the statement 3 is equal to 3 is true then we should print out "condition was true" and if it is false then we should print out "condition was false". Of course in this case it is true and so "condition was true" will be printed.

Characters

A character or char as it is known in Rust represents a single unicode scalar value and takes up four bytes when allocated to memory.

Sidenote 8:

I don't want to get too deep into what unicode is as that is not really relevant to this article but if you are interested, you can look at the characters unicode supports for yourself.

To create a char we use single quotes around the character we wish to represent. For example:

  let a = 'a';
  let one = '1';
  let rabbit = '🐇';
  let warning = '⚠️';
  let japanese_katakana_n = 'ン';

As you can see, each char is a single character representing a unicode compliant value such as a letter, number, emoji or characters of other non-latin languages such as Japanese as shown in the above example thanks to Unicode having these characters supported in the standard too!

Sidenote 9:

Here you will find a list of all languages supported by unicode.

Compound Types

Now that we have looked into scalar types we can move onto what is known as compound types. A compound type can group multiple values into a single representation and rust has two primitive compound types: tuples and arrays.

Tuples

A tuple allows us to group together values of different types and once declared cannot grow or shrink because tuples have a fixed length once defined.

A tuple is represented by rounded brackets containing values, for example: ('a', 1, 2.4).

We can also manually add a type definition if we want to, like so:

  let tuple: (char, u8, f32) = ('a', 1, 2.4);

We don't need to add the manual type annotation unless we wish to be more precise about the types of our values than Rusts inferred type system is.

Tuples also support a nice feature known in most languages as destructuring, for example:

  let user = ("James", 27);
  let (name, age) = user;
  println!("{} is {} years old", name, age);

This is nice because it allows us to provide a name to each item in our tuple instead of directly accessing the value.

If we want to directly access values though, tuples are zero indexed data structures and so we can access data like so:

  let user = ("James", 27);
  println!("{} is {} years old", user.0, user.1);

This works exactly the same as before by taking the first and second values in the tuple and outputting them but personally I would always use the destructured version as it is more descriptive as to what the data represents.

Arrays

Unlike tuples, arrays must contain values of the same type but are otherwise quite similar in that they also have a fixed length and cannot grow or shrink once defined.

An array uses square brackets and elements within are seperated by a comma, for example: ['a', 'b', 'c'].

Arrays are great when you want to guarantee a uniform data type within the collection or if you don't want the collection to change size over time.

Sidenote 10:

A lot of developers avoid arrays when beginning with Rust because in Rust, unlike JavaScript for example, arrays are inflexible and so they reach for a vector instead.

Vectors are great for many use cases but should not be used for all circumstances because we want to be as strict as possible with our types.

If there is a case where limiting the amount of values in the collection or guaranteeing a uniform data type for members of the collection is important, just use an array!

One example use case shown to us in the Rust docs for using an array would be for storing a list of months:

  let months = ["January", "February", "March", "April", "May", "June", "July", "August", "September", "October", "November", "December"];

Even though Rust will infer the types for us, we can declare the type of data our array should contain and how many elements the array should hold too. Expanding the last example we could write:

  let months: [&str; 12] = ["January", "February", "March", "April", "May", "June", "July", "August", "September", "October", "November", "December"];

This explicitly says that our list contains elements of type &str and there should be 12 of them altogether.

Sidenote 11:

We stated above that the variable months is of type [&str; 12] but one thing worth noting is that if the value type &str or the given length 12 or both change, the entire type itself changes as far as the compiler is concerned. For example:

If variable A is of type [i32; 3] and variable B is of type [i32; 4], these are totally different types according to the compiler, even though both represent an array of i32 values.

Another cool trick that arrays can do is repeating a value a set amount of times succinctly. The following code will generate us an array with 3 elements, each holding the char value 'a':

  let months = ['a'; 3]; // -> ['a', 'a', 'a']

We can also index arrays just like we could with tuples but instead of using . notation we use square bracket notation:

  let alphabet = ['a', 'b', 'c'];

  let a = alphabet[0];
  let b = alphabet[1];
  let c = alphabet[2];

We can see here that arrays, just like tuples, are zero indexed data structures. That is to say, the first element is at index 0, the second element is at index 1, and so on.

Sidenote 12:

If you try to access an array index which does not exist the program will panic at runtime, not compile time, and stop your application from executing any further. Thus, be careful when trying to access values by their index by adding a check to make sure that the index you want to use is within range!

The Rust array data type documentation describes the reasons behind this behaviour in more detail.

We will discuss more about Rust guarantees, errors, compilation and more in the future as we progress in this series.

We can now see that arrays are a useful data structure for our toolbelt when developing applications with Rust and serve a niche where a collections value type uniformity and length are an important aspect for the items we wish to store in memory.

Conclusions

Rust gives us a lot of types out of the box, each bringing their own use cases and value to the table.

As we continue through this series we will eventually start working with custom types and sub types such as &str and collections such as String, Vector and HashMap but until then this should give you a good overview of the initial building blocks that these types and collections inevitably themselves end up using.

In the next article we will look at functions in Rust: What they are, how we work with them, when they are useful to use, etc.

I look forward to seeing you then and as ever, feedback and questions are always welcome 😊!

Generating permutations

James Robb — Sat, 20 Jun 2020 17:56:37 +0000

I like to think of permutations as simply:

The rearrangement of a collection of elements into each possible new arrangement of those elements.

Let's demonstrate what the permutations of a dataset could look like:

Dataset: [1, 2, 3]
Permutations: [
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,2,1],
  [3,1,2]
]

Building an algorithm to generate permutations of a collection is also a common technical interview test too and so it is a good thing to be aware of.

Now, for those familiar with the concept of combinations you may remember that permutations and combinations are somewhat related but be aware that there is a difference between these concepts.

In mathematics, permutation is the act of arranging the members of a set into a sequence or order, or, if the set is already ordered, rearranging its elements—a process called permuting. Permutations differ from combinations, which are selections of some members of a set regardless of order.

Source: Permutations Wiki

We can see this inherent difference as we write out the maths behind each concept.

The count of possible combinations (C) is defined as:

\frac{n!}{r!(n-r)!}

The count of possible permutations (P) is defined as:

\frac{n!}{(n-r)!}

With this, we can see the inherent difference between the two concepts.

Tests

const input: number[] = [1,2,3];
const permutations: number[][] = permute(input);

describe("permutations", () => {
  it("returns the correct number of permutations", () => {
    expect(permutations.length).toBe(6);
  });

  it("returns the correct permutations", () => {
    expect(permutations).toEqual([
      [1,2,3],
      [1,3,2],
      [2,1,3],
      [2,3,1],
      [3,2,1],
      [3,1,2]
    ]);
  });
});

The tests are written with Jest as the test runner, TypeScript as our language of choice and TS-Jest as the glue between the two since Jest doesn't support TypeScript out of the box.

If you want to know how to get Jest and TypeScript to work together then you can check the Jest Config and TS Config files from the repl for this article.

If you wish to look at the code, config, or just run the tests, you can do so with the repl below:

Implementation

We will be using TypeScript for our implementation but don't be alarmed if you haven't used that before as we will be diving into the implementation step by step!

function swap<T>(array: T[], x: number, y: number): void {
  const temp = array[x];
  array[x] = array[y];
  array[y] = temp;
}

function permute<T>(array: T[], start: number = 0, result: T[][] = []): T[][] {
  if(start === array.length - 1) {
    result.push([...array]);
  }

  for(let index = start; index < array.length; index++) {
    swap<T>(array, start, index);
    permute<T>(array, start + 1, result);
    swap<T>(array, start, index);
  }

  return result;
}

The `permute` function

The permute function is a recursive function which takes in 3 parameters:

array is the collection that we will be generating permutations from
start is the index of the array to begin from
result is an array of arrays, each of which will contain items of the same type as the items of the original input array

You will never use the start or result parameters because these are only used for each consecutive recursive call of the permute function. If you really wanted to though, you could provide arguments for these although it is not recommended to do so.

As we enter the function body we begin with the "base case" as it is usually named and all this does is provide us a way to break the recursive calls based on a pre-defined definition of done.

In our case, if the start index is equal to the last item of the array's index, we will stop recursing the input array. If we are not currently meeting the criteria of our base case, we then begin a loop going from the start index to the end of the array.

For each item in the array, we will use a method called backtracking which is a way of running an operation and then undoing it again after we complete some action when required.

In our case, we are using the swap function to swap the item from the start index and the item at the current index, running a recursive call of the permute function and finally re-swapping the items from the start index and current index back to their original places once each recursive cycle is completed.

You can imagine this as a tree, we take each item, swap it with every other item and swap those iterations with every other iteration before resetting everything in the original array back to normal and returning the result of each iteration in the tree.

This becomes a problem no matter how it is implemented once the dataset grows over ten or so items however since the count of possible permutations is mathematically tied to the factorial result of the count of items in the input array.

This means that an input array with 4 items will produce 24 permutations but one with 8 items will produce 40,320 and one with 20 items will produce 2,432,902,008,176,640,000. This means we should keep the input array as small as possible at any time to keep things performant.

The `swap` function

The swap function takes in 3 parameters:

An array
The first (x) index for the swap
The second (y) index for the swap

We copy the item at position x in the array, set the item at position x to the value of the item at position y and finally set the item at position y to the item that used to be at position x.

Pretty simple, right?

Conclusions

Permutations are a common occurrence and have use cases in many real-life scenarios and industries such as cyber-security, cryptography, and transportation for example.

In the medical industry, medicine manufacturers use permutations to analyze and predict the spreading of various diseases, genetic sequences, analysis of drug-safety data, and to analyze various permutations of drugs and chemicals as well in relation to the desired outcome of treatment.

Even if it isn't relevant to your work, it is a common coding test and so knowing the theory and practice are good things to have in your back pocket. The best part is that if we know how to swap items, backtracking based on a single index is possible as we have seen in the implementation above and I personally find this method of generating permutations the easiest to remember and implement and I hope it is the same case for you.

I hope this post brought you some value and helped to clear up what permutations are, what real-world use cases for permutations are out there and how we can generate them using swapping, recursion, and backtracking!

The stack

James Robb — Fri, 05 Jun 2020 23:03:26 +0000

A stack is an abstract data structure which uses an order of operations called LIFO (Last In First Out) which does as it says on the tin, the last element added to the stack will be the first one to be removed.

You can think of this like a stack of plates, adding or removing plates is only possible from the top of the stack.

Thus, a stack controls elements held within via two principal operations:

The push operation adds an element to the collection
The pop operation removes the most recent element in the collection

There are a few other methods which we will implement but the ordering combined with these operations are the signature of a stack.

Stacks are used in a variety of ways in the real world, for example the JavaScript Call Stack is a stack which tracks function calls and allows the browser to track all the various things being executed as they run without conflicts between calls occurring.

In this article we will explore how I would implement a stack and I will also explain each method we implement in detail.

Tests

For the tests of our stack I will be using the Jest test runner alongside ts-jest which will support us to test our TypeScript implementation.

let stack: Stack<number>;

beforeEach(() => {
  stack = new Stack<number>();
});

describe("Stack", () => {
  it("Should have predictable defaults", () => {
    expect(stack.count).toBe(0);
    expect(stack.items).toEqual([]);
  });

  it("Should add an item to the stack", () => {
    stack.push(1);
    expect(stack.count).toBe(1);
  });

  it("Should return the index of the item added to the stack", () => {
    expect(stack.push(1)).toBe(0);
  });

  it("Should remove an item from the stack", () => {
    stack.push(1);
    expect(stack.count).toBe(1);
    expect(stack.items).toEqual([1]);
    stack.pop();
    expect(stack.count).toBe(0);
    expect(stack.items).toEqual([]);
  });

  it("Should return the value of the item removed from the stack", () => {
    stack.push(1);
    expect(stack.pop()).toBe(1);
  });

  it("Should return undefined if no items exist in the stack when trying to pop the top value", () => {
    expect(stack.pop()).toBe(undefined);
  });

  it("Should return undefined if the item being searched for doesn't exist", () => {
    expect(stack.find(1)).toBe(undefined);
  })

  it("Should return the index of the value if it is found", () => {
    stack.push(1);
    expect(stack.find(1)).toBe(0);
  });

  it("Should allow us to peek at the item at the top of the stack", () => {
    stack.push(1);
    expect(stack.peek()).toBe(1);
  });

  it("Should return undefined if there is no item to peek at", () => {
    expect(stack.peek()).toBe(undefined);
  });

  it("Should let us check if the stack is empty", () => {
    expect(stack.empty()).toBe(true);
  });

  it("Should let us check how many items are in the stack", () => {
    expect(stack.size()).toBe(0);
  });

  it("Should clear the stack", () => {
    stack.push(1);
    stack.push(1);
    expect(stack.count).toBe(2);
    expect(stack.items).toEqual([1, 1]);
    stack.clear();
    expect(stack.count).toBe(0);
    expect(stack.items).toEqual([]);
  });
});

For the tests I chose to use a Stack using number types for simplicity. If you want to explore and run the tests, you can use the repl below.

Implementation

For this implementation we will be using TypeScript.

class Stack<T> {
  public items: T[] = [];
  public count: number = 0;

  push(item: T): number {
    this.items[this.count] = item;
    this.count++;
    return this.count - 1;
  }

  pop(): T | undefined {
    if(this.count === 0) return undefined;
    this.count--;
    const deletedItem = this.items[this.count];
    this.items = this.items.slice(0, this.count);
    return deletedItem;
  }

  find(value: T): number | undefined {
    for(let index = 0; index < this.size(); index++) {
      const item = this.items[index];
      if(Object.is(item, value)) return index;
    }

    return undefined;
  }

  peek(): T | undefined {
    return this.items[this.count - 1];
  }

  empty(): boolean {
    return this.count === 0;
  }

  size(): number {
    return this.count;
  }

  clear(): T[] {
    this.items = [];
    this.count = 0;
    return this.items;
  }
}

We are using Generics as a part of the implementation to provide opt-in type strictness for our stack, this is represented by the type T in the implementation above. To see this in action we can do this for example:

const stack = new Stack<number>();
stack.push(1); // Works fine
stack.push("1"); // Throws a TypeError

If no type T is provided then anything can be added into the stack like so:

const stack = new Stack();
stack.push(1); // Works fine
stack.push("1"); // Also works fine

Personally though, I would recommend that if you don't want to lock the types of the items in your stack then add the explicit any type to the T type instead since being explicit is always better than being implicit with such things, for example:

const stack = new Stack<any>();
stack.push(1); // Works fine
stack.push("1"); // Also works fine

Properties

Our Stack contains 2 properties, the items currently within the stack and the count of the items in the stack, we can access these like so:

const stack = new Stack();
console.log(stack.count); // 0
console.log(stack.items); // []
state.push(1);
console.log(stack.count); // 1
console.log(stack.items); // [1]

Methods

Alongside the properties of the Stack are it's methods, let's explore these and what they do a bit more.

`push`

The push method adds an item to the stack and returns the index of that item once added, for example:

const stack = new Stack();
const idx = stack.push(1);
const idx2 = stack.push(2);
console.log(idx, idx2, stack.items); // 0, 1, [1, 2]

`pop`

The pop method removes an item from the stack and returns the value of the removed item, for example:

const stack = new Stack();
stack.push(1);
stack.push(2);
const item = stack.pop();
console.log(item, stack.items); // 2, [1]

`find`

The find method finds an item in the stack and returns its index if it is found or undefined if it isn't, for example:

const stack = new Stack();
console.log(stack.find(1)); // undefined
stack.push(1);
console.log(stack.find(1)); // 0

`peek`

The peek method lets us check what item is currently at the top of the stack, for example:

const stack = new Stack();
stack.push(1);
console.log(stack.peek()); // 1

`empty`

The empty method lets us check if the stack is empty or not, for example:

const stack = new Stack();
console.log(stack.empty()); // true
stack.push(1);
console.log(stack.empty()); // false

`size`

The size method lets us see how many items are in the stack currently, for exmaple:

const stack = new Stack();
console.log(stack.size()); // 0
stack.push(1);
console.log(stack.size()); // 1

`clear`

The clear method lets us remove all items from the stack, for example:

const stack = new Stack();
stack.push(1);
stack.push(1);
stack.push(1);
console.log(stack.count, stack.items); // 3, [1, 1, 1]
stack.clear();
console.log(stack.count, stack.items); // 0, []

Conclusions

Stacks are really efficient data structures for setting, getting, deleting and finding a value, we can see that with the Big O of these operations coming in as follows:

	Average	Worst
Get	Θ(n)	Θ(n)
Set	Θ(1)	Θ(1)
Delete	Θ(1)	Θ(1)
Find	Θ(n)	Θ(n)

This makes it one of the most efficient data structures that you can use and this is why it one of the most common data structures you will come across when developing software.

I hope this post brought you some value and feel free to leave a comment below!

Getting started with Rust

James Robb — Wed, 27 May 2020 13:02:56 +0000

Rust is a language which I have been looking into lately and starting with this post I will begin a new series of articles to share what I have learned so far to help other beginners or those interested in getting to know rust get to grips with the language.

So what is rust? Well, the rust wikipedia page states it quite well:

Rust is a multi-paradigm programming language focused on performance and safety, especially safe concurrency. Rust is syntactically similar to C++, but provides memory safety without using garbage collection. Rust was originally designed by Graydon Hoare at Mozilla Research, with contributions from Dave Herman, Brendan Eich, and others.

Source: Rust Wikipedia Page

Getting setup

To get setup go to the installation page of the official rust language site. Follow the instructions for your operating system of choice and once you've installed everything you should be able to run rustc --version in your terminal and get something like this in response:

rustc 1.39.0-nightly (eb48d6bde 2019-09-12)

If that command ran correctly without any errors, the setup stage is over and we are ready to get coding!

Hello world!

Let's make a file called Hello.rs and write the following inside the file:

fn main() {
  println!("Hello world!");
}

The main() function is a required function in rust, it is the function executed when a programme is run. println!() is a macro function (we will look into that concept in a future article) which is roughly equivilent to echo in PHP, System.Console.WriteLine() in C# and console.log() in JavaScript and it's one job like these others is to write content to the terminal/console.

Sidenote 1:

As a heads up, println!() works with values other than strings a bit differently, for example if we wanted to print a number to the terminal we would have to write println!("{}", 2); which basically tells the println!() macro to write a string where the placeholder {} is the value 2.

We can output multiple values this way too, for example println!("{}, {}", 1, 2); will output "1, 2".

We can name our values by index too, for example println!("{1}, {0}", 1, 2); will output "2, 1".

There is also the special debug placeholder println!("{:?}", vec![1, 2, 3]); for vectors, structs, etc. This example would output [1, 2, 3] for reference but don't worry about datatypes just yet, we will look at them in detail in an upcoming article.

Moving back on track, we can go to our terminal and compile our Hello.rs file using the rustc Hello.rs command to tell the rust compiler (rustc) to compile the Hello.rs file. This will output 2 new files names Hello.pdb and Hello.exe.

Sidenote 2:

We can ignore the .pdb file as this is just a programme database file which the .exe file uses to lookup debugging information. Here is a wiki page with more information on .pdb files

To run our application we can now simple type ./Hello into the terminal to run the Hello.exe file and you should see it output the text "Hello world" in the terminal!

Conclusions

Rust can seem like a daunting language that is hard to learn and quite frankly it is at times but we have all had this feeling as we begin to journey into a new language, stack or role and so let us not be daunted when challenged to learn!

I hope this article has brought you some value and has given you a nice first step into getting setup, writing, compiling and executing with rust. See you in the next one.

Approximating PI

James Robb — Mon, 18 May 2020 21:37:39 +0000

In this coding challenge we are going to try to approximate the value of PI using random number generation, Geometry and Cartesian Coordinates.

We will begin with an explainer of what the goal and solution path will be and from there we will visualise the output using p5.js.

The challenge

Given a random set of points on a 2D plane, estimate the value of PI.

This is not such an easy challenge to wrap your head around at first because how can you even begin to approximate PI with nothing more than some randomly generated points and a 2D plane? On the face of it, that would be like saying "Go to the shop and buy some milk and then use it to fly to the moon".

Nevertheless this challenge is what we will be tackling today by breaking it down and piecing a solution back together. As usual we will begin the implementation with some tests.

Tests

For the tests I will be using the Jest testing framework. If you have never used Jest before then I highly recommend you check it out. With that said, our tests are written as follows:

expect.extend({
  toBeWithinRange(received, floor, ceiling) {
    return {
      message: () =>
        `expected ${received} to be within range ${floor} - ${ceiling}`,
      pass: received >= floor && received <= ceiling,
    };
  },
  toBeEither(received, ...options) {
    return {
      message: () =>
          `expected ${received} to be one of ${options}`,
      pass: [...options].filter(current => {
        return Object.is(received, current);
      }).length === 1
    }
  }
});

describe("GuessPI", () => {
  it('Handles the four or zero case', () => {
    const answer = guessPI(1);
    expect(answer).toBeEither(0, 4);
  });

  it('puts PI within roughly 0.5 of the target', () => {
    const answer = guessPI(100);
    expect(answer).toBeWithinRange(Math.PI - 0.5, Math.PI + 0.5);
  });

  it('puts PI within roughly 0.3 of the target', () => {
    const answer = guessPI(1000);
    expect(answer).toBeWithinRange(Math.PI - 0.3, Math.PI + 0.3);
  });

  it('puts PI within 0.2 of the target', () => {
    const answer = guessPI(10000);
    expect(answer).toBeWithinRange(Math.PI - 0.2, Math.PI + 0.2);
  });

  it('puts PI within 0.14 of the target', () => {
    const answer = guessPI(100000);
    expect(answer).toBeWithinRange(Math.PI - 0.14, Math.PI + 0.14);
  });
});

Firstly we extend the default expect object with 2 helper functions:

One to check that the value we are looking for is within a range (inclusive)
One to check that the value we are looking for is one of two options

Next we test our implementation itself.

The first test checks if the guessPI function will return a 0 or a 4 when only 1 point is placed on the plane, this will become clearer as to why these values will be the only 2 epected values to return in such a case later when we implement the guessPI function. The second test gets us within 0.5 of PI, the third within 0.3, the fourth puts us within 0.2 and the last within 0.14.

Ok but how does it work?

Implementation

function guessPI(number) {
  let in_circle_count = 0;
  const in_square_count = number;

  for (let i = number; i > 0; i--) {
    const x = (Math.random() * 101) / 100;
    const y = (Math.random() * 101) / 100;
    const distance = x ** 2 + y ** 2;
    if (distance <= 1) in_circle_count++;
  }

  return 4 * (in_circle_count / in_square_count);
}

Upon reading this implementation you may be having an aha moment regarding how this actually works but for those of you who don't, let's break the implementation down.

The challenge was to approximate PI using only a 2D plane and a set of random points. Assuming that this plane is a square, approximating PI is actually relatively simple since a circle would fit nicely into a square, assuming the squares sides were the same length as the diameter of the circle. In other words, each side of the square in such a case would be twice the radius of the circle in length. All said, we can now use some high school maths to begin working out the value of PI.

Area of the circle:

circleArea = πr^{2}

Area of the square:

squareArea = 4r^{2}

The amount of the square taken up by the circle:

circleToSquareRatio = πr^{2} / 4r^{2}

Since the $r^{2}$ values cancel each other out we can simplify the ratio calculation down to just being:

c i rc l e T o Sq u a re R a t i o = π /4

From this we can work out PI to be:

π = 4 * c i rc l e T o Sq u a re R a t i o

Now we know how we can approximate the value of PI, it's just the calculation of the amount of points within the circle comparitive to those within the square multiplied by 4!

Visualising our implementation

For the following visualisation I have used the p5.js library and adapted the code somewhat from our implementation so as to draw the points.

For this visualisation I wanted to simplify things further and only use a positive cartesian coordinate system and thus we only use a quarter circle section to calculate upon within the square.

This works exactly the same as the full circle in a square calculation since we are just scaling things down 1 to 1 in terms of the square and circle.

Feel free to read the comments in the code to further understand how things are working and otherwise just press the "play" button or click the "open in new tab" button to see the vizualisation in action!

Conclusions

Considering the outline of the challenge we have actually managed to figure out how we can approximate the mathematical constant PI with only a 2D plane and some random points on that plane.

I hope that you found some value in todays post and if you have any questions, comments or suggestions, feel free to leave those in the comments area below the post!

Jump Search

James Robb — Sun, 03 May 2020 15:55:08 +0000

Continuing our recent dive into search algorithms, we will now be covering the Jump Search algorithm. Similar to Binary Search the Jump Search algorithm is a searching algorithm for pre-sorted arrays.

The basic idea is to check fewer elements than Linear Search by jumping ahead by a fixed increment and backtracking when a larger value than the one searched for is found, running a Linear Search from there to find if the value exists. This may sound strange at first but by the end of this article, all will be clear.

This algorithm saves time and is thus faster when compared to a Linear Search since we do not look at all elements in the collection. It is however slower than Binary Search since the Jump Search algorithm runs with a best case Big O of O(√n).

Jump search has one advantage over Binary Search however and that is that we only go backwards once whereas Binary Search can jump back as many as O(Log n) times. This being the case, in situations where Binary Search seems to be running slow due to backward lookups, Jump Search might be able to help you in such a scenario to speed things up.

Tests

from main import jumpSearch;

def test_strings():
  assert jumpSearch(["Dave", "James"], "Dave") == 0;
  assert jumpSearch(["Dave", "James"], "abc") == -1;

def test_integers():
  assert jumpSearch([1,2,3,4], 3) == 2;
  assert jumpSearch([1,2,3,4], 5) == -1;

def test_floats():
  assert jumpSearch([3.14], 3.14) == 0;
  assert jumpSearch([3.141], 3.14) == -1;

def test_booleans():
  assert jumpSearch([False, True], True) == 1;
  assert jumpSearch([False, True], False) == 0;

def test_lists():
  assert jumpSearch([[3.14]], [3.14]) == 0;
  assert jumpSearch([[3.141]], [3.14]) == -1;

def test_nested_lists():
  assert jumpSearch([[3.14, [1]]], [3.14, [1]]) == 0;
  assert jumpSearch([[3.141]], [3.14]) == -1;

def test_sets():
  assert jumpSearch([set([1])], set([1])) == 0;
  assert jumpSearch([set([1])], set([1,2])) == -1;

def test_tuples():
  assert jumpSearch([tuple([1])], tuple([1])) == 0;
  assert jumpSearch([tuple([1])], tuple([1, 2])) == -1;

You may notice that these are similar to the tests for Linear Search and Binary Search that we wrote in previous articles and this is on purpose.

The difference in tests comes, as with binary search, in the comparison operators we are using. In our case the tests for dict were removed and the test for boolean vs None have also been removed. These are not possible to have due to these not being able to compare to one another using the less than (<) operator which is used in the Jump Search algorithm implementation.

You can run and explore through the tests via the repl below:

Implementation

from math import sqrt;
from typing import List, TypeVar;
from operator import eq as deep_equals, ge as greater_than_or_equal, ne as not_equal, lt as less_than;

T = TypeVar('T')

def linearSearch(collection: List[T], value: T) -> int:
  for index, item in enumerate(collection):
    if deep_equals(item, value): return index;
  return -1;

def jumpSearch(collection: List[T], value: T) -> int: 
  n = len(collection);
  step = sqrt(n);
  prev = 0;

  while less_than(collection[int(min(step, n) - 1)], value):
    prev = step;
    step *= 2;
    if greater_than_or_equal(prev, n): return -1;

  foundIndex = linearSearch(collection[int(prev):], value);
  if not_equal(foundIndex, -1): foundIndex += int(prev);
  return foundIndex;

Note 1: Since Jump Search utilises Linear Search, we will use the implementation we built previously in this article series for that.

For the jumpSearch function, we require a collection and a value to be provided and will return an int (integer) representing the index of the value if it is found and -1 if it is not. The value itself is what we will be looking for in the collection.

Note 2: The collection should be a List of items matching the same type as the value we are searching for and thus, if the value is of type str (string) then we expect the collection to be a List[str] for example.

Whence we enter the jumpSearch function body, we declare 3 variables:

The variable n to represent the amount of items in the collection
The variable step to be the value of how far we should jump each time, this is defined as the square root of n
The variable prev to represent the last index visited when the last step was taken

From here we run a while loop as long as the current item at int(min(step, n) - 1) is less than the value we are searching for. You may be wondering why we use int(min(step, n) - 1). Let's break it down from the inside out. Let's use the first iteration of the while loop for a Pseudocode example:

collection = [1, 2, 3];
value = 2;
n = len(collection); # 3
step = sqrt(n); # 1.73205080757
prev = 0; # 0
nextIndex = min(step, n) - 1; # 0.73205080757
indexAsInteger = int(nextIndex) # 0
itemAtIndex = collection[indexAsInteger]; # 1
condition = less_than(itemAtIndex, value); # True
while condition is True: # now we run the loop since the condition is True

That is the essential breakdown of the while loops condition and hopefully that makes sense as to why we run int(min(step, n) - 1) in the implementation now.

Inside the loop we set the prev to equal the current step and then add the step to itself for the next iteration of the while loop. During the loop execution we check that the prev variable is not greater than or equal to the length of the collection which we stored in the variable n. If it is, we haven't found the value in the collection and return -1 to represent that it wasn't found.

If we exit the loop and didn't return -1, we must have the value still in the collection and so we then run the linearSearch function with a new array created from a slice of the collection running from the prev step index to the end of the collection and pass in the value we are looking for also. If the linearSearch run doesn't return -1, we have found the value and all we need to do is add the prev step index value to the foundIndex.

Note 3: We do this because if -1 wasn't returned and thus the value was found. If you remember we took a slice of the collection beginning from the prev step to the end of the collection for the linearSearch to run over and thus if the value was found by linearSearch at index 1 then it would be in the collection at index prev + 1.

This works well for us since we return the foundIndex either way and so if the value is not found we will just return the -1 anyway.

Conclusions

Jump Search is useful in places where Binary Search is potentially slow due to backwards lookups. It is faster than a regular Linear Search and tries to maximise efficiency by using jumps through the sorted collection.

I hope you found some value in this article and if you have any questions or comments, feel free to write them below!

Binary Search

James Robb — Sun, 26 Apr 2020 18:59:28 +0000

Binary search is a blazingly-fast search algorithm that has a worst case Big O of Ο(log n), the average case is O(log n) and the best case is O(1). In short it's a search algorithm that is about as fast as you can get.

Binary Search utilises divide and conquer to reduce much of the potential runtime. In fact, it is a lot like merge sort in how it functions but of course one algorithm is used to sort data and this one is used to find data.

For the algorithm to run properly, the data must be pre-sorted and be have elements of the same or similar types held within. So if your collection contains strings and integers, it won't work, you must have elements using a consistent data type withinin your collection.

When the binary search is executed, it will take an input collection and a value to find and if the value exists we will return the index of that value within the collection and if it doesn't we will return -1 out of convention to represent that the value doesn't exist in the collection after all.

Tests

from main import binarySearch;

def test_strings():
  assert binarySearch(["Dave", "James"], "Dave") == 0;
  assert binarySearch(["Dave", "James"], "abc") == -1;

def test_integers():
  assert binarySearch([1, 2, 3,4], 3) == 2;
  assert binarySearch([1, 2, 3, 4], 5) == -1;

def test_floats():
  assert binarySearch([3.14], 3.14) == 0;
  assert binarySearch([3.141], 3.14) == -1;

def test_booleans():
  assert binarySearch([False, True], True) == 1;
  assert binarySearch([True], False) == -1;

def test_lists():
  assert binarySearch([[3.14]], [3.14]) == 0;
  assert binarySearch([[3.141]], [3.14]) == -1;

def test_nested_lists():
  assert binarySearch([[3.14, [1]]], [3.14, [1]]) == 0;
  assert binarySearch([[3.141]], [3.14]) == -1;

def test_sets():
  assert binarySearch([set([1])], set([1])) == 0;
  assert binarySearch([set([1])], set([1,2])) == -1;

def test_tuples():
  assert binarySearch([tuple([0,2]), tuple([1])], tuple([1])) == 1;
  assert binarySearch([tuple([1])], tuple([1, 2])) == -1;

In python, as with many other languages, some elements can't compare with one another in a non-hacky manner, even if they are both the same type. An example of this is that types such as dict cannot run comparisons like {'a': 1} > {'a': 1}.

For binary search we do need to use comparison operators like that though and so I represented only the types that are comparible with the ==, >, >=, < and <= operators that binary search utilises.

Here is a repl to run and play with the tests:

Implementation

There are a few ways to skin this particular cat. For that reason, I will show you two implementations for the Binary Search algorithm. One will be using an imperative approach and another using Recursion.

Both implementations expect uniform data and are typed for this reason. We expect data to contain consistent types in the input collection so that the search is guaranteed to be able to compare the items in the collection against one another. If we didn't do this we may get unexpected errors such as this:

TypeError: '>' not supported between instances of 'list' and 'str'

Just remember to normalise and sort your data before you begin using the implementations that will be outlined below or if you decide to build your own implementation in the future as these traits are a requirement of the algorithm.

The imperative approach

Imperative programming is a programming paradigm which describes how a programme should run. This paradigm uses statements to alter a programmes state and generate values.

from typing import List, TypeVar;
from operator import eq as deep_equals, gt as greater_than, ne as not_equal, le as less_than_or_equal;
from math import floor;

T = TypeVar('T');

def binarySearch(collection: List[T], value: T) -> int:
  start = 0;
  end = len(collection) - 1;
  middle = floor((start + end) / 2);

  while(not_equal(collection[middle], value) and less_than_or_equal(start, end)):
    if greater_than(value, collection[middle]): start = middle + 1;
    else: end = middle - 1;

    middle = floor((start + end) / 2);

  return middle if deep_equals(collection[middle], value) else -1;

We begin by importing some helpers from the python standard library which has a whole swath of helper functions for us to use in our code.

A point worth noting is the use of TypeVar from the typing module to align our input types for the collection and value.

All this means is that when we recieve the collection, it should have items of consistent type T and the value we want to search for should also be of type T.

So if we have the collection of type List[str] for example then value must also be an str but instead of hard-coding this, we let TypeVar do the work for us.

Our binarySearch function will recieve a collection to search within and a value to look for in that collection. If the value is found then we return it's location (index) in the collection.

To find the index we setup the start, end and middle indexes of the collection. While the value is not equal to the value in the middle of the collection and the start index is less than or equal to the end index, we check if the value is bigger than the middle value, if it is, we set the start index to begin on the next iteration from the middle, otherwise we set the end to be the middle.

We do this because if the value is greater than the value in the middle of the collection, the value must be on the right half of the collection and vice versa for the opposite case.

Either way the condition falls we will then reset the middle index to be in between the new start and end indexes. We continue with this process until the condition on the while loop is no longer true.

When the while loop exits, we check if the middle indexes value is the value we are looking for. If it is, we return the middle index and if it isn't then the value wasn't in the input collection and we return -1 to represent this case.

The recursive approach

from typing import List, TypeVar, Union;
from operator import eq as deep_equals, gt as greater_than, ne as not_equal, le as less_than_or_equal, ge as greater_than_or_equal;
from math import floor;

T = TypeVar('T');

def binarySearch(collection: List[T], value: T, start: int = 0, end: Union[int, None] = None) -> int:
  if deep_equals(end, None): 
    end = len(collection) - 1;

  if greater_than_or_equal(end, start): 
    middle = floor((start + end) / 2);

    if deep_equals(collection[middle], value):
      return middle;

    if greater_than(collection[middle], value):
      return binarySearch(collection, value, start, middle - 1);

    return binarySearch(collection, value, middle + 1, end);

  return -1;

Exactly like the imperative approach outlined above, we begin by importing some helpers from the python standard library which has a whole swath of helper functions for us to use in our code.

A point worth noting is the use of TypeVar from the typing module to align our input types for the collection and value.

All this means is that when we recieve the collection, it should have items of consistent type T and the value we want to search for should also be of type T.

So if we have the collection of type List[str] for example then value must also be an str but instead of hard-coding this, we let TypeVar do the work for us.

The recursive version naturally calls itself again and again and requires a couple more parameters to be provided on each call than the imperative approach does. Namely we need to know where to the start index and end index are for the current recursive call of the binarySearch function.

Initially the start will be at 0 which makes sense since we want to begin at the start of the collection and the end initially will be set to None but will be set to the length of the collection mins one once the function first runs.

Note: We set end to initialise itself with a value of None because in python you can't reference other parameters to use as default values of other parameters. To get around this, we set it's type to Union[None, int] which just means this can be of type None or int. Once the function first executes we set the end value to the length of the collection mins one because if a collection contains 5 items the last index would be 4 since lists/arrays are always 0 indexed.

If the end index is greater than or equal to the starting index we calculate where the middle index of the current collection is and consider 3 cases:

If the item at the middle index equals the value we are looking for, return the middle index
If the item at the middle index is greater than the value we are looking for then run a recursive call to binarySearch to check the left half of the collection for the value
If the item at the middle index is less than the value we are looking for then run a recursive call to binarySearch to check the right half of the collection for the value

If none of these recursive calls manage to find the value in the collection then we return -1 by default.

Conclusions

The Binary Search algorithm is always a fantastic choice to find values within sorted and type-consistent data sets.

Personally I try to always keep data within applications as uniform as possible and thus, I find myself using this algorithm relatively often in my day to day work. I highly recommend looking into it further and seeing how it can benefit you and your work too!

I hope you learned something new today and if you have any questions, ideas or comments, feel free to comment them below!

Linear Search

James Robb — Sun, 19 Apr 2020 21:54:45 +0000

When we want to filter data to a subset of that data, we can use something like a filter function.

What happens though if you just want to search a collection see if a value exists in the first place?

To this end, today we will be implementing the most basic search algorithm there is, the linear search algorithm.

Tests

For the tests I will be using the PyTest runner. If you haven't used it before I highly recommend it if you are a python developer.

from main import linearSearch;

def test_strings():
  assert linearSearch(["Dave", "James"], "Dave") == 0;
  assert linearSearch(["Dave", "James"], "abc") == -1;

def test_integers():
  assert linearSearch([1,2,3,4], 3) == 2;
  assert linearSearch([1,2,3,4], 5) == -1;

def test_floats():
  assert linearSearch([3.14], 3.14) == 0;
  assert linearSearch([3.141], 3.14) == -1;

def test_booleans():
  assert linearSearch([False, True], True) == 1;
  assert linearSearch([False, True], None) == -1;

def test_lists():
  assert linearSearch([[3.14]], [3.14]) == 0;
  assert linearSearch([[3.141]], [3.14]) == -1;

def test_nested_lists():
  assert linearSearch([[3.14, [1]]], [3.14, [1]]) == 0;
  assert linearSearch([[3.141]], [3.14]) == -1;

def test_sets():
  assert linearSearch([set([1])], set([1])) == 0;
  assert linearSearch([set([1])], set([1,2])) == -1;

def test_tuples():
  assert linearSearch([tuple([1])], tuple([1])) == 0;
  assert linearSearch([tuple([1])], tuple([1, 2])) == -1;

def test_dictionaries():
  assert linearSearch([{"a": 1}], {"a": 1}) == 0;
  assert linearSearch([{"a": 2}], {"a": 1}) == -1;

Since we want to find items of different types in our collections, we need to cover our bases and run checks for each type that we can envision coming up during a search run and to make sure that false positives shouldn't come up, heed the -1 cases in each test.

You can find the test repl here to run and explore the tests:

Implementation

Initially for this article I had planned to go with the naive approach and use the simplest form of the linear search algorithm that exists:

from typing import List;

def linearSearch(collection: List, value) -> int:
  for index, item in enumerate(collection):
    if item is value: return index;
  return -1;

In theory this is fine but in practice it is not the best way we could handle comparisons because the is operator in python doesn't cover all types nor does it run deep equality checks such as in the case of nested arrays. To make sure we are able to handle these scenarios I have updated the solution to work with multiple types for use during a search run:

from typing import List;
from operator import eq as deep_equals;

def linearSearch(collection: List, value) -> int:
  for index, item in enumerate(collection):
    if deep_equals(item, value): return index;
  return -1;

Simple, right? With this version of the implementation we can handle pretty much every type there is and thanks to the power of the eq function exposed in the operator module. With this function we can handle things such as deep equality checks, type comparisons and some other things too.

For those of you who want to be really strict about collections holding the same shape of values and their types, you could also write this implementation as:

from typing import List, TypeVar;
from operator import eq as deep_equals;

T = TypeVar('T')

def linearSearch(collection: List[T], value: T) -> int:
  for index, item in enumerate(collection):
    if deep_equals(item, value): return index;
  return -1;

This is great when data is consistently formatted as you will get a swath of benefits that static types can provide. If data is not uniform however, this may not be so easy to rectify but if you know what you are doing it will be worth using in the end.

Conclusions

Knowing how to search through our data is imperative as developers and the linear search algorithm is the simplest implementation of a search algorithm you can have in your toolbelt.

In future articles we will look at more advanced and use-case specific algorithms for searching through different data structures.

I hope you found value in this post and learned something new perhaps too!

The Publisher Subscriber pattern

James Robb — Sun, 12 Apr 2020 21:02:30 +0000

The Publisher Subscriber pattern, also known as PubSub, is an architectural pattern for relaying messages to interested parties through a publisher. The publisher is not generally aware of the subscribers per say but in our implementation it will so that we can ease into the topic.

The PubSub pattern gives us a scalable way to relay messages around our applications but is inflexible in one area and that is the data structure that is sent to each subscriber when a new message is published. Generally this is a good thing though in my opinion since it allows a nice normalised way of transacting data through our applications.

Tests

For the tests I will be using JavaScript and the Jest test runner.

const Publisher = require('./publisher');

let publisher;
beforeEach(() => publisher = new Publisher);

describe("Publisher", () => {
  it("Should construct with default values", () => {
    expect(publisher.topic).toEqual("unknown");
    expect(publisher.subscribers).toEqual([]);
  });

  it("Should add subscribers properly", () => {
    const subscriber = jest.fn();
    expect(publisher.subscribers.length).toEqual(0);
    publisher.subscribe(subscriber);
    expect(publisher.subscribers.length).toEqual(1);
  });

  it("Should publish updates to subscribers", () => {
    const subscriber = jest.fn();
    publisher.subscribe(subscriber);
    publisher.publish("test");
    expect(subscriber).toHaveBeenCalledWith({
      topic: "unknown",
      data: "test"
    });
  });

  it("Should unsubscribe from updates as required", () => {
    const subscriber = jest.fn();
    const subscription = publisher.subscribe(subscriber);
    publisher.publish("test");
    expect(subscriber).toHaveBeenCalledTimes(1);
    publisher.unsubscribe(subscription);
    publisher.publish("test");
    expect(subscriber).toHaveBeenCalledTimes(1);
  });

  it("Should not unsubscribe a subscriber from updates unless it exists", () => {
    const subscriber = jest.fn();
    publisher.subscribe(subscriber);
    expect(publisher.subscribers.length).toEqual(1);
    publisher.unsubscribe(() => 24);
    expect(publisher.subscribers.length).toEqual(1);
  });

  it("Generates a consistent subscription id for each subscriber", () => {
    const subscriber = jest.fn();
    const subscription = publisher.subscribe(subscriber);
    const proof = publisher.createSubscriptionId(subscriber);
    expect(subscription).toEqual(proof);
  });
});

Here we test that:

We begin with sane defaults
We can add subscribers
We can notify subscribers
We can remove subscribers
We only remove subscribers when they exist
We generate consistent ids for each subscriber that is provided

You can run the tests here:

This covers the bases required of a publisher and subscriber and gives us control over who does and does not get notifications when new content is published. Pretty simple so far, right?

Implementation

For our implementation I will be using TypeScript, a typed superset of JavaScript. If you are more comfortable with JavaScript you can compile TypeScript code to JavaScript in the TypeScript playground.

export interface ISubscriberOutput { 
  topic: string; 
  data: any; 
};

export class Publisher {
  public topic: string = "unknown";
  private subscribers: Function[] = [];

  public subscribe(subscriberFn: Function): number {
    this.subscribers = [...this.subscribers, subscriberFn];
    const subscriptionId = this.createSubscriptionId(subscriberFn);
    return subscriptionId;
  }

  public publish(data: any): void {
    this.subscribers.forEach((subscriberFn: Function) => {
      const output: ISubscriberOutput = { topic: this.topic, data };
      subscriberFn(output);
    });
  }

  public unsubscribe(subscriptionId: number): void {
    const subscriberFns = [...this.subscribers];
    subscriberFns.forEach((subscriberFn: Function, index: number) => {
      if(this.createSubscriptionId(subscriberFn) === subscriptionId) {
        subscriberFns.splice(index, 1);
        this.subscribers = [...subscriberFns];
      }
    });
  }

  private createSubscriptionId(subscriberFn: Function): number {
    const encodeString = this.topic + subscriberFn.toString();
    return [...encodeString].reduce((accumulator, char) => {
      return char.charCodeAt(0) + ((accumulator << 5) - accumulator);
    }, 0);
  }
}

This class generates a Publisher with a set of methods for us to use for publishing updates, subscribing to those updates and also unsubscribing when the need arises. Let's break things down from top to bottom.

export interface ISubscriberOutput { 
  topic: string; 
  data: any; 
};

This interface is able to be used by subscribers that will take in messages when the publish method is called on the Publisher and gives us the structured message output we discussed in the introduction of this article.

  public topic: string = "unknown";
  private subscribers: Function[] = [];

As we begin to define the Publisher class, we first initialise the class with a topic of "unknown" since the topic hasn't been provided or overridden. We also have an array of subscribers initialised, each of which should be a Function.

Next we create the subscribe method. This will add the provided subscriberFn function to the subscribers array and then return a subscriptionId for us to use later should we choose to unsubscribe down the road.

  public subscribe(subscriberFn: Function): number {
    this.subscribers = [...this.subscribers, subscriberFn];
    const subscriptionId = this.createSubscriptionId(subscriberFn);
    return subscriptionId;
  }

The createSubscriptionId generates a unique ID for each subscriber and utilises the same algorithm as the the Java String hashCode() Method.

  private createSubscriptionId(subscriberFn: Function): number {
    const encodeString = this.topic + subscriberFn.toString();
    return [...encodeString].reduce((accumulator, char) => {
      return char.charCodeAt(0) + ((accumulator << 5) - accumulator);
    }, 0);
  }

In short we take the current topic and add to that the string representation of the subscriberFn. This gives us a somewhat unique string but is not bulletproof by any means. From here we take each character in the encodeString and reduce it to a number representation unique to that string.

Sidenote: We use the << operator which seems to confuse a lot of developers but in this case we are just doing this in essence: accumulator * (2 ** 5).

So let's say it is the second iteration of the reduce loop and accumulator is at an arbitrary value of 65 which is the character code for lowercase "a".

This being the case the (accumulator << 5) - accumulator line is the same as writing (65 * (2 ** 5)) - 65 during that iteration.

Either way you write it, the resulting number will be 2015 for that example.

Hopefully that makes a bit more sense for you who may not have experienced using bitwise operators before.

I highly recommend reading the MDN bitwise reference for more information.

If we want to unsubscribe from a Publisher at any time, you can simply call the unsubscribe method passing in the return value of the original subscribe call.

  public unsubscribe(subscriptionId: number): void {
    const subscriberFns = [...this.subscribers];
    subscriberFns.forEach((subscriberFn: Function, index: number) => {
      if(this.createSubscriptionId(subscriberFn) === subscriptionId) {
        subscriberFns.splice(index, 1);
        this.subscribers = [...subscriberFns];
      }
    });
  }

Here we clone the current subscribers and loop over the clone until we find one that when it is hashed in the createSubscriptionId function, matches the provided subscriptionId value.

If we find a match then we remove that function from the subscriberFns array and set the subscribers to contain only the remaining subscriberFns.

Lastly we will look at the publish function which takes in some data which can be anything you wish to broadcast to the subscribers.

  public publish(data: any): void {
    this.subscribers.forEach((subscriberFn: Function) => {
      const output: ISubscriberOutput = { topic: this.topic, data };
      subscriberFn(output);
    });
  }

We loop over the current subscribers and notify each one with an object matching the ISubscriberOutput structure.

Overall this implementation keeps things concise and to the point.

Example usage

An example use case could be an article publisher which notifies subscribers when new articles get published. It could look like this for example:

Conclusions

I like this pattern and how it allows a scalable and predictable messaging format and how flexible it can be to the needs of what you are building.

I think this ties in nicely with other architectural patterns like the microservices pattern which uses event queues to pass information around in a way that is not too dissimilar to PubSub.

Hopefully you found some value in todays post and you can make use of this pattern in the future!

Forem: James Robb

What is a Monad?

Okay, so what about monoids vs monads?

What about an Endofunctor?

An example - The Maybe monad

Conclusions

Willans' Formula

Tests

Implementation

Conclusions

Substring search

Tests

Implementation

Conclusions

Data types in Rust

Scalar Types

Integers

Integer Types

Integer Literals

Floating Point Numbers

Booleans

Characters

Compound Types

Tuples

Arrays

Conclusions

Generating permutations

Tests

Implementation

The permute function

The swap function

Conclusions

The stack

Tests

Implementation

Properties

Methods

push

pop

find

peek

empty

size

clear

Conclusions

Getting started with Rust

Getting setup

Hello world!

Conclusions

Approximating PI

The challenge

Tests

Implementation

Visualising our implementation

Conclusions

Jump Search

Tests

Implementation

Conclusions

Binary Search

Tests

Implementation

The imperative approach

The recursive approach

Conclusions

Linear Search

Tests

Implementation

Conclusions

The Publisher Subscriber pattern

Tests

Implementation

Example usage

Conclusions

An example - The `Maybe` monad

The `permute` function

The `swap` function

`push`

`pop`

`find`

`peek`

`empty`

`size`

`clear`