# 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, &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
```