Functional Linked Lists in JavaScript

Given the function list:

function list(head, tailF) {
  return [head, tailF];
}

and given the functions odds and evens:

var odds  = odds();  // 1 -> 3 -> 5 -> 7 -> ...
var evens = evens(); // 2 -> 4 -> 6 -> 8 -> ...

Write the function combine, which returns in constant time:

var ints = combine(odds, evens); // 1 -> 2 -> 3 -> 4 -> ...

Solution

Here is one possible solution.

function combine(xs, ys) {
  return list(xs[0], function() { return combine(ys, xs[1]()); });
}

Demo

function byTwos(x) {
  return list(x, function() { return byTwos(x + 2); });
}

function odds() {
  return byTwos(1);
}

function evens() {
  return byTwos(2);
}

function take(x, xs) {
  if (x == 0) {
    return [];
  } else {
    return list(xs[0], function() { return take(x - 1, xs[1]()) });
  }
}

function show(list) {
  if (list.length == 0) {
    return '[]';
  } else {
    return list[0] + ' : ' + show(list[1]());
  }
}

console.log(show(take(12, ints)));

This file is literate JavaScript, and can be run using Codedown:

$ curl https://earldouglas.com/posts/exercises/javascript-lists.md |
  codedown javascript |
  node
1 : 2 : 3 : 4 : 5 : 6 : 7 : 8 : 9 : 10 : 11 : 12 : []