CHALLENGE #3

HIGHER-ORDER FUNCTIONS

implement a function "foldFromRight" which takes:

a function with two parameters (a "binary function")
a starting value (the accumulator)
a list of values to reduce into a single value

The behavior of your foldFromRight function will be similar to "reduce" in JavaScript and Ruby - except for the fact that it will move from the end of the list to the beginning (instead of from the beginning to the end).

foldFromRight(function(item, memo) {
	return memo.concat([item]);
}, [], [5, 4, 25]); // [25, 4, 5]

Can you implement a function "foldFromLeft" using your "foldFromRight" function? If you can't, that's fine - implement it from scratch.

foldFromLeft(function(memo, item) {
	return memo.concat([item]);
}, [], [5, 4, 25]); // [5, 4, 25]

Implement a function "mapListFromLeft" using your "foldFromLeft" function.

mapListFromLeft(function(item) {
	return item * 2;
}, [10, 20, 30]); // [20, 40, 60]

Implement a function "filterListFromLeft" using your "foldFromLeft" function.

filterListFromLeft(function(item) {
	return item == 2;
}, [1, 2, 3, 2]); // [2, 2]

Implement a function "findInList" that, given a list and a (unary function) predicate returns the first item in the list that satisfies the predicate. The function should return your language's null type if no item in the list satisfies the predicate.

findInList(function(item) {
	return item == 2;
}, [1, 2, 3, 2]); // 2

Implement a function "makeBBST" that, given a list of integers, uses your foldFromLeft function to build a balanced binary search tree. You may choose to represent the balanced binary search tree however you like (create your own class, use JSON... whatever) - but be sure not to CHANGE a tree after you have created one. Insertion should be modeled as creating a new tree (with a node added) from the old tree.

makeBBST([1,2,3,5,4,6]) // something like: ((null, 1, null) 2 null) 3 ((null, 4, null) 5 (null 6 null))

makeBBST([1,2,3,4,5,6,7]) // something like: (((null, 1, null) 2 (null, 3, null)) 4 ((null, 5, null) 6 (null, 7, null)))

For a little more background about this data structure, check out this link: http://java.dzone.com/articles/algorithm-week-balancing

Implement a function "existsInBBST" that, given a predicate and a balanced binary search tree, returns true if there is a value in the tree that satisfies the predicate. If no value that fulfills the predicate is found, false should be returned.

someTree = (((null, 1, null) 2 (null, 3, null)) 4 ((null, 5, null) 6 (null, 7, null)))

existsInBBST(function(value) {
	return value == 7;
}, someTree); // true

BONUS CHALLENGE X: More Datastructure Stuff

Can you implement a function "mapBBST" that, given a unary function and a balanced binary search tree produces a new balanced binary search tree from applying your unary function to each node in the original tree?

BONUS CHALLENGE Y: Parallelism

Can you write parallelized versions of mapListFromLeft and filterListFromLeft?
Given the attached file (some huge text file, say, the text from Moby Dick ( http://www.gutenberg.org/files/2701/old/moby10b.txt ), write a program that returns the top three pairings (in terms of frequency) of words that appear in a sentence together. In the event that pairs are tied in their rank, pick a tiebreaker of your choosing and explain its implementation. Ignore capitalization. A function that returns the "pairs" of words in a sentence might behave like this:

pairs("Hello, my friends!"); // hello+my hello+friends my+hello my+friends

GLOSSARY, BY EXAMPLE

Unary Function (one parameter)

function addOne(x) {
	return x + 1;
}

Binary Function (two parameters)

function add(x, y) {
	return x + y;
}

Predicate

pred = function(n) { return n > 3; }
[1,2,3,4,5].filter(pred); // [4, 5]

laser/three.md