origami.js

/*
 * 'Origami Programming' by Hugo Sereno Ferreira
 *
 * IEEE Talk @ FEUP (2018)
 *
 * Exercise sheet (http://goo.gl/Dd4p7b)
 *
 * Note: Make sure you have node.js, and then install the dependencies using:
 *
 * npm install -g lodash
 *
 * For a Live Programming experience, use the Quokka plugin (https://quokkajs.com) with VSCode (https://code.visualstudio.com)
 */

// region Preamble
const assert = require('assert');
const eq = require('lodash').isEqual;
// endregion

// region Basic example

const a = [1, 2, 3, 4, 5];
let s = 0;
for (let i = 0; i < a.length; i++)
  s += a[i];

s;

// endregion

// region Basic example with strings

const sin = ['To', ' be', ' or', ' not', ' to', ' be!'];
let sout = '';
for (let i = 0; i < a.length; i++)  // a bug lies here!
  sout += sin[i];

sout;

// endregion

// region Filtering even array elements

const b = [1, 2, 3, 4, 5, 6];
let filtered = Array();
for (let i = 0; i < b.length; i++)
  if (a[i] % 2 == 0) filtered.push(a[i]);

filtered;
// endregion

// region Base definition of fold

const fold = (as, base) => (f) => {
  let result = base;
  for (let i = 0; i < as.length; i++)
    result = f(result, as[i]);
  return result;
};

// endregion

// region sum = [as] => Integer

const sum = (as) => fold(as, 0)((sum, a) => sum + a);

assert(sum([1, 2, 3]) === 6);
assert(sum([]) === 0);

// endregion

// region foreach = [a] => (a => void) => void
const foreach = (as) => (f) => fold(as, undefined)((_, a) => f(a));

const farr = new Array();
foreach([1, 2, 3])(e => farr.push(e));
assert(eq(farr, [1, 2, 3]));
// endregion

// region map = [a] => (a => b) => [b]
const map = (as) => (f) => fold(as, [])((bs, a) => bs.concat([f(a)]));

assert(eq(map([1, 2, 3])(e => e + 1), [2, 3, 4]));
assert(eq(map([])(x => x + 5), []));

// endregion

// region filter = [a] => (a => bool) => [a]
const filter = (as) => (f) => fold(as, [])((as, a) => f(a) ? as.concat([a]) : as);

assert(eq(filter([1, 2, 3, 4, 5, 6])(e => e % 2), [1, 3, 5]));
assert(eq(filter([1, 2, 3, 4, 5, 6])(e => e % 2 == 0), [2, 4, 6]));
// endregion

// region filterNot = [a] => (a => bool) => [a]
const filterNot = (as) => (f) => filter(as)(a => !f(a));

assert(eq(filterNot([1, 2, 3, 4, 5, 6])(e => e % 2), [2, 4, 6]));
assert(eq(filterNot([1, 2, 3, 4, 5, 6])(e => e % 2 == 0), [1, 3, 5]));
// endregion

// region exists = [a] => (a => bool) => bool
const exists = (as) => (f) => fold(as, false)((exists, a) => exists ? exists : f(a));

assert(exists([1, 2, 3])(e => e == 3) === true);
assert(exists([1, 2, 3])(e => e > 2) === true);
assert(exists([1, 2, 3])(e => e == 5) === false);
// endregion

// region forall = [a] => (a => bool) => bool
const forall = (as) => (f) => fold(as, true)((all, a) => all && f(a));

assert(forall([1, 2, 3])(e => e < 4) === true);
assert(forall([1, 2, 3])(e => e > 4) === false);
assert(forall([])(e => e > 5) === true);
// endregion

// region length = [a] => Integer
const length = (as) => fold(as, 0)((length, _) => length + 1);

assert(length([1, 2, 3]) == 3);
assert(length([]) == 0);
// endregion

// region isEmpty = [a] => bool
const isEmpty = (as) => length(as) == 0;

assert(isEmpty([]) === true);
assert(isEmpty([1, 2, 3]) === false);
// endregion

// region notEmpty = [a] => bool
const notEmpty = (as) => length(as) != 0;

assert(notEmpty([]) === false);
assert(notEmpty([1, 2, 3]) === true);
// endregion

// region reverse = [a] => [a]
const reverse = (as) => fold(as, [])((as, a) => [a].concat(as));

assert(eq(reverse([1, 2, 3]), [3, 2, 1]));
assert(eq(reverse([]), []));
// endregion

// region first = [a] => a ?
const first = (as) => fold(as, null)((first, a) => first ? first : a);

assert(first([1, 2, 3]) === 1);
assert(first([]) === null);
// endregion

// region last = [a] => a ?
const last = (as) => first(reverse(as));

assert(last([1, 2, 3]) === 3);
assert(last([]) === null);
// endregion

// region tail = [a] => [a]
const tail = (as) => fold(as, undefined)((as, a) => as === undefined ? [] : as.concat([a])) || [];

assert(eq(tail([1, 2, 3]), [2, 3]));
assert(eq(tail([2, 3]), [3]));
assert(eq(tail([3]), []));
assert(eq(tail([]), []));
// endregion

// region second = [a] => a ?
const second = (as) => first(tail(as));

assert(second([1, 2, 3]) === 2);
assert(second([1]) === null);
assert(second([]) === null);
// endregion

// region max = [a] => a
const max = (as) => fold(as, null)((max, a) => max > a ? max : a);

assert(max([1, 2, 3]) === 3);
assert(max([1]) === 1);
assert(max([]) === null);
// endregion

