Skip to content

Latest commit

 

History

History

zipper

Folders and files

NameName
Last commit message
Last commit date

parent directory

..
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

zipper

npm version npm downloads Twitter Follow

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

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

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.03 KB

Dependencies

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