type List[A] is (Cons[A] | Nil[A])
"""
A persistent list with functional transformations.
## Usage
```pony
use "collections/persistent"
actor Main
new create(env: Env) =>
try
let l1 = Lists[U32]([2; 4; 6; 8]) // List(2, 4, 6, 8)
let empty = Lists[U32].empty() // List()
// prepend() returns a new List, leaving the
// old list unchanged
let l2 = empty.prepend(3) // List(3)
let l3 = l2.prepend(2) // List(2, 3)
let l4 = l3.prepend(1) // List(1, 2, 3)
let l4_head = l4.head() // 1
let l4_tail = l4.tail() // List(2, 3)
l4_head == 1
Lists[U32].eq(l4, Lists[U32]([1; 2; 3]))?
Lists[U32].eq(l4_tail, Lists[U32]([2; 3]))?
let doubled = l4.map[U32]({(x) => x * 2 })
Lists[U32].eq(doubled, Lists[U32]([2; 4; 6]))?
end
```
"""
primitive Lists[A]
"""
A primitive containing helper functions for constructing and
testing Lists.
"""
fun empty(): List[A] =>
"""
Returns an empty list.
"""
Nil[A]
fun cons(h: val->A, t: List[A]): List[A] =>
"""
Returns a list that has h as a head and t as a tail.
"""
Cons[A](h, t)
fun apply(arr: Array[val->A]): List[A] =>
"""
Builds a new list from an Array
"""
this.from(arr.values())
fun from(iter: Iterator[val->A]): List[A] =>
"""
Builds a new list from an iterator
"""
var l: List[A] = Nil[A]
for i in iter do
l = Cons[A](i, l)
end
l.reverse()
fun eq[T: Equatable[T] val = A](l1: List[T], l2: List[T]): Bool ? =>
"""
Checks whether two lists are equal.
"""
var a: List[T] = l1
var b: List[T] = l2
while true do
if a.is_empty() and b.is_empty() then return true end
if a.is_empty() or b.is_empty() then return false end
if a.head()? != b.head()? then return false end
a = a.tail()?
b = b.tail()?
end
true
primitive Nil[A] is ReadSeq[val->A]
"""
The empty list of As.
"""
fun size(): USize =>
"""
Returns the size of the list.
"""
0
fun apply(i: USize): val->A ? =>
"""
Returns the i-th element of the sequence. For the empty list this call will
always error because any index will be out of bounds.
"""
error
fun values(): Iterator[val->A]^ =>
"""
Returns an empty iterator over the elements of the empty list.
"""
object ref is Iterator[val->A]
fun has_next(): Bool => false
fun ref next(): val->A ? => error
end
fun is_empty(): Bool =>
"""
Returns a Bool indicating if the list is empty.
"""
true
fun is_non_empty(): Bool =>
"""
Returns a Bool indicating if the list is non-empty.
"""
false
fun head(): val->A ? =>
"""
Returns an error, since Nil has no head.
"""
error
fun tail(): List[A] ? =>
"""
Returns an error, since Nil has no tail.
"""
error
fun reverse(): Nil[A] =>
"""
The reverse of the empty list is the empty list.
"""
this
fun prepend(a: val->A): Cons[A] =>
"""
Builds a new list with an element added to the front of this list.
"""
Cons[A](consume a, this)
fun concat(l: List[A]): List[A] =>
"""
The concatenation of any list l with the empty list is l.
"""
l
fun map[B](f: {(val->A): val->B} box): Nil[B] =>
"""
Mapping a function from A to B over the empty list yields the
empty list of Bs.
"""
Nil[B]
fun flat_map[B](f: {(val->A): List[B]} box): Nil[B] =>
"""
Flatmapping a function from A to B over the empty list yields the
empty list of Bs.
"""
Nil[B]
fun for_each(f: {(val->A)} box) =>
"""
Applying a function to every member of the empty list is a no-op.
"""
None
fun filter(f: {(val->A): Bool} box): Nil[A] =>
"""
Filtering the empty list yields the empty list.
"""
this
fun fold[B](f: {(B, val->A): B^} box, acc: B): B =>
"""
Folding over the empty list yields the initial accumulator.
"""
consume acc
fun every(f: {(val->A): Bool} box): Bool =>
"""
Any predicate is true of every member of the empty list.
"""
true
fun exists(f: {(val->A): Bool} box): Bool =>
"""
For any predicate, there is no element that satisfies it in the empty
list.
"""
false
fun partition(f: {(val->A): Bool} box): (Nil[A], Nil[A]) =>
"""
The only partition of the empty list is two empty lists.
"""
(this, this)
fun drop(n: USize): Nil[A] =>
"""
There are no elements to drop from the empty list.
"""
this
fun drop_while(f: {(val->A): Bool} box): Nil[A] =>
"""
There are no elements to drop from the empty list.
"""
this
fun take(n: USize): Nil[A] =>
"""
There are no elements to take from the empty list.
"""
this
fun take_while(f: {(val->A): Bool} box): Nil[A] =>
"""
There are no elements to take from the empty list.
"""
this
fun val contains[T: (A & HasEq[A!] #read) = A](a: val->T): Bool =>
false
class val Cons[A] is ReadSeq[val->A]
"""
A list with a head and a tail, where the tail can be empty.
"""
let _size: USize
let _head: val->A
let _tail: List[A] val
new val create(a: val->A, t: List[A]) =>
_head = consume a
_tail = consume t
_size = 1 + _tail.size()
fun size(): USize =>
"""
Returns the size of the list.
"""
_size
fun apply(i: USize): val->A ? =>
"""
Returns the i-th element of the list. Errors if the index is out of bounds.
"""
if i == 0 then return _head end
// `apply` has a box receiver, so the walk starts from the tail field
// rather than from `this`
var cur: List[A] = _tail
var n = i - 1
while true do
match cur
| let cons: Cons[A] =>
if n == 0 then return cons.head() end
cur = cons.tail()
n = n - 1
else
error
end
end
error
fun values(): Iterator[val->A]^ =>
"""
Returns an iterator over the elements of the list.
"""
object is Iterator[val->A]
var _list: List[A] box = this
fun has_next(): Bool => _list isnt Nil[A]
fun ref next(): val->A ? => (_list = _list.tail()?).head()?
end
fun is_empty(): Bool =>
"""
Returns a Bool indicating if the list is empty.
"""
false
fun is_non_empty(): Bool =>
"""
Returns a Bool indicating if the list is non-empty.
"""
true
fun head(): val->A =>
"""
Returns the head of the list.
"""
_head
fun tail(): List[A] =>
"""
Returns the tail of the list.
"""
_tail
fun val reverse(): List[A] =>
"""
Builds a new list by reversing the elements in the list.
"""
var out: List[A] = Nil[A]
var cur: List[A] = this
while true do
match cur
| let cons: Cons[A] =>
out = out.prepend(cons.head())
cur = cons.tail()
else
break
end
end
out
fun val prepend(a: val->A): Cons[A] =>
"""
Builds a new list with an element added to the front of this list.
"""
Cons[A](consume a, this)
fun val concat(l: List[A]): List[A] =>
"""
Builds a new list that is the concatenation of this list and the provided
list.
"""
var out: List[A] = this.reverse()
var cur: List[A] = l
while true do
match cur
| let cons: Cons[A] =>
out = out.prepend(cons.head())
cur = cons.tail()
else
break
end
end
out.reverse()
fun val map[B](f: {(val->A): val->B} box): List[B] =>
"""
Builds a new list by applying a function to every member of the list.
"""
var out: List[B] = Nil[B]
var cur: List[A] = this
while true do
match cur
| let cons: Cons[A] =>
out = out.prepend(f(cons.head()))
cur = cons.tail()
else
break
end
end
out.reverse()
fun val flat_map[B](f: {(val->A): List[B]} box): List[B] =>
"""
Builds a new list by applying a function to every member of the list and
using the elements of the resulting lists.
"""
var out: List[B] = Nil[B]
var cur: List[A] = this
while true do
match cur
| let cons: Cons[A] =>
// each result is prepended in order, which reverses it into `out`;
// the reverse at the end puts both levels back the right way round
var inner: List[B] = f(cons.head())
while true do
match inner
| let icons: Cons[B] =>
out = out.prepend(icons.head())
inner = icons.tail()
else
break
end
end
cur = cons.tail()
else
break
end
end
out.reverse()
fun val for_each(f: {(val->A)} box) =>
"""
Applies the supplied function to every element of the list in order.
"""
var cur: List[A] = this
while true do
match cur
| let cons: Cons[A] =>
f(cons.head())
cur = cons.tail()
else
break
end
end
fun val filter(f: {(val->A): Bool} box): List[A] =>
"""
Builds a new list with those elements that satisfy a provided predicate.
"""
var out: List[A] = Nil[A]
var cur: List[A] = this
while true do
match cur
| let cons: Cons[A] =>
if f(cons.head()) then out = out.prepend(cons.head()) end
cur = cons.tail()
else
break
end
end
out.reverse()
fun val fold[B](f: {(B, val->A): B^} box, acc: B): B =>
"""
Folds the elements of the list using the supplied function.
"""
var out: B = consume acc
var cur: List[A] = this
while true do
match cur
| let cons: Cons[A] =>
out = f(consume out, cons.head())
cur = cons.tail()
else
break
end
end
consume out
fun val every(f: {(val->A): Bool} box): Bool =>
"""
Returns true if every element satisfies the provided predicate, false
otherwise.
"""
var cur: List[A] = this
while true do
match cur
| let cons: Cons[A] =>
if not f(cons.head()) then return false end
cur = cons.tail()
else
break
end
end
true
fun val exists(f: {(val->A): Bool} box): Bool =>
"""
Returns true if at least one element satisfies the provided predicate,
false otherwise.
"""
var cur: List[A] = this
while true do
match cur
| let cons: Cons[A] =>
if f(cons.head()) then return true end
cur = cons.tail()
else
break
end
end
false
fun val partition(f: {(val->A): Bool} box): (List[A], List[A]) =>
"""
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.
"""
var hits: List[A] = Nil[A]
var misses: List[A] = Nil[A]
var cur: List[A] = this
while true do
match cur
| let cons: Cons[A] =>
let next = cons.head()
if f(next) then
hits = hits.prepend(next)
else
misses = misses.prepend(next)
end
cur = cons.tail()
else
break
end
end
(hits.reverse(), misses.reverse())
fun val drop(n: USize): List[A] =>
"""
Builds a list by dropping the first n elements.
"""
var cur: List[A] = this
if cur.size() <= n then return Nil[A] end
var count = n
while count > 0 do
match cur
| let cons: Cons[A] =>
cur = cons.tail()
count = count - 1
end
end
cur
fun val drop_while(f: {(val->A): Bool} box): List[A] =>
"""
Builds a list by dropping elements from the front of the list until one
fails to satisfy the provided predicate.
"""
var cur: List[A] = this
while true do
match cur
| let cons: Cons[A] =>
if f(cons.head()) then cur = cons.tail() else break end
else
return Nil[A]
end
end
cur
fun val take(n: USize): List[A] =>
"""
Builds a list of the first n elements.
"""
var cur: List[A] = this
if cur.size() <= n then return cur end
var count = n
var res: List[A] = Nil[A]
while count > 0 do
match cur
| let cons: Cons[A] =>
res = res.prepend(cons.head())
cur = cons.tail()
else
return res.reverse()
end
count = count - 1
end
res.reverse()
fun val take_while(f: {(val->A): Bool} box): List[A] =>
"""
Builds a list of elements satisfying the provided predicate until one does
not.
"""
var cur: List[A] = this
var res: List[A] = Nil[A]
while true do
match cur
| let cons: Cons[A] =>
if f(cons.head()) then
res = res.prepend(cons.head())
cur = cons.tail()
else
break
end
else
return res.reverse()
end
end
res.reverse()