Simple JavaScript implementation of cons list with lazy evaluation of map, filter etc.

ll.js

// Basic cons list.
// Elements are defined as functions so we can have lazy sequences.
function cons(x, xs) {
  return {
    head: function() { return x; },
    tail: typeof xs === 'function' ? xs : function() { return xs; }
  };
}

function isEmpty(xs) { return xs === undefined; }

// Reduce (aka foldl) evaluates all the elements.
function reduce(xs, fn, init) {
  return isEmpty(xs) ? init : reduce(xs.tail(), fn, fn(init, xs.head()));
}

// Convenience print implementation. Evaluates everything.
function print(xs) {
  return '[' + reduce(xs, function(acc, x) {
    return acc.concat(typeof x === 'object' ? print(x) : x);
  }, []).join(', ') + ']';
}

// Take - get leftmost n elements of xs.
// Use before evaluating a lazy sequence which may not terminate.
function take(xs, n) {
  if(!isEmpty(xs) && n > 0) return cons(xs.head(), take(xs.tail(), n - 1));
}

// Lazy map - returns a new cons applying the map.
function map(xs, fn) {
  if(!isEmpty(xs)) return cons(
    fn(xs.head()),
    function() { return map(xs.tail(), fn); }
  );
}

// Lazy sequence of natural numbers starting from n.
// An example of a simple lazy seq implementation.
function natural(n) {
  if(typeof n === 'undefined') n = 1;
  return cons(n, function() { return natural(n + 1); });
}

// Lazy sequence - infinite elements of the same value (x).
function repeat(x) {
  return cons(x, function() { return repeat(x); });
}

// Lazily combine two lists by taking an element from each in turn.
function alternate(xs, ys) {
  if(!isEmpty(xs)) {
    return cons(xs.head(), function() { return alternate(ys, xs.tail()); });
  }
}

// Lazily zip two lists into a list of pairs.
function zip(xs, ys) {
  if(!isEmpty(xs)) return cons(
    cons(xs.head(), cons(ys.head())),
    function() { return zip(xs.tail(), ys.tail()); }
  );
}

// Lazy list filter.
function filter(xs, fn) {
  return fn(xs.head()) ?
    cons(xs.head(), function() { return filter(xs.tail(), fn); }) :
    filter(xs.tail(), fn);
}

// Example of filter applied to list of all positive ints.
function odd() {
  return filter(natural(), function(x) { return x % 2 === 1; });
}

// Example of filter applied to list of all positive ints.
function even() {
  return filter(natural(), function(x) { return x % 2 === 0; });
}

// Put it together:
print(take(zip(odd(), even()), 50));
// > '[[1, 2], [3, 4], [5, 6], [7, 8], [9, 10], [11, 12], [13, 14], [15, 16], [17, 18], [19, 20], [21, 22], [23, 24], [25, 26], [27, 28], [29, 30], [31, 32], [33, 34], [35, 36], [37, 38], [39, 40], [41, 42], [43, 44], [45, 46], [47, 48], [49, 50], [51, 52], [53, 54], [55, 56], [57, 58], [59, 60], [61, 62], [63, 64], [65, 66], [67, 68], [69, 70], [71, 72], [73, 74], [75, 76], [77, 78], [79, 80], [81, 82], [83, 84], [85, 86], [87, 88], [89, 90], [91, 92], [93, 94], [95, 96], [97, 98], [99, 100]]'

// Sieve of Eratosthenes
function primes(xs) {
  if (typeof xs === 'undefined') xs = natural(2);
  return cons(
    xs.head(),
    function() {
      return primes(filter(xs.tail(), function(x) {
        return x % xs.head() !== 0;
      }));
    }
  );
}

// Apply a map to the sequence of primes.
// (Nothing is evaluated yet.)
double_primes = map(primes(), function(x) { return x * 2; });
// > { head: [Function], tail: [Function] }

// Evaluate with take, and print.
print(take(double_primes, 50));
// > '[4, 6, 10, 14, 22, 26, 34, 38, 46, 58, 62, 74, 82, 86, 94, 106, 118, 122, 134, 142, 146, 158, 166, 178, 194, 202, 206, 214, 218, 226, 254, 262, 274, 278, 298, 302, 314, 326, 334, 346, 358, 362, 382, 386, 394, 398, 422, 446, 454, 458]'

// Some complements to take:
// Get all but the leftmost elements
function drop(xs, n) {
  return (isEmpty(xs.tail()) || n < 2) ? xs.tail() : drop(xs.tail(), n - 1);
}

// Get a nested list with two elements: the leftmost n elements, and the rest.
function splitAt(xs, n) {
  return cons(take(xs, n), cons(drop(xs, n)));
}

print(splitAt(take(natural(), 30), 10));
// > '[[1, 2, 3, 4, 5, 6, 7, 8, 9, 10], [11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30]]'

// And group:
function group(xs, n) {
  if(!isEmpty(xs)) return cons(
    take(xs, n),
    function() { return group(drop(xs, n), n); }
  );
}

print(group(take(natural(), 100), 3));
// > '[[1, 2, 3], [4, 5, 6], [7, 8, 9], [10, 11, 12], [13, 14, 15], [16, 17, 18], [19, 20, 21], [22, 23, 24], [25, 26, 27], [28, 29, 30], [31, 32, 33], [34, 35, 36], [37, 38, 39], [40, 41, 42], [43, 44, 45], [46, 47, 48], [49, 50, 51], [52, 53, 54], [55, 56, 57], [58, 59, 60], [61, 62, 63], [64, 65, 66], [67, 68, 69], [70, 71, 72], [73, 74, 75], [76, 77, 78], [79, 80, 81], [82, 83, 84], [85, 86, 87], [88, 89, 90], [91, 92, 93], [94, 95, 96], [97, 98, 99], [100]]'

// Or, lazily:
print(take(group(natural(), 4), 50));
// > '[[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12], [13, 14, 15, 16], [17, 18, 19, 20], [21, 22, 23, 24], [25, 26, 27, 28], [29, 30, 31, 32], [33, 34, 35, 36], [37, 38, 39, 40], [41, 42, 43, 44], [45, 46, 47, 48], [49, 50, 51, 52], [53, 54, 55, 56], [57, 58, 59, 60], [61, 62, 63, 64], [65, 66, 67, 68], [69, 70, 71, 72], [73, 74, 75, 76], [77, 78, 79, 80], [81, 82, 83, 84], [85, 86, 87, 88], [89, 90, 91, 92], [93, 94, 95, 96], [97, 98, 99, 100], [101, 102, 103, 104], [105, 106, 107, 108], [109, 110, 111, 112], [113, 114, 115, 116], [117, 118, 119, 120], [121, 122, 123, 124], [125, 126, 127, 128], [129, 130, 131, 132], [133, 134, 135, 136], [137, 138, 139, 140], [141, 142, 143, 144], [145, 146, 147, 148], [149, 150, 151, 152], [153, 154, 155, 156], [157, 158, 159, 160], [161, 162, 163, 164], [165, 166, 167, 168], [169, 170, 171, 172], [173, 174, 175, 176], [177, 178, 179, 180], [181, 182, 183, 184], [185, 186, 187, 188], [189, 190, 191, 192], [193, 194, 195, 196], [197, 198, 199, 200]]'