Skip to content

Instantly share code, notes, and snippets.

@djedr
Last active May 29, 2019 19:38
Show Gist options
  • Star 2 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save djedr/b65dacdbc4a9dc090598161616dff8b3 to your computer and use it in GitHub Desktop.
Save djedr/b65dacdbc4a9dc090598161616dff8b3 to your computer and use it in GitHub Desktop.
My solution to "A little JavaScript problem" from lisperator.net [ http://lisperator.net/blog/a-little-javascript-problem/ ], with comments.
/**
* @file Solution to "A little JavaScript problem" from [lisperator.net]{@link http://lisperator.net/blog/a-little-javascript-problem/}.
*
* For demonstration. Overdocumented on purpose. Documentation is in a JSDoc-like documentation style.
* The solution itself is 7 SLOC.
* I also included test code to automatically verify correctness of the solution.
* See {@link https://gist.github.com/djedr/68fdaef3cad134788caefac06388534c} for a version without documentation or test code.
*
* Assumes ES6 support.
* Uses nested closures to emulate singly linked lists.
*
* Special thanks to untyped lambda calculus. ;)
*
* @author Dariusz Jędrzejczak
*/
// Type definitions
/**
* List type definition.
*
* A list is implemented as a closure, which emulates a singly linked list.
* The head and tail of the list are stored in the closure's environment.
* The head should contain the data (payload) of the list node and the tail should contain either
* a reference to another node ("nested" closure) or null if this is the last node in the list.
*
* Note: I use the `private` documentation tag to describe the values contained in the closure's environment.
* The `callback` tag is used to define the type, since it fits the best in this case -- a list is really a function.
*
* @callback List
* @private {any} h -- The head of the list.
* @private {?List} t -- The tail of the list.
* @param {boolean=} head -- If true, then the call to the list function returns its head (data).
* If false or not specified, the call to the list function returns its tail.
*
* @see {@link list}
*/
/**
* ListCallback type definition.
*
* A ListCallback is single-argument function, which operates on a value of an element of a list.
* It processes the value of the element and returns the result.
*
* ListCallbacks are used by {@link map} and {@link foreach}.
*
* @callback ListCallback
* @param {any} value -- A value to be processed.
* @return {any} -- The result of processing the element.
*/
// The most important function -- list
/**
* Returns a new list node, with head h and tail t.
*
* @param h {any} -- The head of the list. Should contain the data/payload of the node.
* @param t {?List} -- The tail of the list. Should contain a nested list or null, if this is the last node.
* @return {List} -- A closure, which represents the list node.
*/
let list = (h, t) => (head) => head? h: t;
// Basic functions: range, map and foreach
/**
* Returns a list, which contains the integers in range a (inclusive) to b (exclusive).
*
* @param a {number} -- The first number to be included in the output list.
* This number will always be included, regardless of the value of b.
* @param b {number} -- The number, which specifies the upper limit of the range.
* This number will not be included in the output list.
* If it is less than or equal to a, then the output list will contain only a.
* Otherwise the output list will also contain all integers between a and b.
* @return {List} -- The output list.
*/
let range = (a, b) => list(a, a >= b? null: range(a + 1, b));
/**
* Maps an input list onto a new list using a callback to process each element.
* Every element in the output list has a value,
* which is the result of applying a callback function f to the respective element from the input list.
*
* @param {List} l -- The input list.
* @param {ListCallback} f -- The callback.
* @return {List} -- The new list, mapped from the input list.
*/
let map = (l, f) => list(f(l(true)), l() === null? null: map(l(), f));
/**
* Invokes a callback f on each element of the input list l, in order.
*
* @param {List} l -- The input list.
* @param {ListCallback} f -- The callback.
* @return {undefined}
*/
let foreach = (l, f) => (f(l(true)), l() === null? undefined: foreach(l(), f));
// Helper functions for reverse: last and pop
/**
* Retrieves the value of the last element of the input list.
*
* @param {List} l -- The input list.
* @return {any} -- The value of the last element of the list.
*/
let last = (l) => l() === null? l(true): last(l());
/**
* Returns a new list, which is the same as the input list, except that the last element is missing (popped out).
*
* @param {List} l -- The input list.
* @return {List} -- A copy of the input list without the last element.
*/
let pop = (l) => l() === null? null: list(l(true), pop(l()));
// Finally, reverse itself
/**
* Returns a new list, which contains the same values as in the input list, but in reverse order.
*
* @param {List} l -- The input list.
* @return {List} -- A copy of the input list with elements in reverse order.
*/
let reverse = (l) => list(last(l), l() === null? null: reverse(pop(l)));
/**
* @overview The program code from [the post]{@link http://lisperator.net/blog/a-little-javascript-problem/}.
*
* @author Mihai Bazon
*/
var numbers = range(1, 10);
numbers = map(numbers, function (n) { return n * n });
numbers = reverse(numbers);
foreach(numbers, console.log);
/* output:
100
81
64
49
36
25
16
9
4
1
*/
/**
* @overview Test code to verify if the actual output matches the expected output.
*
* @author Dariusz Jędrzejczak
*/
/**
* A test object which emulates JavaScript console. Uses a string as standard output.
*
* @private {string} output -- The output string, which represents the console's standard output.
*/
let testConsole = (() => {
let output = '';
return {
/**
* Emulates console.log. Writes to the output string.
*
* @param {any} message -- The message to be written to the output.
* It will be converted to a string. A line feed will be appended to the message.
* @return {undefined}
*/
log: (message) => {
output += message + '\n';
},
/**
* Returns the output string.
*
* @return {string} -- The output string, which represents the contents of the console's standard output.
*/
getOutput: () => {
return output;
}
};
})();
/**
* The expected output, as specified in the post.
*
* @type {string}
* @const
*/
const expectedOutput =
`100
81
64
49
36
25
16
9
4
1
`;
// It is assumed that the program is already run by this point.
// Only need to rerun the foreach with testConsole.log to be able to verify the output.
foreach(numbers, testConsole.log);
/**
* The actual output.
*
* @type {string}
* @const
*/
const output = testConsole.getOutput();
// Test the actual output against the expected output.
// Output a message informing whether the test passed.
if (output === expectedOutput) {
console.log('Test passed.');
} else {
console.log('Test failed');
}
@niinpatel
Copy link

Of all the solutions posted on the internet, this one is my favourite. :)

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment