Exercises

Random Rust exercises. Mostly typesystem-oriented.

Warning if you're viewing this not on github.io: this is a live-edited website, errors and accidental spoilers are to be expected.

Solutions

Presently, solutions are often provided in a non-human-readable (compacted+misformatted) form as hidden code. Those are intended for testing that the exercise is even possible to solve.

#![allow(unused)]
fn main() {
/*
fn fix_me() {  // Greyed out because the solution changes this line.
*/
fn fixed_name() {
}

fn do_not_change_this() {
    fixed_name()
}
}

Some exercises may not have the replaced parts greyed out:

#![allow(unused)]
fn main() {
mod __ {
fn fix_me() {
}
}
fn fixed_name() {
}

fn do_not_change_this() {
    fixed_name()
}
}

Chapter 1: Strict Tests

bind

Make this compile and pass tests:

#![allow(unused)]
fn main() {
mod __ {
fn bind<T, F: Fn(T) -> Option<T>>(f: F, fa: Option<T>) -> Option<T> {
    match fa {
        Some(a) => f(a),
        None => None,
    }
}
}
fn bind<T, F: FnOnce(T) -> Option<T>>(f: F, fa: Option<T>) -> Option<T> { fa.and_then(f) }

// don't change anything below

assert_eq!(bind(|x: i32| Some(x + 3), Some(2)), Some(5));
assert_eq!(bind(|x: i32| Some(x + 3), None), None);
assert_eq!(bind(|_: i32| None, Some(2)), None);
assert_eq!(bind(|_: i32| None, None), None);

assert_eq!(bind(|x: &str| Some(x), Some("apple")), Some("apple"));
assert_eq!(bind(|_: &str| Some("banana"), Some("apple")), Some("banana"));

let banana = "banana".to_string();
assert_eq!(
    bind(|_: String| Some(banana), Some("apple".to_string())),
    Some("banana".to_string()),
);
}

Try solving it in the playground:

fn bind<T, F: Fn(T) -> Option<T>>(f: F, fa: Option<T>) -> Option<T> {
    match fa {
        Some(a) => f(a),
        None => None,
    }
}

fn main() {
    assert_eq!(bind(|x: i32| Some(x + 3), Some(2)), Some(5));
    assert_eq!(bind(|x: i32| Some(x + 3), None), None);
    assert_eq!(bind(|_: i32| None, Some(2)), None);
    assert_eq!(bind(|_: i32| None, None), None);

    assert_eq!(bind(|x: &str| Some(x), Some("apple")), Some("apple"));
    assert_eq!(bind(|_: &str| Some("banana"), Some("apple")), Some("banana"));

    let banana = "banana".to_string();
    assert_eq!(
        bind(|_: String| Some(banana), Some("apple".to_string())),
        Some("banana".to_string()),
    );
}

bind, but with references

Make this compile and pass tests:

