std::data::list

This page covers immutable lists and their Index, Fold, and + (concatenation) operations.

Construction

[]
[1, 2, 3]
my head = 0
my tail = [1, 2]
[head, ..tail]

std::data::list::empty()              // []
std::data::list::singleton 1          // [1]
std::data::list::cons(0, [1, 2])      // [0, 1, 2]

The [ ... ] literal is the everyday form. cons and singleton are useful when working with type variables that would otherwise lose information.

Indexing and slicing

my xs = [10, 20, 30, 40]

xs[0]            // 10
xs[xs.len - 1]   // 40
xs[1..<3]        // [20, 30]
xs[..2]          // [10, 20, 30]
xs[1..]          // [20, 30, 40]

list 'a implements Index for both int and range. An out-of-range index or range slice fails at runtime.

Predicates and length

my xs = [10, 20, 30, 40]

xs.len              // 4
std::data::list::is_empty xs    // false

Len is exposed through xs.len.

Iteration

my xs = [10, 20, 30, 40]

for x in xs:
    say x

xs.fold 0 (\acc x -> acc + x)

list 'a implements Fold, so for and fold both work. The body of a for loop is a function applied to each element.

Transformations

my xs = [10, 20, 30, 40]
my double x = x * 2

xs.map double                          // [20, 40, 60, 80]
xs.filter (\x -> x > 15)               // [20, 30, 40]
xs.rev                                 // [40, 30, 20, 10]
xs.sort                                // [10, 20, 30, 40]
xs.append [50, 60]                     // [10, 20, 30, 40, 50, 60]
xs + [50, 60]                          // same — list implements Add

map, filter, rev, sort, and append return new lists; the original is untouched.

Head/tail access

my xs = [10, 20, 30, 40]
my default = 0

xs.first    // opt::just 10
xs.last     // opt::just 40

case std::data::list::uncons xs:
    opt::just (head, tail) -> head
    opt::nil               -> default

first and last return nil for an empty list. uncons also returns nil when there is no head/tail pair.

Mutable list references

{
    my $xs = [1, 2, 3]
    &xs[1] = 99
    my after_update = $xs
    &xs.push 4           // through the list ref method
    (after_update, $xs)  // ([1, 99, 3], [1, 99, 3, 4])
}

When xs is held in a reference (my $xs = ...), the Index impl for ref _ (list _) lets you write &xs[i] = value. Lists pushed through &xs.push v go through the matching ref method.

Nondeterminism

use std::control::nondet::*

my xs = [10, 20, 30, 40]

(each xs).list
(each xs).once

each picks one element nondeterministically. .list collects every choice into a fresh list, .once returns the first as opt.

Quick reference

Operation	Signature
empty()	() -> list 'a
singleton(x)	'a -> list 'a
cons(x, xs)	'a -> list 'a -> list 'a
is_empty(xs)	list 'a -> bool
xs.len	list 'a -> int
xs.map f	list 'a -> ('a -> 'b) -> list 'b
xs.filter p	list 'a -> ('a -> bool) -> list 'a
xs.fold z f	list 'a -> 'b -> ('b -> 'a -> 'b) -> 'b
xs.rev	list 'a -> list 'a
xs.append ys	list 'a -> list 'a -> list 'a
xs.sort	list 'a -> list 'a (requires Ord 'a)
xs.first / xs.last	list 'a -> opt 'a
uncons(xs)	list 'a -> opt ('a, list 'a)

See also

• Patterns → List patterns
• std::data::range — ranges for slicing and iteration
• std::control::nondet — nondeterministic iteration