Implementing Nat in Rust (a la Haskell)

The power of Algebraic Data Types comes to the fore when dealing with complex problem domains. Most modern languages tend towards supporting some form of ADTs, but the complexity of expressing such paradigms is not completely lost when compared to languages that were designed with such support in mind.

Case in point – defining the prototypical example of an algebraic data type, defining the Natural Number type (Nat). Let’s compare the naive implementation in two languages that do have varying support for ADTs – Haskell, and Rust.

First, the Haskell version. Haskell, just like ML and other members of this family, is eminently suited for describing such types almost effortlessly:

module NatDemo where

import Test.HUnit

data Nat = Zero | Succ Nat deriving (Show, Eq)

nat2int :: Nat -> Int
nat2int Zero = 0
nat2int (Succ n) = 1 + nat2int n

int2nat :: Int -> Nat
int2nat 0 = Zero
int2nat n = Succ (int2nat (n-1))

add :: Nat -> Nat -> Nat
add Zero n = n
add (Succ m) n = Succ (add m n)


-- test cases
test1 = TestCase (assertEqual "nat to int" (nat2int (Succ (Succ Zero))) 2)
test2 = TestCase (assertEqual "int to nat" (int2nat 5) (Succ (Succ (Succ (Succ (Succ Zero))))))
test3 = TestCase (assertEqual "add two nats" (add (int2nat 5) (int2nat 6)) (int2nat 11))

tests = TestList [test1, test2, test3]

run = runTestTT tests

Running it to confirm:


Macushla:Nat-in-Rust z0ltan$ ghci
GHCi, version 8.0.2: http://www.haskell.org/ghc/  😕 for help
Loaded GHCi configuration from /Users/z0ltan/.ghci

Prelude> :l Nat.hs
[1 of 1] Compiling NatDemo          ( Nat.hs, interpreted )
Ok, modules loaded: NatDemo.

*NatDemo> run
Cases: 3  Tried: 3  Errors: 0  Failures: 0
Counts {cases = 3, tried = 3, errors = 0, failures = 0}

As can be seen, it’s almost trivial to define the Nat type in Haskell, as well as write functions that operate on this type. It reads almost exactly like the mathematical version of the concept. Simply beautiful.

Now let’s show the Rust version first, and then perhaps a comment or two on the implementation.

#[derive(Debug, PartialEq)]
enum Nat {
    Zero,
    Succ(Box<Nat>),
}

/// open it up for code readability
use Nat::{Zero, Succ};

fn nat_to_int(n: Nat) -> i32 {
    match n {
        Zero => 0,
        Succ(n) => 1 + nat_to_int(*n),
    }
}


fn int_to_nat(n: i32) -> Nat {
    match n {
        0 => Zero,
        n => Succ(Box::new(int_to_nat(n-1))),
    }
}


fn add(m: Nat, n: Nat) -> Nat {
    match (m, n) {
        (Zero, n) => n,
        (Succ(m), n) => Succ(Box::new(add(*m, n))),
    }
}

fn main() {
    assert_eq!(nat_to_int(Succ(Box::new(Succ(Box::new(Succ(Box::new(Zero))))))), 3);
    assert_eq!(int_to_nat(5), Succ(Box::new(Succ(Box::new(Succ(Box::new(Succ(Box::new(Succ(Box::new(Zero)))))))))));
    assert_eq!(add(int_to_nat(5), int_to_nat(11)), int_to_nat(16));
}

Let’s make sure that it’s all in working condition:

Macushla:Nat-in-Rust z0ltan$ rustc nat.rs && ./nat
Macushla:Nat-in-Rust z0ltan$

Excellent! It all just works. However, a couple of points to notice – first of all, because Rust doesn’t really have a runtime, we need to wrap the recursive part in a Box (amongst other choices) so that the compiler knows what size the data is (a box, being a pointer, is of a fixed size determinable at compile time). Of course, the test code is positively ghastly because we have to wrap all calls with Box::new, not to mention to remember to dereference the boxed value inside the functions.

