Rust for functional programmers

Prologue

Rust for C programmers != Rust for functional programmers.

For experienced C programmers with little experience in anything else, Rust presents many new features and strange constructs that look and feel relatively arcane. Even to C++, Java or C# programmers, Rust looks foreign: its has objects but not classes, it has “structured enums”, a strange “match” statement with no equivalent in the C family, it prevents from assigning twice to the same variable, and all manners of strange rules that were unheard of in the C family.

Why is that?

Although no current Rust manual dares putting it so bluntly, Rust is a functional language, inspired from recent advances in programming language design.

The problem faced by Rust advocates is that “functional programming,” both as a term and as a discipline, has developed many stigmas over the last 30 years: functional programs are “unreadable”, they are relatively slow compared to C, they require heavyweight machinery during execution (at least a garbage collector, often many functional wrappers around system I/O), they are difficult to learn, they use a strange syntax, etc.

Trying to describe Rust as a functional language to C programmers, its primary audience, would be a tough sell indeed. This is why the official Rust manuals and tutorials duly and properly explain how to use Rust for low-level tasks, and care to explain step-by-step the Rust equivalents to many C programming patterns, without refering to other more modern languages.

This is all and well, but what if you already know about functional programming?

For experienced users of Haskell, OCaml, etc., yet another detailed manual that presents the basics of programming with a functional flavor are a bore to read. Tailored to this audience, the text below constitutes a fast-track introduction to Rust, from the functional perspective.

Why you should learn Rust

For better or for worse, most hardware processors will continue to be based on program counters, registers and addressable memory for the foreseeable future. This is where we were in the 1970’s, when C was designed, and this is where we are still today, and this is precisely why C is still in prevalent use. Specifically, the C abstract machine model is the snuggest fit for most hardware platforms, and it is therefore a good level of abstraction to build low-level system software like interrupt service routines, garbage collectors and virtual memory managers.

However, the “user interface” of the C language, in particular its preprocessor and its type system, have aged tremendously. For anyone who learned anything newer, they frankly suck.

This is where Rust has been designed: Rust keeps the C abstract machine model but innovates on the language interface. Rust is expressive, its type system makes system code safer, and its powerful meta-programming facilities enable new ways to generate code automatically.

Note however that Rust is not yet fully stable at the time of this writing: it is still subject to change with little notice, and the official documentation is not fully synchronized with the implementation.

Straightforward equivalences

Like in Haskell, Rust number literals without a suffix do not have a predefined type. Their actual type is inferred from the context. Rust character literals can represent any Unicode scalar value, in contrast to OCaml’s character which can only encode Latin-1 characters. Rust’s other literal forms are presented in Literals below.

Primitive types:

The type str in Rust is special: it is primitive, so that the compiler can optimize certain string operations; but it is not first class, so it is not possible to define variables of type str or pass str values directly to functions. To use Rust strings in programs, one should use string references, as described later below.

Operators equivalences:

==  !=  <  >  <=  >=  && ||   // Rust
=   <>  <  >  <=  >=  && ||   (* OCaml *)
==  /=  <  >  <=  >=  && ||   {- Haskell -}

+  +  +  +  -  -  *  *  /     /  %     !    // Rust
+  +. @  ^  -  -. *  *. /     /. mod   not  (* OCaml *)
+  +  ++ ++ -  -  *  *  `div` /  `mod` not  {- Haskell -}

&    |   ^    <<     >>     !          // Rust
land lor lxor [la]sl [la]sr lnot       (* OCaml *)
.&.  .|. xor  shiftL shiftR complement {- Haskell -}

Note that Rust uses ! both for boolean negation and for the unary bitwise NOT operator on integers. The unary ~ has a different meaning in Rust than in C, detailed later below.

Compound expressions:

Note that the value of a block expression is the value of the last expression in the block, except when the block ends with a semicolon, in which case its value is ().

Functions types and definitions:

// Rust
// f : |int,int| -> int
fn f (x:int, y:int) -> int { x + y };

// fact : |int| -> int
fn fact (n:int) -> int {
   if n == 1 { 1 }
   else { n * fact(n-1) }
}

(* OCaml *)
(* val f : int * int -> int *)
let f (x, y) = x + y

