I am currently reviewing sorting in the Coursera/Princeton Algorithms, Part 1 course. While I have covered selection sort, insertion sort, and shell sort, I will be writing about mergesort and quicksort.

Sorting means arraying an array of N items into ascending order by a natural order.

A natural order is generally defined as an order that is natural to humans. For instance, 1, 2, 3, 10, 20, 30 naturally ordered as opposed to a classic alphanumeric ordering, 1, 10, 11, 12, 2, 20, 21, 3.

The items must be of the same type, and is enforced by Java’s type system.

The implementation details of how a data type should be sorted is seperate from the sorting mechanism. In Java, this is achieved by requiring objects to be sorted to implement the Comparable interface:

1
2
3
public interface Comparable<Item> {
    public int compareTo(Item item);
}

The data type itself has to determine how the compareTo() method will work. Every data type that implements Comparable is required to have a compareTo() method. Below is the Java’s String compareTo method:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public int compareTo(String anotherString) {
    int len1 = value.length;
    int len2 = anotherString.value.length;
    int lim = Math.min(len1, len2);
    char v1[] = value;
    char v2[] = anotherString.value;

    int k = 0;
    while (k < lim) {
        char c1 = v1[k];
        char c2 = v2[k];
        if (c1 != c2) {
            return c1 - c2;
        }
        k++;
    }
    return len1 - len2;
}

The following logic is expected by a client using the method (i.e. a sort implementation). Let’s assume v is the item to be compared to another item, w:

  • return a negative integer when v is less than w
  • return 0 when v and w are equal
  • return a positive integer when v is greater than w

You can see String’s compareTo works in this fashion, as it uses the natural order of alphanumeric characters or the length of string.

Sorting Considerations

Certain considerations need to be taken when sorting. The following is not an exhaustive list.

  • certification: are the elements really sorted? how do we check?
  • time complexity: how is performance affected by array reads and writes?
  • space complexity: does the sort work in-place or does it hold another array copy during a sort?
    • in-place takes O(1) extra memory
  • stability: if a keys are equal, does the sort preserve the relative order of the items?
  • is it recursive or non-recursive? how will that affect memory usage?

Common operations in a sort

The are two common operations in sorting that are used across all sort methods. These are abstracted away into helper methods because they are so commonly used. They are the less() and exch() methods.

less() compares two Comparable items and returns a boolean value depending on whether the first item is less than or greater than the second item:

1
2
3
private static boolean less(Comparable v, Comparable w) {
    return v.compareTo(w) < 0;
}

exch() swaps two items in the array, which is a common operation in sorting. The current value of arr[i] is temporarily cached because arr[i] gets overwritten by value arr[j], and arr[j] is then set to the cached value:

1
2
3
4
5
private static void exch(Object[] arr, int i, int j) {
    Object swap = arr[i];
    arr[i] = arr[j];
    arr[j] = swap;
}

Mergesort

Profile of Mergesort:

  • is stable; keys maintain relative order
  • can be implemented in recursive (top-down) and iterative (bottom-up) variations
  • worst case running time is O(N * logN)
  • it’s prime disadvantage is it uses extra space proportional to array size N, so it’s grows by an order of O(N)

“top-down” mergesort works as a divide and conquer algorithm. Divide and Conquer problems are recursively broken down into subproblems until some base case is reached. In Mergesort’s case, arrays are broken down into subarrays. The smallest “problem” is a single entry array, because a one item array is sorted by default.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
public class Merge {
    private static Comparable[] aux;  // auxillary array for merges

    public static void sort(Comparable[] arr) {
        aux = new Comparable[arr.length];  // allocate space just once
        sort(arr, 0, arr.length-1);
    }

    // sort arr[lo..hi]
    private static void sort(Comparable[] arr, int lo, int hi) {
        if (hi <= lo) return;

        int mid = lo + (hi - lo)/2;

        // sort left-half subarray
        sort(arr, lo, mid);
        // sort right-half subarray
        sort(arr, mid+1, hi);

        merge(arr, lo, mid, hi);
    }

    private static void merge(Comparable[] arr, int lo, int mid, int hi) {
        int i = lo;     // pointer for left-half
        int j = mid+1;  // pointer for right-half

        // copy to static auxillary array
        for (int k = lo; k <= hi; k++) aux[k] = arr[k];

        // merge back to arr[lo..hi]
        for (int k = lo; k <= hi; k++) {

            // copy remainder of right-half subarray to `arr` if left-half
            // subarray is  exhausted
            if (i > mid) arr[k] = aux[j++];

            // copy remainder of left-half subarray to `arr` if right-half
            // subarray is exhausted
            else if (j > hi) arr[k] = aux[i++];

            // most often these two lines are run in the loop - 
            // comparing aux[j] to aux[i]
            else if (less(aux[j], aux[i])) arr[k] = aux[j++];
            else arr[k] = aux[i++];
        }
    }    
}

Quicksort

Profile of Quicksort:

  • unstable; items in the array do not necessarily stay in their natural order
  • the average case running time is O(N * logN)
  • the worst case running time is O(N^2), but it is almost impossible for time complexity to be this bad (see below)
  • average case space complexity is O(logN) and works in-place (versus Mergesort’s requirement for an auxillary array)
  • don’t use for small arrays

Quicksort is another D&C algorithm. It works as an in-place sorting method using partitioning to break arrays into subarrays. The point of partition for each array is called the pivot.

Array contents must be shuffled before any sorting or partitioning takes place in order to avoid the worst case running time. If the array is sorted or reverse-sorted, it will take quadratic time.

The basic steps are:

  1. shuffle the array (ie using Knuth Shuffle)
  2. select a pivot and partition the array so:
    • entries smaller than the pivot are to the left of it
    • entries larger than the pivot are to the right of it
  3. recursively call step 2 on the subarrays until the base case of 1 array entry is reached
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
public class Quick {
    public static void sort(Comparable[] arr) {
        StdRandom.shuffle(arr);
        sort(arr, 0, arr.length - 1);
    }

    private static void sort(Comparable[] arr, int lo, int hi) {
        if (hi <= lo) return;

        int  = partition(arr, lo, hi);
        // recursive call sort left-of-pivot: arr[lo..j-1]
        sort(arr, lo, j-1);
        // recursive sort right-of-pivot: arr[j+1..hi]
        sort(arr, j+1, hi);
    }

    private static int partition(Comparable[] arr, int lo, int hi) {
        int i = lo;
        int j = hi + 1;
        Comparable v = arr[lo];

        // scan right, scan left, check for scan complete, and exchange
        while (true) {
            // these inner while-loops are incrementing the pointers for the 
            // left of pivot (`i`) and right of pivot (`j`) subarrays

            // find item in left-of-pivot subarray to swap
            while (less(arr[++i], v)) 
                if (i == hi) break;

            // find item in right-of-pivot subarray to swap
            while (less(v, arr[--j])) 
                if (j == lo) break;

            // if the pointers cross, exit the while-loop
            if (i >= j) break;

            // otherwise, swap the current `i`th and `j`th items
            exch(arr, i, j);
        }

        exch(arr, lo, hi);  // put partitioning item v into arr[j];
        return j;  
    }        
}

Final Notes

Java uses Mergesort to sort objects and Quicksort to sort primitive types. Based on this Stackoverflow question, the reasons are:

  1. Being that Quicksort is not stable, it might cause unwanted swaps for an Object array. For primitive types, this is not an issue as they have no identity
  2. Memory usage – because Mergesort doubles the memory necessary with an O(n) space complexity, it’s generally expected the reference types used in an array of objects will take up more memory, so adding slightly more overhead for the benefit of a stable sort is trivial.

Java offers built-in support for custom iteration via the Iterable and Iterator interfaces. An interface in Java is essentially a contract stating a class will implement specific methods, but does not detail the implementation details.

The Java Iterable interface requires the class implementing it has a publicly available iterator() method that returns an Iterator object:

1
2
3
4
5
public class Items<Item> implements Iterable<Item> {
    public Iterator<Item> iterator() {
        return new ThingsIterator<Item>();
    }
}

The Iterator interface requires the class implementing it have the following methods: hasNext(), next(), and remove(). To expand on the above Items class, adding an class to Items that implements the Iterator interface is one way to go about it.