Secondly, the code is surprisingly clean for the most part. However, writing the code in not nearly as intuitive as writing the same in Haskell (or ML for that matter). I can only imagine how much more daunting the task would be in a language without pattern matching (amongst other higher-level features) such as Java. Of course we would make it work, but the distance between the intent of the code and the code itself would be much much higher. Syntax does matter, folks!

Well, that was a nice little experiment of an evening.

Advertisements
Implementing Nat in Rust (a la Haskell)

Mutual Recursion demo in Rust and Racket (inspired by Haskell)

This is a quick post on a Rust version of the Haskell evens and odds program demonstrating mutual recursion (as shown in Hutton’s book).

First off, the Haskell code:

  evens :: [a] -> [a]
  evens [] = []
  evens (x:xs) = x : odds xs

  odds :: [a] -> [a]
  odds [] = []
  odds (_:xs) = evens xs

A sample run:

*Main> let string = "abcde"
*Main> evens string
"ace"
*Main> odds string
"bd"
*Main> string
"abcde"

So the whole ideas is to have the evens functions display all the characters in even positions (starting from 0), and then odds function likewise display all the characters in odd positions.

The evens function acts as the actual accumulator whilst odds is only used as a trampoline for continuing the recursion.

Now, for a rough Rust version of it (preserving the original character array):


fn main() {
    fn evens<T: Copy>(xs: &[T]) -> Vec<T> {
        if xs.is_empty() {
            Vec::new()
        } else {
            cons(&xs[0], &odds(&xs[1..]))
        }
    }

    fn odds<T: Copy>(xs: &[T]) -> Vec<T> {
        if xs.is_empty() {
            Vec::new()
        } else {
            evens(&xs[1..])
        }
    }

    fn cons<T: Copy>(x: &T, xs: &[T]) -> Vec<T> {
        let mut vec = Vec::new();

        vec.push(*x);

        for e in xs.iter() {
            vec.push(*e);
        }
        vec
    }

    let string = String::from("abcde");

    println!("{}",
             String::from_utf8(evens(&string.clone().into_bytes())).unwrap());
    println!("{}",
             String::from_utf8(odds(&string.clone().into_bytes())).unwrap());

    println!("{}", string);
}

And a quick run:

Macushla:EvensAndOdds z0ltan$ rustc evens_and_odds.rs
Macushla:EvensAndOdds z0ltan$ ./evens_and_odds
ace
bd
abcde

So, as can be clearly seen, the original string is left unmodified. Of course this version looks quite dirty, but the nice bit is that &[T] accepts parameters of type Vec (or reference variants) and vice-versa. This enables using slicing extensively and naturally inside the functions. The vector copying code could, of course, be made to work with an API call, but I feel this is much better in its explicit form.

The Racket version looks much nicer, being more amenable to functional constructs than Rust:

#lang racket

(define (evens xs)
  (if (null? xs)
      '()
      (cons (car xs) (odds (cdr xs)))))

(define (odds xs)
  (if (null? xs)
      '()
      (evens (cdr xs))))

(define (main)
  (let ([string "abcde"])
    (displayln (list->string (evens (string->list string))))
    (displayln (list->string (odds (string->list string))))
    (displayln string)))

And a final run for the Racket version:

evens-and-odds.rkt> (main)
ace
bd
abcde
Mutual Recursion demo in Rust and Racket (inspired by Haskell)

A bit of play with Rust macros

Here are a couple of macros that I wrote up on a slow evening. The first one provides a nice literal way of creating maps, and the second one mimicks Haskell’s list comprehension syntax in a rather crude manner.

My aim originally had been to:

  • have a simple if-then-else structure created in Rust, something like so:
    fn main() {
      let res = if 2 > 3 then "Yes" else "No";
    }
    

    However, this did not appear to be possible with the current macro support in Rust since a fragment of type expr (expression) can be followed only by the following sigils –=> ; ,. So much for that.

  • and secondly, to be able to replicate Haskell’s list comprehension syntax in its entirety, allowing for any possible generator. However, I then realised that Rust’s macro system also did not support actual evaluation of code during expansion like Common Lisp or Scheme/Racket does, even though it does work on the actual AST and not merely text. So out that went through the window as well.

