Rust for functional programmers =============================== :date: July 2014 :modified: 2020-01-25 :Author: Raphael ‘kena’ Poss :category: Programming :tags: rust, haskell, ocaml, functional programming, language comparison, analysis, programming languages 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://blog.ezyang.com/2010/10/ocaml-for-haskellers/ .. __: https://dr-knz.net/haskell-for-ocaml-programmers.html .. contents:: :depth: 1 ---- .. note:: The latest version of this document can be found online at https://dr-knz.net/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-block:: 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-block:: 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-block:: 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-block:: rust // Rust match e { 0 => 1, t @ 2 => t + 1, n if n < 10 => 3, _ => 4 } - .. code-block:: ocaml (* OCaml *) match e with | 0 -> 1 | 2 as t -> t + 1 | n when n < 10 -> 3 | _ -> 4 - .. code-block:: 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-block:: 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-block:: 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-block:: 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-block:: 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-block:: rust // Rust struct Point { x : int, y : int } let v = Point {x:1, y:2}; let s = v.x + v.y - .. code-block:: ocaml (* OCaml *) type Point = { x : int; y : int } let v = { x = 1; y = 2 }; let s = v.x + v.y - .. code-block:: 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-block:: rust // Rust type Pair = (a,b) // id : |t| -> t fn id(x : t) -> t { x } - .. code-block:: ocaml (* OCaml *) type ('a, 'b) pair = 'a * 'b (* val id : 't -> 't *) let id x = x - .. code-block:: haskell {- Haskell -} type Pair a b = (a, b) id :: t -> t id x = x Algebraic data types: .. list-table:: :widths: 33 33 33 * - .. code-block:: rust // Rust enum Option { None, Some(T) } // x : Option match x { None => false, Some(_) => true } - .. code-block:: ocaml (* OCaml *) type 't option = None | Some of 't (* x : t option *) match x with | None -> false | Some _ -> true - .. code-block:: 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-block:: 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-block:: 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-block:: 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-block:: 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-block:: 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-block:: rust // Rust enum Peano { Zero, Succ(Box) } - .. code-block:: 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-block:: 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-block:: 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-block:: rust // Rust trait PartialEq { fn eq(&self, other:&Self) -> bool; fn ne(&self, other:&Self) -> bool { !self.eq(other) } } - .. code-block:: 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-block:: rust // Rust // the following expression: [