zipper/list

A functional zipper data structure for efficient list navigation and manipulation.

Provides $O(1)$ operations for insertion, deletion, and updates at the current focus position, with efficient bidirectional navigation. And Provides $O(n)$ operations for converting between lists and zippers, where $n$ is the number of elements in the zipper.

Usage

import zipper/list as zipper_list

let zipper = zipper_list.from_list([1, 2, 3, 4])

let assert Ok(zipper) = zipper_list.go_right(zipper)
let assert Ok(zipper) = zipper_list.set_value(zipper, 99)
let zipper = zipper_list.insert_left(zipper, 42)
let assert Ok(zipper) = zipper_list.go_right(zipper)
let assert Ok(zipper) = zipper_list.delete(zipper)

zipper_list.to_list(zipper)
// => [1, 42, 99, 4]

Types

Zipper

opaque </>

A zipper for navigating and manipulating lists.

Conceptually, a Zipper represents a specific position within a list, effectively partitioning it. It keeps track of the elements that have been traversed (to the left of the “cursor”) and the elements that are yet to be seen (at and to the right of the “cursor”).

This structure allows for efficient navigation and modification at any point in the list.

pub opaque type Zipper(a)

Values

delete

</>

pub fn delete(zipper: Zipper(a)) -> Result(Zipper(a), Nil)

Delete the current focus element from the zipper.

The focus moves to the right element if it exists, otherwise to the left element.

Returns Ok(zipper) with the focus moved to the new location. Returns Error(Nil) if the zipper is empty or contains only one element.

This operation is prevented when the zipper has only one element to ensure the zipper never becomes empty without a focus.

Examples

// Successful deletion with multiple elements
let zipper = from_list([1, 2, 3])
let assert Ok(zipper) = delete(zipper)
to_list(zipper)
// => [2, 3]

// Error when trying to delete the only element
let single = from_list([42])
delete(single)
// => Error(Nil)

from_list

</>

pub fn from_list(list: List(a)) -> Zipper(a)

Create a zipper from a list, with focus on the first element.

Examples

let zipper = from_list([1, 2, 3])
get_value(zipper)
// => Ok(1)

get

</>

pub fn get(zipper: Zipper(a)) -> Result(a, Nil)

Deprecated: Use `get_value` instead

Get the current focus value of the zipper.

Deprecated: Use get_value instead.

Returns Error(Nil) if the zipper is empty.

Examples

let zipper = from_list([1, 2, 3])
get_value(zipper)
// => Ok(1)

let empty = new()
get_value(empty)
// => Error(Nil)

get_value

</>

pub fn get_value(zipper: Zipper(a)) -> Result(a, Nil)

Get the current focus value of the zipper.

Returns Error(Nil) if the zipper is empty.

Examples

let zipper = from_list([1, 2, 3])
get_value(zipper)
// => Ok(1)

let empty = new()
get_value(empty)
// => Error(Nil)

go_left

</>

pub fn go_left(zipper: Zipper(a)) -> Result(Zipper(a), Nil)

Move the focus one position to the left.

Returns a new zipper with focus moved left, or Error(Nil) if already at leftmost.

Examples

let zipper = from_list([1, 2, 3])
let assert Ok(moved) = go_right(zipper)
let assert Ok(returned) = go_left(moved)
get_value(returned)
// => Ok(1)

go_right

</>

pub fn go_right(zipper: Zipper(a)) -> Result(Zipper(a), Nil)

Move the focus one position to the right.

Returns a new zipper with focus moved right, or Error(Nil) if already at rightmost.

Examples

let zipper = from_list([1, 2, 3])
let assert Ok(moved) = go_right(zipper)
get_value(moved)
// => Ok(2)

insert_left

</>

pub fn insert_left(zipper: Zipper(a), value: a) -> Zipper(a)

Insert a new value to the left of the current focus value.

If the zipper is empty, the new value becomes the focus. If the zipper is not empty, the new value is inserted before the current focus value.

Examples

let zipper =
  from_list([2, 3])
  |> insert_left(1)
to_list(zipper)
// => [1, 2, 3]
get_value(zipper)
// => Ok(2)

