@thi.ng/zipper v2.1.100

This project is part of the @thi.ng/umbrella monorepo.

• About
  • Status
  • Related packages
  • Blog posts
• Installation
• Dependencies
• API
• Benchmark
• Authors
• License

About

Functional tree editing, manipulation & navigation.

Immutable, semi-functional, structural tree editing, manipulation & navigation, based on my fork and optimizations to fast-zip, which in turn is based on clojure.zip and which itself is based on the original data structure invented by Gérard Huet in 1997.

Reference: https://en.wikipedia.org/wiki/Zipper_(data_structure)

Status

STABLE - used in production

Search or submit any issues for this package

Related packages

• @thi.ng/gp - Genetic programming helpers & strategies (tree based & multi-expression programming)

Blog posts

• Evolutionary failures (Part 1)

Installation

yarn add @thi.ng/zipper

ES module import:

<script type="module" src="https://cdn.skypack.dev/@thi.ng/zipper"></script>

Skypack documentation

For Node.js REPL:

# with flag only for < v16
node --experimental-repl-await

> const zipper = await import("@thi.ng/zipper");

Package sizes (gzipped, pre-treeshake): ESM: 1.02 KB

Dependencies

• @thi.ng/api
• @thi.ng/arrays
• @thi.ng/checks
• @thi.ng/errors

API

Generated API docs

import { arrayZipper } from "@thi.ng/zipper";

const x = [1, [5, 4, 3, 2], 6];

// create zipper for given array
const a = arrayZipper(x);

// .next navigates to logically next location (depth-first)
// .node retrieves a location's value
a.next.node
// 1

a.next.next.node
// [5, 4, 3, 2]

// all navigation verbs:
// prev, left, right, up, down, leftmost, rightmost
a.next.next.down.rightmost.node
// 2

// navigate to value `3`, remove it
// then append `7` at top level
// and apply changes by requesting root value
// (the latter is the actual zip operation)
a.next.next.down.rightmost.left.remove().up.up.appendChild(7).root
// [ 1, [ 5, 4, 2 ], 6, 7 ]

// the same edits in different order
a.appendChild(7).next.next.down.rightmost.left.remove().root
// [ 1, [ 5, 4, 2 ], 6, 7 ]

// insert child at the front
a.next.next.insertChild(10).root
// [ 1, [ 10, 5, 4, 3, 2 ], 6 ]

// replace the nested array
a.next.next.replace(10).root
// [1, 10, 6]

// all editing is immutable, original is untouched...
x
// [ 1, [ 5, 4, 3, 2 ], 6 ]

Benchmark

For better comparison, the included benchmarks are also ported from the fast-zip package and measure traversal & editing of a tree of 10 x 10 x 10 values.

Measurements for MBP 2015 2.8GHz, 16GB, node v12.10.0:

$ node bench/index.js

walk:
warmup... 2562ms
warmup... 2469ms
warmup... 2460ms
total: 2476ms, mean: 0.2476ms, runs: 10000

edit:
warmup... 4660ms
warmup... 4573ms
warmup... 4566ms
total: 4616ms, mean: 0.4616ms, runs: 10000

Authors

Karsten Schmidt

If this project contributes to an academic publication, please cite it as:

@misc{thing-zipper,
  title = "@thi.ng/zipper",
  author = "Karsten Schmidt",
  note = "https://thi.ng/zipper",
  year = 2015
}

License

© 2015 - 2021 Karsten Schmidt // Apache Software License 2.0