// First we need to build data structure pair(a, b)
// cons: given a and b, and return a function.
// when you pass cons(a, b) as argument to car, it will return a;
// if you pass it to cdr, it will return b.
const cons = (a, b) => p => p ? a : b;
const car = pair => typeof pair === 'function' ? pair(1) : null;
const cdr = pair => typeof pair === 'function' ? pair(0) : null;

// Now we can build list by chaining pair.
// For example, list [1, 2, 3] will be represented as cons(1, cons(2, 3))

// Some helper functions, we only implement some basic functions here,
// and it shall be complete enough to build other list operation functions based on it.
const shift = xs => x => cons(x, xs);
const length = xs => typeof xs === 'function' ? 1 + length(cdr(xs)) : 1;
const get = xs => index => index ? get(cdr(xs))(index - 1) : typeof xs === 'function' ? car(xs) : xs;
const concat = (xs, ys) => cdr(xs) == null ? cons(xs, ys) : cons(car(xs), concat(cdr(xs), ys));

// Demo time!
const list1 = cons(1, cons(2, 3));

length(list1); // 3
get(list1)(0); // 1
get(list1)(1); // 2
get(list1)(2); // 3


const list2 = shift(list1)(0);

length(list2); // 4
get(list2)(0); // 0
get(list2)(1); // 1
get(list2)(2); // 2
get(list2)(3); // 3


const list3 = concat(cons(2, 4), cons(6, 8));

length(list3); // 4
get(list3)(0); // 2
get(list3)(1); // 4
get(list3)(2); // 6
get(list3)(3); // 8