Lists

Linked.List{T}()
Linked.List(iter)

The Linked.List ($\S{2.1}$) is the simplest of the list types, and the fastest for the primary operations, which are all $\mathcal{O}(1)$.

Examples

julia> using PureFun, PureFun.Linked
julia> l = Linked.List(1:3)
3-element PureFun.Linked.NonEmpty{Int64}
1
2
3


julia> m = pushfirst(l, 10)
4-element PureFun.Linked.NonEmpty{Int64}
10
1
2
3


julia> first(l)
1

julia> first(m)
10

julia> popfirst(m) == l
true

RandomAccess.List{T}()
RandomAccess.List(iter)

A RandomAccess.List ($\S{9.3.2}$) adds efficient ($\mathcal{O}(\log{}n)$) indexing (getindex and setindex) operations to the $\mathcal{O}(1)$ primary operations. The implementation stores elements in complete binary trees representing digits in the skew binary number system, as described in this blog post.

Examples

julia> rl = PureFun.RandomAccess.List(1:1_000)
1
2
3
4
5
6
7
...


julia> rl[937]
937

Catenable.List{T}()
Catenable.List(iter)

A Catenable.List ($\S{10.2.1}$) supports the usual list operations, but unlike the Linked.List you can append two catenable lists in constant time. These lists are presented in section 10.2.1 of the book, as an example of data-structural bootstrapping. In addition to list functions, catenable lists also support push. Catenable lists work by maintaining the head element plus a queue of catenable lists. Each element of this queue is suspended. first takes constant time, while pushfirst, popfirst, push, and ⧺ require amortized (rather than worst-case) constant time.

Examples

julia> a = PureFun.Catenable.List(1:3);

julia> b = PureFun.Catenable.List(4:5);

julia> a ⧺ b
1
2
7
4
5

VectorCopy.List{T}()
VectorCopy.List(iter)

VectorCopy.List is a wrapper around Base.Vector with copy-on-write semantics. pushfirst is $\mathcal{O}(n)$, but iteration and indexing are very fast. Useful for small lists, or for lists that are traversed frequently relative to how often they are modified.

Chunky.@list Name ListType ChunkType

Creates a new list type (implements all list functions and inherits from PureFun.PFList) by assembling a list (of type ListType) of chunks (of type ChunkType). Assuming ChunkType stores chunk elements contiguously, the resulting list will have improved iteration performance. PureFun.Contiguous.VectorChunk and PureFun.Contiguous.StaticChunk implement the chunk type and can be used in chunky lists.

Examples

This example creates a chunky list called ChunkyList consisting of (up to) 16-element chunks stored contiguously in memory as static arrays, linked together via a linked list. The resulting list has the same interface as any other list type in PureFun.jl:

julia> using PureFun, PureFun.Linked, PureFun.Chunky, PureFun.Contiguous

julia> Chunky.@list CList list=Linked.List chunk=Contiguous.StaticChunk{16}

julia> clist = CList(1:100)
100-element CList{Int64}
1
2
3
4
5
6
7
...

julia> clist[18]
18

julia> mapfoldl(sqrt, +, clist)
671.4629471031477

Similarly, the following example uses PureFun.RandomAccess.Lists and chunks of Base.Vector:

julia> using PureFun, PureFun.RandomAccess, PureFun.Chunky, PureFun.Contiguous

julia> Chunky.@list CRList list=RandomAccess.List chunk=Contiguous.VectorChunk{256}

julia> em = CRList{Float64}()
0-element CRList{Float64}


julia> 1.0 ⇀ 2.0 ⇀ em
2-element CRList{Float64}
1.0
2.0

Batched.@deque Name ListType

Deques are like lists but with symmetric efficient operations on the front (pushfirst, popfirst, first) and the back (push, pop, last). The Batched.@deque functor takes any existing list implementation (ListType), and makes it double-ended. The Batched.@deque works by batching occasional reversals (which are $\mathcal{O}(n)$) so that all operations require amortized constant time.

Examples

julia> Batched.@deque Deque PureFun.Linked.List

julia> d = Deque{Int}()
0-element Deque{Int64}


julia> 1 ⇀ 2 ⇀ 3 ⇀ d
3-element Deque{Int64}
1
2
3


julia> alpha = Deque('a':'z')
26-element Deque{Char}
a
b
c
d
e
f
g
...

julia> first(alpha), last(alpha)
('a', 'z')

julia> alpha |> pop |> last
'y': ASCII/Unicode U+0079 (category Ll: Letter, lowercase)

julia> alpha |> popfirst |> first
'b': ASCII/Unicode U+0062 (category Ll: Letter, lowercase)

cons(x, xs::PFList)
pushfirst(xs::PFList, x)
x ⇀ xs

Return the PFList that results from adding x to the front of xs.

popfirst(xs)

Return the collection xs without its first element (without modifying xs).

append(xs, ys)
xs ⧺ ys

Concatenate two PFLists.

julia> l1 = PureFun.Linked.List(1:3);

julia> l2 = PureFun.Linked.List(4:6);

julia> l1 ⧺ l2
1
2
3
4
5
6

insert(list::PFList, ix, v)

Return a new list with the element v inserted at index ix.

setindex(l::PFList, newval, ind)

Return a new list with the value at index ind set to newval

Examples

julia> using PureFun, PureFun.RandomAccess

julia> l = RandomAccess.List(1:10)
10-element PureFun.RandomAccess.List{Int64}
1
2
3
4
5
6
7
...

julia> setindex(l, 99, 4)
10-element PureFun.RandomAccess.List{Int64}
1
2
3
99
5
6
7
...

halfish(xs)

Split xs roughly in half, and return the two halves as a tuple (front, back).

Examples

julia< using PureFun
julia> l = PureFun.Linked.List(1:100)
100-element PureFun.Linked.NonEmpty{Int64}
1
2
3
4
5
6
7
...

julia> halves = halfish(l)
(1, 2, 3, 4, 5, ..., 51, 52, 53, 54, 55, ...)

julia> length(halves[1]), length(halves[2])
(50, 50)

julia> halves[2]
50-element PureFun.Linked.NonEmpty{Int64}
51
52
53
54
55
56
57
...