(* val fact : int -> int *)
let rec fact n =
    if n = 1 then 1
    else n * fact (n-1)

{- Haskell -}
f :: (Int, Int) -> Int
f (x, y) = x + y

fact :: Int -> Int
fact n =
    if n = 1 then 1
    else n * fact(n-1)

Pattern match and guards:

// Rust
match e {
  0           => 1,
  t @ 2       => t + 1,
  n if n < 10 => 3,
  _           => 4
}

(* OCaml *)
match e with
 | 0             -> 1
 | 2 as t        -> t + 1
 | n when n < 10 -> 3
 | _             -> 4

{- Haskell -}
case e of
  0          -> 1
  t @ 2      -> t + 1
  n | n < 10 -> 3
  _          -> 4

Recursion with side effects:

// Rust
fn collatz(n:uint) {
  let v = match n % 2 {
     0 => n / 2,
     _ => 3 * n + 1
  }
  println!("{}", v);
  if v != 1 { collatz(v) }
}
fn main() { collatz(25) }

(* OCaml *)
let rec collatz n =
    let v = match n % 2 with
       | 0 -> n / 2
       | _ -> 3 * n + 1
    in
    Printf.printf "%d\n" v;
    if v <> 1 then collatz v

let _ = collatz 25

{- Haskell -}
collatz n = do
    let v = case n `mod` 2 of
            0 -> n `div` 2
            _ -> 3 * n + 1

    putStrLn $ show v
    when (v /= 1) $ collatz v

main = collatz 25

Obviously, Rust uses strict (eager) evaluation and functions can contain side effecting expressions, just like in OCaml.

Note that Rust does not (yet) guarantee tail call elimination, although the underlying LLVM code generator is smart enough that it should work for the function above. When in doubt, the following is equivalent:

let mut n = 25u;
while n != 1 {
   n = if n % 2 == 0 { n / 2 }
       else { 3 * n + 1 }
   println("{}", n);
}

Record types, expressions and field access:

// Rust
struct Point {
  x : int,
  y : int
}

let v = Point {x:1, y:2};
let s = v.x + v.y

(* OCaml *)
type Point = {
  x : int;
  y : int
}

let v = { x = 1; y = 2 };
let s = v.x + v.y

{- Haskell -}
data Point = Point {
   x :: Int,
   y :: Int
}

v = Point {x = 1, y = 2}
s = (x v) + (y v)

Free type parameters (generic data and function types):

// Rust
type Pair<a,b> = (a,b)

// id<t> : |t| -> t
fn id<t>(x : t) -> t { x }

(* OCaml *)
type ('a, 'b) pair = 'a * 'b

(* val id : 't -> 't *)
let id x = x

{- Haskell -}
type Pair a b = (a, b)

id :: t -> t
id x = x

Algebraic data types:

// Rust
enum Option<T> {
   None,
   Some(T)
}
// x : Option<t>
match x {
  None    => false,
  Some(_) => true
}

(* OCaml *)
type 't option =
    None
  | Some of 't

(* x : t option *)
match x with
  | None -> false
  | Some _ -> true

{- Haskell -}
data Maybe a =
    Nothing
  | Just a

{- x : Maybe t -}
case x of
   Nothing -> False
   Just _ -> True

Lambda expressions and higher-order functions:

// Rust
// ||int,int| -> int, int| -> int
fn ff(f:|int,int|->int, x:int) -> int
{ f (x, x) }

// m2 : |int| -> int
fn m2(n : int) -> int
{ ff ((|x,y| { x + y }), n) }

(* OCaml *)
(* (int*int->b)*int -> int *)
let ff (f, x) =
    f (x, x)

(* m2 : int -> int *)
let m2 n =
    ff ((fun(x,y) -> x + y), n)

{- Haskell -}
ff :: ((int,int)->int, int) -> int
ff (f, x) =
   f (x, x)

m2 :: Int -> Int
m2 n =
   ff ((\(x,y) -> x + y), n)

Traits: Rust’s type classes

Rust’s “traits” are analogous to Haskell’s type classes.

The main difference with Haskell is that traits only intervene for expressions with dot notation, ie. of the form a.foo(b).

For C++/Java/C#/OCaml programmers, however, traits should not be confused with traditional object classes. They are really type classes: it is possible to add traits to arbitrary data types, including the primitive types!