So here’s the first macro demo:

use std::collections::HashMap;

macro_rules! my_map {
    ($($key: expr => $val: expr)*) => {
        {
            let mut map = HashMap::new();

            $(
                map.insert($key, $val);
            )*

          map
        }
    };
}

fn main() {
    let my_map = my_map!{
        1 => "One"
        2 => "Two"
        3 => "Three"
        4 => "Four"
        5 => "Five"
    };

    println!("{:?}", my_map);
}

Nothing fancy here, but you must say that it does look nicer, almost Ruby-esque! Here’s the code run:

Macushla:List_Comprehension_Macro z0ltan$ ./map
{2: "Two", 1: "One", 3: "Three", 5: "Five", 4: "Four"}

And here’s the poor man’s list comprehension that is not only limited in scope, but also entirely inflexible in its syntax (I just couldn’t be bothered tinkering with it for little return):

macro_rules! compr {
    ($id1: ident | $id2: ident <- [$start: expr ; $end: expr] , $cond: expr) => {
        {
            let mut vec = Vec::new();

            for num in $start..$end + 1 {
                if $cond(num) {
                    vec.push(num);
                }
            }

            vec
        }  
    };
}

fn even(x: i32) -> bool {
    x%2 == 0
}

fn odd(x: i32) -> bool {
    x%2 != 0
}

fn main() {
    let evens = compr![x | x <- [1;10], even];
    println!("{:?}", evens);

    let odds = compr![y | y <- [1;10], odd];
    println!("{:?}", odds);
}

As you can see, the ident fragments are completely for show, I cannot use .. in the generator (again due to restrictions on what can follow a expr fragment), and the guards don’t even check against the supposed identifier that’s supposed to be collecting the results into the final list/vector! Anyway, here’s the code run output:

Macushla:List_Comprehension_Macro z0ltan$ rustc list_compr.rs
Macushla:List_Comprehension_Macro z0ltan$ ./list_compr
[2, 4, 6, 8, 10]
[1, 3, 5, 7, 9]

Not too shabby, eh? In all seriousness though, while Rust’s macros are a big improvement over the debacle that is C’s macro system, the surface similarities to Racket’s powerful macro system ends right there – on the surface. As it stands now, there are far too many restrictions on the macro system for it to be considered a viable way of extending the syntax of the language, or even creating new languages (as in the Racket world).

EDIT: The list comprehension macro can actually be improved by using tt for the start and end of the range – this also allows .. to be used much in the Haskell way. Moreover, now we can actually simulate the exact Haskell syntax (for this very specific case, of course), and also make use of the identS as well.

Here’s the new code, but I’m keeping the old code up to remind myself that I can be a doddering idiot at times!

Updated macro:

macro_rules! compr {
    ($id1:ident | $id2:ident <- [$start:tt..$end:tt] , $cond:tt $id3:ident) => {
        {
            let mut vec = Vec::new();
 
            for $id1 in $start..$end + 1 {
                if $cond($id3) {
                    vec.push($id2);
                }
            }
 
            vec
        }  
    };
}
 
fn even(x: i32) -> bool {
    x%2 == 0
}
 
fn odd(x: i32) -> bool {
    x%2 != 0
}
 
fn main() {
    let evens = compr![x | x <- [1..10], even x];
    println!("{:?}", evens);
 
    let odds = compr![y | y <- [1..10], odd y];
    println!("{:?}", odds);
}

And a run just to make sure it’s working:

Macushla:List_Comprehension_Macro z0ltan$ rustc list_compr.rs
Macushla:List_Comprehension_Macro z0ltan$ ./list_compr
[2, 4, 6, 8, 10]
[1, 3, 5, 7, 9]

That’s much better!

A bit of play with Rust macros

A quick comparison of Euclid’s Algorithm in Haskell, Rust, and D