1
2
3
4
5
private class ThingsIterator<Item> implements Iterator<Item> {
    public boolean hasNext() { ... }
    public Item next() { ... }
    public void remove() { ... }
}

hasNext will return a boolean, determining if there is a next item in the data structure. hasNext is called by the next method to determine whether to return an item in the collection if it’s available. Otherwise throw a NoSuchElementException.

Implementing remove is optional; throwing a UnsupportedOperationException() is advisable if the class does not require it.

Using Iterable allows you to write custom collections hidden behind an abstract data type – the client does not have to know how the collection is implemented, all it needs to know is it can iterate over a collection provided by the instance of the iterable implemented class.

For instance, if I have an iterable abstract data type called Things that uses an array or linked list to represent its internal collection, the client only cares about being able to use a for-loop on that collection.

Writing custom iterators is requisite for the Algorithms Stacks, Queues, and Bags assignment. Coding up a Deque and RandomQueue requires the following:

Deque Requirements

1
2
3
4
5
6
7
8
9
10
11
public class Deque<Item> implements Iterable<Item> {
   public Deque()                           // construct an empty deque
   public boolean isEmpty()                 // is the deque empty?
   public int size()                        // return the number of items on the deque
   public void addFirst(Item item)          // add the item to the front
   public void addLast(Item item)           // add the item to the end
   public Item removeFirst()                // remove and return the item from the front
   public Item removeLast()                 // remove and return the item from the end
   public Iterator<Item> iterator()         // return an iterator over items in order from front to end
   public static void main(String[] args)   // unit testing (optional)
}

Performance requirements. Your deque implementation must support each deque operation in constant worst-case time. A deque containing n items must use at most 48n + 192 bytes of memory. and use space proportional to the number of items currently in the deque. Additionally, your iterator implementation must support each operation (including construction) in constant worst-case time.

RandomizedQueue Requirements

1
2
3
4
5
6
7
8
9
10
public class RandomizedQueue<Item> implements Iterable<Item> {
   public RandomizedQueue()                 // construct an empty randomized queue
   public boolean isEmpty()                 // is the queue empty?
   public int size()                        // return the number of items on the queue
   public void enqueue(Item item)           // add the item
   public Item dequeue()                    // remove and return a random item
   public Item sample()                     // return (but do not remove) a random item
   public Iterator<Item> iterator()         // return an independent iterator over items in random order
   public static void main(String[] args)   // unit testing (optional)
}

Performance requirements. Your randomized queue implementation must support each randomized queue operation (besides creating an iterator) in constant amortized time. That is, any sequence of m randomized queue operations (starting from an empty queue) should take at most cm steps in the worst case, for some constant c. A randomized queue containing n items must use at most 48n + 192 bytes of memory. Additionally, your iterator implementation must support operations next() and hasNext() in constant worst-case time; and construction in linear time; you may (and will need to) use a linear amount of extra memory per iterator.

Deque and RandomizedQueue required different iterator implementations. Why? Because they used different data structures.

Deque Iterator Implementation

I implemented Deque using a doubly linked list data structure because all non-iterative operations had to be implemented with constant worst-case time, which is not acheivable with an array when adding or removing an item to/from index 0; the rest of the items in the array have to be shifted back or forward one slot, which takes linear time.

Using a doubly linked list runs constant time for the non-iterative operations because the Deque keeps track of the first and last nodes in the list, and updates those values accordingly when the non-iterative operations are executed.

Here’s how the Deque implements custom iteration. The example omits non-iterative methods for brevity.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
public class Deque<Item> implements Iterable<Item> {
    private Node first;
    private Node last;
    private int count;

    private class Node {
        private Item item;
        private Node next;
        private Node previous;
    }

    private class ListIterator implements Iterator<Item> {
        private Node current = first;

        public boolean hasNext() {
              return current != null;
        }

        public Item next() {
            if (!hasNext()) throw new NoSuchElementException();

            Item item = current.item;
            current = current.next;
            return item;
        }

        public void remove() { throw new UnsupportedOperationException(); }
    }

    public Iterator<Item> iterator() { return new ListIterator(); }

    // non-iterative methods...
}

RandomizedQueue Iterator Implementation

