Closures, Currying, and Recursion

Refer Week 15 for practice projects and prompts. Includes code from peers involved in pair programming sessions.

Example: Closure

const welcome = (salutation) => (name) => `${salutation}! Nice to meet you, ${name}!`

const multiplier = (numBy) => (numTo) => numBy * numTo
const doubler = multiplier(2)
const tripler = multiplier(3)
const quadrupler = multiplier(4)

// Becomes
doubler(4)        // 8
tripler(4)        // 12
quadrupler(4)     // 16

Closures are functions that retain the context of the functions they were declared in and can be returned as functions

Example: Currying

const sentiment = (howMuchLike, thing, reason) => `I ${howMuchLike} ${thing} because ${reason}.`

// Becomes
const sentiment = (howMuchLike) => (thing) => (reason) => `I ${howMuchLike} ${thing} because ${reason}.`
const thingsBugMe = sentiment("do not like")
const loveCoding = sentiment("love")("coding")

thingsBugMe("global variables")("they are a code smell")
// produces: I do not like global variables because they are a code smell
loveCoding("it is fun")
// produces: I love coding because it is fun

Functions returned from within functions enable multiple layers of specificity

Reusable; function composition

Example: Recursion

Counter: counts up to 3

const counter = count => {
    if (isNaN(count))
        return
    if (count >= 3)
        return count
    else
        console.log(count)
        return counter(count + 1)
}

counter(0)
// produces: 0 1 2

Recurse reverse: reverse a string

const reverse = str => {
    if (str == "")
        return ""
    return reverse(str.substring(1)) + str[0]
}

reverse("fern")
// produces: nref

Lookup
- Tail call optimization (node.js has, js not)
- Trampoline function

Trampoline function: Wraps a recursive function in a loop and breaks recursive function down so each function isn't heaped on stack

Coin Counter

Synchronous

const coin_counter = val => {
    const coin_amounts = [];
    coin_amounts.push(Math.floor(val / 25));
    val %= 25;
    coin_amounts.push(Math.floor(val / 10));
    val %= 10;
    coin_amounts.push(Math.floor(val / 5));
    val %= 5;
    coin_amounts.push(val);
    return coin_amounts;
}

Recursion

const counter = (val, i, arr) => {
    if (i == arr.length)
        return arr;
    const n = arr[i];
    arr[i] = Math.floor(val / n);
    return counter(val % n, ++i, arr);
}

const recursion = val => counter(val, 0, [25, 10, 5, 1])

Closure

const coin_counter = () => {
    const quarter = 25;
    const dime = 10;
    const nickel = 5;
    // const penny = 1;
    return val => [
        Math.floor(val / quarter),
        Math.floor((val % quarter) / dime),
        Math.floor((val % quarter % dime) / nickel),
        val % quarter % dime % nickel
        // remainder is always integer, n % 1 = n
    ];
}
const closure = coin_counter();
closure(val);

Currying

const coin_counter = amount => val => [ Math.floor(val / amount), val % amount]

const quarters = coin_counter(25);
const dimes = coin_counter(10);
const nickels = coin_counter(5);
const pennies = coin_counter(1);

const currying = val => {
    const fn = [ quarters, dimes, nickels, pennies ];
    const coin_amounts = [];
    for (let i = 0; i < 4; i++) {
        const [n, rem] = fn[i](val);
        coin_amounts[i] = n;
        val = rem; 
    }
    return coin_amounts;
}

Testing the Functions

const solutions = [ coin_counter, recursion, closure, currying ];
const run_test = fn => {
    const values = [1, 5, 10, 25, 141, 499];
    const expected = [
        [0, 0, 0, 1],
        [0, 0, 1, 0],
        [0, 1, 0, 0],
        [1, 0, 0, 0],
        [5, 1, 1, 1],
        [19, 2, 0, 4]
    ];
    for (let i = 0; i < values.length; ++i) {
        console.log(fn.name);
        const result = fn(values[i]);
        const expected_str = expected[i].join("");
        const result_str = result.join("");
        const passed = expected_str === result_str;
        console.log(passed ? 
            `Test passed - Expected: ${expected[i]}`
            : `Test failed - Expected: ${expected[i]}\n\tResult: ${result}`);
    }
}