// region maxBy = [a] => (a => b) => a
const maxBy = (as) => (f) => fold(as, null)((max, a) => max === null ? a : (f(max) > f(a) ? max : a));

assert(eq(maxBy([{a: 1}, {a: 2}, {a: 3}])(e => e.a), {a: 3}));
// endregion

// region min = [a] => a
const min = (as) => fold(as, null)((min, a) => min === null ? a : (min < a ? min : a));

assert(min([1, 2, 3]) === 1);
assert(min([1]) === 1);
assert(min([]) === null);
// endregion

// region minBy = [a] => (a => b) => a
const minBy = (as) => (f) => fold(as, null)((min, a) => min === null ? a : (f(min) < f(a) ? min : a));

assert(eq(minBy([{ a: 1 }, { a: 2 }, { a: 3 }])(e => e.a), { a: 1 }));
// endregion

// region find = [a] => (a => bool) => a?
const find = (as) => (f) => fold(as, null)((found, a) => f(a) ? a : found);

assert(eq(find([{ name: 'quim', age: 2 }, { name: 'tostas', age: 3 }])(e => e.age == 3), { name: 'tostas', age: 3 }));
assert(find([{ name: 'quim', age: 2 }])(e => e.age == 52) === null);
// endregion

// region takeWhile = [a] => (a => bool) => [a]
const takeWhile = (as) => (f) => fold(as, [])((as, a) => f(a) ? as.concat([a]) : as);

assert(eq(takeWhile([1, 2, 3, 4, 5])(e => e <= 2), [1, 2]));
// endregion

// region dropWhile = [a] => (a => bool) => [a]
const dropWhile = (as) => (f) => fold(as, [])((as, a) => f(a) ? as : as.concat([a]));

assert(eq(dropWhile([1, 2, 3, 4, 5])(e => e <= 2), [3, 4, 5]));
// endregion

// region partition = [a] => (a => bool) => ([a], [a])
const partition = (as) => (f) => fold(as, [[], []])((partition, a) => {
  if (f(a)) {
    return [partition[0].concat([a]), partition[1]];
  } else {
    return [partition[0], partition[1].concat([a])];
  }
});

assert(eq(partition([1, 2, 3, 4])(e => e % 2), [[1, 3], [2, 4]]));
// endregion

// region splitAt = [a] => Integer => ([a], [a])
const splitAt = (as) => (i) => fold(as, [[], []])((split, a) => {
  if (split[0].length < i) {
    return [split[0].concat([a]), split[1]];
  } else {
    return [split[0], split[1].concat([a])];
  }
});

assert(eq(splitAt([1, 2, 3])(2), [[1, 2], [3]]));
// endregion

// region zip = [a] => [b] => [(a, b)]
const zip = (as) => (bs) => fold(as, [[], bs])((state, a) => {
  if (isEmpty(state[1])) return state;
  else {
    const b = first(state[1]);
    return [state[0].concat([[a, b]]), tail(state[1])];
  }
})[0];

assert(eq(zip([1, 2, 3])(['a', 'b', 'c']), [[1, 'a'], [2, 'b'], [3, 'c']]));
// endregion

// region zipWithIndex = [a] => [(Integer, b)]
const zipWithIndex = (as) => fold(as, [[], 0])((state, a) => [state[0].concat([[a, state[1]]]), state[1] + 1])[0];

assert(eq(zipWithIndex(['a', 'b', 'c']), [['a', 0], ['b', 1], ['c', 2]]));
// endregion

// region index = [a] => Integer => a?
const index = (as) => (i) => fold(as, [null, i])((state, a) => [state[1] == 0 ? a : state[0], state[1] - 1])[0];

assert(index(['a', 'b', 'c'])(0) === 'a');
assert(index([1, 2, 3])(1) === 2);
// endregion

// region indexWhere = [a] => (a => bool) => Integer?
const indexWhere = (as) => (f) => fold(as, [null, 0])((state, a) => [state[0] === null && f(a) ? state[1] : state[0], state[1] + 1])[0];

assert(indexWhere(['a', 'b', 'c'])(e => e == 'b') === 1);
assert(indexWhere(['a', 'b', 'c'])(e => e == 'd') === null);
// endregion

// region take = [a] => Integer => [a]
const take = (as) => (i) => fold(as, [[], i])((state, a) => [state[1] > 0 ? state[0].concat([a]) : state[0], state[1] - 1])[0];

assert(eq(take(['a', 'b', 'c'])(2), ['a', 'b']));
assert(eq(take(['a', 'b', 'c'])(5), ['a', 'b', 'c']));
assert(eq(take(['a', 'b', 'c'])(0), []));
// endregion

// region drop = [a] => Integer => [a]
const drop = (as) => (i) => reverse(take(reverse(as))(length(as) - i));

assert(eq(drop(['a', 'b', 'c'])(2), ['c']));
assert(eq(drop(['a', 'b', 'c'])(5), []));
assert(eq(drop(['a', 'b', 'c'])(0), ['a', 'b', 'c']));
// endregion

// EXTRA

// region flatMap = [a] => (a => [b]) => [b]
const flatMap = (as) => (f) => fold(as, [])((bs, a) => bs.concat(f(a)));

assert(eq(flatMap([1, 2, 3, 4])(x => [x, x * 2, x * 3]), [1, 2, 3, 2, 4, 6, 3, 6, 9, 4, 8, 12]));
assert(eq(flatMap([['a'], ['b'], ['c']])(x => x), ['a', 'b', 'c']));
assert(eq(flatMap([])(x => x), []));
// endregion