An example:

// Rust
trait Testable {
    fn test(&self) -> bool
}

impl Testable for int {
    fn test(&self) -> bool {
       if *self == 0 { false }
       else { true }
    }
}

fn hello(x:int) -> bool {
   x.test()
}

{- Haskell -}
class Testable a where
    test :: a -> Bool


instance Testable Int where
    test n =
       if n == 0 then False
       else True


hello :: Int -> Bool
hello x =
    test x

In a trait method declaration, the identifier “self” denotes the actual object on which the method is applied.

Like in Haskell, Rust traits can be used for operator overloading. For example, if one defines a new sum type for Peano integers:

// Rust
enum Peano {
   Zero,
   Succ(Box<Peano>)
}

{- Haskell -}
data Peano =
    Zero
  | Succ Peano

Then one can overload the comparison operator == between Peano integers by instantiating the PartialEq class:

// Rust
impl PartialEq for Peano {
    fn eq(&self, other:&Peano) -> bool {
      match (self, other) {
        (&Zero, &Zero)               => true,
        (&Succ(ref a), &Succ(ref b)) => (a == b),
        (_, _)                       => false
      }
    }
}

{- Haskell -}
instance Eq Peano where
    (==) self other =
        case (self, other) of
          | (Zero, Zero)     -> True
          | (Succ a, Succ b) -> (a == b)
          | (_, _)           -> False

Also, like in Haskell, a trait can provide a default implementation for a method, to be used when instances omit the specialization:

// Rust
trait PartialEq {
   fn eq(&self, other:&Self) -> bool;
   fn ne(&self, other:&Self) -> bool
   { !self.eq(other) }
 }

{- Haskell -}
class Eq a where
   (==) : a -> a -> Bool
   (!=) : a -> a -> Bool
   (!=) x y = not (x == y)

In the method declarations inside a trait declaration, the identifier “Self” refers to the actual type on which the trait applies.

Each overloadable operator in Rust has a corresponding trait in the standard library:

The for loop uses the special trait std::iter::Iterator, as follows:

// Rust

// the following expression:
[<label>] for <pat> in <iterator expression> {
   body...;
}

// ... expands to (internally):
match &mut <iterator expression> {
  _v => [label] loop {
    match _v.next() {
       None => break,
       Some(<pat>) => { body... }
    }
  }
}

The method next is implemented by Iterator. The return type of next is Option, which can have values None, to mean “nothing left to iterate”, or Some(x), to mean the next iteration value is x.

Ad-hoc objects and methods

In addition to the mechanism offered by traits, any struct or enum can be decorated with one or more method interface(s) using “impl”, separately from its definition and/or in different modules:

// Rust
struct R {x:int};

// in some module:
impl R {
 fn hello(&self) {
  println!("hello {}", self.x);



 }
}
// possibly somewhere else:
impl R {
 fn world(&self) {
  println!("world");
 }
}
// Example use:
fn main() {
  let v = R {x:10};
  v.hello();
  v.world();

  (R{x:20}).hello();
}

// Rust
enum E {A, B};

// in some module:
impl E {
 fn hello(&self) {
   match self {
    &A => println!("hello A"),
    &B => println!("hello B")
   }
 }
}
// possibly somewhere else:
impl E {
 fn world(&self) {
  println!("world");
 }
}
// Example use:
fn main() {
  let v = A;
  v.hello();
  v.world();

  B.hello();
}

Safe references

Like in C, by default function parameters in Rust are passed by value. For large data types, copying the data may be expensive so one may want to use references instead.

For any object v of type T, it is possible to create a reference to that object using the expression “&v”. The reference itself then has type &T.

#[derive(Clone,Copy)]
struct Pt { x:f32, y:f32 }

// This works, but may be expensive:
fn dist1(p1 : Pt, p2: Pt) -> f32 {
   let xd = p1.x - p2.x;
   let yd = p1.y - p2.y;
   (xd * xd + yd * yd).sqrt()
}

// Same, using references:
fn dist2(p1 : &Pt, p2: &Pt) -> f32 {
   let xd = p1.x - p2.x;
   let yd = p1.y - p2.y;
   (xd * xd + yd * yd).sqrt()
}

