Zipper in JS

zipper.js

const lastIndex = list => (
  list && list.length > 0 ? list.length - 1 : 0);

const isNone = val => val === null || typeof val === 'undefined';

const asList = list => (isNone(list) ? [] : list);

const isEmptyList = list => list && list.length <= 0;

const isLastIndex = (lst, index) => (asList(lst).length - 1) === index;

const append = (list, elem) => (isNone(elem) ?
  list : [...asList(list), elem]);

const dropLast = list => asList(list).slice(0, lastIndex(list));

const excludeRoot = paths => asList(paths).filter(path => path !== 'root');

const clone = obj => JSON.parse(JSON.stringify(obj));

const setPathValue = (obj, paths, newValue) => {
  const newObj = clone(obj);
  paths.reduce((val, key, index) => {
    if (isLastIndex(paths, index)) {
      const node = val;
      node[key] = newValue;
      return node;
    }
    return val[key];
  }, newObj);
  return newObj;
};

const pathValue = (obj, paths) => paths.reduce(
  (val, key) => val[key], obj
);

const createContainer = ContainerClass => (tree, paths) => {
  if (isEmptyList(paths)) {
    return null;
  }
  return new ContainerClass(tree, paths);
};

const createSetter = withContainer => (ctx, paths, value) => {
  const tree = setPathValue(ctx,
    excludeRoot(paths), value);
  return withContainer(tree, paths);
};

class Zipper {
  constructor(tree, paths = ['root']) {
    this.tree = tree;
    this.paths = paths;
  }

  pushFocusNode(path) {
    const paths = append(this.paths, path);
    const nodeVal = pathValue(this.tree, excludeRoot(paths));
    if (isNone(nodeVal)) {
      return nodeVal;
    }
    return this.asZipper(paths);
  }

  up() {
    return this.asZipper(dropLast(this.paths));
  }

  left() {
    return this.pushFocusNode('left');
  }

  right() {
    return this.pushFocusNode('right');
  }

  value() {
    return pathValue(this.tree,
      excludeRoot(append(this.paths, 'value'))
    );
  }

  delete() {
    return Zipper.setAttribute(this.tree, this.paths, undefined);
  }

  setValue(value) {
    return Zipper.setAttribute(
      this.tree,
      append(this.paths, 'value'),
      value
    );
  }

  setLeft(value) {
    return Zipper.setAttribute(
      this.tree,
      append(this.paths, 'left'),
      value
    );
  }

  setRight(value) {
    return Zipper.setAttribute(
      this.tree,
      append(this.paths, 'right'),
      value
    );
  }

  asZipper(paths) {
    return Zipper.asZipper(this.tree, paths);
  }

  toTree() {
    return this.tree;
  }
}
Zipper.asZipper = createContainer(Zipper);
Zipper.setAttribute = createSetter(Zipper.asZipper);
Zipper.fromTree = t => new Zipper(t);

export default Zipper;

zipper.spec.js

import Zipper from './zipper';

// tests adapted from `problem-specifications/zipper/canonical-data.json` @ v1.0.0

function bt(value, left, right) {
  return {
    value,
    left,
    right,
  };
}

function leaf(value) {
  return bt(value, null, null);
}

describe('Zipper', () => {
  const t1 = bt(1, bt(2, null, leaf(3)), leaf(4));
  const t2 = bt(1, bt(5, null, leaf(3)), leaf(4));
  const t3 = bt(1, bt(2, leaf(5), leaf(3)), leaf(4));
  const t4 = bt(1, leaf(2), leaf(4));
  const t5 = bt(1, bt(2, null, leaf(3)), bt(6, leaf(7), leaf(8)));
  const t6 = bt(1, bt(2, null, leaf(5)), leaf(4));
  const t7 = bt(1, bt(2, null, leaf(3)));

  let zipper;

  beforeEach(() => {
    zipper = Zipper.fromTree(t1);
  });

  test('data is retained', () => {
    expect(zipper.toTree(t1)).toEqual(t1);
  });

  test('left, right and value', () => {
    expect(zipper.left().right().value()).toEqual(3);
  });

  test('dead end', () => {
    expect(zipper.left().left()).toBe(null);
  });

  test('tree from deep focus', () => {
    expect(zipper.left().right().toTree()).toEqual(t1);
  });

  test('traversing up from top', () => {
    expect(zipper.up()).toEqual(null);
  });

  test('left, right and up', () => {
    expect(zipper.left().up().right().up().left().right().value()).toEqual(3);
  });

  test('setValue', () => {
    expect(zipper.left().setValue(5).toTree()).toEqual(t2);
  });

  test('setValue after traversing up', () => {
    expect(zipper.left().right().up().setValue(5).toTree()).toEqual(t2);
  });

  test('setLeft with leaf', () => {
    expect(zipper.left().setLeft(leaf(5)).toTree()).toEqual(t3);
  });

  test('setRight with null', () => {
    expect(zipper.left().setRight(null).toTree()).toEqual(t4);
  });

  test('setRight with subtree', () => {
    expect(zipper.setRight(bt(6, leaf(7), leaf(8))).toTree()).toEqual(t5);
  });

  test('setValue on deep focus', () => {
    expect(zipper.left().right().setValue(5).toTree()).toEqual(t6);
  });

  test('delete on deep focus', () => {
    expect(zipper.right().delete().toTree()).toEqual(t7);
  });
});

Zipper

Creating a zipper for a binary tree.

Zippers are
a purely functional way of navigating within a data structure and
manipulating it. They essentially contain a data structure and a
pointer into that data structure (called the focus).

For example given a rose tree (where each node contains a value and a
list of child nodes) a zipper might support these operations:

• from_tree (get a zipper out of a rose tree, the focus is on the root node)
• to_tree (get the rose tree out of the zipper)
• value (get the value of the focus node)
• prev (move the focus to the previous child of the same parent,
  returns a new zipper)
• next (move the focus to the next child of the same parent, returns a
  new zipper)
• up (move the focus to the parent, returns a new zipper)
• set_value (set the value of the focus node, returns a new zipper)
• insert_before (insert a new subtree before the focus node, it
  becomes the prev of the focus node, returns a new zipper)
• insert_after (insert a new subtree after the focus node, it becomes
  the next of the focus node, returns a new zipper)
• delete (removes the focus node and all subtrees, focus moves to the
  next node if possible otherwise to the prev node if possible,
  otherwise to the parent node, returns a new zipper)