#![allow(unused)]
fn main() {
mod __ {
fn refbind<T, F: Fn(&T) -> Option<&T>>(f: F, fa: Option<&T>) -> Option<&T> {
    match fa {
        Some(a) => f(a),
        None => None,
    }
}
}
fn refbind<'a,'b,T:'a+?Sized>(f:impl 'a+Fn(&'a T)->Option<&'b T>,fa:Option<&'a T>)->Option<&'b T>{fa.and_then(f)}

// don't change anything below

let apple = "apple".to_string();
let banana = "banana".to_string();
assert_eq!(
    refbind(|_: &String| Some(&banana), Some(&apple)),
    Some(&banana)
);

let banana = "banana";
assert_eq!(
    refbind(|_: &str| Some(banana), Some("apple")),
    Some(banana)
);
}

Try solving it in the playground:

fn refbind<T, F: Fn(&T) -> Option<&T>>(f: F, fa: Option<&T>) -> Option<&T> {
    match fa {
        Some(a) => f(a),
        None => None,
    }
}

fn main() {
    let apple = "apple".to_string();
    let banana = "banana".to_string();
    assert_eq!(
        refbind(|_: &String| Some(&banana), Some(&apple)),
        Some(&banana)
    );

    let banana = "banana";
    assert_eq!(
        refbind(|_: &str| Some(banana), Some("apple")),
        Some(banana)
    );
}

const Add?

Define FIVE_SECONDS as const:

#![allow(unused)]
fn main() {
use std::time::Duration;
const fn unwrap<T: Copy>(o: Option<T>) -> T { match o { Some(t) => t, None => panic!() } }
const TWO_SECONDS: Duration = Duration::from_secs(2);
/*
const FIVE_SECONDS: Duration = TWO_SECONDS + Duration::from_secs(3);
*/
const FIVE_SECONDS: Duration = unwrap(TWO_SECONDS.checked_add(Duration::from_secs(3)));
assert_eq!(FIVE_SECONDS, Duration::from_secs(5));
}

Try solving it in the playground:

use std::time::Duration;

const TWO_SECONDS: Duration = Duration::from_secs(2);
const FIVE_SECONDS: Duration = TWO_SECONDS + Duration::from_secs(3);

fn main() {
    assert_eq!(FIVE_SECONDS, Duration::from_secs(5));
}

From<&T>

Make this compile and pass tests:

#![allow(unused)]
fn main() {
fn with_slice<T>(f: impl FnOnce(&str) -> T) -> T {
    let s = "te".to_string() + "st";
    f(&s)
}

pub trait FromRef<T: ?Sized>: for<'a> From<&'a T> { fn from_ref(value: &T) -> Self { Self::from(value) } }
impl<T: ?Sized, U: for<'a> From<&'a T>> FromRef<T> for U {}
let string = with_slice(
/*
    String::from
*/ String::from_ref
);
assert_eq!(string, "test".to_string());
}

Try solving it in the playground:

fn with_slice<T>(f: impl FnOnce(&str) -> T) -> T {
    f("test")
}

fn main() {
    let string = with_slice(
        String::from // Change this
    );
    assert_eq!(string, "test".to_string());
}

Blanket, blanket, blanket

Make this compile with the following restrictions:

• Can't edit definitions of A, test, test1, test2; can only add code outside of those items.
• Some types are A1 but not A2.
• Some types are A2 but not A1.
• Some types are A but not A2.
• Some types are A but not A1.
• A1 doesn't know about/depend on A2.
• A2 doesn't know about/depend on A1.
• A1 doesn't know about/depend on A.
• A2 doesn't know about/depend on A.

#![allow(unused)]
fn main() {
trait A {
    fn a_ref(&self) -> u64;
    fn a_mut(&mut self) -> bool;
    fn a_move(self) -> Self;
}

fn test(x: impl A) {
    x.a_ref();
    let mut x = x.a_move();
    x.a_mut();
}

fn test1(x: impl A1) {
    test(x)
}

fn test2(x: impl A2) {
    test(x)
}
use std::marker::PhantomData;
trait Wrapper<T>: Sized {}
#[repr(transparent)]
struct Wrapped<T, V: ?Sized>(PhantomData<V>, T);
trait AProxy {
type T;
fn ap_ref(t: &Self::T) -> u64;
fn ap_mut(t: &mut Self::T) -> bool;
fn ap_move(t: Self::T) -> Self::T;
}
trait AWrapper: Wrapper<Self::AWrapped> { type AWrapped; }
impl<T: AWrapper> A for T where T::AWrapped: AProxy<T = T> {
fn a_ref(&self) -> u64 { <T::AWrapped as AProxy>::ap_ref(self) }
fn a_mut(&mut self) -> bool { <T::AWrapped as AProxy>::ap_mut(self) }
fn a_move(self) -> Self { <T::AWrapped as AProxy>::ap_move(self) }
}
trait A1: AWrapper<AWrapped = Aw1<Self>> {
fn a1_ref(&self) -> u64;
fn a1_mut(&mut self) -> bool;
fn a1_move(self) -> Self;
}
trait A2: AWrapper<AWrapped = Aw2<Self>> {
fn a2_ref(&self) -> u64;
fn a2_mut(&mut self) -> bool;
fn a2_move(self) -> Self;
}
struct Av1;
struct Av2;
type Aw1<T> = Wrapped<T, Av1>;
type Aw2<T> = Wrapped<T, Av2>;
impl<T: ?Sized + A1> AProxy for Aw1<T> {
type T = T;
fn ap_ref(t: &Self::T) -> u64 { t.a1_ref() }
fn ap_mut(t: &mut Self::T) -> bool { t.a1_mut() }
fn ap_move(t: Self::T) -> Self::T { t.a1_move() }
}
impl<T: ?Sized + A2> AProxy for Aw2<T> {
type T = T;
fn ap_ref(t: &Self::T) -> u64 { t.a2_ref() }
fn ap_mut(t: &mut Self::T) -> bool { t.a2_mut() }
fn ap_move(t: Self::T) -> Self::T { t.a2_move() }
}
}

You may assume that A, A1, A2 can be in separate crates with a dependency graph equivalent to this:

#![allow(unused)]
fn main() {
mod __ {
mod a1 {
    pub trait A1 { /* ... */ }
    /* ... */
}

mod a2 {
    pub trait A2 { /* ... */ }
    /* ... */
}

mod a {
    use super::{a1, a2};
    pub trait A { /* ... */ }
    /* ... */
}

mod external {
    use super::{a::A, a1::A1, a2::A2};
    fn test(x: impl A) { /* ... */ }
    fn test1(x: impl A1) { /* ... */ }
    fn test2(x: impl A2) { /* ... */ }
}
}
}

Template for a workspace:

# Cargo.toml
[workspace]
members = ["a", "a1", "a2", "common"]

[workspace.package]
version = "0.0.1"
edition = "2021"
publish = false

[package]
name = "solution"
version.workspace = true
edition.workspace = true
publish.workspace = true

[dependencies]
a.path = "a"
a1.path = "a1"
a2.path = "a2"
common.path = "common"

# a/Cargo.toml
[package]
name = "a"
version.workspace = true
edition.workspace = true
publish.workspace = true

[dependencies]
a1.path = "../a1"
a2.path = "../a2"
common.path = "../common"

# a1/Cargo.toml
[package]
name = "a1"
version.workspace = true
edition.workspace = true
publish.workspace = true

[dependencies]
common.path = "../common"

# a2/Cargo.toml
[package]
name = "a2"
version.workspace = true
edition.workspace = true
publish.workspace = true

[dependencies]
common.path = "../common"

# common.Cargo.toml
[package]
name = "common"
version.workspace = true
edition.workspace = true
publish.workspace = true

Basic definitions for A1/A2 (this won't work — you need to alter it)

trait A1 {
    fn a1_ref(&self) -> u64;
    fn a1_mut(&mut self) -> bool;
    fn a1_move(self) -> Self;
}

trait A2 {
    fn a2_ref(&self) -> u64;
    fn a2_mut(&mut self) -> bool;
    fn a2_move(self) -> Self;
}

Introducing variance to objects

Make test_covariance compile by making BoolStream<'a> covariant over 'a. Restrictions:

• Can only change implementation details of BoolStream and its methods and add extra items outside of what's given, i.e. no signature/test change.
• Changed version must behave the same way as the original.

Consider the following code:

#![allow(unused)]
fn main() {
pub struct BoolStream<'a>(
    Box<dyn 'a + FnOnce() -> (bool, BoolStream<'a>)>,
);

impl<'a> BoolStream<'a> {
    pub fn new(f: impl 'a + FnOnce() -> (bool, Self)) -> Self {
        Self(Box::new(f))
    }

    pub fn next(self) -> (bool, Self) {
        self.0()
    }
}

fn test_covariance<'a: 'b, 'b>(e: BoolStream<'a>) -> BoolStream<'b> {
    e
}
}