for (const fn of solutions)
    run_test(fn);

Roman Numerals

const numerals = { "I": 1, "V": 5, "X": 10, "L": 50, "C": 100, "D": 500, "M": 1000 };

Recursion I

const recursion_1 = str => {
    const n = numerals(str[0]);
    if (str.length < 2)
        return n;
    const n_plus = numerals(str[1]);
    if (n_plus > n)
        return recursion_1(str.substring[1]) - n;
    else
        return recursion_1(str.substring[1]) + n;
}

Recursion II

const recursion_2 = (str, i) => {
    if (i == str.length - 1)
        return numerals(str[i]);
    const n_i = numerals(str[i]);
    const n_plus = numerals(str[i + 1]);
    return recursion_2(str, i + 1) + (n_plus > n_i ? n_i * -1 : n_i);
}

Currying

const get_numeral = character => value => str => {
    let count = 0;
    for (let i = 0; i < str.length; i++)
        for (str[i] === character)
            count++;
    return value * count - (count > 3 ? value : 0);
}
const get_I = get_numeral("I")(1);
const get_V = get_numeral("V")(5);
const get_X = get_numeral("X")(10);
const get_L = get_numeral("L")(50);
const get_C = get_numeral("C")(100);
const get_D = get_numeral("D")(500);
const get_M = get_numeral("M")(1000);

const currying = str => {
    return get_M(str) + get_D(str) + get_C(str) + get_L(str) + get_X(str) + get_V(str) + get_I(str);
}

Testing the Functions

const solutions = [ recursion_1, recursion_2, currying ];
const run_test = fn => {
    const strings = ["III", "MMMCMXCIX", "XLVIII", "MDCLXVI", "MMMCCCXXXIII"];
    const expected = [3, 3999, 48, 1666, 3333];
    for (let i = 0; i < strings.length; i++) {
        console.log(fn.name);
        const result = fn(strings[i]);
        const passed = expected[i] === result;
        console.log(passed ?
            `Test passed - Expected: ${expected[i]}`
            : `Test failed - Expected: ${expected[i]}\n\tResult: ${result}`
    }
}
for (const fn of solutions)
    run_test(fn);

Prime Sifting

Synchronous

const prime_sifting = n => {
    if (n < 2)
        return [];
    if (n == 2)
        return [2];
    const stack = [2];
    let i = 3;
    while (i <= n) {
        for (let j = 0; j < stack.length; ++j)
            if (i % stack[j] == 0) {
                ++i;
                continue;
            }
        stack.push(i);
        ++i;
    }
    return stack;
}

Recursion

const recursion = (n, k = 2, stack = []) => {
    if (k > n)
        return stack;
    let prime = true;
    for (let i = 0; i < stack.length; ++i)
        if (k % stack[i] == 0)
            prime = false;
    if (prime)
        stack.push(k);
    return recursion(n, ++k, stack);
}

In-progress: Recursion_2

const mod_stack = (k, stack) => {
    if (stack.length != 0)
        for (let i = 0; i < stack.length; i++)
            if (k % stack[i] == 0)
                return stack;
    stack.push(k);
    return stack;
}
const recursion_2 = (n, k = 2, stack = []) => k > n ? stack : recursion_2(n, ++k, mod_stack(k, stack))

In-progress: Closure

const closure = n => {
    const k = 2;
    const stack = [];
    const recurse = (k, stack) => n => {
        if (n < 2)
            return [];
        if (n == 2)
            return [2];
        if (k > n)
            return stack;
        for (let i = 0; i < stack.length; i++)
            if (k % stack[i] == 0)
                return recurse(n, ++k, stack);
        stack.push(k);
        return recurse(n, ++k, stack);
    }
    return recurse(k, stack);
}

Testing the Functions

const solutions = [ prime_sifting, recursion ];
const run_test = fn => {
    const n = [0, 1, 2, 120, 300];
    for (let i = 0; i < n.length; i++) {
        const result = fn(n[i]);
        console.log(fn.name);
        console.log(`\tPrimes in ${n[i]}: ${result}`);
    }
}
for (const fn of solutions)
    run_test(fn);

Testing on prime sifting does not include result comparison, nor specifies if a test passed or failed. It merely prints the results.