n-queens problem in Rust, with (some) reference counting

queens.rs

use std::rc::Rc;

#[derive(Copy, Clone)]
struct IntInt {
    x: i32,
    y: i32,
}

struct Cons<T: Copy> {
    elt: T,
    next: Option<Rc<Cons<T>>>,
}

fn link<T: Copy>(h: T, t: Option<Rc<Cons<T>>>) -> Rc<Cons<T>> {
    Rc::new(Cons { elt: h, next: t })
}

fn length<T: Copy>(xs: Option<&Cons<T>>) -> usize {
    match xs {
        None => 0,
        Some(xs) => 1 + length(xs.next.as_ref().map(AsRef::as_ref)),
    }
}

fn safe(p1: IntInt, p2: IntInt) -> bool {
    let x1 = p1.x;
    let y1 = p1.y;
    let x2 = p2.x;
    let y2 = p2.y;

    x1 != x2 && y1 != y2 && x2 - x1 != y2 - y1 && x1 - y2 != x2 - y1
}

fn filter<T: Copy, F: Fn(T) -> bool>(pred: &F, xs: Option<&Cons<T>>) -> Option<Rc<Cons<T>>> {
    match xs {
        None => None,
        Some(xs) => {
            let h = xs.elt;
            let t = xs.next.as_ref().map(AsRef::as_ref);
            let t = filter(pred, t);

            if pred(h) {
                link(h, t).into()
            } else {
                t
            }
        }
    }
}

fn search<F: Clone + Fn(&Cons<IntInt>, usize) -> usize>(
    f: &F,
    n: usize,
    qs: Option<Rc<Cons<IntInt>>>,
    ps: Option<&Cons<IntInt>>,
    accu: usize,
) -> usize {
    match ps {
        None => if length(qs.as_ref().map(AsRef::as_ref)) == n {
            f(qs.as_ref().map(AsRef::as_ref).unwrap(), accu)
        } else {
            accu
        },
        Some(ps) => {
            let q = ps.elt;
            let ps = ps.next.as_ref().map(AsRef::as_ref);
            let accu = search(f, n, qs.clone(), ps, accu);

            search(
                f,
                n,
                link(q, qs).into(),
                filter(&|p| safe(q, p), ps).as_ref().map(AsRef::as_ref),
                accu
            )
        }
    }
}

fn ps(n: usize, i: i32, j: i32) -> Option<Rc<Cons<IntInt>>> {
    if i as usize == n {
        if j as usize == n - 1 {
            None
        } else {
            ps(n, 0, j + 1)
        }
    } else {
        let p = IntInt {
            x: i,
            y: j,
        };
        link(p, ps(n, i + 1, j)).into()
    }
}

fn f(_xs: &Cons<IntInt>, n: usize) -> usize { n + 1 }

fn queens(n: usize) -> usize {
    search(&f, n, None, ps(n, 0, 0).as_ref().map(AsRef::as_ref), 0)
}

fn main() {
    let n = std::env::args().nth(1).unwrap().parse().unwrap();
    println!("{}-queens: {}", n, queens(n));
}