I recently procured a copy of Graham Hutton’s most excellent book, “Programming in Haskell” (2nd Edition). I had earlier worked through the first edition, and that is the book that really opened my eyes to the power of Haskell! Having become a bit rusty with my Haskell, I decided to work through the second edition book (which is considerably larger and more comprehensive). As part of that exercise, I decided to use a lazy weekend afternoon to code up Euclid’s GCD Algorithm in Haskell, Rust and in D. Just for a quick visual comparison of how the languages look. Here’s how they look:

First off, the Haskell version, which is the best looking one in my opinion:

Macushla:Playground z0ltan$ cat Euclid.hs
module Main where

euclid :: Int -> Int -> Int
euclid m n | m <= 0 && n <= 0 = error "GCD works for positive numbers only"
           | m == n = m
           | m < n = euclid m (n-m)
           | otherwise = euclid (m-n) n

main :: IO ()
main = do putStrLn "Enter the first number: "
          x <- getLine
          putStrLn "Enter the second number: "
          y <- getLine
          let x' = read x :: Int
          let y' = read y :: Int

          putStrLn $ "The GCD of " ++ x
                     ++ " and " ++ y
                     ++ " is " ++ show (euclid x' y')

Macushla:Playground z0ltan$ ghc Euclid.hs
[1 of 1] Compiling Main             ( Euclid.hs, Euclid.o )
Linking Euclid ...
Macushla:Playground z0ltan$ ./Euclid
Enter the first number:
12
Enter the second number:
18
The GCD of 12 and 18 is 6

Here’s the Rust version (a bit uglier, but the Pattern Matching is quite nice):

Macushla:Playground z0ltan$ cat euclid.rs
use std::io;
use std::str::FromStr;
use std::cmp::Ordering;

fn get_number(prompt: &str) -> u32 {
    println!("{}", prompt);

    let mut input = String::new();

    io::stdin().read_line(&mut input)
        .expect("no input!");

    u32::from_str(input.trim()).unwrap()
}

fn main() {
    let x = get_number("Enter the first number: ");
    let y = get_number("Enter the second number: ");

    println!("The GCD of {} and {} is {}", x, y, euclid(x, y));
}

fn euclid(m: u32, n: u32) -> u32 {
    assert!(m > 0 && n > 0);

    match m.cmp(&n) {
        Ordering::Equal => m,
        Ordering::Less => euclid(m, n-m),
        Ordering::Greater => euclid(m-n, n),
        }
}
Macushla:Playground z0ltan$ rustc euclid.rs && ./euclid
Enter the first number:
12
Enter the second number:
18
The GCD of 12 and 18 is 6

And finally, here is the D version – clean, succinct, and a pleasure to read as always:

Macushla:Playground z0ltan$ cat euclid.d
import std.stdio: readln, writeln, writefln;

uint get_number(string prompt) {
    writeln(prompt);

    import std.conv: to;
    import std.string: chomp;

    return readln().chomp().to!(uint);
}

void main() {
    uint x = get_number("Enter the first number: ");
    uint y = get_number("Enter the second number: ");

    writefln("The GCD of %s and %s is %s", x, y, euclid(x, y));
}

uint euclid(uint m, uint n) {
    assert(m > 0 && n > 0);

    if (m < n) {
        return euclid(m, n-m);
    } else if (m == n) {
        return m;
    } else {
        return euclid(m-n, n);
    }
}
Macushla:Playground z0ltan$ dmd -run euclid.d
Enter the first number:
12
Enter the second number:
18
The GCD of 12 and 18 is 6

One thing is for sure. Aside from syntactic differences, most modern languages are all converging in terms of paradigms and features. Hell, even keeping languages like Haskell and Idris aside, most mainstream languages are also converging on the syntactical front! Anyway, this was a fun little exercise on a slow afternoon. I personally like the Haskell version best , followed by the D version, and then finally the Rust version (ruined by the somewhat ugly I/O syntax). What do you think?

A quick comparison of Euclid’s Algorithm in Haskell, Rust, and D

