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

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

let assert Ok(zipper) = list.go_right(zipper)
let assert Ok(zipper) = list.set(zipper, 99)
let zipper = list.insert_left(zipper, 42)
let assert Ok(zipper) = list.go_right(zipper)
let assert Ok(zipper) = list.delete(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 value from the zipper.

Returns a new zipper with focus moved to the next element, or Error(Nil) if empty.

Examples

from_list([1, 2, 3])
|> delete()
|> to_list
// => [2, 3]

from_list

</>

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

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

Examples

from_list([1, 2, 3]) |> get
// => Ok(1)

get

</>

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

Get the current focus value of the zipper.

Returns Error(Nil) if the zipper is empty.

Examples

from_list([1, 2, 3]) |> get
// => Ok(1)

new() |> get
// => 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

from_list([1, 2, 3])
|> go_right()
|> go_left()
|> get
// => 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

from_list([1, 2, 3])
|> go_right()
|> get
// => 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

from_list([2, 3])
|> insert_left(1)
|> to_list
// => [1, 2, 3]

from_list([2, 3])
|> insert_left(1)
|> get
// => Ok(2)

from_list([])
|> insert_left(42)
|> get
// => 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.

Examples

from_list([1, 2])
|> insert_right(3)
|> to_list
// => [1, 3, 2]

is_empty

</>

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

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

Examples

new() |> is_empty
// => True

from_list([1]) |> is_empty
// => 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

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

from_list([1, 2, 3]) |> go_right() |> is_leftmost
// => 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

from_list([1, 2, 3]) |> go_right() |> go_right() |> is_rightmost
// => True

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

new

</>

pub fn new() -> Zipper(a)

Create a new empty zipper.

Examples

new() |> to_list
// => []

set

</>

pub fn set(
  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

from_list([1, 2, 3])
|> set(99)
|> result.map(to_list)
// => Ok([99, 2, 3])

to_list

</>

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

Convert a zipper back to a regular list.

Examples

from_list([1, 2, 3]) |> to_list
// => [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

from_list([1, 2, 3])
|> update(fn(x) { x * 2 })
|> result.map(to_list)
// => Ok([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

// Update existing value
from_list([1, 2, 3])
|> upsert(fn(Some(x)) { x * 2 })
|> to_list
// => [2, 2, 3]

// Insert when empty
new()
|> upsert(fn(None) { 42 })
|> to_list
// => [42]