Multi-Purpose Maps:
Structures, Traits, and Higher-Order Functions

This section covers creating and using structs in Rust, making use of higher order functions and traits to create generic functions. We also introduce tasks, Rust's way of handling multiprocessing, and a simple mechanism for communicating between tasks. In the following section, we'll cover some of the richer cross-task communication abstractions provided by Rust.

As a running example, we will use these concepts to build a structure for a simple linked list, a map function which will apply a given function to all elements in the list, and finally use of tasks to make our simple map execute in parallel.

Structures

A struct is Rust's way of packaging data into a structure. It is similar to struct in C.

Defining Structs

A struct type is defined using:

1
2
3
4
5

struct Name { 
   field1: T1, 
   field2: T2, 
   ... 
}

where T1 and T2 are the types of the preceding fields.

Note that mutability is not specified in the struct type definition. A struct is declared mutable upon creation, and mutability applied to all fields within.

The following code defines a Node for a linked list. The field val is an integer, and the tail field is either a pointer to the next Node , or None for the last Node in the list.

1
2
3
4

struct Node {
    val: int,
    tail: Option<~Node>
}

The tail is an Option<~Node> , so it either points to an owned Node , or is None (an empty LinkedList).

The type Name = Type; construct provides a way to define a new name for a type. Note that this is just for convenience — the Name defined by the type definition means exactly the same thing to the type checker as the Type it is defined to.

For example, we can define the LinkedList type using: type keyword.

1
2
3
4
5
6

type LinkedList = Option<~Node>;

struct Node {
   val: int,
   tail: LinkedList
}

Constructing Structs

A struct is constructed in a similar syntax to how it was defined, with the name of the struct followed by braces with the fields defined using fieldName:value .

The following code defines one immutable and one mutable Node :

1
2
3

    let node1 = Node {val:10,  tail: None};
    let mut node2 = Node {val: 10, tail: None};
    node2.val = 15; 

The mutability qualifier applies all the fields in the struct. Trying to change a field of node1 would result in a compiler error.

For an example, the code below creates a list of n elements:

1
2
3
4
5
6

fn construct_list(n: int, x: int) -> LinkedList {
    match n {
        0 => { None }
        _ => { Some(~Node{val: x, tail: construct_list(n - 1, x + 1)}) }
    }
}

(See the official Rust tutorial for a more elegant way to implement a linked list in Rust using an enum , which we don't cover in this tutorial.)

Traits

Traits provide a way of defining a set of methods. The thing in Java they most closely resemble is interfaces, but traits in Rust can also include implementations of methods.

Defining Traits

The syntax for defining a trait is similar to that for a struct:

1
2
3
4
5

trait Name {
   method1;
   method2;
   ...
}

Each method is a function type declaration.

For example, we can define a Length trait like this:

1
2
3

trait Length {
   fn length(&self) -> int;
}

The function declaration uses &self as the parameter to indicate the object on which length is invoked (similar to how this is used in Java). Note that it does not have a type yet, since we can implement a trait for different types.

Implementing Traits

The impl construct is used to implement a trait for a type. For example,

1
2
3
4
5
6
7
8

impl Length for LinkedList {
   fn length(&self) -> int {
      match self {
        &Some(ref node) => { 1 + node.tail.length() }
        &None => 0
      }
   }
}

implements the Length trait for our LinkedList type by providing an implementation of the length method. We need the ref qualified for the matched variable. This indicated that is it bound by reference rather than by value.

We'll see a more interesting example of implementing a trait for the linked list type at the end of this part of the tutorial.

Higher-Order Functions

A higher-order function is a function which operates on other functions. We can have functions that take other functions as inputs, as well as functions that create and return new functions as their output. Higher-order functions provide a lot of power for concisely and very generally describe computations. By the end of this section, you'll be able to write a single function that can do all of the things in the previous set of exercises!

Functions as Parameters

A parameter can have function type, just like any other type. The type of a function includes the types of its inputs and the type of its output.

For example,

1
2
3

fn twice(n: int, f: |int| -> int) -> int {
    f(f(n))
}

defines a function that takes two inputs, the second of which is a function. The syntax, |arg1, arg2, ...| -> res (with vertical bars around a list of parameter types) specifies a function that takes the argn types as inputs and returns a value of type res .

Here's an example using twice :

1
2
3
4
5
6
7

fn successor(n: int) -> int { n + 1 }
fn double(n:int) -> int { n * 2 }

fn main()
{
    println!("Result: {:d}", twice(twice(1, successor), double));
}

The result is (((1 + 1) + 1) * 2) * 2 = 12.

Functions as Results

It would be a lot more useful if twice didn't take the integer as one of its inputs, but instead returned a function. For example, we would like to be able to do:

1

    let square = twice(double);

to define a squaring function.

We can do this by defining a function that returns a function:

1
2
3

fn twice(f: proc(int) -> int) -> (proc(int) -> int) {
    proc(n: int) { f(f(n)) }
}

Now, twice is a function that take a function as its input (we use proc(int) -> int here to describe the input function, and need to use proc(int) ->int instead of |int| -> int because of Rust's lifetime rules. (Note that the way we defined this, we can only use the returned function once.)

We can use twice like this:

1
2
3
4
5

fn main()
{
    let hexaple = twice(twice(double));
    println!("Result: {:d}", hexaple(2)); // 32
}

Example: Mapping a List

The above examples hopefully give you a sense of the power of higher-order functions, but perhaps not how they would be useful in typical code. Next, we'll see how higher-order functions can be used to provide generic functions for manipulating our LinkedList type. We'll implement a mapping function that applies a function to each element of a list.

We define the Map trait as:

1
2
3

trait Map {
   fn mapr(&mut self, extern fn(int) -> int);
}

Now, we will implement the Map trait for our LinkedList type:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

impl Map for LinkedList {
    fn mapr(&mut self, f: extern fn(int) -> int) {
         match(*self) {
            None => { }
            Some(ref mut current) => { 
               current.val = f(current.val);
               current.tail.mapr(f); 
            }
        } 
    } 
}

Here are some examples using map:

1
2
3
4
5
6
7
8
9

fn inc(n: int) -> int { n + 1 }
fn double(n: int) -> int { n * 2 }

fn main() {
    let mut l10: LinkedList = construct_list(4, 10);
    l10.mapr(inc);
    l10.mapr(double);
    println!("List: {:s}", print_list(l10.clone())); // 22, 24, 26, 28,
}