A simple Tree data structure in Haskell

This is part of my attempt to learn Haskell in a proper manner. I have been on and off learning Haskell for quite a few years now, always getting interrupted for some reason. This time, I decided to bite the bullet and get on with it!

As part of that, I started off with my favourite Haskell textbook, Professor Graham Hutton’s “Programming in Haskell”, 2nd Edition. This is arguably THE book that opened my eyes to Functional Programming in general. This book is almost perfect with one small flaw, in my opinion, of course. The bottom-up approach of solving problems is excellent, but it would have been rather nice if a small synopsis of the problem and the proposed approach were given at the beginning instead of having to read the whole code to understand it.

Having finished around half of that book, I realised that it was a bit short on examples, problems, and the downright dirty parts of Haskell, introducing IO only around the middle of the book. That’s when I decided to go for Allen and Moronuki’s book, “Haskell Programming from First Principles” to get up to speed on actual real-world programming in Haskell. The first few chapters are extremely basic (and I do find the tone a bit too prescriptive and pedantic, but that should suit a complete beginner just fine. For practice and hands-on though, it is a most excellent resource.

As part of my reboot of Haskell, I decided to implement a small Tree data structure in Haskell, all with the express aim of getting rid of the cobwebs. I can’t say that I’m too happy with my first attempt even though it clearly works more or less as expected. It feels very rough and creaky and the Null vs Leaf issue is pretty irritating as well. Well, after some more practice, I should be able to start iterating on better versions!

For now, here’s the code. It’s pretty much self-explanatory. The basic Tree type (single type parameter for now!), a helper function to create a Binary Search Tree (easier to confirm the output using preorder traversal), and the three standard binary tree traversal algorithms.

{- A binary tree implementation -}

data Tree a = Null | Leaf a | Node (Tree a) a (Tree a)  deriving Show


createNode :: a -> Tree a
createNode value = Leaf value 


addNode :: (Ord a) => Tree a -> a -> Tree a
addNode tree value = case tree of
                        Null -> createNode value
                        Leaf x -> if value <= x then
                                    Node (createNode value) x Null
                                  else
                                    Node Null x (createNode value)
                        Node l n r -> if value <= n then
                                        Node (addNode l value) n r
                                      else
                                        Node l n (addNode r value)

makeBST :: Ord a => [a] -> Tree a
makeBST [] = Null  
makeBST (n:ns) = addNode (makeBST ns) n
                     


-- inorder traversal (left, root, right)
inorder :: Tree a -> [a]
inorder tree = case tree of
                 Null -> []
                 Leaf x -> [x]
                 Node l n r -> inorder l ++ [n] ++  inorder r


-- preorder traversal (root, left, right)
preorder :: Tree a -> [a]
preorder tree = case tree of
                  Null -> []
                  Leaf x -> [x]
                  Node l n r -> [n] ++ preorder l ++ preorder r


-- postorder traversal (left, right, root)
postorder :: Tree a -> [a]
postorder tree = case tree of
                   Null -> []
                   Leaf x -> [x]
                   Node l n r -> postorder l ++ postorder r ++ [n]

A sample run:

*Main> let bst = makeBST [10,18,12,7,10,11,3,4,4,-2,-3,100]
*Main> bst
Node (Node Null (-3) (Node Null (-2) (Node (Node (Leaf 3) 4 Null) 4 (Node (Node (Node Null 7 (Leaf 10)) 10 Null) 11 (Node Null 12 (Leaf 18)))))) 100 Null
*Main> inorder bst
[-3,-2,3,4,4,7,10,10,11,12,18,100]
*Main> preorder bst
[100,-3,-2,4,4,3,11,10,7,10,12,18]
*Main> postorder bst
[3,4,10,7,10,18,12,11,4,-2,-3,100]
*Main> 

Ah well, it’s quite exciting to see something working as expected, isn’t it? Well, onwards then with Haskell (and then on to Agda and Idris, which I am very much interested in for edificational purposes!)

A simple Tree data structure in Haskell