Why does it fail to compile?

#![allow(unused)]
fn main() {
pub struct BoolStream<'a>(
    // change this
/*
    Box<dyn 'a + FnOnce() -> (bool, BoolStream<'a>)>,
*/ Box<dyn 'a + Next>
);

impl<'a> BoolStream<'a> {
    pub fn new(f: impl 'a + FnOnce() -> (bool, Self)) -> Self {
        // maybe change this
/*
        Self(Box::new(f))
*/ Self(Box::new(Wrapper(f, PhantomData)))
    }

    pub fn next(self) -> (bool, Self) {
        // maybe change this
/*
        self.0()
*/ self.0.next()
    }
}

fn test_covariance<'a: 'b, 'b>(e: BoolStream<'a>) -> BoolStream<'b> {
    e
}

use std::marker::PhantomData;
struct Wrapper<'a, F>(F, PhantomData<&'a ()>);
trait Next {
fn next<'t>(self: Box<Self>) -> (bool, BoolStream<'t>) where Self: 't;
}
impl<'a, F: 'a + FnOnce() -> (bool, BoolStream<'a>)> Next for Wrapper<'a, F> {
fn next<'t>(self: Box<Self>) -> (bool, BoolStream<'t>) where Self: 't { self.0() }
}

/// Tests to check that behaviour stays the same.

fn get_true<'a>() -> BoolStream<'a> {
    BoolStream::new(|| (true, get_false()))
}

fn get_false<'a>() -> BoolStream<'a> {
    BoolStream::new(|| (false, get_true()))
}

let e = get_true();
let (x, e) = e.next();
assert!(x);
let (x, e) = e.next();
assert!(!x);
let (x, e) = e.next();
assert!(x);
let (x, e) = e.next();
assert!(!x);
test_covariance(e);
}

Owned Chars

Chars but keeping a strong reference (Rc) to the string.