Implementing a RandomizedQueue used an array as it’s data structure. This was needed because retrieving items from the array had to be at random and in constant amortized time. The reason it’s amortized is to take into account array resizing procedures, which essentially copies the current array to a new, larger or smaller sized array when the contents don’t fit within a desired threshold.

The RandomizedQueue example omits non-iterative methods for brevity.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
public class RandomizedQueue<Item> implements Iterable<Item> {
    private Item[] arr = (Item[]) new Object[1];
    private int count;

    private class RandomIter implements Iterator<Item> {
        private int current = 0;
        private Item[] iterArr;

        public RandomIter() {
            iterArr = (Item[]) new Object[count];

            for (int i = 0; i < count; i++) {
                iterArr[i] = arr[i];
            }
            StdRandom.shuffle(iterArr);  // Knuth shuffle
        }

        public boolean hasNext() {
            if (iterArr.length > current && iterArr[current] != null) return true;
            return false;
        }

        public Item next() {
            if (!hasNext()) throw new NoSuchElementException();

            return iterArr[current++];
        }

        public void remove() { throw new UnsupportedOperationException(); }
    }   

    public Iterator<Item> iterator() { return new RandomIter(); }

    // non-iterative methods...
}

The broad strokes of the above iterator implementation: create a new array that belongs to the iterator inner class and copy over the values of RandomizedQueue. Copying the RandomizedQueue array to iterArr is necessary as shuffling it would break behavior related to enqueuing and dequeuing. hasNext() checks the current index current does not go out of bounds. next() returns the current index item.

My first two weeks at Recurse Center have been pretty intense and hyper-focused. While first few days were dedicated to adjusting to the space, managing my time, and trying to scope what exactly I will be covering while I am here, I jumped into my work without much of a hitch.

In previous post I listed a handful of topics I wanted to cover. My top priority is algorithms and data structures and will be for the remainder of the batch.

To give a loose guide as far as what I should cover, I started Part 1 of Coursera/Princeton’s Algorithms course taught by Kevin Wayne and Robert Sedgewick, and using their text book in tandem with the lessons. So far I have covered:

  • stacks and queues
  • space and time complexity for linked lists vs arrays operations

While there are many resources available for learning algorithms and data structures, Sedwick and Wayne’s lessons were the more attractive option because having video lectures to watch text book explanations helpful is the most beneficial for me.

Many of the video lectures contain helpful animations that Sedgewalk walks through step by step as he explains an algorithm and associated data structure(s).

Additionally, each week a project is assigned that uses the information learned during previous week’s lessons.

One thing I would like to touch on is generics in Java. Why mention them in the context of algorithms? Java is the language used in the above mentioned course. Because Java is strongly-typed, a mechanism for type-safe, easy to read algorithm implementation is needed. Otherwise a new version of the same algorithm would have to be implemented for each particular type a client would use (i.e. StringStack, IntegerStack, etc.).

Java Generics

Generics enable types to be parameters when defining classes, interfaces, and methods. Their benefit is allowing code reuse. See the following examples of non-generic versus generic version of the class Box:

1
2
3
4
5
6
// non-generic version
public class Box {
    private Object obj;
    public void set(Object obj) { this.obj = obj; }
    public Object get() { return obj; }
}
1
2
3
4
5
6
7
// generic version
public class Box<T> {
    // `T` is simply an identifier to recogize the *type*
    private T t;
    public void set(T t) { this.t = t; }
    public T get() { return t; }
}

The non-generic Box in the first example gives no way to verify at compile time how the class is used. For instance, if the non-generic Box is used by a client to add and receive Integer objects to and from a Box instance, and later in the code the client attempts to add a String, it will cause a runtime error. The second example uses type parameters (delineated with angle brackets) to determine which type the Box instance will use when instantiated.

This is accomplished using a generic type invocation:

1
Box<Integer> box;

The above code does not create a new Box. All it does is declare the instance box will hold a reference to a Box of type Integer, known as a parameterized type. To instantiate box, we assign it to a new box instance with the expected data type (Box) and type parameter (Integer):

1
box = new Box<Integer>();

Another benefit of generics use is errors will be caught at compile time instead of runtime, leading to less buggy code. Fixing compile time errors are easier to fix than runtime errors, which can be difficult to find.

