Skip to content

List[A: A]

[Source]

A doubly linked list.

The following is paraphrased from Wikipedia.

A doubly linked list is a linked data structure that consists of a set of sequentially linked records called nodes (implemented in Pony via the collections.ListNode class). Each node contains four fields: two link fields (references to the previous and to the next node in the sequence of nodes), one data field, and the reference to the List in which it resides. A doubly linked list can be conceptualized as two singly linked lists formed from the same data items, but in opposite sequential orders.

As you would expect. functions are provided to perform all the common list operations such as creation, traversal, node addition and removal, iteration, mapping, filtering, etc.

Example program

There are a lot of functions in List. The following code picks out a few common examples.

It outputs:

A new empty list has 0 nodes.
Adding one node to our empty list means it now has a size of 1.
The first (index 0) node has the value: A single String
A list created by appending our second single-node list onto our first has size: 2
The List nodes of our first list are now:
  A single String
  Another String
Append *moves* the nodes from the second list so that now has 0 nodes.
A list created from an array of three strings has size: 3
  First
  Second
  Third
Mapping over our three-node list produces a new list of size: 3
Each node-value in the resulting list is now far more exciting:
  First BOOM!
  Second BOOM!
  Third BOOM!
Filtering our three-node list produces a new list of size: 2
  Second BOOM!
  Third BOOM!