#![allow(unused)]
fn main() {
mod rcchars { pub struct RcChars { rc: std::rc::Rc<String>, index: usize }
impl Iterator for RcChars { type Item = char; fn next(&mut self) -> Option<Self::Item> {
let s = self.rc.get(self.index..)?; let c = s.chars().next()?; self.index += c.len_utf8(); Some(c)
} } impl RcChars { pub fn from_rc(rc: std::rc::Rc<String>) -> Self { Self { rc, index: 0 } } }
impl From<std::rc::Rc<String>> for RcChars { fn from(value: std::rc::Rc<String>) -> Self { Self::from_rc(value) } }
} use {std::rc::Rc, rcchars::RcChars};
{
    let rc = Rc::new("abc".to_string());
    let rcc = RcChars::from(rc.clone());
    drop(rc);
    assert_eq!(rcc.collect::<Vec<_>>(), ['a', 'b', 'c']);
}
{
    let rc = Rc::new("abc".to_string());
    let rcc = RcChars::from(rc);
    let rcc = Box::new(rcc);
    assert_eq!(rcc.collect::<Vec<_>>(), ['a', 'b', 'c']);
}
}

Solutions

• The one in hidden code (slightly compacted).
• Implementation used in rattlescript.
• Same solution but with some extra comments.
• Another solution. I prefer this one.
• There's an even simpler version that even an AI can generate (don't do that for unsafe code in production), but I dislike it for several reasons, even though it's mostly sound.

Async to_string

Define the AsyncToString trait to make this compile and pass tests (don't edit existing code):

#![allow(unused)]
fn main() {
extern crate futures;
use futures::{Future, executor::block_on};
trait AsyncToStringRef<'a>: Fn(&'a str) -> Self::F { type F: 'a + Future<Output = String>; }
impl<'a, F: 'a + Future<Output = String>, T: Fn(&'a str) -> F> AsyncToStringRef<'a> for T { type F = F; }
trait AsyncToString: for<'a> AsyncToStringRef<'a> {}
impl<T: for<'a> AsyncToStringRef<'a>> AsyncToString for T {}
async fn test_generic(s: &str, f: impl AsyncToString) -> String {
    f(s).await
}

async fn to_string_async(s: &str) -> String {
    s.to_string()
}

async fn test_concrete(s: &str) -> String {
    test_generic(s, to_string_async).await
}

assert_eq!(block_on(test_concrete("abc")), "abc".to_string())
}

Get Functions

Edit the body of get_functions to make this compile and pass tests:

#![allow(unused)]
fn main() {
struct Functions {
    five: fn() -> i32,
    increment: fn(i32) -> i32,
}

fn get_functions<const STEP: i32>() -> &'static Functions {
/*
    let five = || 5;
    let increment = |n| n + STEP;
    let functions = Functions { five, increment };
    &functions
*/
&Functions { five: || 5, increment: |n| n + STEP }
}

assert_eq!((get_functions::<1>().five)(), 5);
assert_eq!((get_functions::<3>().five)(), 5);
assert_eq!((get_functions::<1>().increment)(4), 5);
assert_eq!((get_functions::<3>().increment)(4), 7);
}

Try solving it in the playground:

struct Functions {
    five: fn() -> i32,
    increment: fn(i32) -> i32,
}

fn get_functions<const STEP: i32>() -> &'static Functions {
    let five = || 5;
    let increment = |n| n + STEP;
    let functions = Functions { five, increment };
    &functions
}

fn main() {
    assert_eq!((get_functions::<1>().five)(), 5);
    assert_eq!((get_functions::<3>().five)(), 5);
    assert_eq!((get_functions::<1>().increment)(4), 5);
    assert_eq!((get_functions::<3>().increment)(4), 7);
}

Linked

Fix (many) errors to make this compile and pass tests:

#![allow(unused)]
fn main() {
#[derive(Clone, Copy)]
struct Node<'a> {
    next: Option<&'a Self>,
    value: &'a str,
}

struct Linked<'a, F> {
    node: Node<'a>,
    callback: &'a mut F,
}

impl<'a, F: FnMut(String)> Linked<'a, F> {
fn __() { mod __ {
struct Node<'a> { next: Option<Box<Self>>, value: &'a str }
struct Linked<'a, F> { node: Box<Node<'a>>, callback: &'a mut F }
impl<F> Linked<'_, F> {
    fn with(&mut self, value: &str) -> Linked<'_, F> {
unimplemented!() } fn with2(self) { let _ =
        Self {
            node: Node {
                next: Some(self.node),
value: unimplemented!(), }.into(), callback: self.callback, }; } } } }
fn with<'b>(&'b mut self, value: &'b str) -> Linked<'b, F> {
Linked {
node: Node {
next: Some(&self.node),
                value,
            },
            callback: self.callback,
        }
    }

    fn call(&mut self) {
        let mut node = self.node;
        let mut value = node.value.to_string();
        while let Some(next) = node.next {
            value += next.value;
impl<'a, F: FnMut(String)> Linked<'a, F> { fn ___(&mut self) { trait Callback { fn callback(&mut self, value: String); }
impl<'a, F: FnMut(String)> Callback for Linked<'a, F> { fn callback(&mut self, value: String) { (self.callback)(value); } }
{ let mut node = 1; let next = 2;
            node = next;
        }
let value = unimplemented!();
        self.callback(value);
} }
node = *next; }
(self.callback)(value);
    }
}