Generics are also helpful because they eliminate the need for casts, for the most part (see below):

1
2
3
4
// non-generic ArrayList
List list = new ArrayList();
list.add("foo");
String s = (String) list.get(0); // casting here...
1
2
3
4
// generic ArrayList
List<String> list - new ArrayList<String>();
list.add("bar");
String s = list.get(0);  // look! no cast necessary!

The one caveat is Java does not allow generic array creation. Let’s say you want to create an array inside a class for the passed-in type-parameter:

1
T[] tArr = new Item[1];  // compilation error!

Instead a cast must be used:

1
T[] tArr = (T[]) new Object[1]; // OK!

It’s been quite some time since I have posted here (four years!), but the stars have aligned for what makes sense for me to start again.

Most of the past four years I worked at Perka, which was my first full-time software development role. I am extremely appreciative of my experience there; my fellow teammates were always willing to guide me and were open to my questions on best practices. If I had to sum up the major items I learned at Perka:

  • design patterns
  • proper testing
  • debugging techniques
  • working with multiple teams to realize a product goal
  • the value of code reviews

While my time at Perka was without a doubt beneficial, I began feeling a yearning to learn material outside of my immediate day to day work. Generally I do spend time outside of work to learn new material, but it can become difficult, as I have many competing interests.

I should also state I do not have a formal computer science background; most of my knowledge is self-taught. My time at ITP taught me the fundamentals of programming and gave a lot of time to practice, but it’s by no means all encompassing — and that’s by design. ITP’s focus is on getting an idea off the ground that is demonstrable and testable for users, not writing enterprise-level code. Which makes a lot of sense when you think about it – future-proofing a codebase isn’t really a concern when you’re building projects that you don’t know are viable and will ever see the light of day outside of a course.

With that said, I decided to apply to Recuse Center. RC has been on the back of my mind for quite some time. I am really excited to join a community of fellow developers who are focused on learning new areas of programming for the sake of learning for an extended period of time.

What excites me most about RC is it’s self-directed. I am have complete autonomy on what I will learn. For now, I will mainly focus on:

  • a deep dive into algorithms and data structures. ϟ
  • getting a more advanced understanding of the Java language.
  • writing complex SQL queries.
  • playing with some newer JS frameworks. ᚬ
  • and if there’s time, learn the fundamentals of Haskell.

Tomorrow is my first day and I look forward to posting updates here as I progress. I plan on doing so to keep track of my work. Additionally, doing some meta-analysis of my progress will certainly deepen my understanding of what I am working on.

ϟ: I plan on using Wayne/Sedgewick’s Algorithms 4th Edition and Skiena’s The Algorithms Design Manual.

ᚬ: most of my experience to date is building web apps with ES2015, Backbone.js, Gulp, Browserify, and some custom JS libraries internal to Perka. I am hoping to log some more miles with React/Preact and Vue and Webpack.

…the main difference between writing JavaScript code like the average Joe (or Jill) and writing it like a JavaScript ninja is understanding JavaScript as a functional language. — John Resig, Secrets of the JavaScript Ninja

Learning the fundamentals of functional programming has many benefits — the code is more succinct and readable. It’s also adds an element of fun while thinking through a problem with the lens of “how can I implement this with higher-order functions”?

Below are cherry-picked explanations and examples from around the web that best describe how to implement higher-order functions. The reason I wrote this post is because having these examples is helpful to have in one place, and perhaps you will find it helpful as well. The explanations in this post are gleaned from the following sources:

Higher order functions

Generally speaking, higher-order functions are functions that accept other functions as arguments. Functions that can be passed as an argument is called a first class function. The first class function executes on each item in the array, not on the array as a whole.

Being able to write what we want to do instead of how we do it is the aim of using higher-order functions. The lower-abstracted details are performed behind the scenes.

forEach

array.forEach(callback[, thisArg])

forEach simply iterates over an array and invokes a function on each item in the array:

var nums = [1, 2, 3];
nums.forEach(function(num) {
  console.log(num * 2)  // 2, 4, 6
});

Note: using a return for the inner function does not work, due to how forEach is setup. forEach simply applies an action to an array item without returning the result.

Also important: the function context for forEach is global if no thisObject is passed. So:

