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 Ponylang 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 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

• Seq[A] ref

Constructors

create

[Source]

Do nothing, but be compatible with Seq.

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

Parameters

• len: USize val = 0

Returns

• List[A] ref^

unit

[Source]

Builds a new list from an element.

new ref unit(
  a: A)
: List[A] ref^

Parameters

• a: A

Returns

• List[A] ref^

from

[Source]

Builds a new list from the sequence passed in.

new ref from(
  seq: Array[A^] ref)
: List[A] ref^

Parameters

• seq: Array[A^] ref

Returns

• List[A] ref^

Public Functions

reserve

[Source]

Do nothing, but be compatible with Seq.

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

Parameters

• len: USize val

Returns

• None val

size

[Source]

Returns the number of items in the list.

fun box size()
: USize val

Returns

• USize val

apply

[Source]

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

fun box apply(
  i: USize val = 0)
: this->A ?

Parameters

• i: USize val = 0

Returns

• this->A ?

update

[Source]

Change the i-th element, raising an error if the index is out of bounds. Returns the previous value, which may be None if the node has been popped but left on the list.

fun ref update(
  i: USize val,
  value: A)
: A^ ?

Parameters

• i: USize val
• value: A

Returns

• A^ ?

index

[Source]

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

fun box index(
  i: USize val)
: this->ListNode[A] ref ?

Parameters

• i: USize val

Returns

• this->ListNode[A] ref ?

remove

[Source]

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

fun ref remove(
  i: USize val)
: ListNode[A] ref ?

Parameters

• i: USize val

Returns

• ListNode[A] ref ?

clear

[Source]

Empties the list.

fun ref clear()
: None val

Returns

• None val

head

[Source]

Get the head of the list.

fun box head()
: this->ListNode[A] ref ?

Returns

• this->ListNode[A] ref ?

tail

[Source]

Get the tail of the list.

fun box tail()
: this->ListNode[A] ref ?

Returns

• this->ListNode[A] ref ?

prepend_node

[Source]

Adds a node to the head of the list.

fun ref prepend_node(
  node: ListNode[A] ref)
: None val

Parameters

• node: ListNode[A] ref

Returns

• None val

append_node

[Source]

Adds a node to the tail of the list.

fun ref append_node(
  node: ListNode[A] ref)
: None val

Parameters

• node: ListNode[A] ref

Returns

• None val

append_list

[Source]

Remove all nodes from that and append them to this.

fun ref append_list(
  that: List[A] ref)
: None val

Parameters

• that: List[A] ref

Returns

• None val

prepend_list

[Source]

Remove all nodes from that and prepend them to this.

fun ref prepend_list(
  that: List[A] ref)
: None val

Parameters

• that: List[A] ref

Returns

• None val

push

[Source]

Adds a value to the tail of the list.

fun ref push(
  a: A)
: None val

Parameters

• a: A

Returns

• None val

pop

[Source]

Removes a value from the tail of the list.

fun ref pop()
: A^ ?

Returns

• A^ ?

unshift

[Source]

Adds a value to the head of the list.

fun ref unshift(
  a: A)
: None val

Parameters

• a: A

Returns

• None val

shift

[Source]

Removes a value from the head of the list.

fun ref shift()
: A^ ?

Returns

• A^ ?

append

[Source]

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

fun ref append(
  seq: (ReadSeq[A] box & ReadElement[A^] box),
  offset: USize val = 0,
  len: USize val = call)
: None val

Parameters

• seq: (ReadSeq[A] box & ReadElement[A^] box)
• offset: USize val = 0
• len: USize val = call

Returns

• None val

concat

[Source]

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

fun ref concat(
  iter: Iterator[A^] ref,
  offset: USize val = 0,
  len: USize val = call)
: None val

Parameters

• iter: Iterator[A^] ref
• offset: USize val = 0
• len: USize val = call

Returns

• None val

truncate

[Source]

Truncate the list to the given length, discarding excess elements. If the list is already smaller than len, do nothing.

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

Parameters

• len: USize val

Returns

• None val

clone

[Source]

Clone the list.

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 member of the list.

fun box map[B: B](
  f: {(this->A!): B^}[A, B] box)
: List[B] ref^

Parameters

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

Returns

• List[B] ref^

flat_map[B: B]

[Source]

Builds a new list by applying a function to every member of the list and using the elements of the resulting lists.

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

• List[B] ref^

filter

[Source]

Builds a new list with those elements that satisfy a provided predicate.

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.

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 provided predicate, false otherwise.

fun box every(
  f: {(this->A!): Bool}[A] box)
: Bool val

Parameters

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

Returns

• Bool val

exists

[Source]

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

fun box exists(
  f: {(this->A!): Bool}[A] box)
: Bool val

Parameters

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

Returns

• Bool val

partition

[Source]

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

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.

fun box drop(
  n: USize val)
: List[this->A!] ref^

Parameters

• n: USize val

Returns

• List[this->A!] ref^

take

[Source]

Builds a list of the first n elements.

fun box take(
  n: USize val)
: List[this->A!] ref

Parameters

• n: USize val

Returns

• List[this->A!] ref

take_while

[Source]

Builds a list of elements satisfying the provided predicate until one does not.

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.

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, false otherwise.

fun box contains[optional B: (A & HasEq[A!] #read)](
  a: box->B)
: Bool val

Parameters

• a: box->B

Returns

• Bool val

nodes

[Source]

Return an iterator on the nodes in the list.

fun box nodes()
: ListNodes[A, this->ListNode[A] ref] ref^

Returns

• ListNodes[A, this->ListNode[A] ref] ref^

rnodes

[Source]

Return an iterator on the nodes in the list.

fun box rnodes()
: ListNodes[A, this->ListNode[A] ref] ref^

Returns

• ListNodes[A, this->ListNode[A] ref] ref^

values

[Source]

Return an iterator on the values in the list.

fun box values()
: ListValues[A, this->ListNode[A] ref] ref^

Returns

• ListValues[A, this->ListNode[A] ref] ref^

rvalues

[Source]

Return an iterator on the values in the list.

fun box rvalues()
: ListValues[A, this->ListNode[A] ref] ref^

Returns

• ListValues[A, this->ListNode[A] ref] ref^