// don't change anything below

let mut vec = vec![];

let s = "0".to_string();

let mut linked = Linked {
    node: Node { next: None, value: &s },
    callback: &mut |value| vec.push(value),
};

// why does removing code below cause the instantiation to fail?

linked.call();
{
    let s = "1".to_string();
    let mut linked = linked.with(&s);
    linked.with("2").call();
    linked.with("3").call();
}
linked.with("4").call();

assert_eq!(vec, ["0", "210", "310", "40"]);
}

Calculating with Functions (based on Codewars)

Original: Calculating with Functions

As you might know, on stable Rust you can't have variable number of arguments passed to a function. However we can alter the exercise to work anyway.

#![allow(unused)]
fn main() {
trait Value { fn value(self) -> i32; }
trait Op { fn apply(self, value: i32) -> i32; }
struct Identity;
impl Op for Identity { fn apply(self, value: i32) -> i32 { value } }
impl<F: FnOnce(i32) -> i32> Op for F { fn apply(self, value: i32) -> i32 { self(value) } }
impl<F: FnOnce(Identity) -> i32> Value for F { fn value(self) -> i32 { self(Identity) } }
impl Value for i32 { fn value(self) -> i32 { self } }
fn zero(f: impl Op) -> i32 { f.apply(0) }
fn one(f: impl Op) -> i32 { f.apply(1) }
fn two(f: impl Op) -> i32 { f.apply(2) }
fn three(f: impl Op) -> i32 { f.apply(3) }
fn four(f: impl Op) -> i32 { f.apply(4) }
fn five(f: impl Op) -> i32 { f.apply(5) }
fn six(f: impl Op) -> i32 { f.apply(6) }
fn seven(f: impl Op) -> i32 { f.apply(7) }
fn eight(f: impl Op) -> i32 { f.apply(8) }
fn nine(f: impl Op) -> i32 { f.apply(9) }
fn plus(x: impl Value) -> impl FnOnce(i32) -> i32 { |y| y + x.value() }
fn minus(x: impl Value) -> impl FnOnce(i32) -> i32 { |y| y - x.value() }
fn times(x: impl Value) -> impl FnOnce(i32) -> i32 { |y| y * x.value() }
fn divided_by(x: impl Value) -> impl FnOnce(i32) -> i32 { |y| y / x.value() }
assert_eq!(seven(times(five)), 35);
assert_eq!(four(plus(nine)), 13);
assert_eq!(eight(minus(three)), 5);
assert_eq!(six(divided_by(two)), 3);
}

Chapter 2: Missing Requirements

AnyStr?

Create something similar to Python's typing.AnyStr.