var nums = [1, 2, 3];
nums.forEach(function(item) {
  console.log(this);  // Returns global window x 3
});

Passing a function context:

var nums = [1, 2, 3];
nums.forEach(function(item) {
  console.log(this);  // Returns `[1, 2, 3]` x 3
}, nums);

map

arr.map(callback[, thisArg])

map applies a function to each item in an array and returns a resulting array. This is just like forEach, but instead of discarding the values returned by the function, it builds a new array of the transformed values.

var nums = [2, 4, 6, 8];

var squareIt = function(num) {
  return num * num;
};

nums.map(squareIt);  // Returns `[4, 16, 36, 64]`

Another map example:

var words = ['foot', 'goose', 'moose', 'kangaroo'];

function fuzzyPlural(single) {
  var result = single.replace(/o/g, 'e');
  if (single === 'kangaroo') {
    result += 'se';
  }
  return result;
}

words.map(fuzzyPlural);  // Returns `['feet', 'geese', 'meese', 'kangareese']`

Or we can use it to return values without transforming them:

var sandwiches = [
  {name: "hamburger", "price": "$6"},
  {name: "BLT",   "price": "$4"},
  {name: "egg salad",  "price": "$4"}];

var prices = sandwiches.map(function(sandwich) { return sandwich.price; });

filter

arr.filter(callback[, thisObject])

Sometimes we only want to get entries that satisfy a certain condition.

Similar to map, filter takes in an array of values and returns a new array. The difference is filter invokes a function that returns a boolean result. If the function returns true, the value is added to the new array. Values that return a falsey result are filtered out.

var nums = [1, 2, 3, 4, 5, 6];

var isEven = function(num) {
  return num % 2 == 0;
}

nums.filter(isEven);  // Returns `[2, 4, 6]`

Another example:

var people = [
  {name:"John",  age: 40},
  {name:"Sue",   age: 30},
  {name:"Mary",  age: 55},
  {name:"Jack",  age: 20}];

people.filter(function(person) {
  return person.age == 40 || person.age == 30;
});

// returns `[John, Sue]` (an array of objects)

some

arr.some(callback[, thisObject])

Often we want to know whether some or all items in an array satisfy a specific condition.

some returns a boolean for the array. It returns true if some of the items satisfy the condition. The condition is determined by the first-class function, which should return a boolean result.

var nums = [5, 8, 2, 10];
var current = 7;

function higherThanCurrent(num) {
  return num > current;
}

if ( nums.some(higherThanCurrent) ) {
  console.log('Some nums are higher than current')
}

every

arr.every(callback[, thisObject])

We can also test if all values satisfy a specific condition with the every method.

var nums = [5, 8, 2, 10];
var current = 7;

function higherThanCurrent(num) {
  return num > current;
}

if ( nums.every(higherThanCurrent) ) {
  console.log('All nums are higher than current.');
} else {
  console.log('Some nums are lower than current.');
}

indexOf and lastIndexOf

arr.indexOf(searchElement[, fromIndex])

arr.lastindexOf(searchElement[, fromIndex])

indexOf is used to test whether an element is present in an array, which searches with a strict === operator.

The method returns an integer index of the searched element in the array. An element not found returns -1. indexOf also takes an optional fromIndex parameter to start a search from a specific position.

var data = ['two', 'four', 'five', 'six'];

data.indexOf('four');  // 1
// Start search from index position 1, return index position for 'five'
data.indexOf('five', 1);  // 2
data.indexOf('eight');  // -1

lastIndexOf starts a search from the end of an array. It takes the same parameters as indexOf, including the optional fromIndex parameter.

var data = ['two', 'four', 'five', 'six', 'four'];

data.lastIndexOf('five');  // 2
data.lastIndexOf('four', 3);  // 1

reduce and reduceRight

arr.reduce(callback,[initialValue])

arr.reduceRight(callback,[initialValue])

reduce and reduceRight allow us to flatten an array into a single value. The intialValue parameter is optional — if omitted it defaults to the first element of the array. Here’s a simple example of reduce:

var nums = [1, 2, 3, 4];

var sum = nums.reduce(function (previous, current) {
  return previous + current;
});

console.log(sum);  // Returns 10