// Usage:
fn main() {
   let a = Pt { x:1.0, y:2.0 };
   let b = Pt { x:0.0, y:3.0 };
   println!("{}", dist1(a, b));
   println!("{}", dist2(&a, &b));
}

As illustrated in this example, Rust provides some syntactic sugar for struct references: it is possible to write p1.x if p1 is of type &Pt and Pt has a field named x. This sugar is also available for method calls (x.foo()).

However, in many other cases, either the referenced value must be “retrieved” using the unary * operator, or patterns must be matched using &:

fn add3(x : &int) -> int {
   println!("x : {}", *x); // OK
   3 + x; // invalid! (+ cannot apply to &int)
   3 + *x; // OK
}

fn test<t>(x : &Option<t>) -> bool {
   match *x {
     None     => false,
     Some(_)  => true
   }
   // Also valid, equivalent:
   match x {
     &None    => false,
     &Some(_) => true
   }
}

Simple references not not allow modifying the underlying object; if mutability by reference is desired, use “&mut” as follows:

fn incx(x : &int) {
   x = x + 1;   // invalid! (mismatched types in "int& = int")
   *x = *x + 1; // invalid! (*x is immutable)
}

fn inc(x : &mut int) {
   x = x + 1;   // invalid! (x is immutable)
   *x = *x + 1; // OK
}

fn main() {
   inc(&3); // invalid! (3 is immutable)
   inc(&mut 3); // OK, temp var forgotten after call
   let v = 3;
   inc(&v); // invalid! (v is immutable)
   inc(&mut v); // OK, temp var forgotten after call
   let mut w = 3;
   inc(&w); // OK
}

Rust’s type system forbids mutable aliases via references: it is not possible to modify the same object using different names via references, unlike in C. This is done via the concept of borrowing: while ownership of an object is borrowed by a reference, the original variable cannot be used any more. For example:

 fn main() {
    let mut a = 1;
    a = 2; // OK
    println!("{}", a); // OK, prints 2
    // {...} introduces a new scope:
    {
      let ra = &mut a;
      a = 3;   // invalid! (a is borrowed by ra)
      *ra = 3; // OK
      println!("{}", a); // invalid! (a is borrowed)
      println!("{}", *ra); // OK, prints 3
    };
    // end of scope, rb is dropped.
    println!("{}", a); // OK, a not borrowed any more (prints 3)
}

Reference types, together with “all values are immutable by default” and the ownership/borrowing rules, are the core features of Rust’s type system that make it fundamentally safer than C’s.

Lifetime and storage, and managed objects

fn main() {

  let b = box 3i; // b has type Box<int>
  b = 4i; // invalid! can't assign int to box<int>
  *b = 4i; // invalid! b is immutable, so is the box
  let mut c = box 3i; // c has type mut Box<int>
  *c = 4i; // OK

  let v = box vec!(1i,2,3); // r1 has type Box<Vec<int>>
  *v.get_mut(0) = 42; // invalid! v is immutable, so is the box
  let mut w = box vec!(1i,2,3);
  *w.get_mut(0) = 42; // OK, rust 0.11.1+ also permits w[0] = 42

  let z = w; // z has type Box<Vec<int>>, captures box
  println!("{}", w); // invalid! box has moved to z

  w = box vec!(2i,4,5); // overwrites reference, not box contents
  println!("{} {}", w, z); // OK, prints [2,4,5] [42,2,3]
}

// Rust
enum Lst<t> {
   Nil,
   Cons(t, Box<Lst<t>>)
}
fn len<t>(l : &Lst<t>) -> uint {
   match *l {
     Nil => 0,
     Cons(_, ref x) => 1 + len(*x)
   }
}

fn main() {
   let l = box Cons('a',
            box Cons('b',
             box Nil));
   println!("{}", len(l));
}

(* OCaml *)
type 't lst =
    Nil
  | Cons of 't * 't lst

let len l =
  match l with
  | Nil -> 0
  | Cons(_, x) -> 1 + len x




let l = Cons('a',
          Cons('b',
              Nil));
print_int (len l)

{- Haskell -}
data Lst t =
    Nil
  | Cons t (Lst t)

let len l =
  case l of
    Nil -> 0
    Cons _ x -> 1 + len x