Example of what it may allow (solution isn't required to pass these tests, but should):

#![allow(unused)]
fn main() {
pub trait Equivalent { type T; }
pub trait Accepts<T> {
type Output;
type E;
fn accept(self) -> Self::Output where Self::E: Equivalent<T = T>;
}
pub trait AnyStrRaw:Equivalent{fn provide<A:Accepts<String,E=Self,Output=Output>+Accepts<Vec<u8>,E=Self,Output=Output>,Output>(accepts:A)->Output;}
impl<T> Equivalent for T { type T = T; }
impl AnyStrRaw for String {
fn provide<A:Accepts<String,E=Self,Output=Output>,Output>(accepts:A)->Output{<A as Accepts<String>>::accept(accepts)}
}
impl AnyStrRaw for Vec<u8> {
fn provide<A:Accepts<Vec<u8>,E=Self,Output=Output>,Output>(accepts:A)->Output{<A as Accepts<Vec<u8>>>::accept(accepts)}
}
pub struct Concat<E: Equivalent>(E::T, E::T);
impl<E: AnyStrRaw> Accepts<String> for Concat<E> {
type Output = E::T;
type E = E;
fn accept(self) -> Self::Output where E: Equivalent<T = String> { self.0 + &self.1 }
}
impl<E: AnyStrRaw> Accepts<Vec<u8>> for Concat<E> {
type Output = E::T;
type E = E;
fn accept(self) -> Self::Output where E: Equivalent<T = Vec<u8>> {
let mut a = self.0;
let mut b = self.1;
a.append(&mut b);
a
}
}
pub trait AnyStr: AnyStrRaw<T = Self> {}
impl<T: AnyStrRaw<T = T>> AnyStr for T {}
pub fn concat<T: AnyStr>(a: T, b: T) -> T { T::provide(Concat(a, b)) }
assert_eq!(concat("ab".to_string(), "cd".to_string()), "abcd".to_string());
assert_eq!(concat(vec![2u8, 3u8], vec![5u8, 7u8]), vec![2u8, 3u8, 5u8, 7u8]);
}

Deserialisation modes

Merge implementations of ConsumesStream and Deterministic for tuple.

It's recommended to first solve this exercise.

#![allow(unused)]
fn main() {
trait Stream: Sized {
    /// Try to read `n` bytes. Consumes the stream on failure.
    fn read_n<A, E>(
        self,
        n: usize,
        ok: impl FnOnce(&[u8]) -> A,
        err: impl FnOnce(&[u8]) -> E,
    ) -> Result<(A, Self), E>;

    /// Read all bytes, consuming the stream.
    fn read_all<A>(self, ok: impl FnOnce(&[u8]) -> A) -> A;
}

/// Can be read from a stream.
trait FromStream: Sized {
    type Error;
}

/// Can be constructed from data of any length. Always consumes the stream.
trait ConsumesStream: FromStream {
    /// Try to read the value. Can handle EOF, can ask for all data the stream has.
    fn read_from(stream: impl Stream) -> Result<Self, Self::Error>;

    /// Push extra data into the value.
    fn extend(self, data: &[u8]) -> Result<Self, Self::Error>;
}

/// Whether the reading is terminated, is only determined by the data already read.
trait Deterministic: FromStream {
    /// Returns the stream, as it shouldn't succeed on unexpected EOF.
    fn read_from<S: Stream>(stream: S) -> Result<(Self, S), Self::Error>;

    /// Always fail on extra data.
    fn fail(data: &[u8]) -> Self::Error;
}

enum Either<L, R> {
    Left(L),
    Right(R),
}

impl<A: FromStream, B: FromStream> FromStream for (A, B) {
    type Error = Either<A::Error, B::Error>;
}

impl<A: Deterministic, B: ConsumesStream> ConsumesStream for (A, B) {
    fn read_from(stream: impl Stream) -> Result<Self, Self::Error> {
        let (a, stream) = A::read_from(stream)
            .map_err(Either::Left)?;
        B::read_from(stream)
            .map_err(Either::Right)
            .map(|b| (a, b))
    }

    fn extend(self, data: &[u8]) -> Result<Self, Self::Error> {
        self.1.extend(data)
            .map_err(Either::Right).map(|b| (self.0, b))
    }
}

impl<A: Deterministic, B: Deterministic> Deterministic for (A, B) {
    fn read_from<S: Stream>(stream: S) -> Result<(Self, S), Self::Error> {
        let (a, stream) = A::read_from(stream)
            .map_err(Either::Left)?;
        B::read_from(stream)
            .map_err(Either::Right)
            .map(|(b, stream)| ((a, b), stream))
    }

    fn fail(data: &[u8]) -> Self::Error {
        Either::Right(B::fail(data))
    }
}
}

Report all errors (or only the first error)

Make this compile and pass tests:

#![allow(unused)]
fn main() {
trait Collects {
type Fast;
type Slow;
type Output;
fn create(&self, next: i32) -> Result<Self::Slow, Self::Fast>;
fn update(&self, slow: &mut Self::Slow, next: i32);
fn regularize(&self, result: Result<Result<Vec<i32>, Self::Slow>, Self::Fast>) -> Result<Vec<i32>, Self::Output>;
}
struct First;
struct All;
impl Collects for First {
type Fast = i32;
type Slow = std::convert::Infallible;
type Output = i32;
fn create(&self, next: i32) -> Result<Self::Slow, Self::Fast> { Err(next) }
fn update(&self, slow: &mut Self::Slow, _next: i32) { match *slow {} }
fn regularize(&self, result: Result<Result<Vec<i32>, Self::Slow>, Self::Fast>) -> Result<Vec<i32>, Self::Output> { result.map(|r| r.unwrap_or_else(|slow| match slow {} )) }
}
impl Collects for All {
type Fast = std::convert::Infallible;
type Slow = Vec<i32>;
type Output = Vec<i32>;
fn create(&self, next: i32) -> Result<Self::Slow, Self::Fast> { let mut slow = vec![]; slow.push(next); Ok(slow) }
fn update(&self, slow: &mut Self::Slow, next: i32) { slow.push(next) }
fn regularize(&self, result: Result<Result<Vec<i32>, Self::Slow>, Self::Fast>) -> Result<Vec<i32>, Self::Output> { result.unwrap_or_else(|fast| match fast {}) }
}
fn first() -> impl Collects<Output = i32> { First }
fn all() -> impl Collects<Output = Vec<i32>> { All }
fn _only_postivie<C: Collects>(numbers: Vec<i32>, c: &C) -> Result<Result<Vec<i32>, C::Slow>, C::Fast> {
let mut state = Ok(vec![]);
for x in numbers { state = if x > 0 { state.map(|mut vec| {vec.push(x); vec}) } else { Err(match state {
Ok(_) => c.create(x)?,
Err(mut slow) => { c.update(&mut slow, x) ; slow }
}) } }
Ok(state)
}
fn only_positive<C: Collects>(numbers: Vec<i32>, c: C) -> Result<Vec<i32>, C::Output> { c.regularize(_only_postivie(numbers, &c)) }
assert_eq!(only_positive(vec![1, -1, 2, -4], first()), Err(-1));
assert_eq!(only_positive(vec![1, 2, 3], first()), Ok(vec![1, 2, 3]));
assert_eq!(only_positive(vec![1, -1, 2, -4], all()), Err(vec![-1, -4]));
assert_eq!(only_positive(vec![1, 2, 3], all()), Ok(vec![1, 2, 3]));
}

• only_positive(..., first()) should short-circuit on first non-positive number.
• only_positive(..., all()) must collect all non-positive numbers.

Chapter 3: Overly Functional

Monad composition?

#![allow(unused)]
fn main() {
use std::ops::ControlFlow;
trait Monad<'a>: 'a {
    type W<A: 'a>: 'a;

    fn map<A: 'a, B: 'a>(
        wa: Self::W<A>,
        f: impl FnOnce(A) -> B,
    ) -> Self::W<B>;

    fn pure<A: 'a>(
        a: A,
    ) -> Self::W<A>;

    fn collect<A: 'a, B: 'a>(
        wab: (Self::W<A>, Self::W<B>),
    ) -> Self::W<(A, B)>;

    fn bind<A: 'a, B: 'a>(
        wa: Self::W<A>,
        f: impl FnOnce(A) -> Self::W<B>,
    ) -> Self::W<B>;

    fn iterate<A: 'a>(
        i: impl Iteration<'a, A = A, M = Self>,
    ) -> Self::W<A>;
}

