Rust for functional programmers
===============================
:Author: `Raphael ‘kena’ Poss`__
:Date: July 2014
This post follows up on `OCaml for Haskellers`__ from
Edward Z. Yang (2010) and my own `Haskell for OCaml programmers`__
from earlier this year.
.. __: http://science.raphael.poss.name/
.. __: http://blog.ezyang.com/2010/10/ocaml-for-haskellers/
.. __: http://science.raphael.poss.name/haskell-for-ocaml-programmers.html
.. contents::
:depth: 1
----
.. note::
The latest version of this document can be found online at
http://science.raphael.poss.name/rust-for-functional-programmers.html.
Alternate formats:
`Source `_,
`PDF `_.
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.
----
.. raw:: latex
\clearpage
Straightforward equivalences
````````````````````````````
================= ========= ============= =====================
Syntax Type Ocaml Haskell
================= ========= ============= =====================
``()`` () ``()`` ``()``
``true`` bool ``true`` ``True``
``false`` bool ``false`` ``False``
``123`` (integer) ``123 {- :: Num a => a }``
``0x123`` (integer) ``0x123 {- :: Num a => a }``
``12.3`` (float) ``12.3 {- :: Fractional a => a }``
``'a'`` char ``'a'``
``"abc"`` str ``"abc"`` ``"abc"``
``b'a'`` u8 ``'a'`` ``toEnum$fromEnum$'a'::Word8``
``123i`` int ``123`` ``123 :: Int``
``123i32`` i32 ``123l`` ``123 :: Int32``
``123i64`` i64 ``123L`` ``123 :: Int64``
``123u`` uint ``123 :: Word``
================= ========= ============= =====================
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:
======== ======= ====== ==============================================
Rust Haskell OCaml Description
======== ======= ====== ==============================================
() () unit Unit type
bool Bool bool Boolean type
int Int int Signed integer, machine-dependent width
uint Word Unsigned integer, machine-dependent width
i8 Int8 8 bit wide signed integer, two's complement
i16 Int16 16 bit wide signed integer, two's complement
i32 Int32 int32 32 bit wide signed integer, two's complement
i64 Int64 int64 64 bit wide signed integer, two's complement
u8 Word8 char 8 bit wide unsigned integer
u16 Word16 16 bit wide unsigned integer
u32 Word32 32 bit wide unsigned integer
u64 Word64 64 bit wide unsigned integer
f32 Float 32-bit IEEE 754 binary floating-point
f64 Double float 64-bit IEEE 754 binary floating-point
char Char Unicode scalar value (non-surrogate code points)
str UTF-8 encoded character string.
======== ======= ====== ==============================================
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:
.. code::
== != < > <= >= && || // 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:
================= ==================== ================= ===============
Rust OCaml Haskell Name
================= ==================== ================= ===============
``R{a:10, b:20}`` ``{a=10; b=20}`` ``R{a=10, b=20}`` Record expression
``R{a:30, ..z}`` ``{z with a=30}`` ``z{a=30}`` Record with functional update
``(x,y,z)`` ``(x,y,z)`` ``(x,y,z)`` Tuple expression
``x.f`` ``x.f`` ``f x`` Field expression
``[x,y,z]`` ``[|x;y;z|]`` Array expression, fixed size
``[x, ..10]`` Array expression, fixed repeats of first value
``x[10]`` ``x.(10)`` ``x!10`` Index expression (vectors/arrays)
``x[10]`` ``x.[10]`` ``x!!10`` Index expression (strings)
``{x;y;z}`` ``begin x;y;z end`` Block expression
``{x;y;}`` ``begin x;y;() end`` Block expression (ends with unit)
================= ==================== ================= ===============
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:
.. list-table::
:widths: 40 30 30
* - .. code:: rust
// 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) }
}
- .. code:: ocaml
(* 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)
- .. code:: haskell
{- 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:
.. list-table::
:widths: 33 33 33
* - .. code:: rust
// Rust
match e {
0 => 1,
t @ 2 => t + 1,
n if n < 10 => 3,
_ => 4
}
- .. code:: ocaml
(* OCaml *)
match e with
| 0 -> 1
| 2 as t -> t + 1
| n when n < 10 -> 3
| _ -> 4
- .. code:: haskell
{- Haskell -}
case e of
0 -> 1
t @ 2 -> t + 1
n | n < 10 -> 3
_ -> 4
Recursion with side effects:
.. list-table::
:widths: 33 33 33
* - .. code:: rust
// 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) }
- .. code:: ocaml
(* 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
- .. code:: haskell
{- 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:
.. code:: rust
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:
.. list-table::
:widths: 33 33 33
* - .. code:: rust
// Rust
struct Point {
x : int,
y : int
}
let v = Point {x:1, y:2};
let s = v.x + v.y
- .. code:: ocaml
(* OCaml *)
type Point = {
x : int;
y : int
}
let v = { x = 1; y = 2 };
let s = v.x + v.y
- .. code:: haskell
{- 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):
.. list-table::
:widths: 33 33 33
* - .. code:: rust
// Rust
type Pair = (a,b)
// id : |t| -> t
fn id(x : t) -> t { x }
- .. code:: ocaml
(* OCaml *)
type ('a, 'b) pair = 'a * 'b
(* val id : 't -> 't *)
let id x = x
- .. code:: haskell
{- Haskell -}
type Pair a b = (a, b)
id :: t -> t
id x = x
Algebraic data types:
.. list-table::
:widths: 33 33 33
* - .. code:: rust
// Rust
enum Option {
None,
Some(T)
}
// x : Option
match x {
None => false,
Some(_) => true
}
- .. code:: ocaml
(* OCaml *)
type 't option =
None
| Some of 't
(* x : t option *)
match x with
| None -> false
| Some _ -> true
- .. code:: haskell
{- Haskell -}
data Maybe a =
Nothing
| Just a
{- x : Maybe t -}
case x of
Nothing -> False
Just _ -> True
Lambda expressions and higher-order functions:
.. list-table::
:widths: 40 30 30
* - .. code:: rust
// 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) }
- .. code:: ocaml
(* 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)
- .. code:: haskell
{- 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:
.. list-table::
:widths: 50 50
* - .. code:: rust
// 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()
}
- .. code:: haskell
{- 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:
.. list-table::
:widths: 50 50
* - .. code:: rust
// Rust
enum Peano {
Zero,
Succ(Box)
}
- .. code:: haskell
{- Haskell -}
data Peano =
Zero
| Succ Peano
Then one can overload the comparison operator ``==`` between Peano
integers by instantiating the ``PartialEq`` class:
.. list-table::
:widths: 50 50
* - .. code:: rust
// 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
}
}
}
- .. code:: haskell
{- 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:
.. list-table::
:widths: 50 50
* - .. code:: rust
// Rust
trait PartialEq {
fn eq(&self, other:&Self) -> bool;
fn ne(&self, other:&Self) -> bool
{ !self.eq(other) }
}
- .. code:: haskell
{- 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:
=========== ================ ====================== ===============================
Expression Expands to Trait Equivalent Haskell class/method
=========== ================ ====================== ===============================
``a == b`` ``a.eq(b)`` std::cmp::PartialEq ``class PartialEq a where (==) : a -> a -> bool``
``a != b`` ``a.ne(b)`` std::cmp::PartialEq ``class PartialEq a where (/=) : a -> a -> bool``
``a < b`` ``a.lt(b)`` std::cmp::PartialOrd ``class PartialOrd a where (<) : a -> a -> bool``
``a > b`` ``a.gt(b)`` std::cmp::PartialOrd ``class PartialOrd a where (>) : a -> a -> bool``
``a <= b`` ``a.le(b)`` std::cmp::PartialOrd ``class PartialOrd a : Eq a where (<=) : a -> a -> bool``
``a >= b`` ``a.ge(b)`` std::cmp::PartialOrd ``class PartialOrd a : Eq a where (>=) : a -> a -> bool``
``a + b`` ``a.add(b)`` std::ops::Add** ``class Add a b c where (+) : a -> b -> c``
``a - b`` ``a.sub(b)`` std::ops::Sub**** ``class Sub a b c where (-) : a -> b -> c``
``a * b`` ``a.mul(b)`` std::ops::Mul**** ``class Mul a b c where (*) : a -> b -> c``
``a / b`` ``a.div(b)`` std::ops::Div**** ``class Div a b c where (/) : a -> b -> c``
``a % b`` ``a.rem(b)`` std::ops::Rem**** ``class Rem a b c where (%) : a -> b -> c``
``-a`` ``a.neg()`` std::ops::Neg ``class Neg a c where (-) : a -> c``
``!a`` ``a.not()`` std::ops::Not ``class Not a c where (!) : a -> c``
``*a`` ``a.deref()`` std::ops::Deref ``class Deref a c where (*) : a -> c``
``a & b`` ``a.bitand(b)`` std::ops::BitAnd**** ``class BitAnd a b c where (&) : a -> b -> c``
``a | b`` ``a.bitor(b)`` std::ops::BitOr**** ``class BitOr a b c where (|) : a -> b -> c``
``a ^ b`` ``a.bitxor(b)`` std::ops::BitXor**** ``class BitXor a b c where (^) : a -> b -> c``
``a << b`` ``a.shl(b)`` std::ops::Shl**** ``class Shl a b c where (<<) : a -> b -> c``
``a >> b`` ``a.shr(b)`` std::ops::Shr**** ``class Shr a b c where (>>) : a -> b -> c``
=========== ================ ====================== ===============================
The ``for`` loop uses the special trait ``std::iter::Iterator``, as follows:
.. code:: rust
// Rust
// the following expression:
[**