The size of our first partitioned list (matches predicate): 1
The size of our second partitioned list (doesn't match predicate): 1
Our matching partition elements are:
  Second BOOM!
  use "collections"

  actor Main
    new create(env:Env) =>

      // Create a new empty List of type String
      let my_list = List[String]()

      env.out.print("A new empty list has " + my_list.size().string() + " nodes.") // 0

      // Push a String literal onto our empty List
      my_list.push("A single String")
      env.out.print("Adding one node to our empty list means it now has a size of "
                    + my_list.size().string() + ".") // 1

      // Get the first element of our List
      try env.out.print("The first (index 0) node has the value: "
                        + my_list.index(0)?()?.string()) end // A single String

      // Create a second List from a single String literal
      let my_second_list = List[String].unit("Another String")

      // Append the second List to the first
      my_list.append_list(my_second_list)
      env.out.print("A list created by appending our second single-node list onto our first has size: "
                    + my_list.size().string()) // 2
      env.out.print("The List nodes of our first list are now:")
      for n in my_list.values() do
        env.out.print("\t" + n.string())
      end
      // NOTE: this _moves_ the elements so second_list consequently ends up empty
      env.out.print("Append *moves* the nodes from the second list so that now has "
                    + my_second_list.size().string() + " nodes.") // 0

      // Create a third List from a Seq(ence)
      // (In this case a literal array of Strings)
      let my_third_list = List[String].from(["First"; "Second"; "Third"])
      env.out.print("A list created from an array of three strings has size: "
                    + my_third_list.size().string()) // 3
      for n in my_third_list.values() do
        env.out.print("\t" + n.string())
      end

      // Map over the third List, concatenating some "BOOM!'s" into a new List
      let new_list = my_third_list.map[String]({ (n) => n + " BOOM!" })
      env.out.print("Mapping over our three-node list produces a new list of size: "
                    + new_list.size().string()) // 3
      env.out.print("Each node-value in the resulting list is now far more exciting:")
      for n in new_list.values() do
        env.out.print("\t" + n.string())
      end

      // Filter the new list to extract 2 elements
      let filtered_list = new_list.filter({ (n) => n.string().contains("d BOOM!") })
      env.out.print("Filtering our three-node list produces a new list of size: "
                        + filtered_list.size().string()) // 2
      for n in filtered_list.values() do
        env.out.print("\t" + n.string()) // Second BOOM!\nThird BOOM!
      end

      // Partition the filtered list
      let partitioned_lists = filtered_list.partition({ (n) => n.string().contains("Second") })
      env.out.print("The size of our first partitioned list (matches predicate): " + partitioned_lists._1.size().string())        // 1
      env.out.print("The size of our second partitioned list (doesn't match predicate): " + partitioned_lists._2.size().string())  // 1
      env.out.print("Our matching partition elements are:")
      for n in partitioned_lists._1.values() do
        env.out.print("\t" + n.string()) // Second BOOM!
      end
class ref List[A: A] is
  Seq[A] ref

Implements


Constructors

create

[Source]

Always creates an empty list with 0 nodes, len is ignored.

Required method for List to satisfy the Seq interface.

let my_list = List[String]
new ref create(
  len: USize val = 0)
: List[A] ref^

Parameters

Returns


unit

[Source]

Creates a list with 1 node of element.

let my_list = List[String].unit("element")
new ref unit(
  a: A)
: List[A] ref^

Parameters

  • a: A

Returns


from

[Source]

Creates a list equivalent to the provided Array (both node number and order are preserved).

let my_list = List[String].from(["a"; "b"; "c"])
new ref from(
  seq: Array[A^] ref)
: List[A] ref^

Parameters

Returns


Public Functions

reserve

[Source]

Do nothing

Required method for List to satisfy the Seq interface.

fun ref reserve(
  len: USize val)
: None val

Parameters

Returns


size

[Source]

Returns the number of items in the list.

let my_list = List[String].from(["a"; "b"; "c"])
my_list.size() // 3
fun box size()
: USize val

Returns


apply

[Source]

Get the i-th element, raising an error if the index is out of bounds.

let my_list = List[String].from(["a"; "b"; "c"])
try my_list.apply(1)? end // "b"
fun box apply(
  i: USize val = 0)
: this->A ?

Parameters

Returns

  • this->A ?

update

[Source]

Change the i-th element, raising an error if the index is out of bounds, and returning the previous value.

let my_list = List[String].from(["a"; "b"; "c"])
try my_list.update(1, "z")? end // Returns "b" and List now contains ["a"; "z"; "c"]
fun ref update(
  i: USize val,
  value: A)
: A^ ?

Parameters

Returns

  • A^ ?

index

[Source]

Gets the i-th node, raising an error if the index is out of bounds.

let my_list = List[String].from(["a"; "b"; "c"])
try my_list.index(0)? end // Returns a ListNode[String] containing "a"
fun box index(
  i: USize val)
: this->ListNode[A] ref ?

Parameters

Returns


remove

[Source]

Remove the i-th node, raising an error if the index is out of bounds, and returning the removed node.

let my_list = List[String].from(["a"; "b"; "c"])
try my_list.remove(0)? end // Returns a ListNode[String] containing "a" and List now contains ["b"; "c"]
fun ref remove(
  i: USize val)
: ListNode[A] ref ?

Parameters

Returns


clear

[Source]

Empties the list.

fun ref clear()
: None val

Returns


[Source]

Show the head of the list, raising an error if the head is empty.

let my_list = List[String].from(["a"; "b"; "c"])
try my_list.head()? end // Returns a ListNode[String] containing "a"
fun box head()
: this->ListNode[A] ref ?

Returns


tail

[Source]

Show the tail of the list, raising an error if the tail is empty.

let my_list = List[String].from(["a"; "b"; "c"])
try my_list.tail()? end // Returns a ListNode[String] containing "c"
fun box tail()
: this->ListNode[A] ref ?

Returns


prepend_node

[Source]

Adds a node to the head of the list.

let my_list = List[String].from(["a"; "b"; "c"])
let new_head = ListNode[String]("0")
my_list.prepend_node(new_head) // ["0", "a"; "b"; "c"]
fun ref prepend_node(
  node: ListNode[A] ref)
: None val

Parameters

Returns


append_node

[Source]

Adds a node to the tail of the list.

let my_list = List[String].from(["a"; "b"; "c"])
let new_tail = ListNode[String]("0")
my_list.append_node(new_head) // ["a"; "b"; "c", "0"]
fun ref append_node(
  node: ListNode[A] ref)
: None val

Parameters

Returns


append_list

[Source]

Empties the provided List by appending all elements onto the receiving List.

let my_list = List[String].from(["a"; "b"; "c"])
let other_list = List[String].from(["d"; "e"; "f"])
my_list.append_list(other_list)  // my_list is ["a"; "b"; "c"; "d"; "e"; "f"], other_list is empty
fun ref append_list(
  that: List[A] ref)
: None val

Parameters

Returns


prepend_list

[Source]

Empties the provided List by prepending all elements onto the receiving List.

let my_list = List[String].from(["a"; "b"; "c"])
let other_list = List[String].from(["d"; "e"; "f"])
my_list.prepend_list(other_list)  // my_list is ["d"; "e"; "f"; "a"; "b"; "c"], other_list is empty
fun ref prepend_list(
  that: List[A] ref)
: None val

Parameters

Returns


push

[Source]

Adds a new tail value.

let my_list = List[String].from(["a"; "b"; "c"])
my_list.push("d")  // my_list is ["a"; "b"; "c"; "d"]
fun ref push(
  a: A)
: None val

Parameters

  • a: A

Returns


pop

[Source]

Removes the tail value, raising an error if the tail is empty.

let my_list = List[String].from(["a"; "b"; "c"])
try my_list.pop() end  // Returns "c" and my_list is ["a"; "b"]
fun ref pop()
: A^ ?

Returns

  • A^ ?

unshift

[Source]

Adds a new head value.

let my_list = List[String].from(["a"; "b"; "c"])
my_list.unshift("d")  // my_list is ["d"; "a"; "b"; "c"]
fun ref unshift(
  a: A)
: None val

Parameters

  • a: A

Returns


shift

[Source]

Removes the head value, raising an error if the head is empty.

let my_list = List[String].from(["a"; "b"; "c"])
try my_list.shift() end  // Returns "a" and my_list is ["b"; "c"]
fun ref shift()
: A^ ?

Returns

  • A^ ?

append

[Source]

Append len elements from a sequence, starting from the given offset.

When len is -1, all elements of sequence are pushed.

Does not remove elements from sequence.

let my_list = List[String].from(["a"; "b"; "c"])
let other_list = List[String].from(["d"; "e"; "f"])
my_list.append(other_list)  // my_list is ["a"; "b"; "c"; "d"; "e"; "f"], other_list is unchanged
fun ref append(
  seq: (ReadSeq[A] box & ReadElement[A^] box),
  offset: USize val = 0,
  len: USize val = call)
: None val

Parameters

Returns


concat

[Source]

Add len iterated elements to the tail of the list, starting from the given offset.

When len is -1, all elements of iterator are pushed.

Does not remove elements from iterator.

let my_list = List[String].from(["a"; "b"; "c"])
let other_list = List[String].from(["d"; "e"; "f"])
my_list.concat(other_list.values())  // my_list is ["a"; "b"; "c"; "d"; "e"; "f"], other_list is unchanged
fun ref concat(
  iter: Iterator[A^] ref,
  offset: USize val = 0,
  len: USize val = call)
: None val

Parameters

Returns


truncate

[Source]

Pop tail elements until the list is len size. If the list is already smaller than len, do nothing.

let my_list = List[String].from(["a"; "b"; "c"])
my_list.truncate(1)  // my_list is ["a"]
fun ref truncate(
  len: USize val)
: None val

Parameters

Returns


clone

[Source]

Clone all elements into a new List.

Note: elements are not copied, an additional reference to each element is created in the new List.

let my_list = List[String].from(["a"; "b"; "c"])
let other_list = my_list.clone()  // my_list is ["a"; "b"; "c"], other_list is ["a"; "b"; "c"]
fun box clone()
: List[this->A!] ref^

Returns

  • List[this->A!] ref^

map[B: B]

[Source]

Builds a new List by applying a function to every element of the List.

let my_list = List[String].from(["a"; "b"; "c"])
let other_list = my_list.map[String]( {(s: String): String => "m: " + s } )  // other_list is ["m: a"; "m: b"; "m: c"]
fun box map[B: B](
  f: {(this->A!): B^}[A, B] box)
: List[B] ref^

Parameters

  • f: {(this->A!): B^}[A, B] box

Returns


flat_map[B: B]

[Source]

Builds a new List by applying a function to every element of the List, producing a new List for each element, then flattened into a single List.

let my_list = List[String].from(["a"; "b"; "c"])
let other_list = my_list.flat_map[String]( {(s: String): List[String] => List[String].from( ["m"; s] )} )  // other_list is ["m"; "a"; "m"; "b"; "m"; c"]
fun box flat_map[B: B](
  f: {(this->A!): List[B]}[A, B] box)
: List[B] ref^

Parameters

  • f: {(this->A!): List[B]}[A, B] box

Returns


filter

[Source]

Builds a new List with those elements that satisfy the predicate.

let my_list = List[String].from(["a"; "b"; "c"])
let other_list = my_list.filter( {(s: String): Bool => s == "b" } )  // other_list is ["b"]
fun box filter(
  f: {(this->A!): Bool}[A] box)
: List[this->A!] ref^

Parameters

  • f: {(this->A!): Bool}[A] box

Returns

  • List[this->A!] ref^

fold[B: B]

[Source]

Folds the elements of the List using the supplied function.

On the first iteration, the B argument in f is the value acc, on the second iteration B is the result of the first iteration, on the third iteration B is the result of the second iteration, and so on.

let my_list = List[String].from(["a"; "b"; "c"])
let folded = my_list.fold[String]( {(str: String, s: String): String => str + s }, "z")  // "zabc"
fun box fold[B: B](
  f: {(B!, this->A!): B^}[A, B] box,
  acc: B)
: B

Parameters

  • f: {(B!, this->A!): B^}[A, B] box
  • acc: B

Returns

  • B

every

[Source]

Returns true if every element satisfies the predicate, otherwise returns false.

let my_list = List[String].from(["a"; "b"; "c"])
let all_z = my_list.every( {(s: String): Bool => s == "z"} ) // false
fun box every(
  f: {(this->A!): Bool}[A] box)
: Bool val

Parameters

  • f: {(this->A!): Bool}[A] box

Returns


exists

[Source]

Returns true if at least one element satisfies the predicate, otherwise returns false.

let my_list = List[String].from(["a"; "b"; "c"])
let b_exists = my_list.exists( {(s: String): Bool => s == "b"} ) // true
fun box exists(
  f: {(this->A!): Bool}[A] box)
: Bool val

Parameters

  • f: {(this->A!): Bool}[A] box

Returns


partition

[Source]

Builds a pair of Lists, the first of which is made up of the elements satisfying the predicate and the second of which is made up of those that do not.

let my_list = List[String].from(["a"; "b"; "c"])
(let lt_b, let gt_b) = my_list.partition( {(s: String): Bool => s < "b"} )  // lt_b is ["a"], while gt_b is ["b"; "c"]
fun box partition(
  f: {(this->A!): Bool}[A] box)
: (List[this->A!] ref^ , List[this->A!] ref^)

Parameters

  • f: {(this->A!): Bool}[A] box

Returns

  • (List[this->A!] ref^ , List[this->A!] ref^)

drop

[Source]

Builds a List by dropping the first n elements.

let my_list = List[String].from(["a"; "b"; "c"])
let other_list = my_list.drop(1)  // ["b"; "c"]
fun box drop(
  n: USize val)
: List[this->A!] ref^

Parameters

Returns

  • List[this->A!] ref^

take

[Source]

Builds a List by keeping the first n elements.

let my_list = List[String].from(["a"; "b"; "c"])
let other_list = my_list.drop(1)  // ["a"]
fun box take(
  n: USize val)
: List[this->A!] ref

Parameters

Returns

  • List[this->A!] ref

take_while

[Source]

Builds a List of elements satisfying the predicate, stopping at the first false return.

let my_list = List[String].from(["a"; "b"; "c"])
let other_list = my_list.take_while( {(s: String): Bool => s < "b"} )  // ["a"]
fun box take_while(
  f: {(this->A!): Bool}[A] box)
: List[this->A!] ref^

Parameters

  • f: {(this->A!): Bool}[A] box

Returns

  • List[this->A!] ref^

reverse

[Source]

Builds a new List by reversing the elements in the List.

let my_list = List[String].from(["a"; "b"; "c"])
let other_list = my_list.reverse() // ["c"; "b"; "a"]
fun box reverse()
: List[this->A!] ref^

Returns

  • List[this->A!] ref^

contains[optional B: (A & HasEq[A!] #read)]

[Source]

Returns true if the List contains the provided element, otherwise returns false.

let my_list = List[String].from(["a"; "b"; "c"])
let contains_b = my_list.contains[String]("b") // true
fun box contains[optional B: (A & HasEq[A!] #read)](
  a: box->B)
: Bool val

Parameters

  • a: box->B

Returns


nodes

[Source]

Return an iterator on the nodes in the List in forward order.

let my_list = List[String].from(["a"; "b"; "c"])
let nodes = my_list.nodes()  // node with "a" is before node with "c"
fun box nodes()
: ListNodes[A, this->ListNode[A] ref] ref^

Returns


rnodes

[Source]

Return an iterator on the nodes in the List in reverse order.

let my_list = List[String].from(["a"; "b"; "c"])
let rnodes = my_list.rnodes()  // node with "c" is before node with "a"
fun box rnodes()
: ListNodes[A, this->ListNode[A] ref] ref^

Returns


values

[Source]

Return an iterator on the values in the List in forward order.

let my_list = List[String].from(["a"; "b"; "c"])
let values = my_list.values()  // value "a" is before value "c"
fun box values()
: ListValues[A, this->ListNode[A] ref] ref^

Returns


rvalues

[Source]

Return an iterator on the values in the List in reverse order.

let my_list = List[String].from(["a"; "b"; "c"])
let rvalues = my_list.rvalues()  // value "c" is before value "a"
fun box rvalues()
: ListValues[A, this->ListNode[A] ref] ref^

Returns