trait Iteration<'a>: 'a + Sized {
    type A: 'a;

    type M: ?Sized + Monad<'a>;

    fn next(self) -> IWrap<'a, Self>;
}

type Wrap<'a, M, A> = <M as Monad<'a>>::W<A>;

type IOutput<'a, I> = ControlFlow<<I as Iteration<'a>>::A, I>;

type IWrap<'a, I> = Wrap<'a, <I as Iteration<'a>>::M, IOutput<'a, I>>;

struct Composition<U, V>(U, V);

impl<'a, U, V> Monad<'a> for Composition<U, V>
where
    U: Monad<'a>,
    V: Monad<'a>,
    // something missing here?
V: Local<'a>,
{
    type W<A: 'a> = U::W<V::W<A>>;

    fn map<A: 'a, B: 'a>(
        wa: Self::W<A>,
        f: impl FnOnce(A) -> B,
    ) -> Self::W<B> {
        U::map(wa, |va| V::map(va, f))
    }

    fn pure<A: 'a>(
        a: A,
    ) -> Self::W<A> {
        U::pure(V::pure(a))
    }

    fn collect<A: 'a, B: 'a>(
        wab: (Self::W<A>, Self::W<B>),
    ) -> Self::W<(A, B)> {
        U::map(U::collect(wab), V::collect)
    }

    fn bind<A: 'a, B: 'a>(
        wa: Self::W<A>,
        f: impl FnOnce(A) -> Self::W<B>,
    ) -> Self::W<B> {
        // impossible
U::bind(wa, |va| U::map(V::wrap::<_, U>(V::map(va, f)), |vvb| V::bind(vvb, |vb| vb)))
    }

    fn iterate<A: 'a>(
        i: impl Iteration<'a, A = A, M = Self>,
    ) -> Self::W<A> {
        // impossible
U::iterate(ComposedIteration(i))
    }
}
trait Local<'a>: Monad<'a> { fn wrap<A: 'a, M: Monad<'a>>(wa: Self::W<M::W<A>>) -> M::W<Self::W<A>>; }
struct CfInstance<E>(ControlFlow<(), E>);
use ControlFlow::{Continue, Break};
impl<'a, E: 'a> Monad<'a> for CfInstance<E> {
type W<A: 'a> = ControlFlow<A, E>;
fn map<A: 'a, B: 'a>(wa: Self::W<A>, f: impl FnOnce(A) -> B) -> Self::W<B> {
match wa { Continue(c) => Continue(c), Break(a) => Break(f(a)) }
}
fn pure<A: 'a>(a: A) -> Self::W<A> { Break(a) }
fn collect<A: 'a, B: 'a>(wab: (Self::W<A>, Self::W<B>)) -> Self::W<(A, B)> {
match wab { (Continue(e), _) => Continue(e), (_, Continue(e)) => Continue(e), (Break(a), Break(b)) => Break((a, b)) }
}
fn bind<A: 'a, B: 'a>(wa: Self::W<A>, f: impl FnOnce(A) -> Self::W<B>) -> Self::W<B> {
match wa { Continue(e) => Continue(e), Break(a) => f(a) }
}
fn iterate<A: 'a>(mut i: impl Iteration<'a, A = A, M = Self>) -> Self::W<A> {
loop { match i.next() { Continue(e) => break Continue(e), Break(Continue(next_i)) => i = next_i, Break(Break(a)) => break Break(a) } }
}
}
struct ComposedIteration<F>(F);
impl<'a, U: Monad<'a>, V: Local<'a>, F: Iteration<'a, M = Composition<U, V>>> Iteration<'a> for ComposedIteration<F> {
type A = Wrap<'a, V, F::A>;
type M = U;
fn next(self) -> IWrap<'a, Self> { U::map(self.0.next(), |vstate| { ControlFlow::Continue(Self(V::wrap::<_, CfInstance<_>>(vstate)?)) }) }
}
}