let empty = from_list([])
let zipper = insert_left(empty, 42)
get_value(zipper)
// => Ok(42)

insert_right

</>

pub fn insert_right(zipper: Zipper(a), value: a) -> Zipper(a)

Insert a new value to the right of the current focus value. If the original zipper is empty, the new value becomes the focus; otherwise, the original focus remains unchanged.

Examples

let zipper = from_list([1, 2])
let zipper = insert_right(zipper, 3)
to_list(zipper)
// => [1, 3, 2]
get_value(zipper)
// => Ok(1)

is_empty

</>

pub fn is_empty(zipper: Zipper(a)) -> Bool

Check if the zipper is empty (contains no elements).

Examples

let empty = new()
is_empty(empty)
// => True

let zipper = from_list([1])
is_empty(zipper)
// => False

is_leftmost

</>

pub fn is_leftmost(zipper: Zipper(a)) -> Bool

Check if the current focus is the leftmost element in the zipper list.

Returns True if there are no elements to the left of the current focus.

Examples

let zipper = from_list([1, 2, 3])
is_leftmost(zipper)
// => True

let zipper = from_list([1, 2, 3])
let assert Ok(moved) = go_right(zipper)
is_leftmost(moved)
// => False

is_rightmost

</>

pub fn is_rightmost(zipper: Zipper(a)) -> Bool

Check if the current focus is the rightmost element in the zipper list.

Returns True if there are no elements to the right of the current focus.

Examples

let zipper = from_list([1, 2, 3])
is_rightmost(zipper)
// => False

let zipper = from_list([1, 2, 3])
let assert Ok(moved) = go_right(zipper)
let assert Ok(rightmost) = go_right(moved)
is_rightmost(rightmost)
// => True

new

</>

pub fn new() -> Zipper(a)

Create a new empty zipper.

Examples

let empty = new()
to_list(empty)
// => []

set

</>

pub fn set(
  zipper: Zipper(a),
  new_value: a,
) -> Result(Zipper(a), Nil)

Deprecated: Use `set_value` instead

Set the current focus value of the zipper list.

Deprecated: Use set_value instead.

Returns the previous value if successful, or Error(Nil) if the zipper is empty.

Examples

let zipper = from_list([1, 2, 3])
let assert Ok(updated) = set_value(zipper, 99)
to_list(updated)
// => [99, 2, 3]

set_value

</>

pub fn set_value(
  zipper: Zipper(a),
  new_value: a,
) -> Result(Zipper(a), Nil)

Set the current focus value of the zipper list.

Returns the previous value if successful, or Error(Nil) if the zipper is empty.

Examples

let zipper = from_list([1, 2, 3])
let assert Ok(updated) = set_value(zipper, 99)
to_list(updated)
// => [99, 2, 3]

to_list

</>

pub fn to_list(zipper: Zipper(a)) -> List(a)

Convert a zipper back to a regular list.

Examples

let zipper = from_list([1, 2, 3])
to_list(zipper)
// => [1, 2, 3]

update

</>

pub fn update(
  zipper: Zipper(a),
  updater: fn(a) -> a,
) -> Result(Zipper(a), Nil)

Update the current focus value of the zipper list using a transformation function.

Returns the previous value if successful, or Error(Nil) if the zipper is empty.

Examples

let zipper = from_list([1, 2, 3])
let assert Ok(updated) = update(zipper, fn(x) { x * 2 })
to_list(updated)
// => [2, 2, 3]

upsert

</>

pub fn upsert(
  zipper: Zipper(a),
  updater: fn(option.Option(a)) -> a,
) -> Zipper(a)

Update or insert a value at the current focus position.

If the zipper is empty, inserts a new value. If the zipper has a focus, updates the current value using the transformation function.

The updater function receives the current focus value as Some(value) if present, or None if the zipper is empty.

Examples

let transform = fn(x) {
  case x {
    Some(value) -> value * 2
    None -> 42
  }
}

// Update existing value
let zipper = from_list([1, 2, 3])
let zipper = upsert(zipper, transform)
to_list(zipper)
// => [2, 2, 3]

// Insert when empty
let empty = new()
let zipper = upsert(empty, transform)
to_list(zipper)
// => [42]