What’s happening here? We are going through the array and getting:

  1. The previous value of every callback, which initially is the first element since it’s equal to intialValue
  2. The current value of every callback, which at first call is 2
  3. The last two arguments — index and array

Finally we return the sum of our previous and current values, which becomes the previous value of the next iteration, and the current value is set to the next element. It looks like:

// initial set
previous = initialValue = 1, current = 2

// first iteration
previous = (1 + 2) =  3, current = 3

// second iteration
previous = (3 + 3) =  6, current = 4

// third iteration
previous = (6 + 4) =  10, current = undefined (exit)

Generic nature of higher-order functions

What’s really cool about these higher-level functions is they can be applied to other object types as long they have a length property and numeric indices.

// Get the reference to the map method
var map = Array.prototype.map;

// Call it on a string, which will return an array
var helloArray = map.call('hello world', function (char) {
  return char + '*';
});

// Join the array items
console.log( hello.join('') ); // 'h*e*l*l*o* *w*o*r*l*d*'

We can also do the opposite. Such as applying a string method to an array:

var toUpperCase = String.prototype.toUpperCase;

var upper = toUpperCase.apply(['foo', 'bar']).split(',');

console.log(upper);  // ['FOO', 'BAR']

Notice how call and apply are used in these examples. This “generic nature” is the result of having the ability to pass in a different this to the native object methods, via call or apply. call is used when there is a set number of parameters to pass. apply is used to pass in an array.

For the past 3 months I have been working with Backbone.js. Specifically, refactoring my thesis project Notestream as a single page application. I’d like to share a couple insights. Note: I did not include Marionette with this project.

Refactoring this project gave me perspective on whether it’s worthwhile to use a clientside framework. Will you have to maintain the project in the future? Are there a lot of moving parts? Then yes, a framework will probably be useful. Regardless, I highly recommend building a static version of the web app first before incorporating a framework. This way you’ll know how to split out your views and organize your data structures.

The biggest positives for using Backbone with this project are:

  • Splitting DOM elements out from data through templating.
  • Not having to manually poll the server. Events trigger communication with the server now.
  • A single page application feels very snappy

RequireJS

To keep the my code as modularized as possible, I incorporated RequireJS. This way I was able to split out all my code and markup into seperate files, and use them when necessary. Organizing your application using Modules by Thomas Davis as well as Jeffrey Way’s video tuturial do a great job explaining how to use the two in tandem.

One thing to note that was not covered in the tutorials, is the ability to set up your modules a la nodeJS like so:

define(function(require) {
  var Backbone = require('lib/backbone'),
      nestedView = require('views/nestedView')
      demoTemplate = require('text!../../templates/demoView.html');

  // demo view code...
});

Instead of seperately definining your modules and declaring the function:

define(["lib/backbone", "views/nestedView" , "text!../../templates/demoView.html"],
  function(Backbone, nestedView, demoTemplate) {
    // demo view code ...
  }

You can imagine if you have multiple modules, for example many nested views, how the former setup is is better organized. Another potential headache with the latter is the function arguments have to match the order of the modules being defined. Again, that’s solved using variables.

Authentication

One area I had some difficulty with a how to implement authentication with a single page app. I have not seen a lot of detailed tutorials or example code on implementing authentication along with Backbone.js.

For now, I am using seperate routes for authentication with Passport.js, while the Notestream app itself is a single page app.

For the past five weeks I have been poring over Backbone.js tutorials. After building Notestream, it became apparent why using a clientside framework is necessary. By the time I had to present my thesis, I was in nested-callback hell. The code was becoming difficult to manage, and I could see how cumbersome a project can become without a framework to organize it.

So I picked up a couple resources to learn how to implement Backbone, and I am in the process of refactoring my thesis project now. I can’t see myself building a webapp without a framework again!

Here are the resources I found most useful:

Connected to the Backbone by Jeffrey Way

Jeffrey Way’s Connected to the Backbone does an excellent job walking the viewer step by step through the Backbone concepts using a tasks example and contact manager example. The lessons also focus on proper namespacing in Backbone, which has been helpful as well.

My suggestion is learn the code by heart, even if you’re not unsure about what all the parts are doing yet. You’ll see the patterns Backbone implements, and learn accordingly.

With that said, there are a few hang-ups with this tutorial.

First, there are a lot of example files missing from the project source. Most of the time I had to copy from the video instead of reviewing from a text file. More importantly, Jeffrey uses Laravel as his backend. These files were not included, and they were only quickly reviewed in the videos. Because of this, I ended up taking a break from the lessons. More on that later.

Secondly, coverage of routes was lacking. Particularly event handling for routes. Ultimately a lot of Googling, and searching Stackoverflow and Github got me what I needed. Still, this concept is pretty integral to Backbone, and would have been helpful to see it tied in with the examples used.

Lastly, a minor point: the tutorial is relatively dated. It was recorded in August of 2012, before Backbone 1.0 was released. While the changes are minor, coming into the framework complete new, I wasn’t sure when I was hitting an error due to my code, or a method that was deprecated from an older version. My suggestion: pay close attention to the viewer comments that go along with the videos.

Developing Backbone.js Applications by Addy Osmani

I can’t speak for the entirety of Developing Backbone.js Applications, but it gave me a thorough understanding on how to integrate nodeJS and MongoDB with Backbone. As explained, I took a breather from Connected to the Backbone in order to implement a nodeJS server with a proper RESTful API.

The book is still being updated, and you can download the latest version at the Github repo.

Today I moved my blog content from Squarespace to Octopress. Octopress touts itself as “a blogging framework for hackers”, and rightly so. After poking around the framework file hierarchy, administration compared to Squarespace is a lot easier for a number of reasons:

  1. Octopress is run from the command-line and a text editor. It’s a lot faster to post, edit, and tweak the styling and features compared Squarespace’s web interface.

  2. Version control through git. Squarespace does offer version control now as well, however if you use it you have to create your own templates from scratch—there’s no happy medium.

  3. Open source. There’s an active community behind Octopress pushing plugins and themes.

  4. Markdown files. Squarespace offers export functionality, however the single export option is Wordpress. I can’t export text files for personal use, so I am moving the content over by hand one post at a time. With Octopress I am simply pushing commits with the markdown files to my Github repo.

Don’t get me wrong, Squarespace is great if you need an “out of the box” website solution—not to mention, their customer support is first class. However, now I have complete control of my content and how it’s displayed, and it feels good!

These instructions were helpful in getting started with Octopress:

And I’m using the Greyshade theme from Shashank Mehta.

ITP

This week I graduated from ITP, and it’s bitter sweet. I hope to find a place with such a concentration of talented, creative, and intellectually curious people in my future days.

As for now, I will continue building on Notestream, and dive further into Backbone.js, and get a cursory understanding of the Go language. I also want to find some kind of mentor so I can write more efficient Javascript and learn better coding practices.

This is also a time for me to self-assess in terms of employment. What are my strengths and where am I mediocre? What type of organization do I want to work with? What are my goals for the next 18 months? Now that I have some time on my hands, I can figure out what I plan on doing post-ITP.

With that said, there are a couple “must-haves” going forward in terms of my career in design and software development:

  • Work with a team of people who love what they do.

  • Be challenged by what I am doing and proud of the work I am putting into the world.

I have a feeling the rest will fall into place.

My thesis project Notestream was built on top of nodeJS and Express. What has really sold me on nodeJS is the active community and the amount of modules available for use.

Here are a few modules I found useful during Notestream’s development.

Shred

Shred is an HTTP client library. I used the Shred module for AJAX posts when I wanted to append more meta data, but didn’t want to slow down the user from advancing to the next page.

For example, Notestream users save a Vimeo video to their video collection in order to mark it up with annotations. After a user submits the ‘save video’ form, Shred allows the server to gather additional meta-data from Vimeo after the AJAX post is made. It’s all happening in the background.

JSON2csv

Another useful module is JSON2csv, and title pretty much says it all. Notestream users can download their notes in csv format thanks to JSON2csv. The module pings the Notestream API when a user chooses to download their notes, and formats the JSON accordingly.

Tock

Tock is Javascript countdown clock and timer. Why use this when JS already offers interval and timeout functionality? Because they’re not very accurate. What’s awesome about Tock is it self-corrects the time based on the system clock, so it won’t lose track of the time.