main = do
         let l = Cons 'a'
                      (Cons 'b'
                            Nil)
         putStrLn $ show l

Shared objects: Rc and Arc

In complement to the facilities offered by box, the Rust standard library also implements two implementations of reference counted wrappers to immutable objects that can be referred to from multiple owners:

use std::rc::Rc;
fn main() {
    let b = Rc::new(3i);
    let c = &b;
    println("{} {}", b, c); // OK
}

The use of reference counts ensures that an object gets deallocated exactly when its last reference is dropped. The trade-off with boxes is that the reference counter must be updated every time a new reference is created or a reference is dropped.

Two implementations are provided: std::rc::Rc and std::arc::Arc. Both offer the same interface. The reason for this duplication is to offer a controllable trade-off over performance to programmers: Rc does not use memory atomics, so it is more lightweight and thus faster, however it cannot be shared across threads. Arc does use atomics, is thus slightly less efficient than Rc, but can be used to share data across threads.

Macros and meta-programming

The basic syntax of a macro definition is as follows:

macro_rules! MACRONAME (
    (PATTERN...) => (EXPANSION...);
    (PATTERN...) => (EXPANSION...);
    ...
)

For example, the following macro defines a Pascal-like for loop:

macro_rules! pfor (
   ($x:ident = $s:expr to $e:expr $body:expr)
       => (match $e { e => {
              let mut $x = $s;
              loop {
                   $body;
                   $x += 1;
                   if $x > e { break; }
              }
          }});
);

// Example use:
fn main() {
     pfor!(i = 0 to 10 {
         println!("{}", i);
     });
}

Note how this macro uses the match statement to assign a local name to an expression, so that it does not get evaluated more than once.

Like in Scheme, macros can be recursive. For example, the following macro uses recursion to implement pfor both with and without step:

macro_rules! pfor (
   ($x:ident = $s:expr to $e:expr step $st:expr $body:expr)
       => (match $e,$st { e, st => {
              let mut $x = $s;
              loop {
                   $body;
                   $x += st;
                   if $x > e { break; }
              }
          }});
   ($x:ident = $s:expr to $e:expr $body:expr)
      => (pfor!($x = $s to $e step 1 $body));
);

// Example use:
fn main() {
     pfor!(i = 0 to 10 step 2 {
         println!("{}", i);
     });
}

Macros can also be variadic, in that arbitrary repetitions of a syntax form can be captured by one macro argument. For example, the following macro invokes println! on each of its arguments, which can be of arbitrary type:

macro_rules! printall (
     ( $( $arg:expr ),*  ) => (
          $( println!("{}", $arg) );*
     );
);

// example use:
fn main() {
    printall!("hello", 42, 3.14);
}

The syntax works as follows: on the left hand side (pattern) the form $( PAT )DELIM* matches zero or more occurrences of PAT delimited by DELIM; on the right hand side (expansion), the form $( TEXT )DELIM* expands to one or more repetitions of TEXT separated by DELIM. The number of repetitions of the expansion is determined by the number of matches of the enclosed macro argument(s). In the example, each argument (separated by commas) is substituted by a corresponding invocation of println!, separated by semicolons.

Literals

Rust provides various lexical forms for number literals:

Escapes in character, byte and string literals:

Note that the other common escapes in the C family (\a, \f, etc.) are not valid in Rust, nor are octal escapes (eg. \0123).

Finally, Rust like Python supports raw strings and multiple string delimiters, to avoid quoting occurrences of the delimiters within the string:

Acknowledgements

Many thanks to the numerous commenters on Reddit and Hacker news who provided high-quality comments and substantively contributed to improving upon the first version of this article.

References

• The Rust Language Tutorial, version 0.10, April 2014.
• The Rust Language Tutorial, version 0.11.0, July 2014.
• The Rust Guide, version 0.11.0, July 2014.
• Aaron Turon, Rust Guidelines, 2014.
• Will Yager. Why Go is not good, 2014. Explains how Go lacks many features found in Rust and thereby fails to be a modern functional language.
• Edward Z. Yang, OCaml for Haskellers, October 2010.
• Raphael ‘kena’ Poss, Haskell for OCaml programmers, March 2014.
• Xavier Leroy et al., The OCaml system release 4.01, September 2013.