함수형으로 작성한 단일 연결 리스트

linked_list_fp.js

const reduce = (f) => (acc, iter) => {
  if (!iter) acc = (iter = acc[Symbol.iterator]()).next().value;
  for (const a of iter) acc = f(acc, a);
  return acc;
}

const go = (arg, ...fs) => reduce((arg, f) => f(arg))(arg, fs);

const Pair = (left, right) => (destructurePair) => destructurePair(left, right);

const first = (pair) => pair((left, _) => left);

const second = (pair) => pair((_, right) => right);

const Cons = (head, tail) => (destructureNode) => destructureNode(head, tail);

const Nil = (_, destrutureNil) => destrutureNil();

const head = (list) => list !== Nil ? list((head, _) => head) : list;

const toArray = (list) => list((head, tail) => [head].concat(toArray(tail)), () => [])

const append = (val) => (list) => list((head, tail) => Cons(head, append(val)(tail)), () => Cons(val, Nil));

const prepend = (val) => (list) => Cons(val, list);

const shift = (list) => list !== Nil ? Pair(list((head, tail) => head), list((head, tail) => tail, () => Nil)) : () => { throw new Error('Empty List') };

const reverse = (list) => list((head, tail) => append(head)(reverse(tail)), () => Nil);

const get = (index) => (list) => list((head, tail) => index === 0 ? head : get(index - 1)(tail), () => new Error('Out of bound'));

const update = (index, val) => (list) => list((head, tail) => index === 0 ? Cons(val, tail) : Cons(head, update(index - 1, val)(tail)), () => new Error('Out of bound'))

go(
  Nil,
  append(1),
  append(2),
  append(3),
  prepend(4),
  toArray,
  console.log // [4, 1, 2, 3]
);

go(
  Nil,
  append(1),
  append(2),
  append(3),
  reverse,
  shift,
  second,
  toArray,
  arr => console.log(arr) // [2, 1]
);

go(
  Nil,
  prepend(1),
  append(2),
  append(3),
  reverse,
  shift,
  first,
  console.log // 3
);

go(
  Cons(1, Nil),
  append(2),
  append(3),
  update(1, 10),
  get(1),
  console.log // 10
)