Err(Err)

1. Implement the function for both groups of tests.
2. Provide usecases for each group.
3. How does this relate to the rest of this chapter (generic functional programming)?

#![allow(unused)]
fn main() {
// `try_join` or `zip` may be a better name
fn join<A, B, E0, E1>(
    r0: Result<Result<A, E0>, E1>,
    r1: Result<Result<B, E0>, E1>,
) -> Result<Result<(A, B), E0>, E1> {
/*
    todo!()
*/
Ok((|r0, r1| Ok((r0?, r1?)))(r0?, r1?))
}

fn join_alt<A, B, E0, E1>(
r0: Result<Result<A, E0>, E1>,
r1: Result<Result<B, E0>, E1>,
) -> Result<Result<(A, B), E0>, E1> {
match (r0, r1) {
(Ok(Err(e)), _) | (_, Ok(Err(e))) => Ok(Err(e)),
(Err(e), _) | (_, Err(e)) => Err(e),
(Ok(Ok(a)), Ok(Ok(b))) => Ok(Ok((a, b))),
}
}
let mut short = false;
for join in [join, join_alt] {
let tested = |
r0: Result<Result<i32, i32>, &'static str>,
r1: Result<Result<&'static str, i32>, &'static str>
| join(r0, r1);
let join = tested;
// applies to both
assert_eq!(join(Ok(Ok(0)), Ok(Ok("1"))), Ok(Ok((0, "1"))));
assert_eq!(join(Ok(Err(2)), Ok(Ok("3"))), Ok(Err(2)));
assert_eq!(join(Ok(Ok(3)), Ok(Err(4))), Ok(Err(4)));
assert_eq!(join(Ok(Err(5)), Ok(Err(5))), Ok(Err(5)));
assert_eq!(join(Err("6"), Ok(Ok("7"))), Err("6"));
assert_eq!(join(Ok(Ok(8)), Err("9")), Err("9"));
assert_eq!(join(Err("10"), Err("10")), Err("10"));
// the following two groups are mutually exclusive
if short {
    // group 1
assert_eq!(join(Ok(Err(11)), Err("12")), Ok(Err(11)));
assert_eq!(join(Err("13"), Ok(Err(14))), Ok(Err(14)));
} else {
    // group 2
assert_eq!(join(Ok(Err(11)), Err("12")), Err("12"));
assert_eq!(join(Err("13"), Ok(Err(14))), Err("13"));
short = true;
}
}
}

Currying

Implement curry and make it pass the tests.

#![allow(unused)]
fn main() {
trait Curried<A, B>: FnOnce(A) -> Self::Inner {
type C;
type Inner: FnOnce(B) -> Self::C;
}
impl<A, B, C, Inner: FnOnce(B) -> C, F: FnOnce(A) -> Inner> Curried<A, B> for F {
type C = C;
type Inner = Inner;
}
fn curry<A, B, C>(f: impl FnOnce(A, B) -> C) -> impl Curried<A, B, C = C> { |a| |b| f(a, b) }
assert_eq!(curry(|a, b| a * b)(3)(5), 15);
let mut x = 0;
curry(|x: &mut i32, y| *x = y)(&mut x)(5);
assert_eq!(x, 5);
}

Try solving it in the playground:

fn main() {
    assert_eq!(curry(|a, b| a * b)(3)(5), 15);
    let mut x = 0;
    curry(|x: &mut i32, y| *x = y)(&mut x)(5);
    assert_eq!(x, 5);
}

Topics

Rows are ordered based on estimated difficulty.

p.s. most of the exercises are actually about traits, this categorisation isn't strict.